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

doi:10.11959/j.issn.1000-0801.2023091

电信科学 ›› 2023, Vol. 39 ›› Issue (4): 87-100.doi: 10.11959/j.issn.1000-0801.2023091

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

邓琨¹^,², 蒋庆丰³, 刘星妍¹

¹ 嘉兴学院信息科学与工程学院，浙江嘉兴 314001
² 嘉兴学院浙江省医学电子与数字健康重点实验室，浙江嘉兴 314001
³ 常熟理工学院计算机科学与工程学院，江苏常熟 225500

修回日期:2023-04-12 出版日期:2023-04-20 发布日期:2023-04-01
作者简介:邓琨（1980- ），男，博士，嘉兴学院信息科学与工程学院、嘉兴学院浙江省医学电子与数字健康重点实验室副教授、硕士生导师，主要研究方向为网络结构分析、数据挖掘、异构网络分析等
蒋庆丰（1983- ），男，博士，常熟理工学院计算机科学与工程学院讲师，主要研究方向为计算机网络及信息安全等
刘星妍（1980- ），女，嘉兴学院信息科学与工程学院高级工程师，主要研究方向为数据挖掘、网络结构分析等
基金资助:
国家自然科学基金资助项目(61370083);教育部人文社会科学研究专项任务项目(22JDSZ3023);浙江省教育科学规划课题项目(2020SCG046);教育部产学合作协同育人项目(220603372015422);教育部产学合作协同育人项目(220604029012441)

Community detection algorithm of hybrid node analysis and edge analysis in complex networks

Kun DENG¹^,², Qingfeng JIANG³, Xingyan LIU¹

¹ College of Information Science and Engineering, Jiaxing University, Jiaxing 314001, China
² Key Laboratory of Medical Electronics and Digital Health of Zhejiang Province, Jiaxing University, Jiaxing 314001, China
³ School of Computer Science and Engineering, Changshu Institute of Technology, Changshu 225500, China

Revised:2023-04-12 Online:2023-04-20 Published:2023-04-01
Supported by:
The National Natural Science Foundation of China(61370083);The Humanity and Social Science Research Project of Ministry of Education of China(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)

摘要/Abstract

摘要：

针对边社区识别与节点型社区识别两类算法在识别社区过程中均存在相应缺陷，影响复杂网络社区识别质量的问题，提出融合节点分析与边分析的复杂网络社区识别（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.

Key words: complex network, community detection, edge community, node analysis, edge analysis

中图分类号:

TP391

邓琨, 蒋庆丰, 刘星妍. 融合节点分析与边分析的复杂网络社区识别算法[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.

图/表 12

图1

图2

图3

表1

表2

表3

图4

图5

图6

图7

表4

表5

参考文献 24

[1]	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.
[2]	FORTUNATO S . Community detection in graphs[J]. Physics Reports, 2010,486(3): 75-174.
[3]	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.
[4]	SATHIYAKUMARI K , VIJAYA M . Hybrid approach for community detection using k-core and clique percolation[J]. Zeichen Journal, 2021,7(2): 187-201.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	GREGORY S . Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010,12(10): 103018.
[12]	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.
[13]	邓琨, 李文平, 陈丽 ,等. 一种新的基于标签传播的复杂网络重叠社区识别算法[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.
[14]	AHN Y Y , BAGROW J P , LEHMANN S . Link communities reveal multiscale complexity in networks[J]. Nature, 2010,466(7307): 761-764.
[15]	邓亚景, 张海, 郭骁 ,等. 基于节点度和社区信息的复杂网络链接预测[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.
[16]	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.
[17]	LANCICHINETTI A , FORTUNATO S , RADICCHI F . Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008,78(4): 046110.
[18]	BRUTZ M , MEYER F G . A flexible multiscale approach to overlapping community detection[J]. Social Network Analysis and Mining, 2015,5(1): 1-17.
[19]	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.
[20]	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.
[21]	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.
[22]	NEWMAN M . Network data from mark newman’s home page[EB]. 2022.
[23]	GREGORY S . Network research[EB]. 2022.
[24]	LESKOVEC J . Stanford network analysis project[EB]. 2022.

算法阶段	分析过程	时间复杂度
初始化边社区阶段	每个节点需要分析k个邻居节点的度，因此，其时间复杂度为O( 2k )，那么分析网络G中n个节点的时间复杂度为O(nk²)，将与c个核心节点连接的边归入社区的时间复杂度为O(ck)，因此，初始化边社区的时间复杂度约为O(ck+nk²)	O(ck+nk ²)
扩展边社区阶段	分析每条边与其邻接社区存在紧密连接边与紧密连接组的时间复杂度约为O(2k)，计算m条边的边社区增量函数的时间复杂度约为O(mt)，因此扩展边社区阶段的时间复杂度不会超过O(2mkt)	O (2mkt)
扩展节点社区阶段	分析孤立节点、重叠节点与其邻接社区的节点社区增量函数的时间复杂度约为O(2m_c)，分析o个孤立节点与重叠节点的时间复杂度约为O(2om_c)	O (2om_c)

算法	开发环境	提出时间
CFINDER	C++	2005年
MS	Java	2016年
CoEuS	Java	2017年
OLPC	MATLAB	2019年
CDHNE	MATLAB	2023年

网络名称	节点/边/平均度
Lesmis（《悲惨世界》中人物的共现网络）^[22]	77/254/6.6
Email（电子邮件交往网络）^[22]	1 133/5 451/9.62
Netscience（科研作者合作网络）^[22]	1 588/2 742/3.45
Word（语汇语义网络）^[23]	7 207/31 784/8.82
PGP（信任网络）^[22]	10 680/24 316/4.55
Internet（互联网快照网络）^[22]	22 963/48 436/4.22
Facebook（脸书交互网络）^[24]	134 833/1 380 293/10.24

网络	CDHNE	CFINDER	MS	CoEus	OLPC
Lesmis	0.532 9	0.395 3（k=6）	0.386 6	0.309 8	0.421 5
Email	0.358 2	0.264 1（k=4）	0.151 3	0.183 5	0.305 5
Netscience	0.890 1	0.761 1（k=3）		0.150 6	0.738 1
Word	0.162 3	0.164 9（k=4）		0.012 8
PGP	0.493 7			0.012 8	0.695 9
Internet	0.367 6			0.257 9	0.274 3
Facebook	0.412 1

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

Community detection algorithm of hybrid node analysis and edge analysis in complex networks

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 24

相关文章 3

Metrics

推荐阅读 0

网络	n	k	k_max	C_max	C_min	O_n	O_m	μ
R1	5 000	10	30	50	30	500	2	0.1～0.4
R2	5 000	10	30	50	30	2 500	2	0.1～0.4
R3	5 000	10	30	50	30	500	2～6	0.1
R4	5 000	10	30	50	30	500	2～6	0.3

[1]	王尔申, 李宇, 宏晨, 孙庆华, 刘畅. Linux软件网络的结构属性及静态稳健性[J]. 电信科学, 2019, 35(11): 9-18.
[2]	李倩,江昊,杨锦涛. 基于手机上网记录数据的个体相遇预测[J]. 电信科学, 2017, 33(10): 115-123.
[3]	畅兴平,夏清华. 确定性复杂网络的稳定性受随机打击影响的研究[J]. 电信科学, 2010, 26(7): 109-113.