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

Kun DENG; Qingfeng JIANG; Xingyan LIU

doi:10.11959/j.issn.1000-0801.2023091

您当前的位置：

首页 >

文章列表页 >

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

Research and Development | 更新时间：2024-06-05

- Community detection algorithm of hybrid node analysis and edge analysis in complex networks
- Telecommunications Science Vol. 39, Issue 4, Pages: 87-100(2023)
- 作者机构：
  
  1. 嘉兴学院信息科学与工程学院，浙江嘉兴 314001
  2. 嘉兴学院浙江省医学电子与数字健康重点实验室，浙江嘉兴 314001
  3. 常熟理工学院计算机科学与工程学院，江苏常熟 225500
- 作者简介：
- 基金信息：
  
  The Humanity and Social Science Research Project of Ministry of Education of China(22JDSZ3023)
- DOI：10.11959/j.issn.1000-0801.2023091
  CLC： TP391
- Published Online：2023-04，
  
  Published：20 April 2023
- 稿件说明：
移动端阅览
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：

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 .

Views

206

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Structural properties and static robustness of Linux software network

Individual encounter prediction based on mobile internet record data

Related Author

Ershen WANG

Yu LI

Chen HONG

Qinghua SUN

Chang LIU

Qian LI

Hao JIANG

Jintao YANG

Related Institution

School of Electronic and Information Engineering, Shenyang Aerospace University

Beijing Key Laboratory of Information Service Engineering,Beijing Union University

College of Robotics,Beijing Union University

⁰