IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v12y2024i15p2374-d1446203.html
   My bibliography  Save this article

New Random Walk Algorithm Based on Different Seed Nodes for Community Detection

Author

Listed:
  • Jiansheng Cai

    (School of Mathematics and Statistics, Weifang University, Dongfeng East Street, Weifang 261061, China
    These authors contributed equally to this work.)

  • Wencong Li

    (School of Mathematical Sciences, Ocean University of China, Songling Road, Qingdao 266100, China
    These authors contributed equally to this work.)

  • Xiaodong Zhang

    (School of Mathematical Sciences, MOE-LSC, SHL-MAC, Shanghai Jiao Tong University, Dongchuan Road, Shanghai 200240, China)

  • Jihui Wang

    (School of Mathematical Sciences, University of Jinan, West Nanxinzhuang Road, Jinan 250022, China)

Abstract

A complex network is an abstract modeling of complex systems in the real world, which plays an important role in analyzing the function of complex systems. Community detection is an important tool for analyzing network structure. In this paper, we propose a new community detection algorithm (RWBS) based on different seed nodes which aims to understand the community structure of the network, which provides a new idea for the allocation of resources in the network. RWBS provides a new centrality metric ( M C ) to calculate node importance, which calculates the ranking of nodes as seed nodes. Furthermore, two algorithms are proposed for determining seed nodes on networks with and without ground truth, respectively. We set the number of steps for the random walk to six according to the six degrees of separation theory to reduce the running time of the algorithm. Since some traditional community detection algorithms may detect smaller communities, e.g., two nodes become one community, this may make the resource allocation unreasonable. Therefore, modularity ( Q ) is chosen as the optimization function to combine communities, which can improve the quality of detected communities. Final experimental results on real-world and synthetic networks show that the RWBS algorithm can effectively detect communities.

Suggested Citation

  • Jiansheng Cai & Wencong Li & Xiaodong Zhang & Jihui Wang, 2024. "New Random Walk Algorithm Based on Different Seed Nodes for Community Detection," Mathematics, MDPI, vol. 12(15), pages 1-21, July.
    • Handle: RePEc:gam:jmathe:v:12:y:2024:i:15:p:2374-:d:1446203
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/12/15/2374/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/12/15/2374/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Duncan J. Watts & Steven H. Strogatz, 1998. "Collective dynamics of ‘small-world’ networks," Nature, Nature, vol. 393(6684), pages 440-442, June.
    2. 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.
    3. Roger Guimerà & Luís A. Nunes Amaral, 2005. "Functional cartography of complex metabolic networks," Nature, Nature, vol. 433(7028), pages 895-900, February.
    4. Fang, Wenyi & Wang, Xin & Liu, Longzhao & Wu, Zhaole & Tang, Shaoting & Zheng, Zhiming, 2022. "Community detection through vector-label propagation algorithms," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    5. Jiao, Qing-Ju & Huang, Yan & Shen, Hong-Bin, 2015. "Community mining with new node similarity by incorporating both global and local topological knowledge in a constrained random walk," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 424(C), pages 363-371.
    Full references (including those not matched with items on IDEAS)

    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. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    2. Milena Oehlers & Benjamin Fabian, 2021. "Graph Metrics for Network Robustness—A Survey," Mathematics, MDPI, vol. 9(8), pages 1-48, April.
    3. Samrachana Adhikari & Beau Dabbs, 2018. "Social Network Analysis in R: A Software Review," Journal of Educational and Behavioral Statistics, , vol. 43(2), pages 225-253, April.
    4. Wang, Xiaojie & Slamu, Wushour & Guo, Wenqiang & Wang, Sixiu & Ren, Yan, 2022. "A novel semi local measure of identifying influential nodes in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    5. Lin, Dan & Wu, Jiajing & Xuan, Qi & Tse, Chi K., 2022. "Ethereum transaction tracking: Inferring evolution of transaction networks via link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 600(C).
    6. Ferreira, D.S.R. & Ribeiro, J. & Oliveira, P.S.L. & Pimenta, A.R. & Freitas, R.P. & Dutra, R.S. & Papa, A.R.R. & Mendes, J.F.F., 2022. "Spatiotemporal analysis of earthquake occurrence in synthetic and worldwide data," Chaos, Solitons & Fractals, Elsevier, vol. 165(P2).
    7. Qinghu Liao & Wenwen Dong & Boxin Zhao, 2023. "A New Strategy to Solve “the Tragedy of the Commons” in Sustainable Grassland Ecological Compensation: Experience from Inner Mongolia, China," Sustainability, MDPI, vol. 15(12), pages 1-24, June.
    8. Jianhua Hou, 2017. "Exploration into the evolution and historical roots of citation analysis by referenced publication year spectroscopy," Scientometrics, Springer;Akadémiai Kiadó, vol. 110(3), pages 1437-1452, March.
    9. Perc, Matjaž, 2010. "Zipf’s law and log-normal distributions in measures of scientific output across fields and institutions: 40 years of Slovenia’s research as an example," Journal of Informetrics, Elsevier, vol. 4(3), pages 358-364.
    10. Ding, Waverly & Choi, Emily, 2008. "Divergent Paths or Stepping Stones: A Comparison of Scientists’ Advising and Founding Activities," Institute for Research on Labor and Employment, Working Paper Series qt4907j25p, Institute of Industrial Relations, UC Berkeley.
    11. He, Xuan & Zhao, Hai & Cai, Wei & Liu, Zheng & Si, Shuai-Zong, 2014. "Earthquake networks based on space–time influence domain," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 407(C), pages 175-184.
    12. Jianhong Chen & Hongcai Ma & Shan Yang, 2023. "SEIOR Rumor Propagation Model Considering Hesitating Mechanism and Different Rumor-Refuting Ways in Complex Networks," Mathematics, MDPI, vol. 11(2), pages 1-22, January.
    13. Daniel Reisinger & Fabian Tschofenig & Raven Adam & Marie Lisa Kogler & Manfred Füllsack & Fabian Veider & Georg Jäger, 2024. "Patterns of stability in complex contagions," Journal of Computational Social Science, Springer, vol. 7(2), pages 1895-1911, October.
    14. Martins, Francisco Leonardo Bezerra & do Nascimento, José Cláudio, 2022. "Power law dynamics in genealogical graphs," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 596(C).
    15. Gregory Gutin & Tomohiro Hirano & Sung-Ha Hwang & Philip R. Neary & Alexis Akira Toda, 2021. "The effect of social distancing on the reach of an epidemic in social networks," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 16(3), pages 629-647, July.
    16. Jie, Ke-Wei & Liu, San-Yang & Sun, Xiao-Jun & Xu, Yun-Cheng, 2023. "A dynamic ripple-spreading algorithm for solving mean–variance of shortest path model in uncertain random networks," Chaos, Solitons & Fractals, Elsevier, vol. 167(C).
    17. Yu Gong & Xiaojiang Xu & Changping Zhao & Tobias Schoenherr, 2024. "Multi-Tier Supply Chain Learning Networks: A Simulation Study Based on the Experience-Weighted Attraction (EWA) Model," Sustainability, MDPI, vol. 16(10), pages 1-25, May.
    18. Weimao Ke, 2013. "A fitness model for scholarly impact analysis," Scientometrics, Springer;Akadémiai Kiadó, vol. 94(3), pages 981-998, March.
    19. Divakaruni, Anantha & Zimmerman, Peter, 2023. "The Lightning Network: Turning Bitcoin into money," Finance Research Letters, Elsevier, vol. 52(C).
    20. Li, Wei & Huang, Ce & Wang, Miao & Chen, Xi, 2017. "Stepping community detection algorithm based on label propagation and similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 472(C), pages 145-155.

    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:gam:jmathe:v:12:y:2024:i:15:p:2374-:d:1446203. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.