Source-linked AI summary
Tracking and Predicting Evolution of Social Communities
Mark Goldberg, Malik Magdon-Ismail, Srinivas Nambirajan, James Thompson
TL;DR
The paper addresses how to track and predict the evolution and lifespan of communities when communities are observed across successive time steps. It develops an axiomatic framework and efficient algorithms for valid evolutionary chains, evaluates them across four social-network datasets, and finds robust links between early structural features and lifespan.
Problem
Tracking community evolution requires a general framework that can operate on supplied communities despite unresolved computational and conceptual challenges in detecting communities.
Method
The authors use axioms showing that chain strength is determined by its weakest link, then apply dynamic programming to identify valid community-evolution chains and derive early-evolution features.
Results
Across four social networks, detected community evolutions show power-law behavior and greater stability than random communities, while early density, intersection, core size, and size consistently correlate with lifespan.
Takeaways & Limitations
Intense, small, stable communities tend to last longest, and early structural features can predict community lifespan across datasets and detection algorithms.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper presents an axiomatic, algorithmic framework for tracking community evolution from communities detected at successive times, then evaluates evolution and lifespan prediction across four large social networks.
- Community structure and evolution are fundamental to understanding the organization and functionality of large social networks.
- The authors formulate a foundational framework in which an evolution is at most as strong as its weakest link, enabling efficient identification of valid evolutionary sequences.
- Empirical analyses use established community-detection algorithms on DBLP, IMDB, BLOGS, and WIKI social networks.
- Early community size and intensity are identified as predictive properties of ultimate lifespan, with leave-one-out cross-validation used to reduce overfitting.
- The framework tracks community evolutions using only the communities supplied at each time, rather than relying on properties specific to a community-detection method.
II. AXIOMATIC FOUNDATIONS FOR EVOLUTION
The paper defines valid community evolutions as maximal chains whose strength exceeds a threshold, then uses axioms about chain strength to reduce exhaustive search to efficient local extension and dynamic programming.
- At each discretized time step, an evolution is a sequence of communities beginning with a parent community and ending at a later leaf community.
- A chain is accepted as a valid evolution when its oracle-assigned strength exceeds a user-defined threshold, with maximal valid chains as the main target.
- The problem is to determine all valid maximal chains from the sets of communities observed at successive time steps.
- Because brute-force testing may require examining exponentially many chains, the authors focus experimentally on the longest valid chains while seeking algorithms for all valid chains.
- Intuitive axioms characterize chain strength through one-step validity, allowing the full evolution problem to be solved with an efficient dynamic programming algorithm.
A. Chain Strength Axioms
The paper's axioms imply that a chain's strength equals the strength of its weakest consecutive link, reducing valid-evolution detection to one-step transitions. This characterization supports efficient construction of all valid and maximal evolutions.
- Axioms and theorem: The identity, monotonicity, and extension axioms imply that chain strength equals the minimum strength of its consecutive links.Theorem 1 states F(X0, ..., Xk) = min_i=0,...,k−1 F(Xi, Xi+1).
- Validity criterion: Computing valid evolutions therefore requires specifying the oracle only for pairs of communities in consecutive time steps.Long-chain validity follows from the one-step strengths.
- Validity criterion: An evolution is valid if and only if every consecutive pair has strength at least λ.This makes validity a local condition on one-step transitions.
- Evolution graph: The method constructs a weighted multipartite graph whose nodes are communities at each time and whose consecutive-time edges carry transition strengths.Maximal paths in this graph represent maximal valid chains and can be computed efficiently.
B. Detecting Communities
Communities are detected from interaction graphs at each time step, using algorithms that permit overlap. In DBLP, community lifetimes follow a power-law tail with exponent α = −5.98 under LOS clustering.
- Lifetime distribution: α = −5.98 for the tail of DBLP community lifetimes under LOS clustering.The tail exhibits power-law decay.
- Community detection: At each time step, the social-network graph Gt is supplied to a community-detection algorithm to produce the community set Ct.For DBLP, edges represent co-publication and weights reflect co-publication patterns involving additional authors.
- Community detection: The tested detection algorithms are LOS, K-CP, RRW, FOG, and SSDE, and they allow communities to overlap.Overlap is treated as necessary for social-network communities in the experiments.
III. PREDICTION
The prediction task uses the first four communities of an evolution to characterize its early structure. It derives 26 features from community sizes, density, intersections, cores, and hypercore.
- Prediction setup: The first four communities X0 . . . X3 are used to predict the evolution's length.The early sequence supplies the structural measurements used for prediction.
- Structural features: The feature set includes community sizes, density, consecutive intersections, cores, and a four-community hypercore.These quantities capture stability and change across the early evolution.
- Structural features: 26 features are derived to characterize the early evolution of a community.Examples include stability and rate of change.
IV. EXPERIMENTS
Experiments analyze four social-network datasets and find inverse-power-law evolution lengths. The similarity threshold is calibrated against random communities, while feature usefulness is assessed by repeated significance.
- Datasets: Four datasets—DBLP, IMDB, BLOG, and WIKI—are used to construct communities over disjoint time intervals and find evolutions.The datasets cover academic coauthorship, movie co-stars, blog interactions, and Wikipedia edits.
- Evolution lengths: Evolution-length distributions follow an inverse power law across the four datasets.The distribution is illustrated in Figure 1.
- Threshold selection: λ = 0.25 is selected because most random evolutions then have lifespans of at most 3.Higher λ can split true evolutions, whereas lower λ can accept meaningless ones.
- Feature analysis: Features are reported as useful for prediction when they are significant more than 40% of the time.This frequency is used to identify the most useful predictive features.
V. CONCLUSION
The framework finds that detected community evolutions exhibit power-law behavior absent from random communities and that detected communities are more stable. Early structural features consistently predict lifespan: density, intersection, and core size correlate positively, while size correlates negatively.
- Detected community evolutions display power-law behavior that is absent from random communities.This indicates that the detected communities are non-random.
- Detected communities are more stable than random communities, as measured by average lifespan.
- Density, intersection, and core size show strong positive correlations with lifespan, whereas size shows a strong negative correlation.These features were consistent across different datasets and community detection algorithms.
- Intense, small, stable communities last longest.