Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence

Abstract

The simplest null models for networks, used to distinguish significant features of a particular network from {\it a priori} expected features, are random ensembles with the degree sequence fixed by the specific network of interest. These "fixed degree sequence" (FDS) ensembles are, however, famously resistant to analytic attack. In this paper we introduce ensembles with partially-fixed degree sequences (PFDS) and compare analytic results obtained for them with Monte Carlo results for the FDS ensemble. These results include link likelihoods, subgraph likelihoods, and degree correlations. We find that local structural features in the FDS ensemble can be reasonably well estimated by simultaneously fixing only the degrees of few nodes, in addition to the total number of nodes and links. As test cases we use a food web, two protein interaction networks (\textit{E. coli, S. cerevisiae}), the internet on the autonomous system (AS) level, and the World Wide Web. Fixing just the degrees of two nodes gives the mean neighbor degree as a function of node degree, $<k^{\prime }{>}_k$, in agreement with results explicitly obtained from rewiring. For power law degree distributions, we derive the disassortativity analytically. In the PFDS ensemble the partition function can be expanded diagrammatically. We obtain an explicit expression for the link likelihood to lowest order, which reduces in the limit of large, sparse undirected networks with $L$ links and with $k_{\max }\ll L$ to the simple formula $P(k,k^{\prime })=k{k}^{\prime }/(2L+k{k}^{\prime })$. In a similar limit, the probability for three nodes to be linked into a triangle reduces to the factorized expression $P_{\Delta }(k_1,k_2,k_3)=P(k_1,k_2)P(k_1,k_3)P(k_2,k_3)$.

17 pages, includes 11 figures; first revision: shortened to 14 pages (7 figures), added discussion of subgraph counts, deleted discussion of directed networks

References in corpus (20)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• The diameter of the world wide web
• Evolution of networks
• Mixing patterns in networks
• Specificity and stability in topology of protein networks
• Surrogate time series
• Generation of uncorrelated random scale-free networks
• The statistical mechanics of networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Robust Patterns in Food Web Structure
• The origin of degree correlations in the Internet and other networks
• Subgraphs in random networks
• Correlated random networks
• Go with the Winners: a General Monte Carlo Strategy
• Homogeneous complex networks
• Earthquake recurrence as a record breaking process
• Subgraph Ensembles and Motif Discovery Using a New Heuristic for Graph Isomorphism
• Graph animals, subgraph sampling and motif search in large networks

Cited by in corpus (10)

• Structural Properties of the Caenorhabditis elegans Neuronal Network
• Edge direction and the structure of networks
• Evolving networks in the human epileptic brain
• Maximum lilkelihood estimation in the $\beta$-model
• Clustering Drives Assortativity and Community Structure in Ensembles of Networks
• Constrained Markovian dynamics of random graphs
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
• Constrained Randomisation of Weighted Networks
• STDP-driven networks and the \emph{C. elegans} neuronal network