摘要
局部社区发现算法通常选取种子节点进行社区发现,针对现有重叠社区发现算法中种子节点选取时有效性不足的问题,提出了一种基于子图结构的局部社区发现算法(Subgragh Structure Based Overlapping Community Detection,SUSBOCD)。该算法提出了一种新的节点重要性度量指标,不仅考虑了节点的邻居数量,同时也考虑了邻居间的链接紧密程度。首先,选取未被访问且重要性最大的节点以及与其最为相似的邻居节点,将该两个节点及其公共邻居节点合并形成一个初始种子子图,该过程迭代运行直到所有节点均被访问;其次,根据种子子图的邻域信息进行相似度判断,若相似则进行合并,从而形成初始社区结构,持续扩展该过程直到所有种子子图均被访问;最后,对社区进行优化处理,若存在未分配社区的节点,则将其加入到最相似的初始社区,再合并重叠度较高的初始社区结构。在人工数据集和真实数据集上,对所提算法进行实验验证,实验结果表明,与其他重叠社区发现算法相比,SUSBOCD算法在ONMI,EQ和Omega这3个评价指标上均有所提升,即该算法能有效地提高重叠社区的划分质量。
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.
作者
陈湘涛
赵美杰
杨梅
CHEN Xiang-tao;ZHAO Mei-jie;YANG Mei(College of Computer Science and Electronic Engineering,Hunan University,Changsha 410000,China)
出处
《计算机科学》
CSCD
北大核心
2021年第9期244-250,共7页
Computer Science
基金
国家自然科学基金(61873089)
国家重点研究发展计划项目(2018YFC0910405)
国家自然科学基金(61572180)。
关键词
重叠社区发现
局部扩展
种子选取
社区扩展
社区优化
Overlapping community detection
Local expansion
Seed selection
Community expansion
Community optimization