冯健 史丹丹 罗香玉 叶鸥

摘 要：社團发现能够揭示复杂网络的拓扑结构特性。针对现有社团发现算法社团初始节点选择随机、相似度计算过分依赖节点间共享邻居以及需要事先设定社团个数等问题，依托层次聚类思想提出基于节点重要度和社团接近度的社团划分算法。首先引入节点重要度的定义并给出重要节点的计算模型，根据该模型得到最重要节点作为社团的初始聚类中心;然后兼顾节点的共享关系和直接影响定义节点的社团接近度，依据社团接近度指标寻找与社团最接近的节点，根据该节点的加入为社团带来的局部模块度增量判断是否将其加入到已有社团。首个社团划分完毕后，重复选取初始聚类中心并构造社团的过程，直到没有可归入社团的节点。在2个典型复杂网络数据集上进行了测试，

并与Girvan-Newman算法和Newman快速算法从准确率和模块度进行对比，实验结果表明所提算法在社团数目未知的前提下能够获得更好的社团划分结果。关键词：社团发现;层次聚类;节点重要性;社团接近度中图分类号：TP 399

文献标志码：A

文章编号：1672-9315（2020）01-0181-06

DOI：10.13800/j.cnki.xakjdxxb.2020.0124开放科学（资源服务）标识码（OSID）：

Discovering community structure using node importance

and community proximity

FENG Jian 1，SHI Dan-dan 2，LUO Xiang-yu 1，YE Ou 1

（1.College of Computer Science and Engineering，Xian University of Science and Technology，Xian 710054，China;

2.Chengdu Skysoft Information Technology Co.，Ltd.，Chengdu 610041，China）

Abstract：Community discovery can reveal the topological characteristics of complex networks.For the existing community discovery algorithms，selection of the initial node for a community is random，similarity calculation is over-reliant to the shared neighbors between nodes，and the numbers of communities needs to be set in advance.To overcome these problems，based on the idea of hierarchical clustering，a community discovery algorithm based on node importance and community proximity is proposed.Firstly，the definition of node importance is introduced and the calculation model of important nodes is given.According to the model，the most important node is taken as the initial cluster center of a community.Then，the concept of node-community proximity is defined by taking the sharing relationship and direct effect of nodes into account.The node closest to the community should be found according to the node-community proximity index，andwhether to add it to the existing community is decided according to the increment of partial modularity brought by the node.After the first community is divided，the process of selecting the initial cluster center and constructing the community is repeated until there are no nodes left.Experiments are carried out on two typical complex network datasets，

with a comparison of the accuracy and modularity made between the results by Girvan-Newman algorithm and Newman fast algorithm.The experimental results show that the proposed algorithm can get better result of community division under the premise that the number of communities is unknown.Key words：community discovery;hierarchical clustering;node importance;community proximity

0 引 言

大量研究表明，结构性是复杂网络的本质特性。结构性体现为社团，是指复杂网络中的节点呈现出以簇为特征的聚集状态，簇内节点联系紧密，簇间节点联系松散[1]。发现网络社团结构也称作社团划分，有助于揭示网络的组织原则和功能特性[2]，具有十分重要的理论和应用价值。……