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

Detecting community structure using biased random merging

Author

Listed:
  • Liu, Xu
  • Forrest, Jeffrey Yi-Lin
  • Luo, Qiang
  • Yi, Dong-Yun

Abstract

Decomposing a network into small modules or communities is beneficial for understanding the structure and dynamics of the network. One of the most prominent approaches is to repeatedly join communities together in pairs with the greatest increase in modularity so that a dendrogram that shows the order of joins is obtained. Then the community structure is acquired by cutting the dendrogram at the levels corresponding to the maximum modularity. However, there tends to be multiple pairs of communities that share the maximum modularity increment and the greedy agglomerative procedure may only merge one of them. Although the modularity function typically admits a lot of high-scoring solutions, the greedy strategy may fail to reach any of them. In this paper we propose an enhanced data structure in order to enable diverse choices of merging operations in community finding procedure. This data structure is actually a max-heap equipped with an extra array that stores the maximum modularity increments; and the corresponding community pairs is merged in the next move. By randomly sampling elements in this head array, additional diverse community structures can be efficiently extracted. The head array is designed to host the community pairs corresponding to the most significant increments in modularity so that the modularity structures obtained out of the sampling exhibit high modularity scores that are, on the average, even greater than what the CNM algorithm produces. Our method is tested on both real-world and computer-generated networks.

Suggested Citation

  • Liu, Xu & Forrest, Jeffrey Yi-Lin & Luo, Qiang & Yi, Dong-Yun, 2012. "Detecting community structure using biased random merging," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(4), pages 1797-1810.
    • Handle: RePEc:eee:phsmap:v:391:y:2012:i:4:p:1797-1810
    DOI: 10.1016/j.physa.2011.09.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437111007667
    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.2011.09.028?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. Pan, Ying & Li, De-Hua & Liu, Jian-Guo & Liang, Jing-Zhang, 2010. "Detecting community structure in complex networks via node similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(14), pages 2849-2857.
    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. J. M. Kumpula & J. Saramäki & K. Kaski & J. Kertész, 2007. "Limited resolution in complex network community detection with Potts model approach," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 56(1), pages 41-45, March.
    4. Réka Albert & Hawoong Jeong & Albert-László Barabási, 1999. "Diameter of the World-Wide Web," Nature, Nature, vol. 401(6749), pages 130-131, September.
    5. Chen, Duanbing & Fu, Yan & Shang, Mingsheng, 2009. "A fast and efficient heuristic algorithm for detecting community structures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(13), pages 2741-2749.
    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. Cui, Yaozu & Wang, Xingyuan & Li, Junqiu, 2014. "Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 85-91.
    2. Zhou, HongFang & Li, Jin & Li, JunHuai & Zhang, FaCun & Cui, YingAn, 2017. "A graph clustering method for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 551-562.

    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. Sun, Hong-liang & Ch’ng, Eugene & Yong, Xi & Garibaldi, Jonathan M. & See, Simon & Chen, Duan-bing, 2018. "A fast community detection method in bipartite networks by distance dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 108-120.
    2. Shang, Jiaxing & Liu, Lianchen & Li, Xin & Xie, Feng & Wu, Cheng, 2016. "Targeted revision: A learning-based approach for incremental community detection in dynamic networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 70-85.
    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. 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.
    5. Gong, Maoguo & Ma, Lijia & Zhang, Qingfu & Jiao, Licheng, 2012. "Community detection in networks by using multiobjective evolutionary algorithm with decomposition," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(15), pages 4050-4060.
    6. Li, Junqiu & Wang, Xingyuan & Cui, Yaozu, 2014. "Uncovering the overlapping community structure of complex networks by maximal cliques," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 415(C), pages 398-406.
    7. Guo, Xue & Li, Weibo & Zhang, Hu & Tian, Tianhai, 2022. "Multi-likelihood methods for developing relationship networks using stock market data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 585(C).
    8. Weiwei Zhang & Jinde Cao & Dingyuan Chen & Ahmed Alsaedi, 2019. "Out Lag Synchronization of Fractional Order Delayed Complex Networks with Coupling Delay via Pinning Control," Complexity, Hindawi, vol. 2019, pages 1-7, August.
    9. Pang, Shaopeng & Hao, Fei, 2017. "Optimizing controllability of edge dynamics in complex networks by perturbing network structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 470(C), pages 217-227.
    10. Shen, Yi & Pei, Wenjiang & Wang, Kai & Li, Tao & Wang, Shaoping, 2008. "Recursive filtration method for detecting community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(26), pages 6663-6670.
    11. Weihua Zhan & Jihong Guan & Zhongzhi Zhang, 2017. "A New Method for Extracting the Hierarchical Organization of Networks," International Journal of Information Technology & Decision Making (IJITDM), World Scientific Publishing Co. Pte. Ltd., vol. 16(05), pages 1359-1385, September.
    12. Qiming Lu & G. Korniss & Boleslaw Szymanski, 2009. "The Naming Game in social networks: community formation and consensus engineering," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 4(2), pages 221-235, November.
    13. Shang, Ronghua & Bai, Jing & Jiao, Licheng & Jin, Chao, 2013. "Community detection based on modularity and an improved genetic algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(5), pages 1215-1231.
    14. Yang, Kai & Guo, Qiang & Liu, Jian-Guo, 2018. "Community detection via measuring the strength between nodes for dynamic networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 509(C), pages 256-264.
    15. Kibae Kim & Jörn Altmann & Sodam Baek, 2015. "Role of Platform Providers in Software Ecosystems," TEMEP Discussion Papers 2015120, Seoul National University; Technology Management, Economics, and Policy Program (TEMEP), revised Jan 2015.
    16. Shen, Huawei & Cheng, Xueqi & Cai, Kai & Hu, Mao-Bin, 2009. "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(8), pages 1706-1712.
    17. Beiró, Mariano G. & Busch, Jorge R. & Grynberg, Sebastian P. & Alvarez-Hamelin, J. Ignacio, 2013. "Obtaining communities with a fitness growth process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(9), pages 2278-2293.
    18. Li, Wenyuan & Lin, Yongjing & Liu, Ying, 2007. "The structure of weighted small-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 376(C), pages 708-718.
    19. Gupta, Naveen & Singh, Anurag & Cherifi, Hocine, 2016. "Centrality measures for networks with community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 452(C), pages 46-59.
    20. Havlin, Shlomo & Stanley, H. Eugene & Bashan, Amir & Gao, Jianxi & Kenett, Dror Y., 2015. "Percolation of interdependent network of networks," Chaos, Solitons & Fractals, Elsevier, vol. 72(C), pages 4-19.

    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:391:y:2012:i:4:p:1797-1810. 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.