融合节点分析与边分析的复杂网络社区识别算法

邓琨; 蒋庆丰; 刘星妍

doi:10.11959/j.issn.1000-0801.2023091

您当前的位置：

首页 >

文章列表页 >

融合节点分析与边分析的复杂网络社区识别算法

研究与开发 | 更新时间：2024-06-05

- 融合节点分析与边分析的复杂网络社区识别算法
- Community detection algorithm of hybrid node analysis and edge analysis in complex networks
- 电信科学 2023年39卷第4期页码：87-100
- 作者机构：
  
  1. 嘉兴学院信息科学与工程学院，浙江嘉兴 314001
  2. 嘉兴学院浙江省医学电子与数字健康重点实验室，浙江嘉兴 314001
  3. 常熟理工学院计算机科学与工程学院，江苏常熟 225500
- 作者简介：
  
  [ "邓琨（1980- ），男，博士，嘉兴学院信息科学与工程学院、嘉兴学院浙江省医学电子与数字健康重点实验室副教授、硕士生导师，主要研究方向为网络结构分析、数据挖掘、异构网络分析等" ]
  [ "蒋庆丰（1983- ），男，博士，常熟理工学院计算机科学与工程学院讲师，主要研究方向为计算机网络及信息安全等" ]
  [ "刘星妍（1980- ），女，嘉兴学院信息科学与工程学院高级工程师，主要研究方向为数据挖掘、网络结构分析等" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61370083);教育部人文社会科学研究专项任务项目(22JDSZ3023);浙江省教育科学规划课题项目;Zhejiang Educational Science Planning Project(2020SCG046);教育部产学合作协同育人项目;The Ministry of Education’s Industry-University Collaboration Education Project(220603372015422);教育部产学合作协同育人项目;The Ministry of Education’s Industry-University Collaboration Education Project(220604029012441)
- DOI：10.11959/j.issn.1000-0801.2023091
  中图分类号： TP391
- 网络出版日期：2023-04，
  
  纸质出版日期：2023-04-20
- 稿件说明：
移动端阅览
邓琨, 蒋庆丰, 刘星妍. 融合节点分析与边分析的复杂网络社区识别算法[J]. 电信科学, 2023,39(4):87-100.

Kun DENG, Qingfeng JIANG, Xingyan LIU. Community detection algorithm of hybrid node analysis and edge analysis in complex networks[J]. Telecommunications science, 2023, 39(4): 87-100.
邓琨, 蒋庆丰, 刘星妍. 融合节点分析与边分析的复杂网络社区识别算法[J]. 电信科学, 2023,39(4):87-100. DOI： 10.11959/j.issn.1000-0801.2023091.

Kun DENG, Qingfeng JIANG, Xingyan LIU. Community detection algorithm of hybrid node analysis and edge analysis in complex networks[J]. Telecommunications science, 2023, 39(4): 87-100. DOI： 10.11959/j.issn.1000-0801.2023091.

摘要

针对边社区识别与节点型社区识别两类算法在识别社区过程中均存在相应缺陷，影响复杂网络社区识别质量的问题，提出融合节点分析与边分析的复杂网络社区识别（CDHNE）算法。该算法首先运用边在网络中较为稳定的特点，在算法执行初期通过边社区识别构建较为准确的社区结构；然后利用节点较为灵活的特点，在边社区形成后，对边社区的边缘进行精确识别，更准确地识别出复杂网络中的社区结构。在计算机生成网络实验中，当网络的社区结构逐渐变得模糊、重叠节点数量与重叠节点归属社区数量不断增加时， CDHNE 算法的社区识别精度较传统算法平均提高 10%，在重叠节点识别精度上较传统算法平均提高 15%；在真实网络实验中，算法识别的社区结构紧密度较好，特别是面对拥有十几万个节点的大规模网络时，CDHNE算法高质量地完成了识别任务，EQ值达到0.412 1。实验结果表明，CDHNE算法在运行稳定性和处理大规模网络方面具有优势。

Abstract

The community detection of hybrid node analysis and edge analysis in complex networks (CDHNE)

a novel community detection algorithm

was proposed aiming at the problem that both edge community detection and node-based community detection algorithms had corresponding shortcomings in the process of detecting communities

which affected the quality of complex network community detection.The relatively stable characteristics of the edge in the networks were firstly used by the algorithm to construct a more accurate community structure through edge community detection at the early stage of algorithm execution.Then

after the formation of the edge communities

the flexible characteristics of the node were used to accurately detect the boundary of edge communities

so as to more accurately detect the community structure in the complex networks.In the computer-generated network experiments

when the community structure of the network gradually became fuzzy

the number of overlapping nodes and the number of communities to which the overlapping nodes belonged kept increasing.Compared to traditional algorithms

the accuracy of community detection and overlapping nodes detection were improved by an average of 10% and 15%

respectively

by the CDHNE algorithm.In the real network experiments

the tightness of the community structure detected by the CDHNE algorithm was better.Especially when facing large-scale networks with more than 100 000 nodes

the detection task was completed by the CDHNE algorithm with high quality

