CS Paper Radar

Tracking and Predicting Evolution of Social Communities

Mark Goldberg, Malik Magdon-Ismail, Srinivas Nambirajan, James Thompson

cs.SI ·submitted 2026-09-06 16:35 UTC · v1
publishedhighly cited

Abstract

We develop an algorithmic framework for studying the evolution of communities in social networks. We begin with the theoretical foundation, from which we conclude that an evolution is at most as strong as its weakest link. This allows us to formulate an efficient algorithm to identify all evolutionary sequences in a dynamic social network. We use this algorithm to empirically study community evolution in several large social networks, to identify those features of the early stages of a community that indicate whether a community is going to be shortlived or not. Our results show that it is possible to correlate the lifespan of a community to structural parameters of its early evolution; these conclusions are robust across all the social networks we have investigated.

Journal ref
2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing, pp. 780-783. IEEE, 2011
DOI
10.1109/PASSAT/SocialCom.2011.102

Closest papers

Nearest neighbours by meaning across the whole index.

A Novel Information Workflow for Structural Behavioural Analysis in Dynamic Attributed Graphs

cs.SI ·2026-08-27 ·Gatadi Ashwitha, K. Swarupa Rani
similarity 0.65
Abstract · 12 pages, 2 figures

Social systems play a vital role through interactions around shared interests and the maintenance of relationships, which are part of society. These can be represented as networks, and their analysis plays a crucial role in dynamic environments, which can be achieved through link prediction and community detection tasks. Several link prediction approaches estimate new relationships, such as suggesting friends on social media. On the other hand, a social faction is a group of connected people that reveals the internal structure of the social system and can be identified through community detection approaches. The evolution of social systems can be understood using these approaches by analysing their structure and behaviour. To handle this, a combination of these approaches, along with interaction-based analysis, is used to form cohesive communities, thereby enabling the study of social systems dynamically. In addition, attribute information plays a critical role. Most real-world graphs, like Facebook and Twitter, have attribute information that provides context, and integrating them with structural information offers deeper insights into patterns, which is a critical task. However, existing approaches have limitations in handling dynamics of social systems. Additionally, no existing approaches in the literature help identify potential links and form densely connected communities for attributed graphs. To address these challenges, we have proposed an information workflow, i.e., inc-LPCDAG (\underline{inc}remental Link Prediction and Community Detection in Attributed Graphs). We conducted experiments to evaluate efficiency, and results demonstrate the effectiveness of our proposed workflow by analysing and understanding structural and behavioural processes.

0.34

An Information-Theoretic Model for the Evolution of a Social Network

cs.SI ·2026-10-20 ·Johnathan Brink, Lewis Mitchell, Mengbin Ye
similarity 0.62
Abstract

Echo chambers and filter bubbles provide a framework to view communication and connection in a social network age. Such systems are characterised by isolated communities regurgitating information which reinforces prior beliefs. Theoretical analysis of echo chambers is suited for a network science approach to understand the mechanics of information influences between users. Here, we propose an evolutionary network model that extends the Quoter Model, rewiring edges according to cross-entropy between text-generating nodes. Parameters characterise binary reinforcement vs exploration node intents, determining whether a node will seek high or low novelty neighbours, measured by cross-entropy. Through an empirical simulation study, we observe emergent model attributes. Specifically, we compare to a Watts--Strogatz model, highlighting parameter regions of high clustering and hyper-exploration. Further, we identify a quality of disjoint communities akin to rudimentary echo chamber structures. These findings underscore user behaviours that drive echo chamber entrenchment, contextualising future social network analysis.

0.21

Scalable dynamic community detection on temporal graphs using graph neural networks

cs.SI ·2026-08-28 ·Peijie Zhong, Raul Mondragon, Richard G. Clegg
similarity 0.61
Abstract · Submitted to Trans KDD

Dynamic community detection on temporal graphs seeks to identify evolving community structures while allowing node memberships to change over time. In this work, we formulate dynamic community detection over observed node-time instances, where each node-time instance in the temporal interaction stream is assigned a cluster label. We propose a diffusion-guided contrastive learning framework that uses a local temporal diffusion affinity matrix to construct positive and negative node-time pairs and organise the learned representations according to their temporal structural relationships. We then apply a clustering algorithm to the resulting embedding space to detect dynamic communities. Experiments on synthetic temporal networks show that the proposed method outperforms static community detection baselines and achieves competitive or better performance than existing dynamic community detection methods in terms of AMI and ARI, while maintaining good scalability. We further apply the method to a large-scale OpenAlex computer science collaboration network from 2016 to 2025, revealing persistent and evolving collaboration communities in real scientific data. These results suggest that time-node-level representation learning provides an effective framework for scalable dynamic community detection on temporal graphs.

0.25

Inferring the microscopic mechanisms of opinion dynamics using a kinetic Ising model

