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

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Author

Listed:
  • Chen, Duanbing
  • Fu, Yan
  • Shang, Mingsheng

Abstract

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K–L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:phsmap:v:388:y:2009:i:13:p:2741-2749
    DOI: 10.1016/j.physa.2009.03.022
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437109002209
    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.2009.03.022?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. Dorogovtsev, S.N. & Mendes, J.F.F., 2003. "Evolution of Networks: From Biological Nets to the Internet and WWW," OUP Catalogue, Oxford University Press, number 9780198515906.
    2. Wang, Xutao & Chen, Guanrong & Lu, Hongtao, 2007. "A very fast algorithm for detecting community structures in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 384(2), pages 667-674.
    3. Steven H. Strogatz, 2001. "Exploring complex networks," Nature, Nature, vol. 410(6825), pages 268-276, March.
    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. Hanlin You & Mengjun Li & Jiang Jiang & Bingfeng Ge & Xueting Zhang, 2017. "Evolution monitoring for innovation sources using patent cluster analysis," Scientometrics, Springer;Akadémiai Kiadó, vol. 111(2), pages 693-715, May.
    2. Li, Junqiu & Wang, Xingyuan & Eustace, Justine, 2013. "Detecting overlapping communities by seed community in weighted complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6125-6134.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Zhang, Dawei & Xie, Fuding & Zhang, Yong & Dong, Fangyan & Hirota, Kaoru, 2010. "Fuzzy analysis of community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(22), pages 5319-5327.
    10. Angelito Calma & José Martí-Parreño & Martin Davies, 2019. "Journal of the Academy of Marketing Science 1973–2018: an analytical retrospective," Scientometrics, Springer;Akadémiai Kiadó, vol. 119(2), pages 879-908, May.
    11. Wang, Xingyuan & Li, Junqiu, 2013. "Detecting communities by the core-vertex and intimate degree in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(10), pages 2555-2563.
    12. 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.

    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, Yun & Liu, Yongguo & Li, Jieting & Zhu, Jiajing & Yang, Changhong & Yang, Wen & Wen, Chuanbiao, 2020. "WOCDA: A whale optimization based community detection algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    2. Wang, Qingyun & Duan, Zhisheng & Chen, Guanrong & Feng, Zhaosheng, 2008. "Synchronization in a class of weighted complex networks with coupling delays," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(22), pages 5616-5622.
    3. Juan Pablo Cárdenas & Gerardo Vidal & Carolina Urbina & Gastón Olivares & Pablo Rodrigo & Miguel Fuentes, 2018. "Social Crises: Signatures of Complexity in a Fast-Growing Economy," Complexity, Hindawi, vol. 2018, pages 1-11, April.
    4. Selen Onel & Abe Zeid & Sagar Kamarthi, 2011. "The structure and analysis of nanotechnology co-author and citation networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(1), pages 119-138, October.
    5. Wen, Guanghui & Duan, Zhisheng & Chen, Guanrong & Geng, Xianmin, 2011. "A weighted local-world evolving network model with aging nodes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(21), pages 4012-4026.
    6. Cárdenas, J.P. & Mouronte, M.L. & Benito, R.M. & Losada, J.C., 2010. "Compatibility as underlying mechanism behind the evolution of networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(8), pages 1789-1798.
    7. 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.
    8. Tanimoto, Jun, 2016. "A multi-community homogeneous small-world network and its fundamental characteristics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 88-97.
    9. 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.
    10. Rafael Rentería-Ramos & Rafael Hurtado-Heredia & B Piedad Urdinola, 2019. "Morbi-Mortality of the Victims of Internal Conflict and Poor Population in the Risaralda Province, Colombia," IJERPH, MDPI, vol. 16(9), pages 1-18, May.
    11. Yun Wang, Qing & Rong Chen, Guan & Shao Lu, Qi & Hao, Fei, 2007. "Novel criteria of synchronization stability in complex networks with coupling delays," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378(2), pages 527-536.
    12. Jianxi Gao & Xueming Liu & Daqing Li & Shlomo Havlin, 2015. "Recent Progress on the Resilience of Complex Networks," Energies, MDPI, vol. 8(10), pages 1-24, October.
    13. Pawel Sobkowicz, 2009. "Modelling Opinion Formation with Physics Tools: Call for Closer Link with Reality," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 12(1), pages 1-11.
    14. Li, Junqiu & Wang, Xingyuan & Eustace, Justine, 2013. "Detecting overlapping communities by seed community in weighted complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(23), pages 6125-6134.
    15. G. De Masi & M. Gallegati, 2012. "Bank–firms topology in Italy," Empirical Economics, Springer, vol. 43(2), pages 851-866, October.
    16. Emerson, Isaac Arnold & Amala, Arumugam, 2017. "Protein contact maps: A binary depiction of protein 3D structures," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 465(C), pages 782-791.
    17. Ya-Chun Gao & Zong-Wen Wei & Bing-Hong Wang, 2013. "Dynamic Evolution Of Financial Network And Its Relation To Economic Crises," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 24(02), pages 1-10.
    18. Faedo, Nicolás & García-Violini, Demián & Ringwood, John V., 2021. "Controlling synchronization in a complex network of nonlinear oscillators via feedback linearisation and H∞-control," Chaos, Solitons & Fractals, Elsevier, vol. 144(C).
    19. Zhou, Wei-Xing & Jiang, Zhi-Qiang & Sornette, Didier, 2007. "Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 375(2), pages 741-752.
    20. Bezsudnov, I.V. & Snarskii, A.A., 2014. "From the time series to the complex networks: The parametric natural visibility graph," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 414(C), pages 53-60.

    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:388:y:2009:i:13:p:2741-2749. 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.