Abstract: Focusing on the problem that the best neighbor nodes of the communities can not accurately be found in most local community detection algorithms, an improved local community detection algorithm was proposed based on local modularity. The concept of node intimacy was introduced to quantify the relationship between the community and the neighbor nodes by the algorithm, and the nodes were selected into the communities according to the node intimacy in descending order. In the end,the extension of the local community was terminated by the local modularity index. Compared with the four kinds of typical community detection algorithms such as the random walk algorithm based on information compression, the algorithm was applied in the real networks and the artificial simulation network. The comprehensive evaluation indexs (F1score) and Normalized Mutual Informations (NMI) of the results are better than comparison algorithms. The experiments show that the algorithm has better efficiency and accuracy, and is very suitable for community detection in a large scale network.

Key words: complex network, community detection, node intimacy, modularity, synthetic network

摘要： 针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。

关键词: 复杂网络, 社团划分, 节点亲密度, 模块度, 人工合成网络