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. 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.
    2. 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.
    3. 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.
    4. Meila, Marina, 2007. "Comparing clusterings--an information based distance," Journal of Multivariate Analysis, Elsevier, vol. 98(5), pages 873-895, May.
    5. Leo Katz, 1953. "A new status index derived from sociometric analysis," Psychometrika, Springer;The Psychometric Society, vol. 18(1), pages 39-43, March.
    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. 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.
    3. 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).
    4. 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).
    5. Lee, Yan-Li & Dong, Qiang & Zhou, Tao, 2021. "Link prediction via controlling the leading eigenvector," Applied Mathematics and Computation, Elsevier, vol. 411(C).
    6. 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).
    7. Karimi, Fatemeh & Lotfi, Shahriar & Izadkhah, Habib, 2021. "Community-guided link prediction in multiplex networks," Journal of Informetrics, Elsevier, vol. 15(4).
    8. 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).
    9. Shenshen Bai & Longjie Li & Jianjun Cheng & Shijin Xu & Xiaoyun Chen, 2018. "Predicting Missing Links Based on a New Triangle Structure," Complexity, Hindawi, vol. 2018, pages 1-11, December.
    10. 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.
    11. 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.
    12. 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.
    13. Zhang, Xue & Wang, Xiaojie & Zhao, Chengli & Yi, Dongyun & Xie, Zheng, 2014. "Degree-corrected stochastic block models and reliability in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 393(C), pages 553-559.
    14. 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.
    15. Zhou, Yinzuo & Wu, Chencheng & Tan, Lulu, 2021. "Biased random walk with restart for link prediction with graph embedding method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 570(C).
    16. 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).
    17. 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.
    18. Zeng, Shan, 2016. "Link prediction based on local information considering preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 443(C), pages 537-542.
    19. Wang, Xiaojie & Zhang, Xue & Zhao, Chengli & Xie, Zheng & Zhang, Shengjun & Yi, Dongyun, 2015. "Predicting link directions using local directed path," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 260-267.
    20. Wenjun Li & Ting Li & Kamal Berahmand, 2023. "An effective link prediction method in multiplex social networks using local random walk towards dependable pathways," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-27, January.

    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.