Foster Jacob G, Foster David V, Grassberger Peter, Paczuski Maya
Department of Physics and Astronomy, University of Calgary, Calgary, Canada T2N 1N4.
Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Oct;76(4 Pt 2):046112. doi: 10.1103/PhysRevE.76.046112. Epub 2007 Oct 19.
The simplest null models for networks, used to distinguish significant features of a particular network from 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 a few nodes, in addition to the total number of nodes and links. As test cases we use two protein interaction networks (Escherichia coli, Saccharomyces 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;{'}{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}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}) .
用于将特定网络的显著特征与先验预期特征区分开来的最简单网络零模型，是度序列由感兴趣的特定网络固定的随机集合。然而，这些“固定度序列”（FDS）集合以难以进行解析分析而闻名。在本文中，我们引入了具有部分固定度序列（PFDS）的集合，并将针对它们获得的解析结果与FDS集合的蒙特卡罗结果进行比较。这些结果包括链接似然、子图似然和度相关性。我们发现，除了节点总数和链接数之外，通过仅同时固定少数节点的度，可以相当好地估计FDS集合中的局部结构特征。作为测试用例，我们使用两个蛋白质相互作用网络（大肠杆菌、酿酒酵母）、自治系统（AS）级别的互联网以及万维网。仅固定两个节点的度就给出了平均邻居度作为节点度(k)的函数(k_{k}')，这与通过重新布线明确获得的结果一致。对于幂律度分布，我们通过解析方法推导出了非关联性。在PFDS集合中，配分函数可以通过图形展开。我们得到了链接似然到最低阶的显式表达式，在具有(L)个链接且(k_{max}L)的大型稀疏无向网络的极限情况下，该表达式简化为简单公式(P(k,k';) = kk'(2L + kk'))。在类似的极限情况下，三个节点链接成一个三角形的概率简化为因式分解表达式(P_{\Delta}(k_{1},k_{2},k_{3}) = P(k_{1},k_{2})P(k_{1},k_{3})P(k_{2},k_{3}))。