and the EQ value reached 0.412 1.The experimental results show that the CDHNE algorithm has advantages in operational stability and handling large-scale networks.

关键词

Keywords

references

NEWMAN M E , GIRVAN M . Finding and evaluating community structure in networks [J ] . Physical Review E,Statistical,Nonlinear,and Soft Matter Physics , 2004 , 69 ( 2 ): 026113 .

FORTUNATO S . Community detection in graphs [J ] . Physics Reports , 2010 , 486 ( 3 ): 75 - 174 .

PALLA G , DERÉNYI I , FARKAS I , et al . Uncovering the overlapping community structure of complex networks in nature and society [J ] . Nature , 2005 , 435 ( 7043 ): 814 - 818 .

SATHIYAKUMARI K , VIJAYA M . Hybrid approach for community detection using k-core and clique percolation [J ] . Zeichen Journal , 2021 , 7 ( 2 ): 187 - 201 .

SATHYAKALA M , SANGEETHA M . Retraction note to:a weak clique based multi objective genetic algorithm for overlapping community detection in complex networks [J ] . Journal of Ambient Intelligence and Humanized Computing , 2023 , 14 ( 1 ): 259 .

SUN L P , YE T , SUN J , et al . Density-peak-based overlapping community detection algorithm [J ] . IEEE Transactions on Computational Social Systems , 2022 , 9 ( 4 ): 1211 - 1223 .

LANCICHINETTI A , FORTUNATO S , KERTÉSZ J . Detecting the overlapping and hierarchical community structure in complex networks [J ] . New Journal of Physics , 2009 , 11 ( 3 ): 033015 .

ASMI K , LOTFI D , ABARDA A . The greedy coupled-seeds expansion method for the overlapping community detection in social networks [J ] . Computing , 2022 , 104 ( 2 ): 295 - 313 .

DILMAGHANI S , BRUST M R , RIBEIRO C H C , et al . From communities to protein complexes:a local community detection algorithm on PPI networks [J ] . PLoS One , 2022 , 17 ( 1 ): e0260484 .

LIAKOS P , NTOULAS A , DELIS A . COEUS:Community detection via seed-set expansion on graph streams [C ] // Proceedings of 2017 IEEE International Conference on Big Data . Piscataway:IEEE Press , 2018 : 676 - 685 .

GREGORY S . Finding overlapping communities in networks by label propagation [J ] . New Journal of Physics , 2010 , 12 ( 10 ): 103018 .

ATTAL J P , MALEK M , ZOLGHADRI M . Overlapping community detection using core label propagation algorithm and belonging functions [J ] . Applied Intelligence , 2021 , 51 ( 11 ): 8067 - 8087 .

邓琨 , 李文平 , 陈丽 , 等 . 一种新的基于标签传播的复杂网络重叠社区识别算法 [J ] . 控制与决策 , 2020 , 35 ( 11 ): 2733 - 2742 .

DENG K , LI W P , CHEN L , et al . A novel algorithm for overlapping community detection based on label propagation in complex networks [J ] . Control and Decision , 2020 , 35 ( 11 ): 2733 - 2742 .

AHN Y Y , BAGROW J P , LEHMANN S . Link communities reveal multiscale complexity in networks [J ] . Nature , 2010 , 466 ( 7307 ): 761 - 764 .

邓亚景 , 张海 , 郭骁 , 等 . 基于节点度和社区信息的复杂网络链接预测 [J ] . 工程数学学报 , 2020 , 37 ( 2 ): 245 - 259 .

DENG Y J , ZHANG H , GUO X , et al . Link prediction in complex networks incorporating the degree and community information [J ] . Chinese Journal of Engineering Mathematics , 2020 , 37 ( 2 ): 245 - 259 .

LIU Z H , WANG H M , WANG G S , et al . Link community detection combined with network pruning and local community expansion [J ] . Modern Physics Letters B , 2021 , 35 ( 5 ): 2150098 .

LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms [J ] . Physical Review E , 2008 , 78 ( 4 ): 046110 .

BRUTZ M , MEYER F G . A flexible multiscale approach to overlapping community detection [J ] . Social Network Analysis and Mining , 2015 , 5 ( 1 ): 1 - 17 .

DENG K , CHEN L , LI W P . An overlapping community detection algorithm with label propagation control for complex networks [J ] . Instrumentation Mesure Métrologie , 2019 , 18 ( 2 ): 105 - 109 .

XIE J R , KELLEY S , SZYMANSKI B K . Overlapping community detection in networks:the state-of-the-art and comparative study [J ] . ACM Computing Surveys , 2013 , 45 ( 4 ): 1 - 35 .

SHEN H W , CHENG X Q , GUO J F . Quantifying and identifying the overlapping community structure in networks [J ] . Journal of Statistical Mechanics:Theory and Experiment , 2009 , 2009 ( 7 ): P07042 .

NEWMAN M . Network data from mark newman’s home page [EB ] . 2022 .

GREGORY S . Network research [EB ] . 2022 .

LESKOVEC J . Stanford network analysis project [EB ] . 2022 .

浏览量

206

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

Linux软件网络的结构属性及静态稳健性

基于手机上网记录数据的个体相遇预测