IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0083739.html
   My bibliography  Save this article

Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm

Author

Listed:
  • Zhenping Li
  • Xiang-Sun Zhang
  • Rui-Sheng Wang
  • Hongwei Liu
  • Shihua Zhang

Abstract

Identification of communities in complex networks is an important topic and issue in many fields such as sociology, biology, and computer science. Communities are often defined as groups of related nodes or links that correspond to functional subunits in the corresponding complex systems. While most conventional approaches have focused on discovering communities of nodes, some recent studies start partitioning links to find overlapping communities straightforwardly. In this paper, we propose a new quantity function for link community identification in complex networks. Based on this quantity function we formulate the link community partition problem into an integer programming model which allows us to partition a complex network into overlapping communities. We further propose a genetic algorithm for link community detection which can partition a network into overlapping communities without knowing the number of communities. We test our model and algorithm on both artificial networks and real-world networks. The results demonstrate that the model and algorithm are efficient in detecting overlapping community structure in complex networks.

Suggested Citation

  • Zhenping Li & Xiang-Sun Zhang & Rui-Sheng Wang & Hongwei Liu & Shihua Zhang, 2013. "Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-10, December.
    • Handle: RePEc:plo:pone00:0083739
    DOI: 10.1371/journal.pone.0083739
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0083739
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0083739&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0083739?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Vicsek, Tamás, 2007. "Phase transitions and overlapping modules in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378(1), pages 20-32.
    3. T. S. Evans & R. Lambiotte, 2010. "Line graphs of weighted networks for overlapping communities," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 77(2), pages 265-272, September.
    4. Li, Kun & Gong, Xiaofeng & Guan, Shuguang & Lai, C.-H., 2012. "Efficient algorithm based on neighborhood overlap for community identification in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(4), pages 1788-1796.
    5. István A Kovács & Robin Palotai & Máté S Szalay & Peter Csermely, 2010. "Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy, Identify Key Nodes and Predict Network Dynamics," PLOS ONE, Public Library of Science, vol. 5(9), pages 1-14, September.
    6. Marcel Salathé & James H Jones, 2010. "Dynamics and Control of Diseases in Networks with Community Structure," PLOS Computational Biology, Public Library of Science, vol. 6(4), pages 1-11, April.
    7. Zhang, Shihua & Wang, Rui-Sheng & Zhang, Xiang-Sun, 2007. "Identification of overlapping community structure in complex networks using fuzzy c-means clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 374(1), pages 483-490.
    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. Frank Havemann & Jochen Gläser & Michael Heinz, 2017. "Memetic search for overlapping topics based on a local evaluation of link communities," Scientometrics, Springer;Akadémiai Kiadó, vol. 111(2), pages 1089-1118, May.
    2. Benati, Stefano & Puerto, Justo & Rodríguez-Chía, Antonio M. & Temprano, Francisco, 2022. "A mathematical programming approach to overlapping community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 602(C).
    3. Peng Wu & Li Pan, 2015. "Multi-Objective Community Detection Based on Memetic Algorithm," PLOS ONE, Public Library of Science, vol. 10(5), pages 1-31, May.
    4. Seungseob Lee & SuKyoung Lee & Kyungsoo Kim & Yoon Hyuk Kim, 2015. "Base Station Placement Algorithm for Large-Scale LTE Heterogeneous Networks," PLOS ONE, Public Library of Science, vol. 10(10), pages 1-19, October.

    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. 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.
    2. 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.
    3. 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.
    4. Zhang, Zhiwei & Wang, Zhenyu, 2015. "Mining overlapping and hierarchical communities in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 421(C), pages 25-33.
    5. 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.
    6. Wu, Jianshe & Wang, Xiaohua & Jiao, Licheng, 2012. "Synchronization on overlapping community network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(3), pages 508-514.
    7. 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.
    8. 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.
    9. Chen, Duanbing & Shang, Mingsheng & Lv, Zehua & Fu, Yan, 2010. "Detecting overlapping communities of weighted networks via a local algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(19), pages 4177-4187.
    10. Yi-Shan Sung & Dashun Wang & Soundar Kumara, 0. "Uncovering the effect of dominant attributes on community topology: A case of facebook networks," Information Systems Frontiers, Springer, vol. 0, pages 1-12.
    11. Tzai-Hung Wen & Wei Chien Benny Chin, 2015. "Incorporation of Spatial Interactions in Location Networks to Identify Critical Geo-Referenced Routes for Assessing Disease Control Measures on a Large-Scale Campus," IJERPH, MDPI, vol. 12(4), pages 1-15, April.
    12. Lan Huang & Guishen Wang & Yan Wang & Enrico Blanzieri & Chao Su, 2013. "Link Clustering with Extended Link Similarity and EQ Evaluation Division," PLOS ONE, Public Library of Science, vol. 8(6), pages 1-18, June.
    13. Wang, Zhenwen & Hu, Yanli & Xiao, Weidong & Ge, Bin, 2013. "Overlapping community detection using a generative model for networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(20), pages 5218-5230.
    14. Abdolhosseini-Qomi, Amir Mahdi & Yazdani, Naser & Asadpour, Masoud, 2020. "Overlapping communities and the prediction of missing links in multiplex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 554(C).
    15. Wu, Jianshe & Lu, Rui & Jiao, Licheng & Liu, Fang & Yu, Xin & Wang, Da & Sun, Bo, 2013. "Phase transition model for community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(6), pages 1287-1301.
    16. Ma, Xiaoke & Gao, Lin & Yong, Xuerong & Fu, Lidong, 2010. "Semi-supervised clustering algorithm for community structure detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(1), pages 187-197.
    17. Carlo Piccardi, 2011. "Finding and Testing Network Communities by Lumped Markov Chains," PLOS ONE, Public Library of Science, vol. 6(11), pages 1-13, November.
    18. Shang, Jiaxing & Liu, Lianchen & Li, Xin & Xie, Feng & Wu, Cheng, 2015. "Epidemic spreading on complex networks with overlapping and non-overlapping community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 171-182.
    19. Taghavian, Fatemeh & Salehi, Mostafa & Teimouri, Mehdi, 2017. "A local immunization strategy for networks with overlapping community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 467(C), pages 148-156.
    20. Sun, Peng Gang, 2015. "Community detection by fuzzy clustering," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 408-416.

    More about this item

    Statistics

    Access and download statistics

    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:plo:pone00:0083739. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.