cs.CY physics.soc-phcond-mat.stat-mechcs.SI ·2026-09-20 ·Ixandra Achitouv, David Chavalarias, Vincent Lahoche
similarity 0.57
Abstract · 12 pages, 6 figures

Kinetic Ising models are widely used to describe binary opinion dynamics, but their microscopic validity has rarely been tested empirically. Here, we infer the transition probabilities governing opinion updates from a year-long online social network and show that they are accurately described by an Ising heat-bath dynamics. The inferred parameters admit a direct sociological interpretation: the external field quantifies intrinsic bias, the coupling strength measures social influence, and a persistence term captures temporal inertia. We further show that persistence is positively correlated with node degree, while both persistence and interaction strength are strongly correlated with global network heterogeneity and clustering. Using the inferred time-dependent parameters in Monte Carlo simulations on the empirical temporal networks, we accurately reproduce the observed response functions, flip probabilities, and macroscopic opinion dynamics. Within the Twitter climate debate, our results provide direct empirical support for a kinetic Ising description of online opinion formation and establish a quantitative link between microscopic social behavior and evolving network topology.

0.10

Scaled Null-Adjusted Persistence: A Multiscale Bridge between Modularity and Persistence

cs.SI math.OC ·2026-08-31 ·Alessandro Avellone, Paolo Bartesaghi, Stefano Benati, Rosanna Grassi
similarity 0.55
Abstract

Community detection methods must balance two competing objectives: identifying small, cohesive groups while avoiding excessive fragmentation. Modularity, the most widely adopted optimization criterion, typically merges small communities in large networks due to its resolution limit. In contrast, a persistence-based criterion promotes more granular partitions. We introduce Scaled Null-Adjusted Persistence (Scaled-NAP), a parametric family of quality functions that incorporates both these criteria. The definition exploits the exact identity between a cluster's modularity contribution and its Null-Adjusted Persistence (NAP) multiplied by its relative volume. Raising this volume factor to a parameter $α\in[0,1]$ yields NAP at $α=0$ and modularity at $α=1$, while intermediate values control the scale of the detected partition. We derive conditions under which merging two communities improves the objective function and characterize the emergence of scale dependence, including resolution-limit behaviour on Caveman graphs. We develop the Milano algorithm, a multilevel Louvain-style heuristic for optimizing Scaled-NAP on large networks. Experiments on weighted and unweighted Lancichinetti-Fortunato-Radicchi benchmarks show that Scaled-NAP achieves the highest or tied-highest recovery wherever the ground truth structure is detectable, with its advantage increasing under community-size heterogeneity. Tests on three real networks with up to 1.1 million nodes confirm its capability to identify fine-grained ground-truth communities. The Milano algorithm also turned out to be the fastest method evaluated on large networks. These results show that Scaled-NAP provides an effective and scalable bridge between modularity-based and persistence-based community detection methodologies.

0.26

Discretization-free exact recovery in geometric community detection

cs.SI math.PR ·2026-08-23 ·Maarten Hoeneveld, Moritz Otto, Raphaël Sala
theory similarity 0.55
Abstract · 30 pages, 2 figures

Geometric community detection seeks to recover latent communities in networks where connectivity depends jointly on community structure and continuous spatial geometry. Existing exact-recovery approaches typically discretize the underlying space, which can impose restrictive structural assumptions on the connectivity functions. We develop a polynomial-time, discretization-free algorithm for exact recovery in the Geometric Hidden Community Model (GHCM), operating directly on the continuous geometry. Our method succeeds even when connectivity functions coincide on a nontrivial portion of their visibility range and when two communities can be distinguished only through their connectivity to a third community. We prove exact recovery under these weaker conditions and provide experiments showing that the algorithm succeeds beyond the theoretically guaranteed regime.

0.23

Ollivier's Ricci Curvature on Complex-weighted Graphs

cs.SI math.MGphysics.soc-ph ·2026-08-10 ·Yu Tian, Eleanor Wiesler, Melanie Weber
similarity 0.54
Abstract · 32 pages, 11 figures

Understanding the geometry of complex networks is critical for effective modeling and analysis across domains. While discrete notions of Ricci curvature have emerged as powerful tools for characterizing both local and global network structure, existing formulations are largely confined to undirected networks with real-valued weights. This limits the use of curvature-based analysis of directional and complex-weighted relations that arise naturally in many applications, from social and biological systems to quantum and signal-processing networks. In this work, we introduce a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case. We establish fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that relate curvature to cycle structure in local neighborhoods. We further develop computational methods for curvature estimation and demonstrate their utility in community detection on directed networks.

0.10

Percolation in the Stochastic Block Model

cs.SI physics.soc-phcond-mat.stat-mechmath.PR ·2026-09-22 ·Luca Pieleanu, Moritz Laber, Narayan G. Sabhahit, Dmitri Krioukov
similarity 0.54
Abstract · 23 pages, 10 figures

The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.

0.19