一种基于局部路径信息的重叠社区发现算法  

Overlapping Community Detection Algorithm Based on Local Path Information

作　　者：郑文萍[1,2,3] 王宁[1] 杨贵[1] ZHENG Wen-ping;WANG Ning;YANG Gui(School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China;Institute of Intelligent Information Processing,Shanxi University,Taiyuan 030006,China)

机构地区：[1]山西大学计算机与信息技术学院,太原030006 [2]计算智能与中文信息处理教育部重点实验室(山西大学),太原030006 [3]智能信息处理研究所(山西大学),太原030006

出　　处：《计算机科学》2022年第12期155-162,共8页Computer Science

基　　金：国家自然科学基金(62072292);山西省1331工程项目。

摘　　要：重叠社区发现是复杂网络分析的主要任务之一。针对现有的基于局部扩展和优化的重叠社区发现方法受初始种子节点选择影响较大、适应度函数无法度量节点间多样的连接方式等问题,提出了一种基于局部路径信息的重叠社区发现算法(Local Path Information-based Overlapping Community Detection Algorithm,LPIO)。首先选取局部极大度点作为初始种子节点,并根据社区内节点邻域标签一致性更新社区的种子节点集,避免初始种子节点对算法性能的影响;然后为度量稀疏网络中节点间多样的连接方式,给出了基于局部路径信息的社区适应度函数,扩展种子节点集得到社区结构;最后计算未聚类节点与社区种子集之间的点不重复路径数量,得到未聚类节点与已有社区间的距离,为未聚类节点分配社区。在4个有标签网络和8个无标签网络上,与7个经典重叠社区发现算法进行对比,实验结果表明,所提算法在重叠标准互信息(ONMI)、F1分数、扩展模块度(EQ)等方面表现良好。The detection of overlapping communities is one of the main tasks of complex network analysis.The performance of most existing methods based on local expansion and optimization are greatly affected by the selection of initial seed nodes and the community structure significance measurement.Aiming at these problems,an overlapping community detection algorithm is proposed based on local path information(LPIO).First,the local maximum degree points are selected as initial seeds,which will be updated according to the label consistency of node’s neighborhood in the community to reduce the influence of the selection of initial seeds.To measure the various connection patterns between nodes in networks,a community fitness function is defined based on local path information to obtain community structures from seed nodes.Finally,unclustered nodes are assigned to proper communities according to the number of non-repetitive paths between the unclustered nodes and the community seed sets.Comparative experiments on 4 labeled networks and 8 unlabeled networks with 7 classic overlapping community detection algorithms show that the proposed algorithm performs well on overlapping standard mutual information(ONMI),F1 score,and extended modularity(EQ).

关 键 词：重叠社区发现 局部扩展和优化 社区适应度 局部路径信息 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]