IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v522y2019icp69-79.html
   My bibliography  Save this article

Overlapping community detection based on conductance optimization in large-scale networks

Author

Listed:
  • Gao, Yang
  • Zhang, Hongli
  • Zhang, Yue

Abstract

Community structure reveals useful information in domains of sociology, biology, physics and computer science. In this work, an overlapping community detection algorithm for large-scale networks based on local expansion is proposed, in which we present a novel seeding method. And we optimize conductance of communities by: (1) modifying inaccurate community affiliations by node movements; (2) combining densely overlapping communities with a novel combining function; (3) finding communities for the outliers with our proposed theorem. Experimental results in synthetic networks show that the optimization largely enhance the community accuracy. Experimental results in large real-world networks show that our approach is superior to the others in the state of the art.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:phsmap:v:522:y:2019:i:c:p:69-79
    DOI: 10.1016/j.physa.2019.01.142
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119301487
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.01.142?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. Daniel D. Lee & H. Sebastian Seung, 1999. "Learning the parts of objects by non-negative matrix factorization," Nature, Nature, vol. 401(6755), pages 788-791, October.
    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. 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.
    4. 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. 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).
    2. Sahar Bakhtar & Hovhannes A. Harutyunyan, 2022. "A new metric to compare local community detection algorithms in social networks using geodesic distance," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2809-2831, November.
    3. Manuel Guerrero & Consolación Gil & Francisco G. Montoya & Alfredo Alcayde & Raúl Baños, 2020. "Multi-Objective Evolutionary Algorithms to Find Community Structures in Large Networks," Mathematics, MDPI, vol. 8(11), pages 1-18, November.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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).
    8. 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).
    9. 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.
    10. Sun, Peng Gang, 2015. "Community detection by fuzzy clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 408-416.
    11. 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.
    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:phsmap:v:522:y:2019:i:c:p:69-79. 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: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.