Detecting Overlapping Community Structures in Networks with Global Partition and Local Expansion
Detecting Overlapping Community Structures in Networks with Global Partition and Local Expansion
复制标题
DOI：
10.1007/978-3-540-78849-2_7
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
Fang Wei;Chen Wang;Li Ma;Aoying Zhou
中科院分区：
文献类型：
--
作者：
Fang Wei;Chen Wang;Li Ma;Aoying Zhou
发现网络中的社区结构的问题在社会网络、博客、蛋白质相互作用网络等领域受到了广泛的关注。然而，大多数的努力都是为了测量、鉴定、检测和改进网络中的“未交叉”社区，网络中的每个成员都被隐含地假设为扮演与其居住社区相对应的独特角色。实际上，这个假设并不总是合理的。例如，在社交网络中，一个人可以表现出不同的兴趣，从而成为多个真实的社区的成员。在这种情况下，我们提出了一种新的算法，从网络中找到重叠的社区结构。该算法可以分为两个阶段：1）在全局范围内收集合适的种子，并从中产生社区; 2）通过一个设计良好的局部优化过程，从种子中随机遍历网络。我们通过真实世界的网络进行实验。实验结果表明，我们的算法的高质量和验证的有用性发现重叠社区结构的网络。
The problem of discovering community structures in a network has received a lot of attention in many fields like social network, weblog, and protein-protein interaction network. Most of the efforts, however, were made to measure, qualify, detect, and refine “uncrossed” communities from a network, where each member in a network was implicitly assumed to play an unique role corresponding to its resided community. In practical, this hypothesis is not always reasonable. In social network, for example, one people can perform different interests and thus become members of multiple real communities. In this context, we propose a novel algorithm for finding overlapping community structures from a network. This algorithm can be divided into two phases: 1) globally collect proper seeds from which the communities are derived in next step; 2) randomly walk over the network from the seeds by a well designed local optimization process. We conduct the experiments by real-world networks. The experimental results demonstrate high quality of our algorithm and validate the usefulness of discovering overlapping community structures in a networks.