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

Closed walks for community detection

Author

Listed:
  • Yang, Yang
  • Sun, Peng Gang
  • Hu, Xia
  • Li, Zhou Jun

Abstract

In this paper, we propose a novel measure that integrates both the concept of closed walks and clustering coefficients to replace the edge betweenness in the well-known divisive hierarchical clustering algorithm, the Girvan and Newman method (GN). The edges with the lowest value are removed iteratively until the network is degenerated into isolated nodes. The experimental results on computer generated networks and real-world networks showed that our method makes a better tradeoff of accuracy and runtime. Based on the analysis of the results, we observe that the nontrivial closed walks of order three and four can be considered as the basic elements in constructing community structures. Meanwhile, we discover that those nontrivial closed walks outperform trivial closed walks in the task of analyzing the structure of networks. The double peak structure problem is mentioned in the last part of the article. We find that our proposed method is a novel way to solve the double peak structure problem. Our work can provide us with a new perspective for understanding community structure in complex networks.

Suggested Citation

  • Yang, Yang & Sun, Peng Gang & Hu, Xia & Li, Zhou Jun, 2014. "Closed walks for community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 397(C), pages 129-143.
    • Handle: RePEc:eee:phsmap:v:397:y:2014:i:c:p:129-143
    DOI: 10.1016/j.physa.2013.11.034
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437113011011
    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.2013.11.034?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. Cristopher Moore & M. E. J. Newman, 2000. "Epidemics and Percolation in Small-World Networks," Working Papers 00-01-002, Santa Fe Institute.
    2. Kleczkowski, Adam & Grenfell, Bryan T., 1999. "Mean-field-type equations for spread of epidemics: the ‘small world’ model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 274(1), pages 355-360.
    3. S. Redner, 1998. "How popular is your paper? An empirical study of the citation distribution," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 4(2), pages 131-134, July.
    4. 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.
    5. Chen, Duanbing & Lü, Linyuan & Shang, Ming-Sheng & Zhang, Yi-Cheng & Zhou, Tao, 2012. "Identifying influential nodes in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(4), pages 1777-1787.
    6. Estrada, Ernesto & Rodríguez-Velázquez, Juan A., 2006. "Subgraph centrality and clustering in complex hyper-networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 364(C), pages 581-594.
    7. 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.
    8. H. Jeong & B. Tombor & R. Albert & Z. N. Oltvai & A.-L. Barabási, 2000. "The large-scale organization of metabolic networks," Nature, Nature, vol. 407(6804), pages 651-654, October.
    9. Z.-Z. Zhang & S.-G. Zhou & T. Zou, 2007. "Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 56(3), pages 259-271, 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. Sun, Peng Gang, 2016. "Imbalance problem in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 457(C), pages 364-376.
    2. Ling-Ling Li & Shi-Yu Wen & Ming-Lang Tseng & Anthony S. F. Chiu, 2020. "Photovoltaic array prediction on short-term output power method in Centralized power generation system," Annals of Operations Research, Springer, vol. 290(1), pages 243-263, July.
    3. Nadaï, Alain & Labussière, Olivier & Debourdeau, Ariane & Régnier, Yannick & Cointe, Béatrice & Dobigny, Laure, 2015. "French policy localism: Surfing on ‘Positive Energie Territories’ (Tepos)," Energy Policy, Elsevier, vol. 78(C), pages 281-291.
    4. Curran, Giorel, 2017. "Social licence, corporate social responsibility and coal seam gas: framing the new political dynamics of contestation," Energy Policy, Elsevier, vol. 101(C), pages 427-435.
    5. Ghosh, Sumita, 2021. "Urban agriculture potential of home gardens in residential land uses: A case study of regional City of Dubbo, Australia," Land Use Policy, Elsevier, vol. 109(C).

    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. Fu, Jingcheng & Wu, Jianliang & Liu, Chuanjian & Xu, Jin, 2016. "Leaders in communities of real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 428-441.
    2. Dassisti, M. & Carnimeo, L., 2013. "A small-world methodology of analysis of interchange energy-networks: The European behaviour in the economical crisis," Energy Policy, Elsevier, vol. 63(C), pages 887-899.
    3. Laurie A. Schintler & Aura Reggiani & Rajendra Kulkarni & Peter Nijkamp, 2003. "Scale-Free Phenomena in Communication Networks: A Cross-Atlantic Comparison," ERSA conference papers ersa03p436, European Regional Science Association.
    4. Polovnikov, Kirill & Kazakov, Vlad & Syntulsky, Sergey, 2020. "Core–periphery organization of the cryptocurrency market inferred by the modularity operator," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    5. Guillaume, Jean-Loup & Latapy, Matthieu, 2006. "Bipartite graphs as models of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 371(2), pages 795-813.
    6. Saoud, Bilal & Moussaoui, Abdelouahab, 2018. "A new hierarchical method to find community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 495(C), pages 418-426.
    7. Yao, Xin & Zhang, Chang-shui & Chen, Jin-wen & Li, Yan-da, 2005. "On the formation of degree and cluster-degree correlations in scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 353(C), pages 661-673.
    8. Türker, İlker, 2018. "Generating clustered scale-free networks using Poisson based localization of edges," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 72-85.
    9. Tamás Nepusz & Tamás Vicsek, 2013. "Hierarchical Self-Organization of Non-Cooperating Individuals," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-9, December.
    10. Faxu Li & Hui Xu & Liang Wei & Defang Wang, 2023. "RETRACTED ARTICLE: Identifying vital nodes in hypernetwork based on local centrality," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-13, January.
    11. Laurienti, Paul J. & Joyce, Karen E. & Telesford, Qawi K. & Burdette, Jonathan H. & Hayasaka, Satoru, 2011. "Universal fractal scaling of self-organized networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(20), pages 3608-3613.
    12. Chen, Qinghua & Shi, Dinghua, 2004. "The modeling of scale-free networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 335(1), pages 240-248.
    13. 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.
    14. J. Esquivel-Gómez & R. E. Balderas-Navarro & P. D. Arjona-Villicaña & P. Castillo-Castillo & O. Rico-Trejo & J. Acosta-Elias, 2017. "On the Emergence of Islands in Complex Networks," Complexity, Hindawi, vol. 2017, pages 1-10, January.
    15. Zhang, Zhongzhi & Rong, Lili & Comellas, Francesc, 2006. "High-dimensional random Apollonian networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 364(C), pages 610-618.
    16. Filiposka, Sonja & Juiz, Carlos, 2015. "Community-based complex cloud data center," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 356-372.
    17. P.B., Divya & Lekha, Divya Sindhu & Johnson, T.P. & Balakrishnan, Kannan, 2022. "Vulnerability of link-weighted complex networks in central attacks and fallback strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 590(C).
    18. Wang, Junjie & Zhou, Shuigeng & Guan, Jihong, 2011. "Characteristics of real futures trading networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(2), pages 398-409.
    19. Chen, Shu-Heng & Chang, Chia-Ling & Tseng, Yi-Heng, 2014. "Social networks, social interaction and macroeconomic dynamics: How much could Ernst Ising help DSGE?," Research in International Business and Finance, Elsevier, vol. 30(C), pages 312-335.
    20. Rendón de la Torre, Stephanie & Kalda, Jaan & Kitt, Robert & Engelbrecht, Jüri, 2016. "On the topologic structure of economic complex networks: Empirical evidence from large scale payment network of Estonia," Chaos, Solitons & Fractals, Elsevier, vol. 90(C), pages 18-27.

    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:397:y:2014:i:c:p:129-143. 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.