Model-based edge clustering for weighted networks with a noise component

Haomin Li, Daniel K. Sewell · 2025

Read Model-based edge clustering for weighted networks with a noise component by Haomin Li, Daniel K. Sewell (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06822.txt.

Introduction

Haomin Li and Daniel Sewell cluster the edges of weighted networks while letting the model throw out noise edges. Their 2025 paper answers two blind spots in older edge clustering: weights that carry strength are ignored, and junk links blur the true pattern. Arbitrary cutoffs were the usual noise fix.

The new model, WECAN, folds weights into the grouping and adds a noise bucket for stray edges. Data, not a hand-set line, decides which edges count as noise. Simulations and real datasets show clear gains over classic methods. An R package ships with the paper for direct use. The authors pitch the tool for any field where link strength and link junk both matter.

Catalog record

CREATORHaomin Li, Daniel K. Sewell
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06822

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Model-based edge clustering for weighted networks with a noise component Haomin Li, Daniel K. Sewell Abstract Clustering is a fundamental task in network analysis, essential for uncovering hidden structures within complex systems. Edge clustering, which focuses on relationships between nodes rather than the nodes themselves, has gained increased attention in recent years. However, existing edge clustering algorithms often overlook the significance of edge weights, which can represent the strength or capacity of connections, and fail to account for noisy edges—connections that obscure the true structure of the network. To address these challenges, the Weighted Edge Clustering Adjusting for Noise (WECAN) model is introduced. This novel algorithm integrates edge weights into the clustering process and includes a noise component that filters out spurious edges. WECAN offers a data-driven approach to distinguishing between meaningful and noisy edges, avoiding the arbitrary thresholding commonly used in network analysis. Its effectiveness is demonstrated through simulation studies and applications to real-world datasets, showing significant improvements over traditional clustering methods. Additionally, the R package "WECAN" 1 1 1 https://github.com/HaominLi7/WECAN has been developed to facilitate its practical implementation. Journal: Computational Statistics \& Data Analysis 1 Introduction Networks arise as dominant structures in various fields, including epidemiology, sociology, biology, neuroscience, and computer science. In network analysis, entities of interest are depicted as nodes, while the connections between them are typically denoted by edges. These edges can take the form of unordered pairs, indicating undirected relationships, or ordered pairs, signifying directed relationships ( Butts, 2009 ) . One of the pivotal research areas within network analysis is clustering, of which community detection is a special case. Communities in a network are typically characterized by dense groups of nodes, exhibiting dense internal connections while maintaining sparser connections with nodes outside the group, although more broadly clusters of nodes tend to exhibit structural similarities. Network clustering serves as a cornerstone in unraveling the functionality of complex networks ( Khan and Niazi, 2017 ) . As one of the most broadly-studied topics in network science, various algorithms and statistical models have been developed for community detection. Among them, there are algorithmic methods such as the Kernighan-Lin algorithm for graph partitioning ( Kernighan and Lin, 1970 ) , the Girvan Newman (GN) algorithm ( Newman and Girvan, 2004 ) , the spectral clustering algorithm ( Ng et al., 2001 ) ; in addition, many model-based methods exist such as the latent position cluster model ( Handcock et al., 2007 ) , and the stochastic block model ( Nowicki and Snijders, 2001 ) and their many variants. These algorithms have been widely accepted and used in various fields. However, despite advantages in interpretation and intuition in many settings, all of these models focus on grouping nodes into clusters based on similarity, but ignore the potential that lay in edge clustering. The idea of edge-centric clustering is attractive through the following aspects. First, it is common for communities to be built based on the identities of the edges in realistic networks. For example, in a scientific collaboration network, nodes represent researchers and edges represent joint research efforts or co-authorship of papers. In such a network, communities emerge based on research topics, academic disciplines, or shared research interests. Second, membership in multiple organizations is extremely common. Through notions of mixed-membership, node-centric network clustering methods have been developed to address this; yet difficulties remain in interpreting the results, as a node can be divided into multiple proportions, each of which belongs to a distinct community ( Amelio and Pizzuti, 2014 ) . For instance, a person may be a member of multiple interest groups, yet it is counter-intuitive to say that 50\% of that person belongs to a dance club. Clustering on edges overcomes this issue, as edges represent relationships, and in most cases a relationship forms within a single context/cluster. Despite the advantages above, very little work has been devoted to the area of edge clustering when compared with the numerous node-centric clustering algorithms. A few algorithms tried to solve this question by performing standard community detection on the line graph ( Evans and Lambiotte, 2009 ) ; ( Evans and Lambiotte, 2010 ) ; ( Yoshida, 2013 ) ; ( Tian et al., 2023 ) . In recent years, the latent space edge clustering (LSEC) model ( Sewell, 2021 ) was introduced as the first model-based edge community detection algorithm for directed networks. Building on this, the automated latent space edge clustering (aLSEC) model ( Pham and Sewell, 2024 ) was developed, using an overfitted mixture prior to automatically determine the number of clusters. This addresses the limitation of the LSEC model, which requires the number of clusters to be specified in advance. Even though the LSEC model and aLSEC model have been shown to be accurate and computationally efficient, there are two fundamental limitations, described below. The first limitation is that none of these edge clustering algorithms takes edge weights into consideration. Incorporating edge weights into the clustering model is crucial as they quantify the strength of relationships between connected nodes. Strongly weighted edges often signify more substantial interactions, indicative of specific communities or functional modules ( Opsahl and Panzarasa, 2009 ) . While node-centric clustering algorithms, such as weighted stochastic blockmodels ( Aicher et al., 2015 ) , have integrated edge weights to enhance accuracy, edge-centric clustering methods have largely overlooked this factor. In this study, we aim to fill this gap by developing the first model-based edge clustering algorithm tailored for weighted networks. Second, while noise contamination has long been recognized as an important consideration in clustering of traditional data ( Banfield and Raftery, 1993 ) , this has not been addressed in network analysis. Through clustering edges and analyzing their weights, we gain a distinct advantage in identifying “noisy edges”. The notion of a “noisy edge” refers to edges that do not conform to the patterns or structures present in the majority of the edges in the network. For instance, in the email network, while a high-level manager may send regular emails to various teams under her supervision (which may share the same nodes between them), she may send a spurious email to everyone regarding a phishing attempt, or she may simply relay a message on behalf of someone else. The first example email highlights meaningful structure in a communication network, whereas the latter two may only serve to obscure the team structure. In a contact tracing network, this could be contacts caused by pedestrians passing by each other. The presence of noisy edges can sometimes pose challenges in clustering analysis, as they may obscure the underlying structure of the network, lead to over- or underestimation of the number of clusters, or lead to misinterpretations of the clusters. Therefore, it is essential to account for noisy edges and handle them appropriately in clustering algorithms to ensure accurate and meaningful results. Though such noisy edges widely exist in real-world networks, to the authors’ knowledge, currently no algorithms have been proposed to identify them in networks. In this paper, we propose the Weighted Edge Clustering Adjusting for Noise (WECAN) model to address these two methodological research gaps by clustering weighted directed edges and identifying the noisy edges. The WECAN model automatically selects the number

Read the complete text