LLMs Between the Nodes: Community Discovery Beyond Vectors

Ekta Gujral and Apurva Sinha · 2025

Read LLMs Between the Nodes: Community Discovery Beyond Vectors by Ekta Gujral and Apurva Sinha (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-2507-22955.txt.

Introduction

Ekta Gujral and Apurva Sinha test large language models as community finders in social networks, in this 2025 paper. Group detection helps reveal how influence and information spread online. Classic methods use graph structure alone. The authors instead pair a language model with graph-aware prompts, in a two-step framework they call CommLLM.

They tested the approach on six real social network datasets, scoring how well the found groups matched known ones. Language models, especially with careful prompts and graph context, did well on small and medium graphs. The study argues that words and structure together beat structure alone, while noting that the setup must be tuned to each graph.

Catalog record

CREATOREkta Gujral and Apurva Sinha
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22955

Browse the full library · About the Tower of Babel

Full text

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

LLMs Between the Nodes: Community Discovery Beyond Vectors Ekta Gujral and Apurva Sinha Abstract Community detection in social network graphs plays a vital role in uncovering group dynamics, influence pathways, and the spread of information. Traditional methods focus primarily on graph structural properties, but recent advancements in Large Language Models (LLMs) open up new avenues for integrating semantic and contextual information into this task. In this paper, we present a detailed investigation into how various LLM-based approaches perform in identifying communities within social graphs. We introduce a two-step framework called CommLLM , which leverages the GPT-4o model along with prompt-based reasoning to fuse language model outputs with graph structure. Evaluations are conducted on six real-world social network datasets, measuring performance using key metrics such as Normalized Mutual Information (NMI), Adjusted Rand Index (ARI), Variation of Information (VOI), and cluster purity. Our findings reveal that LLMs, particularly when guided by graph-aware strategies, can be successfully applied to community detection tasks in small to medium-sized graphs. We observe that the integration of instruction-tuned models and carefully engineered prompts significantly improves the accuracy and coherence of detected communities. These insights not only highlight the potential of LLMs in graph-based research but also underscore the importance of tailoring model interactions to the specific structure of graph data. 1 Introduction Community detection in social networks is crucial for understanding the underlying structure [ 16 ] and dynamics of complex systems. It helps uncover groups of nodes with dense internal connections, revealing patterns such as shared interests, behaviors, or functions. This technique is widely applied across domains like marketing (to target consumer groups), cyber security (to detect malicious clusters), biology (to identify functional modules in protein networks), and politics (to map ideological communities). As networks [ 15 , 3 ] grow more intricate, traditional methods struggle with scalability and adaptability. Recently, large language models (LLMs) [ 13 , 7 , 33 ] have emerged as powerful tools in this field. Their ability to reason over text and structure enables them to detect nuanced relationships and community patterns in both textual and graph data. LLMs are increasingly being integrated into research workflows, outperforming many classical algorithms in terms of flexibility, interpretability, and cross-domain applicability. Despite their impressive capabilities across a wide range of natural language tasks, existing large language models (LLMs) encounter significant challenges when applied to community detection within social network graphs. One of the primary limitations is their lack of innate access to graph-structured data; LLMs are fundamentally designed to process sequential text rather than inherently parallel or interconnected structures such as graphs [ 6 ] . This sequential bias limits their ability to model complex topological features, such as node centrality, clustering coefficients, and higher-order neighborhood interactions, all of which are critical for accurately identifying communities. Moreover, LLMs do not naturally encode graph-specific inductive biases—such as permutation invariance or localized neighborhood aggregation—which are essential for tasks like node clustering and structural role identification. Their inability to capture hierarchical or multi-scale structures within graphs often results in shallow representations that fail to generalize across diverse network topologies. While techniques such as graph embeddings or hybrid models attempt to bridge this gap, these approaches typically decouple the graph topology from the language modeling process, which can lead to a loss of structural fidelity and semantic nuance. Scalability is another core issue. LLMs, especially those deployed on large-scale or dynamic social networks, suffer from computational inefficiencies and memory bottlenecks. Representing large graphs in a form consumable by LLMs (e.g., through serialization or textual descriptions) becomes increasingly infeasible as network size grows. Additionally, LLMs lack temporal awareness and dynamic reasoning capabilities required to model evolving communities or time-sensitive interactions in dynamic social graphs. Furthermore, most LLMs are trained on general-purpose corpora and lack task-specific fine-tuning for graph mining or community detection tasks [ 32 ] . As a result, they often struggle with domain adaptation, interpretability, and robustness when applied to network analysis. They may also be susceptible to spurious correlations or biases embedded in the training data, which can skew the understanding of social graph dynamics and community boundaries. Lastly, LLMs typically do not incorporate explicit constraints or priors related to graph theory, such as modularity maximization or spectral properties, which are central to many traditional community detection algorithms. Figure 1: Illustration of CommLLM that includes two main steps: graph-to-text conversion and then LLM Reasoning to detect the communities in the graph In contrast, our work introduces a novel approach CommLLM (as shown in Figure 1 ) powered by GPT-4o [ 23 ] that empowers large language models (LLMs) to detect communities more effectively by integrating graph-aware text representations with language-based reasoning. By embedding structural information directly into the input, our method preserves the topology of the network while leveraging the LLM’s capacity for pattern recognition and inference. This hybrid strategy allows the model to understand both the semantic and relational aspects of nodes. It enables nuanced community detection, even in complex or sparsely connected graphs. Additionally, our approach improves interpretability and generalization across different types of networks. Our contributions are summarized as follows: • We propose method CommLLM , which uses GPT-4o to detect communities in social network graphs. It includes two main steps: graph-to-text conversion and then prompt engineering to detect the communities in the graph. (See Figure 1 ) • The results on real datasets indicate that CommLLM outperforms the baseline LLM methods in context to community detection. Furthermore, prompt comparison experiments reveal that the designed prompt effectively aids LLMs in understanding the graph communities. • The dataset used and graph-to-text conversion script in this study is publicly available at link 1 1 1 https://drive.google.com/drive/folders/1IKV-Qi_oz0hjAJHqCszLIbwlACmgNWXM for better reproducibility of the research. 2 Literature Review 2.1 Traditional Community detection Community detection in complex networks has garnered significant attention, leading to the development of a wide range of methodologies. Modularity-based approaches, such as the Louvain algorithm [ 5 ] , aim to maximize a modularity score to identify groups of nodes with dense intra-community connections relative to a null model. Spectral clustering techniques utilize the eigenvectors of graph Laplacians to reveal partitions in the network structure [ 20 ] . Label propagation algorithms [ 26 ] iteratively update node labels based on neighbor consensus, offering scalability and simplicity. Statistical inference methods, including the Stochastic Block Model [ 18 ] , model networks probabilistically, often capturing assortative and disassortative structures. Hierarchical clustering builds dendrograms of nodes through agglomerative or divisive strategies, while edge betweenness-based methods [ 10 ] sequentially remove edges with high centrality to expose community boundaries. Random walk-based techniques, such as Walktrap, cluster nodes based on transition probabilities, whereas clique percolation methods identify overlapping communities through adjacent k-cliques. Information-theoretic frameworks like Infomap [ 27 ] aim to compress the description of network flows. More recent approaches include graph embedding techniques (e.g., DeepWalk [ 25 , 2 ] ), which learn low-dimensional node representations for clustering, and deep learning-based models like graph neural networks (GNNs) that jointly learn features and community assignments [ 19 ] . Additionally, matrix factorization methods (e.g., NMF) decompose adjacency matrices to detect latent community structure. Bayesian methods incorporate prior distributions into community inference [ 24 ] , while evolutionary algorithms apply

Read the complete text