Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (4): 49-55.doi: 10.11896/jsjkx.210800275

• Special Issue of Social Computing Based Interdisciplinary Integration • Previous Articles     Next Articles

EWCC Community Discovery Algorithm for Two-Layer Network

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

  1. 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).

PDF (PC)

2340

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

CLC Number: 

  • TP312
[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.
[1] HE Yi-chen, MAO Yi-jun, XIE Xian-fen, GU Wan-rong. Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation [J]. Computer Science, 2022, 49(6A): 272-279.
[2] ZHANG Qing-qi, LIU Man-dan. Multi-objective Five-elements Cycle Optimization Algorithm for Complex Network Community Discovery [J]. Computer Science, 2020, 47(8): 284-290.
[3] DONG Ming-gang, GONG Jia-ming and JING Chao. Multi-obJective Evolutionary Algorithm Based on Community Detection Spectral Clustering [J]. Computer Science, 2020, 47(6A): 461-466.
[4] ZHENG Xiang-ping, YU Zhi-yong, WEN Guang-bin. Community Discovery in Location Network [J]. Computer Science, 2018, 45(6): 46-50.
[5] PENG Li-zhen and WU Yang-yang. Semantic Similarity Computing Based on Community Mining of Wikipedia [J]. Computer Science, 2016, 43(4): 45-49.
[6] LIU Jing-lian, WANG Da-ling, ZHAO Wei-ji, FENG Shi and ZHANG Yi-fei. Algorithm for Discovering Network Community with Centrality and Overlap [J]. Computer Science, 2016, 43(3): 33-37.
[7] CAO Xiao-chun, JING Li-hua, WANG Rui, ZHANG Rui, DONG Zhen-jiang and XIONG Hong-kai. Specific Content Monitoring on Social Networks Based on Social Computing and Deep Learning [J]. Computer Science, 2016, 43(10): 1-8.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.