计算机科学 ›› 2021, Vol. 48 ›› Issue (9): 244-250.doi: 10.11896/jsjkx.201100010

• 人工智能 • 上一篇    下一篇

基于子图结构的局部社区发现算法

陈湘涛, 赵美杰, 杨梅   

  1. 湖南大学信息科学与工程学院 长沙410000
  • 收稿日期:2020-11-02 修回日期:2021-03-22 出版日期:2021-09-15 发布日期:2021-09-10
  • 通讯作者: 陈湘涛(xtchen2009@sina.cn)
  • 基金资助:
    国家自然科学基金(61873089);国家重点研究发展计划项目(2018YFC0910405);国家自然科学基金(61572180)

Overlapping Community Detection Algorithm Based on Subgraph Structure

CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei   

  1. College of Computer Science and Electronic Engineering,Hunan University,Changsha 410000,China
  • Received:2020-11-02 Revised:2021-03-22 Online:2021-09-15 Published:2021-09-10
  • About author:CHEN Xiang-tao,born in 1973,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include data mining,heterogenous information network,social network and network embedding.
  • Supported by:
    National Natural Science Foundation of China(61873089),National Key R&D Program of China(2018YFC0910405) and National Natural Science Foundation of China(61572180)

摘要: 局部社区发现算法通常选取种子节点进行社区发现,针对现有重叠社区发现算法中种子节点选取时有效性不足的问题,提出了一种基于子图结构的局部社区发现算法(Subgragh Structure Based Overlapping Community Detection,SUSBOCD)。该算法提出了一种新的节点重要性度量指标,不仅考虑了节点的邻居数量,同时也考虑了邻居间的链接紧密程度。首先,选取未被访问且重要性最大的节点以及与其最为相似的邻居节点,将该两个节点及其公共邻居节点合并形成一个初始种子子图,该过程迭代运行直到所有节点均被访问;其次,根据种子子图的邻域信息进行相似度判断,若相似则进行合并,从而形成初始社区结构,持续扩展该过程直到所有种子子图均被访问;最后,对社区进行优化处理,若存在未分配社区的节点,则将其加入到最相似的初始社区,再合并重叠度较高的初始社区结构。在人工数据集和真实数据集上,对所提算法进行实验验证,实验结果表明,与其他重叠社区发现算法相比,SUSBOCD算法在ONMI,EQ和Omega这3个评价指标上均有所提升,即该算法能有效地提高重叠社区的划分质量。

关键词: 局部扩展, 社区扩展, 社区优化, 种子选取, 重叠社区发现

Abstract: Local community detection algorithms usually select seed nodes for community detection.To improve the quality of effectiveness of seed node selection,we propose an overlapping community detection algorithm based on subgraph structure(SUSBOCD).This algorithm proposes a new measure of node importance,which not only considers the number of neighbors,but also considers the degree of density between neighbors.First,SUSBOCD selects the most important node that is not visited and the most similar neighbor node,and merges the two nodes and their common neighbor nodes to form an initial seed subgraph.The process runs iteratively until all nodes have been visited.Second,the similarity is judged according to the neighborhood information of the seed subgraph.If it is similar,it is merged to form the initial community structure.The process runs iteratively until all seed subgraphs are visited.Finally,we optimize the community.If there are nodes without assigned communities,they are added to the most similar community,and then the community structure with high overlap is merged.Experiments on real and artificial networks show that SUSBOCD can improve the quality of overlapping community partition effectively in the three evaluation indexes of ONMI,EQ and Omega.

Key words: Community expansion, Community optimization, Local expansion, Overlapping community detection, Seed selection

中图分类号: 

  • TP391
[1]NEWMAN M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.
[2]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[3]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[4]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detec-tingthe overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[5]CHEN Q,WU T T,FANG M.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537.
[6]LI Y,HE J,WU Y X.Overlapping Community Discovery Me-thod Based on Greedy Expansion of Seed Nodes[J].Journal of Chinese Computer Systems,2019,40(5):1115-1119.
[7]WANG X,LIU G,LI J,et al.Locating structural centers:A density-based clustering method for community detection[J].PloS one,2017,12(1):e0169355.
[8]WANG X,LIU G,LI J.Overlapping community detection based on structural centrality in complex networks[J].IEEE Access,2017,5:25258-25269.
[9]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[10]YU Z Y,CHEN J J,GUO K.Overlapping Community Detection Based on Influence and Seeds Extension[J].Acta Electronica Sinica,2019,47(1):153-160.
[11]ZHANG X,WANG C,SU Y,et al.A fast overlapping community detection algorithm based on weak cliques for large-scale networks[J].IEEE Transactions on Computational Social Systems,2017,4(4):218-230.
[12]GREGORY S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024.
[13]PALLA G,IMRE D,ILLÉS F,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[14]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.DEMON:a Local-First Discovery Method for Overlapping Communities [C]//Proceeding of ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2012:615-623.
[15]CHEN X,LI J.Overlapping Community Detection by Node-Weighting[C]//Proceedings of the 2nd International Confe-rence on Compute and Data Analysis,ICCDA.2018:70-74.
[1] 宁懿昕, 谢辉, 姜火文.
图神经网络社区发现研究综述
Survey of Graph Neural Network in Community Detection
计算机科学, 2021, 48(11A): 11-16. https://doi.org/10.11896/jsjkx.210500151
[2] 薛磊, 唐旭清.
基于中心团的重叠社区检测算法
Algorithm for Detecting Overlapping Communities Based on Centered Cliques
计算机科学, 2020, 47(8): 157-163. https://doi.org/10.11896/jsjkx.200300034
[3] 张琴, 陈红梅, 封云飞.
一种基于粗糙集和密度峰值的重叠社区发现方法
Overlapping Community Detection Method Based on Rough Sets and Density Peaks
计算机科学, 2020, 47(5): 72-78. https://doi.org/10.11896/jsjkx.190400160
[4] 张琴, 陈红梅, 封云飞.
基于粗糙集和距离动态模型的重叠社区发现方法
Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model
计算机科学, 2020, 47(10): 75-82. https://doi.org/10.11896/jsjkx.190800002
[5] 刘春, 张国良.
一种基于重叠社区发现的软件特征提取方法
Software Feature Extraction Method Based on Overlapping Community Detection
计算机科学, 2019, 46(12): 201-207. https://doi.org/10.11896/jsjkx.181001856
[6] 张忠正,李建武.
一种基于局部拓展的并行重叠社区发现算法
Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion
计算机科学, 2016, 43(9): 61-65. https://doi.org/10.11896/j.issn.1002-137X.2016.09.011
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!