research-article

Modeling with Node Popularities for Autonomous Overlapping Community Detection

Authors:

Weixiong ZhangAuthors Info & Claims

ACM Transactions on Intelligent Systems and Technology (TIST), Volume 11, Issue 3

Article No.: 27, Pages 1 - 23

https://doi.org/10.1145/3373760

Published: 17 April 2020 Publication History

Abstract

Overlapping community detection has triggered recent research in network analysis. One of the promising techniques for finding overlapping communities is the popular stochastic models, which, unfortunately, have some common drawbacks. They do not support an important observation that highly connected nodes are more likely to reside in the overlapping regions of communities in the network. These methods are in essence not truly unsupervised, since they require a threshold on probabilistic memberships to derive overlapping structures and need the number of communities to be specified a priori. We develop a new method to address these issues for overlapping community detection. We first present a stochastic model to accommodate the relative importance and the expected degree of every node in each community. We then infer every overlapping community by ranking the nodes according to their importance. Second, we determine the number of communities under the Bayesian framework. We evaluate our method and compare it with five state-of-the-art methods. The results demonstrate the superior performance of our method. We also apply this new method to two applications, showing its superb performance on practical problems.

References

[1]

Yong-Yeol Ahn, James P. Bagrow, and Sune Lehmann. 2010. Link communities reveal multiscale complexity in networks. Nature 466, 7307 (2010), 761.

[2]

Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. 2008. Mixed membership stochastic blockmodels. J. Mach. Learn. Res. 9, 1 (2008), 1981--2014.

Digital Library

[3]

Michael Ashburner, Catherine A. Ball, Judith A. Blake, David Botstein, Heather Butler, J. Michael Cherry, Allan P. Davis, Kara Dolinski, Selina S. Dwight, Janan T. Eppig, et al. 2000. Gene ontology: Tool for the unification of biology. Nat. Genet. 25, 1 (2000), 25.

[4]

Brian Ball, Brian Karrer, and Mark E. J. Newman. 2011. Efficient and principled method for detecting communities in networks. Phys. Rev. E 84, 3 (2011), 036103.

[5]

Gema Bello-Orgaz, Sancho Salcedo-Sanz, and David Camacho. 2018. A multi-objective genetic algorithm for overlapping community detection based on edge encoding. Inf. Sci. 462, 30 (2018), 290--314.

Digital Library

[6]

Tanmoy Chakraborty, Saptarshi Ghosh, and Noseong Park. 2019. Ensemble-based overlapping community detection using disjoint community structures. Knowl.-Based Syst. 163, 1 (2019), 241--251.

[7]

Jia Hou Chin and Kuru Ratnavelu. 2016. Detecting community structure by using a constrained label propagation algorithm. PLoS ONE 11, 5 (2016), e0155320.

[8]

Leon Danon, Albert Diaz-Guilera, Jordi Duch, and Alex Arenas. 2005. Comparing community structure identification. J. Stat. Mech.: Theory Exp. 2005, 9 (2005), P09008.

[9]

Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc. Ser. B. 39, 1 (1977), 1--38.

[10]

Hossein Fani and Ebrahim Bagheri. 2017. Community detection in social networks. Encyclopedia with Semantic Computing and Robotic Intelligence 1, 1 (2017), 1630001.

[11]

C. Felbaum. 1998. Wordnet, an Electronic Lexical Database for English.

[12]

Santo Fortunato. 2010. Community detection in graphs. Phys. Rep. 486, 3–5 (2010), 75--174.

[13]

Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Phys. Rep. 659, 54 (2016), 1--44.

[14]

Prem K. Gopalan and David M. Blei. 2013. Efficient discovery of overlapping communities in massive networks. Proc. Natl. Acad. Sci. U.S.A. 110, 36 (2013), 14534--14539.

[15]

Steve Gregory. 2010. Finding overlapping communities in networks by label propagation. New J. Phys. 12, 10 (2010), 103018.

[16]

Lennart Gulikers, Marc Lelarge, and Laurent Massoulié. 2017. A spectral method for community detection in moderately sparse degree-corrected stochastic block models. Adv. Appl. Probab. 49, 3 (2017), 686--721.

[17]

Dongxiao He, Dayou Liu, Di Jin, and Weixiong Zhang. 2015. A Stochastic Model for Detecting Heterogeneous Link Communities in Complex Networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'15). 130--136.

[18]

