Finding Statistically Significant Communities in Networks with Weighted Label Propagation
Finding Statistically Significant Communities in Networks with Weighted Label Propagation
复制标题
DOI：
10.4236/sn.2013.23012
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Wei-Gang Hu
中科院分区：
文献类型：
--
作者：
Wei-Gang Hu
当今世界存在各种网络，包括生物、社会、信息和通信网络，其中互联网是最大的网络。这些网络的一个显著的结构特征是形成顶点的群体或社区，这些群体或社区往往在同一个群体内相互联系，而不是与外部的联系。因此，这些社区的检测在许多应用中是非常感兴趣和重要的主题，并且已经为此目的开发了包括标签传播的不同算法。说话人-收听人标签传播算法（SLPA）具有近似线性的时间复杂度，因此在处理大型网络时非常理想。作为SLPA算法的扩展，本文提出了一种新的加权标签传播算法（WLPA），并在四个真实的社交网络上进行了测试。WLPA对空手道俱乐部网络中发现的社区进行的Wilcoxon检验表明，SLPA的统计显著性有所提高。在Wilcoxon检验的帮助下，我们能够确定相对于地面真值划分，该网络中两个社区的最佳可能形成，这可以用作评估社区检测算法的新基准。最后，与地面实况相比，WLPA在另外三个真实的社交网络中的两个中预测出比SLPA更好的社区。
Various networks exist in the world today including biological, social, information, and communication networks with the Internet as the largest network of all. One salient structural feature of these networks is the formation of groups or communities of vertices that tend to be more connected to each other within the same group than to those outside. Therefore, the detection of these communities is a topic of great interest and importance in many applications and different algorithms including label propagation have been developed for such purpose. Speaker-listener label propagation algorithm (SLPA) enjoys almost linear time complexity, so desirable in dealing with large networks. As an extension of SLPA, this study presented a novel weighted label propagation algorithm (WLPA), which was tested on four real world social networks with known community structures including the famous Zachary's karate club network. Wilcoxon tests on the communities found in the karate club network by WLPA demonstrated an improved statistical significance over SLPA. Withthehelp of Wilcoxon tests again, we were able to determine the best possible formation of two communities in this network relative to the ground truth partition, which could be used as a new benchmark for assessing community detection algorithms. Finally WLPA predicted better communities than SLPA in two of the three additional real social networks, when compared to the ground truth.