research-article

Motif‐based embedding label propagation algorithm for community detection

Authors:

Yanchun ZhangAuthors Info & Claims

International Journal of Intelligent Systems, Volume 37, Issue 3

Pages 1880 - 1902

https://doi.org/10.1002/int.22759

Published: 25 January 2022 Publication History

Abstract

Community detection can exhibit the aggregation behavior of complex networks. Network motifs are the fundamental building blocks which can reveal the higher‐order structure of complex networks. Label propagation algorithm has the advantage of approximately linear time complexity, unfortunately, the randomness of label update is a major but unsolved issue. For these reasons, this paper proposes a novel community detection method, named motif‐based embedding label propagation algorithm (MELPA). First, complex network topology is reconstructed by merging higher‐order topology with lower‐order connectivity features, where higher‐order topology is captured by mining network motifs. Second, We design a label propagation characteristic model according to nodes influence, then a new label update rule is formulated based on reconstructed weighted network, the rule integrates frequency among neighbor labels, influence of nodes, propagation characteristics and closeness of nodes to update the node label, the purpose is to overcome the randomness of label selection and identify a better and more stable community structure. Finally, extensive experiments on synthetic networks and real‐world complex networks are conducted to verify the effectiveness of MELPA, especially for the complex networks with unobvious community structure, MELPA will get unexpected results.

References

[1]

Zhang Y, Yu JX, Hou J. Web Communities: Analysis and Construction. Springer‐Verlag Berlin; 2006.

[2]

Xu G, Zhang Y, Lin L. Web Mining and Social Networking: Techniques and Applications. Springer‐Verlag Berlin; 2011.

[3]

Sun M, Yang R. An efficient secure k nearest neighbor classification protocol with highdimensional features. Int J Intell Syst. 2020;35(11):1791‐1813.

Digital Library

[4]

Girvan M, Newman MEJ. Community structure in social and biological networks. Proc Natl Acad Sci USA. 2002;99(12):7821‐7826.

[5]

Leskovec J, Lang KJ, Dasgupta A, Mahoney MW. Community structure in large networks: natural cluster sizes and the absence of large well‐defined clusters. Internet Math. 2009;6(1):29‐123.

[6]

Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Phys Rev E. 2004;69:026113.

[7]

Xie J, Szymanski BK, Liu X. Slpa: uncovering overlapping communities in social networks via a speaker‐listener interaction dynamic process. In: Proceedings of IEEE 11th International Conference on Data Mining Workshops; 2011:344‐349.

[8]

Shang R, Luo S, Zhang W, Stolkin R, Jiao L. A multiobjective evolutionary algorithm to find community structures based on affinity propagation. Phys A. 2016;453:203‐227.

[9]

Epasto A, Lattanzi S, Leme RP. Ego‐splitting framework: from non‐overlapping to overlapping clusters. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2017:145‐153.

[10]

Leskovec J, Lang KJ, Mahoney MW. Empirical comparison of algorithms for network community detection. In: Proceedings of the 19th International Conference on World Wide Web; 2010:631‐640.

[11]

Coscia M, RosseSi G, GiannoSi F, Pedreschi D, Uncovering hierarchical and overlapping communities with a local‐first approach. ACM T Knowl Discov D. 2014;9(1):6.1‐6.27.

[12]

Epasto A, Lattanzi S, Mirrokni V, Sebeand IO. Ego‐net community mining applied to friend suggestion. In: Proceedings of the VLDB Endowment; 2015:324‐335.

[13]

Milo R, Shen‐Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U. Network motifs: simple building blocks of complex networks. Science. 2002;298(5594):824‐827.

[14]

Yaveroğlu őN, Malod‐Dognin N, Davis D, Levnajic Y. Revealing the hidden language of complex networks. Sci Rep. 2014;4(1):4547.

[15]

Benson AR, Gleich DF, Leskovec J. Higher‐order organization of complex networks. Science. 2016;353(6295):163‐166.

[16]

Tang Z, Tang Y, Li C, Cao J, Chen G. A fast local community detection algorithm in complex networks. World Wide Web. 2021;24:1929‐1955.

Digital Library

[17]

Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q. Line: large‐scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web; 2015:1067‐1077.

[18]

Wang D, Cui P. Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2016:1225‐1234.

[19]

Zhu M, Wang X, Shi C, Ji H. Interpreting and unifying graph neural networks with an optimization framework. In: Proceedings of the 30th Web Conference; 2021:1215‐1226.

[20]

Li P, Huang L, Wang C, Lai J, Huang D. Community detection by motif‐aware label propagation. ACM Trans Knowl Discov D. 2019;14(2):111.1‐111.20.

[21]

