基于非加权图的大型社会网络检测算法研究

Research on a large scale community detection algorithm based on non-weighted graph

社区检测和划分已经成为大规模社会网络中一个非常关键的问题。然而,大多数现有的算法受限于计算成本,其适用性十分有限。为了提高社区划分质量和计算效率,提出了一种基于非加权图的社区网络检测算法。首先,算法采用两个新的参数来度量社区并实现社区检测,即聚类系数和共同的邻居相似性,并通过理论分析和公式推导证明其有效性。最后采用真实社会网络数据集进行了大量的模拟,实验结果表明,与传统的生成树算法以及CBCD算法相比,提出的方法更加有效,且计算运行时间具有线性复杂度,适用于大规模社会网络的社区检测。

Community detection and partitioning has become a critical issue in large-scale social networks. However, the applicability of most existing methods is limited by computational costs. In order to improve the quality of community division and calculation efficiency, a community detection algorithm based on un-weighted graphs is proposed. This algorithm uses two parameters to mea- sure the community to achieve community discovery, which is clustering coefficient and common neighbor similarity, and its effec- tiveness is proved by the academic formula. Experimental analysis is carried out using a real social network dataset, and compared with other algorithms proposed two methods. The experimental results show that the proposed method is more efficient and the com- putation time is linear. It is suitable for community detection in large-scale social networks.