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

Detecting community structure in complex networks using simulated annealing with k-means algorithms

Author

Listed:
  • Liu, Jian
  • Liu, Tingzhan

Abstract

Identifying the community structure in a complex network has been addressed in many different ways. In this paper, the simulated annealing strategy is used to maximize the modularity of a network, associating with a dissimilarity-index-based and with a diffusion-distance-based k-means iterative procedure. The proposed algorithms outperform most existing methods in the literature as regards the optimal modularity found. They can not only identify the community structure, but also give the central node of each community during the cooling process. An appropriate number of communities can be efficiently determined without any prior knowledge about the community structure. The computational results for several artificial and real-world networks confirm the capability of the algorithms.

Suggested Citation

  • Liu, Jian & Liu, Tingzhan, 2010. "Detecting community structure in complex networks using simulated annealing with k-means algorithms," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(11), pages 2300-2309.
    • Handle: RePEc:eee:phsmap:v:389:y:2010:i:11:p:2300-2309
    DOI: 10.1016/j.physa.2010.01.042
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037843711000097X
    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.2010.01.042?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. Zhang, Junhua & Zhang, Shihua & Zhang, Xiang-Sun, 2008. "Detecting community structure in complex networks based on a measure of information discrepancy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(7), pages 1675-1682.
    2. Barabási, A.L & Jeong, H & Néda, Z & Ravasz, E & Schubert, A & Vicsek, T, 2002. "Evolution of the social network of scientific collaborations," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 311(3), pages 590-614.
    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. 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.
    2. Shang, Ronghua & Luo, Shuang & Zhang, Weitong & Stolkin, Rustam & Jiao, Licheng, 2016. "A multiobjective evolutionary algorithm to find community structures based on affinity propagation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 453(C), pages 203-227.
    3. Laassem, Brahim & Idarrou, Ali & Boujlaleb, Loubna & Iggane, M’bark, 2022. "Label propagation algorithm for community detection based on Coulomb’s law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 593(C).
    4. Zhang, Weitong & Zhang, Rui & Shang, Ronghua & Li, Juanfei & Jiao, Licheng, 2019. "Application of natural computation inspired method in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 130-150.
    5. 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.
    6. Chen, Ling-Jiao & Zhang, Zi-Ke & Liu, Jin-Hu & Gao, Jian & Zhou, Tao, 2017. "A vertex similarity index for better personalized recommendation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 607-615.
    7. Zhou, Kuang & Martin, Arnaud & Pan, Quan, 2015. "A similarity-based community detection method with multiple prototype representation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 438(C), pages 519-531.
    8. 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.
    9. Xiang, Ju & Hu, Tao & Zhang, Yan & Hu, Ke & Li, Jian-Ming & Xu, Xiao-Ke & Liu, Cui-Cui & Chen, Shi, 2016. "Local modularity for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 451-459.
    10. Wu, Tao & Chen, Leiting & Zhong, Linfeng & Xian, Xingping, 2017. "Predicting the evolution of complex networks via similarity dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 465(C), pages 662-672.
    11. Dabaghi Zarandi, Fataneh & Kuchaki Rafsanjani, Marjan, 2018. "Community detection in complex networks using structural similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 882-891.
    12. Gao, Jian & Zhou, Tao, 2017. "Evaluating user reputation in online rating systems via an iterative group-based ranking method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 473(C), pages 546-560.
    13. Zhao, Zi-Juan & Guo, Qiang & Yu, Kai & Liu, Jian-Guo, 2020. "Identifying influential nodes for the networks with community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 551(C).
    14. Ai, Jun & Cai, Yifang & Su, Zhan & Zhang, Kuan & Peng, Dunlu & Chen, Qingkui, 2022. "Predicting user-item links in recommender systems based on similarity-network resource allocation," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    15. 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.
    16. Zhu, Junfang & Ren, Xuezao & Ma, Peijie & Gao, Kun & Wang, Bing-Hong & Zhou, Tao, 2022. "Detecting network communities via greedy expanding based on local superiority index," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 603(C).
    17. Leila M Naeni & Hugh Craig & Regina Berretta & Pablo Moscato, 2016. "A Novel Clustering Methodology Based on Modularity Optimisation for Detecting Authorship Affinities in Shakespearean Era Plays," PLOS ONE, Public Library of Science, vol. 11(8), pages 1-27, August.

    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. Lemarchand, Guillermo A., 2012. "The long-term dynamics of co-authorship scientific networks: Iberoamerican countries (1973–2010)," Research Policy, Elsevier, vol. 41(2), pages 291-305.
    2. Ann Bostrom & Ragnar E. Löfstedt, 2003. "Communicating Risk: Wireless and Hardwired," Risk Analysis, John Wiley & Sons, vol. 23(2), pages 241-248, April.
    3. Lilian Cervo Cabrera & Carlos Eduardo Caldarelli & Marcia Regina Gabardo Camara, 2020. "Mapping collaboration in international coffee certification research," Scientometrics, Springer;Akadémiai Kiadó, vol. 124(3), pages 2597-2618, September.
    4. de Oliveira, Thaiane Moreira & de Albuquerque, Sofia & Toth, Janderson Pereira & Bello, Debora Zava, 2018. "International cooperation networks of the BRICS bloc," SocArXiv b6x43, Center for Open Science.
    5. Peng Liu & Haoxiang Xia, 2015. "Structure and evolution of co-authorship network in an interdisciplinary research field," Scientometrics, Springer;Akadémiai Kiadó, vol. 103(1), pages 101-134, April.
    6. Elias Carroni & Paolo Pin & Simone Righi, 2020. "Bring a Friend! Privately or Publicly?," Management Science, INFORMS, vol. 66(5), pages 2269-2290, May.
    7. Kim, Jinseok & Diesner, Jana, 2015. "The effect of data pre-processing on understanding the evolution of collaboration networks," Journal of Informetrics, Elsevier, vol. 9(1), pages 226-236.
    8. Andreas Spitz & Emőke-Ágnes Horvát, 2014. "Measuring Long-Term Impact Based on Network Centrality: Unraveling Cinematic Citations," PLOS ONE, Public Library of Science, vol. 9(10), pages 1-12, October.
    9. Huan Chen & Lixin Tian & Minggang Wang & Zaili Zhen, 2017. "Analysis of the Dynamic Evolutionary Behavior of American Heating Oil Spot and Futures Price Fluctuation Networks," Sustainability, MDPI, vol. 9(4), pages 1-29, April.
    10. Georg Groh & Christoph Fuchs, 2011. "Multi-modal social networks for modeling scientific fields," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(2), pages 569-590, November.
    11. Sameer Kumar & Kuru Ratnavelu, 2016. "Perceptions of Scholars in the Field of Economics on Co-Authorship Associations: Evidence from an International Survey," PLOS ONE, Public Library of Science, vol. 11(6), pages 1-18, June.
    12. Zhengzheng Pan, 2012. "Opinions and Networks: How Do They Effect Each Other," Computational Economics, Springer;Society for Computational Economics, vol. 39(2), pages 157-171, February.
    13. Chakraborty, Tanmoy & Tammana, Vihar & Ganguly, Niloy & Mukherjee, Animesh, 2015. "Understanding and modeling diverse scientific careers of researchers," Journal of Informetrics, Elsevier, vol. 9(1), pages 69-78.
    14. Mark Kibanov & Raphael H. Heiberger & Simone Rödder & Martin Atzmueller & Gerd Stumme, 2019. "Social studies of scholarly life with sensor-based ethnographic observations," Scientometrics, Springer;Akadémiai Kiadó, vol. 119(3), pages 1387-1428, June.
    15. Sameer Kumar & Jariah Mohd. Jan, 2013. "Mapping research collaborations in the business and management field in Malaysia, 1980–2010," Scientometrics, Springer;Akadémiai Kiadó, vol. 97(3), pages 491-517, December.
    16. Greg Morrison & L Mahadevan, 2012. "Discovering Communities through Friendship," PLOS ONE, Public Library of Science, vol. 7(7), pages 1-9, July.
    17. Chris Fields, 2015. "Co-authorship proximity of A. M. Turing Award and John von Neumann Medal winners to the disciplinary boundaries of computer science," Scientometrics, Springer;Akadémiai Kiadó, vol. 104(3), pages 809-825, September.
    18. Behfar, Stefan Kambiz & Turkina, Ekaterina & Cohendet, Patrick & Burger-Helmchen, Thierry, 2016. "Directed networks’ different link formation mechanisms causing degree distribution distinction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 462(C), pages 479-491.
    19. Jiancheng Guan & Lanxin Pang, 2018. "Bidirectional relationship between network position and knowledge creation in Scientometrics," Scientometrics, Springer;Akadémiai Kiadó, vol. 115(1), pages 201-222, April.
    20. Abrar Chaudhury, 2020. "Role of Intermediaries in Shaping Climate Finance in Developing Countries—Lessons from the Green Climate Fund," Sustainability, MDPI, vol. 12(14), pages 1-17, July.

    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:389:y:2010:i:11:p:2300-2309. 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.