Mingqing Huang, Guobing Zou, Bofeng Zhang, Yue Liu, Yajun Gu, and Keyuan Jiang. 2018. Overlapping community detection in heterogeneous social networks via the user model. Inf. Sci. 432, 11 (2018), 164--184.

[19]

Di Jin, Zheng Chen, Dongxiao He, and Weixiong Zhang. 2015. Modeling with node degree preservation can accurately find communities. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’15). 160--167.

[20]

Di Jin, Bingyi Li, Pengfei Jiao, Dongxiao He, and Hongyu Shan. 2019. Community detection via joint graph convolutional network embedding in attribute network. In Proceedings of the International Conference on Artificial Neural Networks. Springer, 594--606.

Digital Library

[21]

Di Jin, Hongcui Wang, Jianwu Dang, Dongxiao He, and Weixiong Zhang. 2016. Detect overlapping communities via ranking node popularities. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’16). 172--178.

[22]

Di Jin, Xiaobao Wang, Ruifang He, Dongxiao He, Jianwu Dang, and Weixiong Zhang. 2018. Robust detection of link communities in large social networks by exploiting link semantics. 2018. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'18). 314--321.

[23]

Di Jin, Bo Yang, Carlos Baquero, Dayou Liu, Dongxiao He, and Jie Liu. 2011. A Markov random walk under constraint for discovering overlapping communities in complex networks. J. Stat. Mech.: Theory Exp. 2011, 05 (2011), P05031.

[24]

Brian Karrer and Mark E. J. Newman. 2011. Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 1 (2011), 016107.

[25]

Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. 2013. Spectral redemption in clustering sparse networks. Proc. Natl. Acad. Sci. U.S.A. 110, 52 (2013), 20935--20940.

[26]

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

[27]

Andrea Lancichinetti, Santo Fortunato, and János Kertész. 2009. Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11, 3 (2009), 033015.

[28]

Andrea Lancichinetti, Filippo Radicchi, José J. Ramasco, and Santo Fortunato. 2011. Finding statistically significant communities in networks. PLoS ONE 6, 4 (2011), e18961.

[29]

Daniel D. Lee and H. Sebastian Seung. 2001. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems. 556--562.

[30]

Jure Leskovec and Andrej Krevl. 2014. SNAP: Stanford network analysis project. https://snap.stanford.edu.

[31]

Jure Leskovec, Kevin J. Lang, and Michael Mahoney. 2010. Empirical comparison of algorithms for network community detection. In Proceedings of the 19th International Conference on World Wide Web. ACM, 631--640.

Digital Library

[32]

Y. Li, H. Chen, and B. Yang. 2018. Reparameterized stochastic block model adaptive to heterogeneous degree and block distributions. IEEE Access 6, 7 (2018), 37615--37626.

[33]

Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. 2018. Community detection in attributed graphs: An embedding approach. (2018).

[34]

Qiang Liu, Caihong Liu, Jiajia Wang, Xiang Wang, Bin Zhou, and Peng Zou. 2017. Evolutionary link community structure discovery in dynamic weighted networks. Physica A 466, 2 (2017), 370--388.

[35]

Zhenqi Lu, Johan Wahlström, and Arye Nehorai. 2018. Community detection in complex networks via clique conductance. Sci. Rep. 8, 1 (2018), 5982.

[36]

Vince Lyzinski, Minh Tang, Avanti Athreya, Youngser Park, and Carey E Priebe. 2017. Community detection and classification in hierarchical stochastic blockmodels. IEEE Trans. Netw. Sci. Eng. 4, 1 (2017), 13--26.

[37]

Douglas L. Nelson, Cathy L. McEvoy, and Thomas A. Schreiber. 2004. The University of South Florida free association, rhyme, and word fragment norms. Behav. Res. Methods Instrum. Comput. 36, 3 (2004), 402--407.

[38]

Mark E. J. Newman. 2012. Communities, modules and large-scale structure in networks. Nat. Phys. 8, 1 (2012), 25.

[39]

Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043 (2005), 814.

[40]

Francesco Sanna Passino and Nicholas A. Heard. 2019. Bayesian estimation of the latent dimension and communities in stochastic blockmodels. arXiv preprint arXiv:1904.05333 (2019).

[41]

Subhadeep Paul, Yuguo Chen, et al. 2016. Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel. Electr. J. Stat. 10, 2 (2016), 3807--3870.

[42]

Yulong Pei, Nilanjan Chakraborty, and Katia Sycara. 2015. Nonnegative matrix tri-factorization with graph regularization for community detection in social networks. In Proceedings of the 24th International Joint Conference on Artificial Intelligence.

