面向双层网络的EWCC社区发现算法

doi:10.11896/jsjkx.210800275

计算机科学 ›› 2022, Vol. 49 ›› Issue (4): 49-55.doi: 10.11896/jsjkx.210800275

• 基于社会计算的多学科交叉融合专题^* • 上一篇下一篇

面向双层网络的EWCC社区发现算法

唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜

青海师范大学计算机学院西宁 810016; 省部共建藏语智能信息处理及应用国家重点实验室西宁 810008; 藏文信息处理教育部重点实验室西宁 810008; 青海省藏文信息处理与机器翻译重点实验室西宁 810008

收稿日期:2021-08-31 修回日期:2021-12-12 发布日期:2022-04-01
通讯作者: 赵海兴(h.x.zhao@163.com)
作者简介:(Tangcyqh@163.com)
基金资助:
国家自然科学基金(61763041); 青海省科技项目(2020-GX-112); 青海师范大学自然科学中青年科研基金(2020QZR007)

EWCC Community Discovery Algorithm for Two-Layer Network

TANG Chun-yang, XIAO Yu-zhi, ZHAO Hai-xing, YE Zhong-lin, ZHANG Na

College of Computer, Qinghai Normal University, Xining 810016, China; The Provincial and Ministerial Joint Construction of the State Key Laboratory of Tibetan Intelligent Information Processing and Application, Xining 810008, China; Key Laboratory of Tibetan Information Processing, Ministry of Education, Xining 810008, China; Tibetan Information Processing and Machine Translation Key Laboratory of Qinghai Province, Xining 810008, China

Received:2021-08-31 Revised:2021-12-12 Published:2022-04-01
Supported by:
This work was supported by the National Natural Science Foundation of China(61763041),Science and Technology Department of Qinghai Province(2020-GX-112) and Middle-Youth Program of Natural Science Foundation of Qinghai Normal University(2020QZR007).

摘要/Abstract

摘要： 针对关系型网络的社区发现问题,考虑节点间相互作用的强弱程度和信息渗流机理,创新性地提出了一种基于边权重和连通分支(Edge Weight and Connected Component,EWCC)的社区发现算法。为了验证算法的有效性,首先,构建了5种具有相互作用的双层网络模型,通过分析层间节点作用的强弱程度对网络拓扑结构的影响,确定了5种双层网络模型下生成的30个数据集;其次,选用真实数据集分别与GN算法和KL算法在模块度、算法复杂度和社区划分数目评价准则上进行了对比,实验结果表明EWCC算法的准确性较高;然后,结合数值仿真得出,随着层间作用关系减弱,模块度值和社区数目成反比,并且当双层网络层间节点关系较弱时,社区划分效果较好;最后,作为算法的应用,利用实证数据构建了 “用户-APP” 的双层网络并进行了社区划分。

关键词: 边权重, 关系型网络, 连通分支, 社区发现, 双层网络

Abstract: Aiming at the problem of community discovery in relational networks, considering the strength of interaction between nodes and information seepage mechanism, an edge weight and connected component (EWCC) community discovery algorithm based on edge weight and connected branches is innovatively proposed.In order to verify effectiveness of the algorithm, firstly, five kinds of interactive two-layer network models are constructed.By analyzing influence of interaction degree of nodes between layers on the network topology, 30 data sets generated under five kinds of two-layer network models are determined.Secondly, the real data set is selected to compare with GN algorithm and KL algorithm in the evaluation criteria of modularity, algorithm complexity and community division number.Experimental results show that EWCC algorithm has high accuracy.Then, the numerical simulation shows that with the weakening of interaction relationship between layers, the module degree is inversely proportional to number of communities, and the community division effect is better when node relationship between layers is weaker.Finally, as an application of the algorithm, the “user-APP” two-layer network is constructed based on empirical data, and the community is divided.

Key words: Community discovery, Connected branch, Edge weight, Relational network, Two-Layer network

中图分类号:

TP312

唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法[J]. 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275

TANG Chun-yang, XIAO Yu-zhi, ZHAO Hai-xing, YE Zhong-lin, ZHANG Na. EWCC Community Discovery Algorithm for Two-Layer Network[J]. Computer Science, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275

参考文献

