The Role of Community Detection Methods in Performance Variations of Graph Mining Tasks
Shrabani Ghosh [0000-0002-6084-4964], Erik Saule [0000-0003-1634-9234] · 2025
Read The Role of Community Detection Methods in Performance Variations of Graph Mining Tasks by Shrabani Ghosh [0000-0002-6084-4964], Erik Saule [0000-0003-1634-9234] (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-2509-09045.txt.
Introduction
Shrabani Ghosh and 1 co-author test how the choice of community finder shapes graph mining results in a 2025 paper. Large graphs show links in complex systems, and communities are tight clusters in them. Traits drawn from communities can boost tasks like link prediction and node class calls.
True communities are rarely known, and no one finder wins on all tasks. A frame lets many finders plug in so their downstream effects can be compared in a fair way. Some finders clearly suit some tasks more than others. Choice thus moves results a lot, yet users often pick with no such test. The pair urge a deliberate match of finder to task.
Catalog record
| CREATOR | Shrabani Ghosh [0000-0002-6084-4964], Erik Saule [0000-0003-1634-9234] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-09045
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Role of Community Detection Methods in Performance Variations of Graph Mining Tasks Shrabani Ghosh [0000-0002-6084-4964], Erik Saule [0000-0003-1634-9234] Abstract In real-world scenarios, large graphs represent relationships among entities in complex systems. Mining these large graphs—often containing millions of nodes and edges—helps uncover structural patterns and meaningful insights. Dividing a large graph into smaller subgraphs facilitates complex system analysis by revealing local information. Community detection extracts clusters or communities of graphs based on statistical methods and machine learning models using various optimization techniques. Structure-based community detection methods are more suitable for applying on graphs because they do not rely heavily on rich node or edge attribute information. The features derived from these communities can improve downstream graph mining tasks, such as link prediction and node classification. In real-world applications, we often lack ground-truth community information. Additionally, there is neither a universally accepted “gold standard” for community detection nor a single method that is consistently optimal across diverse applications. In many cases, it is unclear how practitioners select community detection methods, and choices are often made without explicitly considering their potential impact on downstream tasks. In this study, we investigate whether the choice of community detection algorithm significantly influences the performance of downstream applications. We propose a framework capable of integrating various community detection methods to systematically evaluate their effects on downstream task outcomes. Our comparative analysis reveals that specific community detection algorithms yield superior results in certain applications, highlighting that method selection substantially affects performance. † † institute: University of North Carolina Charlotte, Charlotte NC 28223, USA. 1 Introduction Graphs, or networks, are fundamental structures used to model numerous complex systems across a wide range of real-world contexts, from social media networks to biological networks. Graphs represent relationships between entities, with nodes signifying individual entities and edges connecting those related entities. For graph mining, feature extraction is crucial for downstream tasks, which can often be challenging. To address this issue, a large graph is often partitioned into smaller subgraphs, facilitating easier processing and mining. Community detection su2022comprehensive aims to uncover groups of nodes that are more densely connected within the same community than the rest of the graph. Researchers use community detection for downstream tasks such as node classification and link prediction han2023link . In real-world applications, labeled datasets are often rare; by employing graph features, nodes/edges can be automatically classified using community features bhagat2011node . In node classification, unlabeled nodes are classified using community features. In link prediction, predicting relationships that do not exist but could be created in the future can be assessed using community features zhang2018link . Several approaches to community detection have been proposed, and surveys have provided a summary and comparative analysis of these methods rehman2012graph ; su2022comprehensive ; jin2021survey . The wide variety of community detection algorithms available based on various approaches, such as modularity optimization von2007tutorial , spectral von2007tutorial , and graph embedding techniques perozzi2014deepwalk ; cui2020adaptive to extract features from graphs as communities and utilize the features for further graph analysis. Researchers often rely on choosing methods without evaluating how their choice may affect the performance of downstream applications. This oversight can lead to suboptimal results and missed opportunities to maximize effectiveness in real-world scenarios. To evaluate the impact of community detection algorithms on downstream applications, we selected several well-known methods that provides comprehensive coverage of non-overlapping and overlapping approaches. For downstream analysis, we chose representative applications that heavily rely on community structures at the intermediate level of their processes: 1) Recommendation Systems that leverage community propensity information to generate personalized product recommendations based on group interests; 2) Trust Prediction which utilize community structures in social graphs to predict absent or potential link/trust relationships among users; and 3) Anomaly Detection to identify irregularities or abnormal interaction patterns within networks to classify potentially malicious nodes. Our contribution is to systematically explore the relationship between the choice of community detection algorithms and the performance outcomes in applications. We make the following contributions: 1) Investigating whether the choice of community detection methods has an impact on downstream task performance. 2) We introduce a framework capable of integrating and evaluating different community detection algorithms, thus facilitating direct comparisons in downstream applications. 3) We experimentally validate that the selection of community detection algorithms significantly impacts downstream task performance, highlighting that certain methods are inherently more suitable for particular applications and datasets. In this paper, Section 2 discusses community detection methods briefly. Section 3 describes our framework for study the impact of community detection method in downstream tasks. We then study our three use cases: Recommendation (Section 4 ), Trust Prediction (Section 5 ) and Anomaly Detection (Section 6 ). Section 7 presents the conclusion. 2 Community Detection 2.1 Definitions A basic network of n nodes and m edges is defined as G=(V,E) , where V=\{v_{1},v_{2},...,v_{n}\} is the node set and E=\{e_{ij}\} represents the edge set, when there is an edge exists between node v_{i} and v_{j} . A=[a_{ij}] denotes an n\times n dimensional adjacency matrix where a_{ij}=1 , if e_{ij} belongs to E , otherwise, a_{ij}=0 . A degree of a node v denotes by deg(v) . Community detection, sometimes termed partitioning or clustering, is referred to as a community detection method in this paper. 2.1.1 Communities: A community in a graph is a concept intended to denote a subset of nodes that are more densely connected to each other than to the rest of the network. These nodes form tightly-knit groups, where intra-group connections are significantly stronger or more frequent compared to inter-group connections. The nodes in a community often have a regional structure and some common group properties. We define number of communities as k . The set of communities is denoted by C=\{C_{1},C_{2},C_{3},...,C_{k}\} . Communities can be either non-overlapping or overlapping. In non-overlapping communities, nodes belong to only one cluster, whereas in overlapping communities, nodes can belong to multiple communities. The community (or communities) node i belongs to is denoted C(i) . 2.1.2 Quality Functions The community detection algorithms identifies the subgraphs using objective functions. Some algorithms return a few communities, while others return many communities. The detected communities are typically assessed using quality functions, which consider two perspectives: Global Partition Quality measures how well the entire graph is partitioned. A common example is modularity, which quantifies the density of edges inside communities compared to edges between communities. Modularity=\frac{1}{2m}\sum_{(u,v)\in V^{2}}\left[A_{uv}-\left(\frac{deg(u)deg(v)}{2m}\right)X_{uv}\right] (1) The decision variable is defined by X_{uv}\in\{0,1\} which indicates whether the nodes u and v belong to the same cluster ( X_{uv} = 1) or not ( X_{uv} = 0). The modularity score ranges within -1 to 1. A value close to 1 denotes a strong community structure. Local Community Quality measures how cohesive individual communities are, often using metrics such as density or conductance. Density measures the proportion of actual edges present within a community compared to the maximum possible number of edges. The density of a community with n nodes and m internal edges given by: Density=\frac{2m}{n(n-1)} (2) The density value ranges between 0 and 1. There are some other quality functions: the normalized cut that measures the cost of cutting edges between communities while keeping internal connections within communities dhillon2004kernel , Clustering Coefficient assesses the triangular pattern and the connectivity