Raghavan UN, Albert R, Kumara S. Near linear time algorithm to detect community structures in large‐scale networks. Phys Rev E. 2007;76(3):036106.

[22]

Chen J, Hsu W, Lee ML. Labeling network motifs in protein interactomes for protein function prediction. In: Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering; 2007:106‐115.

[23]

Arenas A, Fernandez A, Fortunato S, Gomez S. Motifbased communities in complex networks. Phys A: Math Theor. 2008;41(22):224001.

[24]

Kovanen L, Kaski K, Kertész J, Saramäki J. Temporal motifs reveal homophily. Gender‐specific patterns, and group talk in call sequences. Proc Natl Acad Sci USA. 2013;110(45):18070‐18075.

[25]

Huang L, Wang C, Chao H. HM‐modularity: a harmonic motif modularity approach for multilayer network community detection. IEEE T Knowl Data Eng. 2021;33(6):2520‐2533.

[26]

Arnau P, David D, Josep‐M B, Josep‐Lluis L, Put three and three together: triangle‐driven community detection. ACM T Knowl Discov D. 2016;10(3):1‐42.

[27]

Tsourakakis CE, Pachocki J, Mitzenmacher M. Scalable motif‐aware graph clustering. In: Proceedings of the 26th International Conference on World Wide Web; 2017:1451‐1460.

[28]

Pizzuti C, Socievole A. Motif‐based community detection in multiplex networks. In: Proceedings of the International Workshop on Complex Networks and their Applications; 2017:190‐201.

[29]

Li PZ, Huang L, Wang CD, Huang D, Lai JH. Community detection using attribute homogenous motif. IEEE Access. 2018;6(8):47707‐47716.

[30]

Yin H, Benson AR, Leskovec J, Gleich DF. Local higher‐order graph clustering. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2017:555‐564.

[31]

Ma W, Cai L, He T, Chen L, Cao Z, Li R. Local expansion and optimization for higher‐order graph clustering. IEEE Internet Things. 2019;6(5):8702‐8713.

[32]

Lu Z, Wahlström J, Nehorai A. Community detection in complex networks via clique conductance. Sci Rep. 2018;8(1):5982.

[33]

Zhang Y, Wu B, Liu Y, Lv J. Local community detection based on network motifs. Tsinghua Sci Technol. 2018;24(6):716‐727.

[34]

Huang L, Chao H, Xie G. MuMod: a micro‐unit connection approach for hybrid‐order community detection. In: Proceedings of the AAAI Conference on Artificial Intelligence; 2020:107‐114.

[35]

Wu X, Wang CD, Jiao P. Hybrid‐order stochastic block model. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence; 2021;35(5):4470‐4477.

[36]

Lu M, Zhang Z, Qu Z, Kang Y. LPANNI: overlapping community detection using label propagation in large‐scale complex networks. IEEE T Knowl Data Eng. 2019;31(9):1736‐1749.

Digital Library

[37]

Chen N, Liu Y, Chen H, Cheng J. Detecting communities in social networks using label propagation with information entropy. Phys A. 2017;471:788‐798.

[38]

Staudt CL, Meyerhenke H. Engineering parallel algorithms for community detection in massive networks. IEEE Trans Parallel Distrib Syst. 2016;27(1):171‐184.

Digital Library

[39]

Hua Z, Yang Y, Qiu H. Node influence‐based label propagation algorithm for semi‐supervised learning. Neural Comput & Applic. 2021;33:2753‐2768.

Digital Library

[40]

Yang G, Zheng W, Che C, Wang W. Graph‐based label propagation algorithm for community detection. Int J Mach LearnCybern. 2020;11:1319‐1329.

[41]

Deng ZH, Qiao HH, Song Q, Gao L, A complex network community detection algorithm based on label propagation and fuzzy C‐means. Phys A. 2019;519:217‐226.

[42]

Raju E, Ramadevi Y, Sravanthi K. CILPA: a cohesion index based label propagation algorithm for unveiling communities in complex social networks. Int J Inf Tecnol. 2018;10:435‐445.

[43]

Li P, Huang L, Wang C, lai J. EdMot: an edge enhancement approach for motif‐aware community detection. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2019:479‐487.

[44]

Aral S, Walker D. Identifying influential and susceptible members of social networks. Science. 2012;337(6092):337‐341.

[45]

Zhang Y, Liu Y, Li Q, Jin R. LILPA: a label importance based label propagation algorithm for community detection with application to core drug discovery. Neurocomputing. 2020;413(9):107‐133.

[46]

Chakraborty T, Dalmia A, Mukherjee A, Ganguly N. Metrics for community analysis: a survey. ACM Comput Surv. 2017;50(4):54.1‐54.37.

[47]