[1] WANG X F,LIU Y B.A survey of community structure algorithms in complex networks[J].Journal of University of Electronic Science and Technology of China,2009,38(5):537-543.
[2] XIE J,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.
[3] AN X D,ZHANG X Q,CAO F Y.Binary network community discovery algorithm based on edge density propagation[J].Computer Applications and Software,2019,36(3):243-248,254.
[4] ZHANG H,WU Y K,YANG Z Z,et al.Community discovery method based on multi-layer node similarity[J].Computer Science,2018,45(1):216-222.
[5] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proc. Natl. Acad. Sci.,2001,99(12):7821-7826.
[6] XIE J,SZYMANSKI B K.Community Detection Using a Neighborhood Strength Driven Label Propagation Algorithm[C]//2021 IEEE Network Science Workshop.West Point,NY,USA:IEEE,2011:188-195.
[7] KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970,49(2):291-307.
[8] CHEN K J,CHEN L M,WU T.A review of research on disco-very of multi-layer Network communities[J].Journal of Frontiers of Computer Science & Technology,2020,14(11):1801-1812.
[9] HMIMIDA M,KANAWATI R.Community Detection in Multiplex Networks:A Seed-centric Approach[J].Networks & He-terogeneous Media,2015,10(1):71-85.
[10] YAKOUBI Z,KANAWATI R.LICOD:A leader-driven algo-rithm for community detection in complex networks[J].Vietnam Journal of Computer Science,2014,1(4):241-256.
[11] ALIMADADI F,KHANANGI E,BAGHERI A.Community detection in facebook activity networks and presenting a new multilayer label propagation algorithm for community detection[J].International Journal of Modern Physics B,2019,33(10):1950089(1)-1950089(21).
[12] INTERDONATO R,TAGARELLI A,IENCO D,et al.Local Community Detection in Multilayer Networks[J].Data Mining &Knowledge Discovery,2017,31(5):1444-1479.
[13] KUNCHEVA Z,MONTANA G.Community detection in multiplex networks using locally adaptive random walks[C]//Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.Paris,France:IEEE,2015:1308-1315.
[14] BARABASI A L,ALBERT R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.
[15] WATTS D J,STROGATZ S H.Collective dynamics of ‘small-world’ network[J].Nature,1998,393(6684):440-442.
[16] ERDOS P,RENYI A.On the Evolution of Random Graphs[J].Publ.Math.Inst.Hung.Acad Sci,1960,5(1):17-61.
[17] HOLME P,KIM B J,YOON C N,et al.Attack vulnerability of complex networks[J].Physical Review E Statistical Nonlinear &Soft Matter Physics,2002,65(5):056109.
[18] NEWMAN M,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):423-433.

相关文章 15

[1]	何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159
[2]	王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[3]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[4]	陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010
[5]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[6]	徐新黎, 肖云月, 龙海霞, 杨旭华, 毛剑飞. 基于矩阵分解的属性网络嵌入和社区发现算法 Attributed Network Embedding Based on Matrix Factorization and Community Detection 计算机科学, 2021, 48(12): 204-211. https://doi.org/10.11896/jsjkx.210300060
[7]	宁懿昕, 谢辉, 姜火文. 图神经网络社区发现研究综述 Survey of Graph Neural Network in Community Detection 计算机科学, 2021, 48(11A): 11-16. https://doi.org/10.11896/jsjkx.210500151
[8]	张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法 Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery 计算机科学, 2020, 47(8): 284-290. https://doi.org/10.11896/jsjkx.190700082
[9]	董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究 Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering 计算机科学, 2020, 47(6A): 461-466. https://doi.org/10.11896/JsJkx.191100215
[10]	张琴, 陈红梅, 封云飞. 一种基于粗糙集和密度峰值的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Density Peaks 计算机科学, 2020, 47(5): 72-78. https://doi.org/10.11896/jsjkx.190400160
[11]	赵卫绩,张凤斌,刘井莲. 复杂网络社区发现研究进展 Review on Community Detection in Complex Networks 计算机科学, 2020, 47(2): 10-20. https://doi.org/10.11896/jsjkx.190100214
[12]	张琴, 陈红梅, 封云飞. 基于粗糙集和距离动态模型的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model 计算机科学, 2020, 47(10): 75-82. https://doi.org/10.11896/jsjkx.190800002
[13]	赵霞, 李娴, 张泽华, 张晨威. 结合社区嵌入和节点嵌入的社区发现算法 Community Detection Algorithm Combing Community Embedding and Node Embedding 计算机科学, 2020, 47(10): 121-125. https://doi.org/10.11896/jsjkx.191000099
[14]	龚卫华, 沈松. 基于社区发现的兴趣点推荐 Community Detection Based Point-of-interest Recommendation 计算机科学, 2019, 46(12): 63-68. https://doi.org/10.11896/jsjkx.190400440
[15]	刘春, 张国良. 一种基于重叠社区发现的软件特征提取方法 Software Feature Extraction Method Based on Overlapping Community Detection 计算机科学, 2019, 46(12): 201-207. https://doi.org/10.11896/jsjkx.181001856

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

面向双层网络的EWCC社区发现算法

EWCC Community Discovery Algorithm for Two-Layer Network

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0