Finding overlapping communities in networks by label propagation
Finding overlapping communities in networks by label propagation
复制标题
DOI：
10.1088/1367-2630/12/10/103018
复制
发表时间：
2010-10-13
影响因子：
3.3
通讯作者：
Gregory, Steve
中科院分区：
文献类型：
--
作者：
Gregory, Steve
我们提出了一种在超大型网络中发现重叠社区结构的算法。该算法基于Raghavan、Albert和Kumara的标签传播技术，但能够检测出重叠的社区。与原始算法一样，顶点具有在相邻顶点之间传播的标签，以便社区成员就其社区成员身份达成共识。我们的主要贡献是扩展了标记和传播步骤，以包括关于多个社区的信息：每个顶点现在可以属于多达v个社区，其中v是算法的参数。我们的算法还可以处理加权网络和二部网络。在一组独立设计的基准测试和真实网络上的测试表明，该算法在恢复重叠社区方面非常有效。它还非常快，可以在短时间内处理非常大和密集的网络。
We propose an algorithm for finding overlapping community structure in very large networks. The algorithm is based on the label propagation technique of Raghavan, Albert and Kumara, but is able to detect communities that overlap. Like the original algorithm, vertices have labels that propagate between neighbouring vertices so that members of a community reach a consensus on their community membership. Our main contribution is to extend the label and propagation step to include information about more than one community: each vertex can now belong to up to v communities, where v is the parameter of the algorithm. Our algorithm can also handle weighted and bipartite networks. Tests on an independently designed set of benchmarks, and on real networks, show the algorithm to be highly effective in recovering overlapping communities. It is also very fast and can process very large and dense networks in a short time.