Hierarchical structure and the prediction of missing links in networks
Hierarchical structure and the prediction of missing links in networks
复制标题
DOI：
10.1038/nature06830
复制
发表时间：
2008-05-01
期刊：
影响因子：
64.8
通讯作者：
Newman, M. E. J.
中科院分区：
文献类型：
--
作者：
Clauset, Aaron;Moore, Cristopher;Newman, M. E. J.
近年来，网络已成为描述和量化许多科学分支中复杂系统的宝贵工具（1-3）。最近的研究表明，网络通常表现出层次结构，其中顶点划分为组，进一步细分为组的组，等等。在许多情况下，这些群体被发现与已知的功能单位相对应，例如食物网中的生态位、生物化学网络中的模块（蛋白质相互作用网络、代谢网络或遗传调控网络）或社交网络中的社区（4-7）。在这里，我们提出了一个一般的技术，从网络数据推断层次结构，并表明层次的存在可以同时解释和定量再现许多常见的网络拓扑性质，如右偏度分布，高聚类系数和短路径长度。我们进一步表明，层次结构的知识可以用于预测部分已知网络中丢失的连接，具有高精度，并且比竞争技术更一般的网络结构（8）。总之，我们的研究结果表明，层次结构是复杂网络的中心组织原则，能够提供洞察许多网络现象。
Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science(1-3). Recent studies suggest that networks often exhibit hierarchical organization, in which vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases the groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks ( protein interaction networks, metabolic networks or genetic regulatory networks) or communities in social networks(4-7). Here we present a general technique for inferring hierarchical structure from network data and show that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks, such as right- skewed degree distributions, high clustering coefficients and short path lengths. We further show that knowledge of hierarchical structure can be used to predict missing connections in partly known networks with high accuracy, and for more general network structures than competing techniques(8). Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena.