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

Network Refinement: Denoising complex networks for better community detection

Author

Listed:
  • Yu, Jiating
  • Leng, Jiacheng
  • Sun, Duanchen
  • Wu, Ling-Yun

Abstract

Network models are widely used in many fields for their powerful ability to provide a vivid representation of relationships between variables. Modeling entity relationships as networks can be affected by many factors, such as experimental noise and missing data, making the network structure unclear, which inherently hampers the effectiveness of network-based downstream analyses, especially community detection. Consequently, it is necessary to denoise networks before analyzing networks. However, the significance of the network pre-processing step for downstream analysis has been neglected in most current studies of community detection. On the other hand, existing researches on network denoising are very limited and lack adaptability studies. Specialized denoising methods for improving community detection accuracy are not yet available. In this study, we highlighted the necessity of using network denoising as a pre-processing step to improve the performance of community detection. We proposed a novel network denoising method, called Network Refinement (NR), which used a global diffusion process defined by random walk on graph to enhance the self-organization properties of complex networks. NR took a noisy network as input and output a denoised network with clearer community structure by adjusting the edge weights. We have proved that NR can be understood as a degree normalized version of the Katz index, which renders paths with higher intermediate node degrees less important because their information is dispersed through more adjacent edges. We have showed through sufficient numerical experiments that NR significantly improves the clarity of the network’s mesoscale structure, and NR can be applied as a pre-processing step to substantially boost the performance of various community detection algorithms on both simulated networks and real-world networks.

Suggested Citation

  • Yu, Jiating & Leng, Jiacheng & Sun, Duanchen & Wu, Ling-Yun, 2023. "Network Refinement: Denoising complex networks for better community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 617(C).
  • Handle: RePEc:eee:phsmap:v:617:y:2023:i:c:s0378437123002364
    DOI: 10.1016/j.physa.2023.128681
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437123002364
    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.2023.128681?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. Bo Wang & Armin Pourshafeie & Marinka Zitnik & Junjie Zhu & Carlos D. Bustamante & Serafim Batzoglou & Jure Leskovec, 2018. "Network enhancement as a general method to denoise weighted biological networks," Nature Communications, Nature, vol. 9(1), pages 1-8, December.
    2. Meila, Marina, 2007. "Comparing clusterings--an information based distance," Journal of Multivariate Analysis, Elsevier, vol. 98(5), pages 873-895, May.
    3. István A. Kovács & Katja Luck & Kerstin Spirohn & Yang Wang & Carl Pollis & Sadie Schlabach & Wenting Bian & Dae-Kyum Kim & Nishka Kishore & Tong Hao & Michael A. Calderwood & Marc Vidal & Albert-Lász, 2019. "Network-based prediction of protein interactions," Nature Communications, Nature, vol. 10(1), pages 1-8, December.
    4. Leo Katz, 1953. "A new status index derived from sociometric analysis," Psychometrika, Springer;The Psychometric Society, vol. 18(1), pages 39-43, March.
    5. Tao Zhou & Linyuan Lü & Yi-Cheng Zhang, 2009. "Predicting missing links via local information," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 71(4), pages 623-630, October.
    6. Jia Wang & Zhiping Wang & Ping Yu & Peiwen Wang, 2022. "The SEIR Dynamic Evolutionary Model with Markov Chains in Hyper Networks," Sustainability, MDPI, vol. 14(20), pages 1-16, October.
    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. Lee, Yan-Li & Zhou, Tao, 2021. "Collaborative filtering approach to link prediction," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 578(C).
    2. Yu, Jiating & Wu, Ling-Yun, 2022. "Multiple Order Local Information model for link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 600(C).
    3. Aziz, Furqan & Gul, Haji & Muhammad, Ishtiaq & Uddin, Irfan, 2020. "Link prediction using node information on local paths," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 557(C).
    4. Ziqi Gao & Chenran Jiang & Jiawen Zhang & Xiaosen Jiang & Lanqing Li & Peilin Zhao & Huanming Yang & Yong Huang & Jia Li, 2023. "Hierarchical graph learning for protein–protein interaction," Nature Communications, Nature, vol. 14(1), pages 1-12, December.
    5. Zhou, Tao & Lee, Yan-Li & Wang, Guannan, 2021. "Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 564(C).
    6. Lee, Yan-Li & Dong, Qiang & Zhou, Tao, 2021. "Link prediction via controlling the leading eigenvector," Applied Mathematics and Computation, Elsevier, vol. 411(C).
    7. 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).
    8. Wang, Zuxi & Wu, Yao & Li, Qingguang & Jin, Fengdong & Xiong, Wei, 2016. "Link prediction based on hyperbolic mapping with community structure for complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 609-623.
    9. Moradabadi, Behnaz & Meybodi, Mohammad Reza, 2016. "Link prediction based on temporal similarity metrics using continuous action set learning automata," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 361-373.
    10. Kai Yang & Yuan Liu & Zijuan Zhao & Xingxing Zhou & Peijin Ding, 2023. "Graph attention network via node similarity for link prediction," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 96(3), pages 1-10, March.
    11. Mungo, Luca & Lafond, François & Astudillo-Estévez, Pablo & Farmer, J. Doyne, 2023. "Reconstructing production networks using machine learning," Journal of Economic Dynamics and Control, Elsevier, vol. 148(C).
    12. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    13. Charikhi, Mourad, 2024. "Association of the PageRank algorithm with similarity-based methods for link prediction in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 637(C).
    14. Bütün, Ertan & Kaya, Mehmet, 2019. "A pattern based supervised link prediction in directed complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 1136-1145.
    15. Joon Hyung Cho & Jungpyo Lee & So Young Sohn, 2021. "Predicting future technological convergence patterns based on machine learning using link prediction," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(7), pages 5413-5429, July.
    16. Xiaoji Wan & Fen Chen & Hailin Li & Weibin Lin, 2022. "Potentially Related Commodity Discovery Based on Link Prediction," Mathematics, MDPI, vol. 10(19), pages 1-27, October.
    17. Nazim Choudhury & Shahadat Uddin, 2016. "Time-aware link prediction to explore network effects on temporal knowledge evolution," Scientometrics, Springer;Akadémiai Kiadó, vol. 108(2), pages 745-776, August.
    18. Víctor Martínez & Fernando Berzal & Juan-Carlos Cubero, 2019. "NOESIS: A Framework for Complex Network Data Analysis," Complexity, Hindawi, vol. 2019, pages 1-14, October.
    19. Xing Li & Qingsong Li & Wei Wei & Zhiming Zheng, 2022. "Convolution Based Graph Representation Learning from the Perspective of High Order Node Similarities," Mathematics, MDPI, vol. 10(23), pages 1-13, December.
    20. Najari, Shaghayegh & Salehi, Mostafa & Ranjbar, Vahid & Jalili, Mahdi, 2019. "Link prediction in multiplex networks based on interlayer similarity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).

    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:617:y:2023:i:c:s0378437123002364. 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.