Digital Library

[43]

Simon Pool, Francesco Bonchi, and Matthijs van Leeuwen. 2014. Description-driven community detection. ACM Trans. Intell. Syst. Technol. 5, 2 (2014), 28.

Digital Library

[44]

Ioannis Psorakis, Stephen Roberts, Mark Ebden, and Ben Sheldon. 2011. Overlapping community detection using bayesian non-negative matrix factorization. Phys. Rev. E 83, 6 (2011), 066114.

[45]

Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E 76, 3 (2007), 036106.

[46]

Mohammad Sattari and Kamran Zamanifar. 2018. A spreading activation-based label propagation algorithm for overlapping community detection in dynamic social networks. Data Knowl. Eng. 113, 1 (2018), 155--170.

[47]

Huawei Shen, Xueqi Cheng, Kai Cai, and Mao-Bin Hu. 2009. Detect overlapping and hierarchical community structure in networks. Physica A 388, 8 (2009), 1706--1712.

[48]

Hua-Wei Shen, Xue-Qi Cheng, and Jia-Feng Guo. 2011. Exploring the structural regularities in networks. Phys. Rev. E 84, 5 (2011), 056111.

[49]

Heli Sun, Jiao Liu, Jianbin Huang, Guangtao Wang, Xiaolin Jia, and Qinbao Song. 2017. LinkLPA: A link-based label propagation algorithm for overlapping community detection in networks. Comput. Intell. 33, 2 (2017), 308–331.

Digital Library

[50]

Toni Valles-Catala, Francesco A. Massucci, Roger Guimera, and Marta Sales-Pardo. 2016. Multilayer stochastic block models reveal the multilayer structure of complex networks. Phys. Rev. X 6, 1 (2016), 011036.

[51]

Twan Van Laarhoven and Elena Marchiori. 2016. Local network community detection with continuous optimization of conductance and weighted kernel k-means. J. Mach. Learn. Res. 17, 147 (2016), 1--28.

[52]

Hadrien Van Lierde, G. Chen, and Tommy W. S. Chow. 2019. Scalable spectral clustering for overlapping community detection in large-scale networks. IEEE Trans. Knowl. Data Eng. 32, 4 (2019), 754--767.

[53]

Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. 2017. Community preserving network embedding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’17). 203--209.

[54]

Xiao Wang, Di Jin, Xiaochun Cao, Liang Yang, and Weixiong Zhang. 2016. Semantic community identification in large attribute networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI’16). 265--271.

[55]

Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon. 2016. Overlapping community detection using neighborhood-inflated seed expansion. IEEE Trans. Knowl. Data Eng. 28, 5 (2016), 1272--1284.

Digital Library

[56]

Ioannis Xenarios, Danny W. Rice, Lukasz Salwinski, Marisa K. Baron, Edward M. Marcotte, and David Eisenberg. 2000. DIP: The database of interacting proteins. Nucleic Acids Res. 28, 1 (2000), 289--291.

[57]

Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski. 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Comput. Surv. 45, 4 (2013), 43.

Digital Library

[58]

Jierui Xie and Boleslaw K. Szymanski. 2012. Towards linear time overlapping community detection in social networks. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 25--36.

[59]

Jierui Xie, Boleslaw K. Szymanski, and Xiaoming Liu. 2011. Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In Proceedings of the IEEE 11th International Conference on Data Mining Workshops (ICDMW’11). IEEE, 344--349.

Digital Library

[60]

Bo Yang, Xuehua Hao, and Xueyan Liu. 2015. Bayesian approach to modeling and detecting communities in signed network. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI'15). 1952--1958.

[61]

Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: A nonnegative matrix factorization approach. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining. ACM, 587--596.

Digital Library

[62]

Jaewon Yang and Jure Leskovec. 2014. Structure and overlaps of ground-truth communities in networks. ACM Trans. Intell. Syst. Technol. 5, 2 (2014), 26.

Digital Library

[63]

Wayne W. Zachary. 1977. An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33, 4 (1977), 452--473.

[64]

Yu Zhang and Dit-Yan Yeung. 2012. Overlapping community detection via bounded nonnegative matrix tri-factorization. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 606--614.

Digital Library

[65]

Chen Zhe, Aixin Sun, and Xiaokui Xiao. 2019. Community detection on large complex attribute network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery 8 Data Mining. ACM, 2041--2049.

Digital Library

Cited By

Li YCheng SFeng YZhang YAngeloudis PQuddus MOchieng W(2024)Developing a novel approach in estimating urban commute traffic by integrating community detection and hypergraph representation learningExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123790249:PCOnline publication date: 17-Jul-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123790
Yang HZhang JDing XChen CWang L(2022)GTIP: A Gaming-Based Topic Influence Percolation Model for Semantic Overlapping Community DetectionEntropy10.3390/e2409127424:9(1274)Online publication date: 9-Sep-2022
https://doi.org/10.3390/e24091274
Wang MLi BHe KHopcroft J(2022)Uncovering the Local Hidden Community Structure in Social NetworksACM Transactions on Knowledge Discovery from Data10.1145/356759717:5(1-25)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3567597
Show More Cited By

Index Terms

Modeling with Node Popularities for Autonomous Overlapping Community Detection
1. Computing methodologies
  1. Artificial intelligence
  2. Machine learning
    1. Machine learning algorithms

Recommendations

Overlapping community detection using seed set expansion
CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

Community detection is an important task in network analysis. A community (also referred to as a cluster) is a set of cohesive vertices that have more connections inside the set than outside. In many social and information networks, these communities ...
Overlapping community detection at scale: a nonnegative matrix factorization approach
WSDM '13: Proceedings of the sixth ACM international conference on Web search and data mining

Network communities represent basic structures for understanding the organization of real-world networks. A community (also referred to as a module or a cluster) is typically thought of as a group of nodes with more connections amongst its members than ...
Local Overlapping Community Detection

Local community detection refers to finding the community that contains the given node based on local information, which becomes very meaningful when global information about the network is unavailable or expensive to acquire. Most studies on local ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Intelligent Systems and Technology

ACM Transactions on Intelligent Systems and Technology Volume 11, Issue 3

Survey Paper and Regular Papers

June 2020

286 pages

ISSN:2157-6904

EISSN:2157-6912

DOI:10.1145/3392081

Editor:
Yu Zheng
JD Finance, China

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 April 2020

Accepted: 01 November 2019

Revised: 01 October 2019

Received: 01 December 2018

Published in TIST Volume 11, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Natural Science Foundation of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
400
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YCheng SFeng YZhang YAngeloudis PQuddus MOchieng W(2024)Developing a novel approach in estimating urban commute traffic by integrating community detection and hypergraph representation learningExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123790249:PCOnline publication date: 17-Jul-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123790
Yang HZhang JDing XChen CWang L(2022)GTIP: A Gaming-Based Topic Influence Percolation Model for Semantic Overlapping Community DetectionEntropy10.3390/e2409127424:9(1274)Online publication date: 9-Sep-2022
https://doi.org/10.3390/e24091274
Wang MLi BHe KHopcroft J(2022)Uncovering the Local Hidden Community Structure in Social NetworksACM Transactions on Knowledge Discovery from Data10.1145/356759717:5(1-25)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3567597
Singh SSrivastava VKumar ATiwari SSingh DLee H(2022)Social Network Analysis: A Survey on Measure, Structure, Language Information Analysis, Privacy, and ApplicationsACM Transactions on Asian and Low-Resource Language Information Processing10.1145/353973222:5(1-47)Online publication date: 8-Jun-2022
https://dl.acm.org/doi/10.1145/3539732
Wang YJin DHe DMusial KDang J(2022)Community Detection in Social Networks Considering Social BehaviorsIEEE Access10.1109/ACCESS.2022.320970410(109969-109982)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3209704
Lin HZhan YZhao ZChen YDong C(2021)Overlapping Community Detection Based on Attribute Augmented GraphEntropy10.3390/e2306068023:6(680)Online publication date: 28-May-2021
https://doi.org/10.3390/e23060680
Sun HLi YLv BYan WHe LQiao SHuang J(2021)Graph Community InfomaxACM Transactions on Knowledge Discovery from Data10.1145/348024416:3(1-21)Online publication date: 15-Nov-2021
https://dl.acm.org/doi/10.1145/3480244
Jin DYu ZJiao PPan SHe DWu JYu PZhang W(2021)A Survey of Community Detection Approaches: From Statistical Modeling to Deep LearningIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.3104155(1-1)Online publication date: 2021
https://doi.org/10.1109/TKDE.2021.3104155
Mahabadi AHosseini M(2021)SLPA-based parallel overlapping community detection approach in large complex social networksMultimedia Tools and Applications10.1007/s11042-020-09993-180:5(6567-6598)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11042-020-09993-1

View Options

Get Access

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents