Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequences
Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequences
复制标题
DOI：
10.1103/physreve.76.046112
复制
发表时间：
2007-10-01
影响因子：
2.4
通讯作者：
Paczuski, Maya
中科院分区：
文献类型：
--
作者：
Foster, Jacob G.;Foster, David V.;Paczuski, Maya
最简单的网络零模型用于区分特定网络的重要特征与先验预期特征，是具有由感兴趣的特定网络固定的度序列的随机集合。然而，这些“固定度序列”（FDS）集合以抵抗分析攻击而闻名。在本文中，我们介绍了具有部分固定度序列（PFDS）的系综，并将其获得的分析结果与 FDS 系综的蒙特卡罗结果进行了比较。这些结果包括链接可能性、子图可能性和程度相关性。我们发现，除了节点和链接的总数之外，通过同时固定少数节点的度数，可以很好地估计 FDS 系综中的局部结构特征。作为测试用例，我们使用两个蛋白质相互作用网络（大肠杆菌、酿酒酵母）、自治系统 (AS) 级别的互联网和万维网。仅固定两个节点的度数给出了作为节点度数的函数的平均邻居度数 < k(')>(k)，与从重新连线中明确获得的结果一致。对于幂律度分布，我们通过分析推导出不相配性。在 PFDS 系综中，配分函数可以用图解法展开。我们获得了最低阶链接可能性的显式表达式，这减少了具有 L 个链接和 k(max) 的大型稀疏无向网络的限制
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)