Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
复制标题
DOI：
10.1080/15427951.2009.10129177
复制
发表时间：
2009-01-01
影响因子：
--
通讯作者：
Mahoney, Michael W.
中科院分区：
文献类型：
--
作者：
Leskovec, Jure;Lang, Kevin J.;Mahoney, Michael W.
大量的工作致力于定义和识别社会和信息网络中的集群或社区，即，在图中，节点代表底层的社会实体，边代表节点对之间的某种交互。大多数这样的研究都是从这样一个前提开始的，即社区或集群应该被认为是一组节点，其成员之间的连接比网络的其余部分更多和/或更好。在本文中，我们从一个新的角度探讨了在大型社会和信息网络中识别有意义社区的几个问题，并得出了几个惊人的结论。与其定义一个从图中提取节点集的过程，然后试图将这些节点集解释为“真实的”社区，我们采用近似算法的图形分区问题，以表征作为大小的函数的统计和结构属性的分区的图形，可以合理地解释为社区。特别是，我们定义的网络社区配置文件图，其特征在于“最好的”可能的社区，根据电导测量，在很宽的范围内的大小尺度。我们研究了100多个大型现实网络，从传统的和在线的社交网络，到技术和信息网络和网络图，规模从数千到数千万个节点不等，我们的研究结果表明，大型网络中的社区结构比以前认识到的要精细得多。我们的观察结果与以前对小网络的研究一致，但我们发现大型网络具有非常不同的结构。特别是，我们观察到在非常小的规模（最多约100个节点）上几乎不与网络其余部分连接的紧密社区;而规模超过约100个节点的社区逐渐“融入”网络的扩展器样核心，从而变得不那么“社区样”，社区规模和最佳社区质量之间大致呈反比关系。这一观察结果与所谓的邓巴数（Dunbar number）吻合得很好，邓巴数给出了一个运转良好的社区的规模限制，然而，这种行为无法用任何常用的网络生成模型来解释，即使是在定性层面上。此外，这与人们根据扩展图、低维或流形图以及作为社区检测算法测试床的小型社交网络的直觉所预期的完全相反。网络社区简档图作为增加社区大小的函数的相对逐渐的增加以微妙的方式取决于局部聚类信息在网络中从较小尺寸尺度传播到较大尺寸尺度的方式。我们已经发现，生成图模型，其中通过迭代的“森林火灾”燃烧过程添加新的边缘，能够产生显示网络社区配置文件图的图形，类似于我们在网络数据集中观察到的。
A large body of work has been devoted to defining and identifying clusters or communities in social and information networks, i.e., in graphs in which the nodes represent underlying social entities and the edges represent some sort of interaction between pairs of nodes. Most such research begins with the premise that a community or a cluster should be thought of as a set of nodes that has more and/or better connections between its members than to the remainder of the network. In this paper, we explore from a novel perspective several questions related to identifying meaningful communities in large social and information networks, and we come to several striking conclusions.Rather than defining a procedure to extract sets of nodes from a graph and then attempting to interpret these sets as "real" communities, we employ approximation algorithms for the graph-partitioning problem to characterize as a function of size the statistical and structural properties of partitions of graphs that could plausibly be interpreted as communities. In particular, we define the network community profile plot, which characterizes the "best" possible community-according to the conductance measure-over a wide range of size scales. We study over one hundred large real-world networks, ranging from traditional and online social networks, to technological and information networks and web graphs, and ranging in size from thousands up to tens of millions of nodes.Our results suggest a significantly more refined picture of community structure in large networks than has been appreciated previously. Our observations agree with previous work on small networks, but we show that large networks have a very different structure. In particular, we observe tight communities that are barely connected to the rest of the network at very small size scales (up to approximate to 100 nodes); and communities of size scale beyond approximate to 100 nodes gradually "blend into" the expander-like core of the network and thus become less "community-like," with a roughly inverse relationship between community size and optimal community quality. This observation agrees well with the so-called Dunbar number, which gives a limit to the size of a well-functioning community.However, this behavior is not explained, even at a qualitative level, by any of the commonly used network-generation models. Moreover, it is exactly the opposite of what one would expect based on intuition from expander graphs, low-dimensional or manifold-like graphs, and from small social networks that have served as test beds of community-detection algorithms. The relatively gradual increase of the network community profile plot as a function of increasing community size depends in a subtle manner on the way in which local clustering information is propagated from smaller to larger size scales in the network. We have found that a generative graph model, in which new edges are added via an iterative "forest fire" burning process, is able to produce graphs exhibiting a network community profile plot similar to what we observe in our network data sets.