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

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

2006-10-16

arxiv.org/abs/cond-mat/0610446v2

Physics

Condensed Matter

Statistical Mechanics

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

Scientific paper

10.1103/PhysRevE.76.046112

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$, 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_{\rm max} \ll L$ to the simple formula $P(k,k') = kk'/(2L + kk')$. 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)$.

Affiliated with

Also associated with

No associations

Rating

Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-390045