Shang R, Zhang W, Jiao L, Stolkin R, Xue Y. A community integration strategy based on an improved modularity density increment for large‐scale networks. Phys A 2017;469(45):471‐485.

[48]

Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E. 2009;80(1):016118.

[49]

Wernicke S, Rasche F. FANMOD: a tool for fast network motif detection. Bioinformatics. 2006;22(9):1152‐1153.

Digital Library

[50]

Li Y, Sha C, Huang X, Zhang Y. Community detection in attributed graphs: an embedding approach. In: Proceedings of the Thirty‐Second AAAI Conference on Artificial Intelligence (AAAI‐18); 2018:338‐345.

Cited By

Hajibabaei HSeydi VKoochari A(2024)A motif-based probabilistic approach for community detection in complex networksJournal of Intelligent Information Systems10.1007/s10844-024-00850-362:5(1285-1303)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10844-024-00850-3
Cai TLiao YMa CLiu L(2023)Community Detection Algorithm Based on Local Random Walk with Restart and Label PropagationProceedings of the 2023 11th International Conference on Computer and Communications Management10.1145/3617733.3617769(221-225)Online publication date: 4-Aug-2023
https://dl.acm.org/doi/10.1145/3617733.3617769
Yue YWang GHu JLi Y(2023)An improved label propagation algorithm based on community core node and label importance for community detection in sparse networkApplied Intelligence10.1007/s10489-022-04397-053:14(17935-17951)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s10489-022-04397-0
Show More Cited By

Recommendations

An Improved Label Propagation Algorithm Based on Motif and Critical Node for Community Detection
Advanced Intelligent Computing Technology and Applications
Abstract
Community detection can reveal the structural properties of real social networks. In community detection, label propagation is an effective typical method which has the advantage of nearly linear time complexity. However, it usually random selects ...
Semi-supervised partial label learning algorithm via reliable label propagation
Abstract
Partial label learning (PLL) is a weakly supervised learning method that is able to predict one label as the correct answer from a given candidate label set. In PLL, when all possible candidate labels are as signed to real-world training examples, ...
Community Detection Using Label Propagation in Entropic Order
CIT '12: Proceedings of the 2012 IEEE 12th International Conference on Computer and Information Technology

Community structure is an important topological property of complex networks and community detection has become a common methodology to understand the organization and function of various complex networks. Label propagation is an extremely fast ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Intelligent Systems

International Journal of Intelligent Systems Volume 37, Issue 3

March 2022

871 pages

ISSN:0884-8173

DOI:10.1002/int.v37.3

Issue’s Table of Contents

© 2021 Wiley Periodicals LLC.

Publisher

John Wiley and Sons Ltd.

United Kingdom

Publication History

Published: 25 January 2022

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hajibabaei HSeydi VKoochari A(2024)A motif-based probabilistic approach for community detection in complex networksJournal of Intelligent Information Systems10.1007/s10844-024-00850-362:5(1285-1303)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10844-024-00850-3
Cai TLiao YMa CLiu L(2023)Community Detection Algorithm Based on Local Random Walk with Restart and Label PropagationProceedings of the 2023 11th International Conference on Computer and Communications Management10.1145/3617733.3617769(221-225)Online publication date: 4-Aug-2023
https://dl.acm.org/doi/10.1145/3617733.3617769
Yue YWang GHu JLi Y(2023)An improved label propagation algorithm based on community core node and label importance for community detection in sparse networkApplied Intelligence10.1007/s10489-022-04397-053:14(17935-17951)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s10489-022-04397-0
Chen XZhao M(2022)A Stable Community Detection Approach for Large-Scale Complex Networks Based on Improved Label Propagation AlgorithmIntelligent Computing Methodologies10.1007/978-3-031-13832-4_25(288-303)Online publication date: 7-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-13832-4_25
Ren XZheng XZhou HLiu WDong X(2022)Contrastive hashing with vision transformer for image retrievalInternational Journal of Intelligent Systems10.1002/int.2308237:12(12192-12211)Online publication date: 19-Sep-2022
https://dl.acm.org/doi/10.1002/int.23082
Xie XNing WHuang YLi ZYu SYang H(2022)Graph‐based Bayesian network conditional normalizing flows for multiple time series anomaly detectionInternational Journal of Intelligent Systems10.1002/int.2302737:12(10924-10939)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1002/int.23027
Huang LTang YFu CWang JWang C(2022)GHOCInternational Journal of Intelligent Systems10.1002/int.2298037:11(9055-9079)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1002/int.22980
Li NTu WAi HDeng HTao JHu TSun X(2022)VISELInternational Journal of Intelligent Systems10.1002/int.2291337:10(7992-8020)Online publication date: 20-May-2022
https://dl.acm.org/doi/10.1002/int.22913

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents