IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v390y2021ics0096300320305567.html
   My bibliography  Save this article

An effective and scalable overlapping community detection approach: Integrating social identity model and game theory

Author

Listed:
  • Wang, Yuyao
  • Bu, Zhan
  • Yang, Huan
  • Li, Hui-Jia
  • Cao, Jie

Abstract

Because of its broad real-life application, community detection (in the realm of a complex network) is an attractive challenge to many researchers. However, current methods fail to reveal the full community structure and its formation process. Thus, here we present SIMGT, an effective and Scalable approach that detects overlapping communities: Integrating social identity Model and Game Theory. Inspired by social identity theory and nodes’ high-order proximities, first we weight and rewire the original network, then we associate each node with a new utility function. Next, we model community formation as a non-cooperative game among all nodes, and we regard the nodes as self-interested players. Further, we use a stochastic gradient-ascent method to update players’ strategies toward different communities, and prove that our game greatly resembles and matches how a potential game works (in the classical sense in game theory), indicating that the Nash equilibrium point must exist. Finally, we implement comprehensive experiments on several synthetic and real-life networks. The results show that whatever weighting strategy we choose, SIMGT can gain better performance on community detection task. In particular, SIMGT achieves a best result when we choose the Jaccard coefficient. After comparing SIMGT with six benchmark algorithms, we obtain convincing results in terms of how well the algorithms reveal communities, as well as algorithms’ scalability.

Suggested Citation

  • Wang, Yuyao & Bu, Zhan & Yang, Huan & Li, Hui-Jia & Cao, Jie, 2021. "An effective and scalable overlapping community detection approach: Integrating social identity model and game theory," Applied Mathematics and Computation, Elsevier, vol. 390(C).
  • Handle: RePEc:eee:apmaco:v:390:y:2021:i:c:s0096300320305567
    DOI: 10.1016/j.amc.2020.125601
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300320305567
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.amc.2020.125601?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hu, Jun & Xia, Chengyi & Li, Huijia & Zhu, Peican & Xiong, Wenjun, 2020. "Properties and structural analyses of USA’s regional electricity market: A visibility graph network approach," Applied Mathematics and Computation, Elsevier, vol. 385(C).
    2. Gergely Palla & Imre Derényi & Illés Farkas & Tamás Vicsek, 2005. "Uncovering the overlapping community structure of complex networks in nature and society," Nature, Nature, vol. 435(7043), pages 814-818, June.
    3. Hao Long & Xiao-Wei Liu, 2019. "A Unified Community Detection Algorithm In Large-Scale Complex Networks," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 22(03), pages 1-19, May.
    4. Jens Josephson, 2008. "Stochastic better-reply dynamics in finite games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(2), pages 381-389, May.
    5. Xie, Yingkang & Wang, Zhen & Lu, Junwei & Li, Yuxia, 2020. "Stability analysis and control strategies for a new SIS epidemic model in heterogeneous networks," Applied Mathematics and Computation, Elsevier, vol. 383(C).
    6. Peng, Hao & Peng, Wangxin & Zhao, Dandan & Wang, Wei, 2020. "Impact of the heterogeneity of adoption thresholds on behavior spreading in complex networks," Applied Mathematics and Computation, Elsevier, vol. 386(C).
    7. Yong-Yeol Ahn & James P. Bagrow & Sune Lehmann, 2010. "Link communities reveal multiscale complexity in networks," Nature, Nature, vol. 466(7307), pages 761-764, August.
    8. Yin, Qian & Wang, Zhishuang & Xia, Chengyi & Dehmer, Matthias & Emmert-Streib, Frank & Jin, Zhen, 2020. "A novel epidemic model considering demographics and intercity commuting on complex dynamical networks," Applied Mathematics and Computation, Elsevier, vol. 386(C).
    9. Andrea Lancichinetti & Filippo Radicchi & José J Ramasco & Santo Fortunato, 2011. "Finding Statistically Significant Communities in Networks," PLOS ONE, Public Library of Science, vol. 6(4), pages 1-18, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lin, Wei & Li, Min & Zhou, Shuming & Liu, Jiafei & Chen, Gaolin & Zhou, Qianru, 2021. "Phase transition in spectral clustering based on resistance matrix," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 566(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wu, Zhihao & Lin, Youfang & Wan, Huaiyu & Tian, Shengfeng & Hu, Keyun, 2012. "Efficient overlapping community detection in huge real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(7), pages 2475-2490.
    2. Franke, R., 2016. "CHIMERA: Top-down model for hierarchical, overlapping and directed cluster structures in directed and weighted complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 461(C), pages 384-408.
    3. Badie, Reza & Aleahmad, Abolfazl & Asadpour, Masoud & Rahgozar, Maseud, 2013. "An efficient agent-based algorithm for overlapping community detection using nodes’ closeness," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(20), pages 5231-5247.
    4. Zhang, Hongli & Gao, Yang & Zhang, Yue, 2018. "Overlapping communities from dense disjoint and high total degree clusters," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 286-298.
    5. Eustace, Justine & Wang, Xingyuan & Cui, Yaozu, 2015. "Overlapping community detection using neighborhood ratio matrix," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 421(C), pages 510-521.
    6. Sun, Peng Gang & Wu, Xunlian & Quan, Yining & Miao, Qiguang, 2022. "Influence percolation method for overlapping community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    7. Zhou, Xu & Liu, Yanheng & Zhang, Jindong & Liu, Tuming & Zhang, Di, 2015. "An ant colony based algorithm for overlapping community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 427(C), pages 289-301.
    8. Sun, Peng Gang, 2015. "Community detection by fuzzy clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 408-416.
    9. Gao, Yang & Zhang, Hongli & Zhang, Yue, 2019. "Overlapping community detection based on conductance optimization in large-scale networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 522(C), pages 69-79.
    10. Jia, Songwei & Gao, Lin & Gao, Yong & Nastos, James & Wen, Xiao & Zhang, Xindong & Wang, Haiyang, 2017. "Exploring triad-rich substructures by graph-theoretic characterizations in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 468(C), pages 53-69.
    11. Gao, Yang & Zhang, Hongli & Zhang, Yue, 2019. "Overlapping communities from lines and triangles in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 521(C), pages 455-466.
    12. Yu, Shuo & Alqahtani, Fayez & Tolba, Amr & Lee, Ivan & Jia, Tao & Xia, Feng, 2022. "Collaborative Team Recognition: A Core Plus Extension Structure," Journal of Informetrics, Elsevier, vol. 16(4).
    13. Jiang, Yawen & Jia, Caiyan & Yu, Jian, 2013. "An efficient community detection method based on rank centrality," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2182-2194.
    14. Zhou, Xu & Liu, Yanheng & Wang, Jian & Li, Chun, 2017. "A density based link clustering algorithm for overlapping community detection in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 486(C), pages 65-78.
    15. Chagas, Guilherme Oliveira & Lorena, Luiz Antonio Nogueira & dos Santos, Rafael Duarte Coelho, 2022. "A hybrid heuristic for overlapping community detection through the conductance minimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(C).
    16. Jean-Gabriel Young & Antoine Allard & Laurent Hébert-Dufresne & Louis J Dubé, 2015. "A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure," PLOS ONE, Public Library of Science, vol. 10(10), pages 1-19, October.
    17. Fu, Xianghua & Liu, Liandong & Wang, Chao, 2013. "Detection of community overlap according to belief propagation and conflict," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(4), pages 941-952.
    18. Xiaofeng Wang & Gongshen Liu & Jianhua Li & Jan P Nees, 2017. "Locating Structural Centers: A Density-Based Clustering Method for Community Detection," PLOS ONE, Public Library of Science, vol. 12(1), pages 1-23, January.
    19. Lovro Šubelj & Nees Jan van Eck & Ludo Waltman, 2016. "Clustering Scientific Publications Based on Citation Relations: A Systematic Comparison of Different Methods," PLOS ONE, Public Library of Science, vol. 11(4), pages 1-23, April.
    20. Akshat Singhal & Song Cao & Christopher Churas & Dexter Pratt & Santo Fortunato & Fan Zheng & Trey Ideker, 2020. "Multiscale community detection in Cytoscape," PLOS Computational Biology, Public Library of Science, vol. 16(10), pages 1-10, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:apmaco:v:390:y:2021:i:c:s0096300320305567. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.