Source-linked AI summary
An Evolutionary Algorithm Approach to Link Prediction in Dynamic Social Networks
Catherine A. Bliss, Morgan R. Frank, Christopher M. Danforth, Peter Sheridan Dodds
TL;DR
The paper tackles short-term link prediction in evolving networks, where identifying localized future connections is important but large networks make many approaches costly. It uses CMA-ES to optimize a linear combination of sixteen neighborhood and node-similarity indices, and reports strong Twitter reciprocal-reply-network performance, including roughly 10^4 improvement over random selection for the top 20 links.
Problem
The problem is predicting localized future links in large evolving networks, where existing approaches face computational constraints and model interpretations may offer limited insight into network evolution.
Method
The method applies CMA-ES to optimize coefficients in a linear model combining neighborhood similarity measures and node-specific data, with fitness evaluated at multiple top-N scales.
Results
10^4 improvement over random link selection was achieved for the top 20 or fewer predicted links, with 10^3 improvement across several orders of magnitude for top-N predictions.
Takeaways & Limitations
The transparent predictor identifies useful indices and suggests possible mechanisms associated with the evolution of Twitter reciprocal reply networks.
Takeaways & Limitations
The study cautions that its linear model structure may be suboptimal, and comparisons with industry-standard methods are limited by unbalanced classes.
Abstract
from arXiv · showhide
Many real world, complex phenomena have underlying structures of evolving networks where nodes and links are added and removed over time. A central scientific challenge is the description and explanation of network dynamics, with a key test being the prediction of short and long term changes. For the problem of short-term link prediction, existing methods attempt to determine neighborhood metrics that correlate with the appearance of a link in the next observation period. Recent work has suggested that the incorporation of topological features and node attributes can improve link prediction. We provide an approach to predicting future links by applying the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) to optimize weights which are used in a linear combination of sixteen neighborhood and node similarity indices. We examine a large dynamic social network with over $10^6$ nodes (Twitter reciprocal reply networks), both as a test of our general method and as a problem of scientific interest in itself. Our method exhibits fast convergence and high levels of precision for the top twenty predicted links. Based on our findings, we suggest possible factors which may be driving the evolution of Twitter reciprocal reply networks.
1. Introduction
The paper addresses short-term prediction of future links in evolving networks, focusing on localized connections that global growth models do not identify. It combines topological and node-specific information with an evolutionary optimization approach designed for large, dynamic social networks.
- 1. Introduction: Future-link prediction asks which links in a network snapshot G_t are most likely to appear at the next timestep, t + 1.The task targets localized network dynamics rather than only global growth properties.
- 1. Introduction: No single similarity index is consistently best, because effective predictors may depend on network structure and changing endogenous or exogenous factors.This motivates combining multiple measures rather than assuming a universal predictor.
- 1. Introduction: The proposed predictor uses CMA-ES to optimize coefficients in a linear combination of neighborhood similarity measures and node-specific data, avoiding equal-weight assumptions.The approach is intended to converge quickly without parametric thresholds or computational undersampling.
- 1. Introduction: The method includes sixteen interchangeable or augmentable similarity indices and is presented as independent of network type, with measure selection depending on available data and network size.The stated application is Twitter reciprocal reply networks, where links represent reciprocal replies and active engagement.
- 1. Introduction: The method is designed to remain transparent, identifying indices that predict future links and may help elucidate mechanisms associated with network evolution.This addresses concerns that supervised-learning model interpretations may provide little information about evolutionary processes.
2. Methods
The method constructs reciprocal-reply networks from Twitter data, combines sixteen similarity indices, and uses CMA-ES to evolve predictor weights for next-week link prediction. It evaluates candidate predictors across multiple top-N fitness scales and cross-references their highest-scoring pairs.
- Data: 51 million tweets collected from September 9 to December 1, 2008 were used to construct weekly unweighted, undirected reciprocal reply networks.A link exists when two users exchanged reciprocal replies during the week.
- Prediction task: 35% of new links occurred between individuals connected by a path of length 2.
- Similarity indices: The predictor combines sixteen similarity indices spanning local topological measures and four node-specific measures.Node-specific measures include Twitter Id, tweet count, word, and happiness similarity; scores are rescaled to [0, 1] and stored as sparse matrices.
- Evolutionary algorithm: CMA-ES evolves real-valued weights for a linear combination of similarity-index matrices to minimize link-prediction error.The method avoids differentiability and continuity assumptions and uses 100 restarts to reduce the risk of local optima.
- Validation and prediction: Four fitness functions evaluate the top 20, 200, 2000, and 20000 predicted links, testing sensitivity to the validation scale.The final predictions cross-reference the highest-scoring pairs across evolved predictors, with Resource Allocation added when predicting fewer than ten links.
3. Results
The evolved all16 predictor outperformed individual and other combined indices, converging rapidly and achieving strong validation performance. Coefficient rankings also identified similarity measures associated with predicted future links, while missing Twitter data constrained evaluation.
- Predictor performance: The all16 predictor outperformed every individual and combined alternative on training data.It combined all sixteen similarity indices using evolved coefficients.
- Predictor performance: For top N=20 predictions, the all16 predictor most clearly exceeded the twelve-index topological predictor.The same ordering held across the other fitness functions.
- Coefficient interpretation: Adamic-Adar, Common neighbors, Resource Allocation, Happiness, and Twitter Id similarity commonly received the largest positive coefficients, while LHN often received the largest negative coefficient.These rankings came from 100 evolved solutions for Week 7-to-8 prediction.
- Validation performance: F1 peaked around top N≈10^4, while precision-oriented Fβ performance peaked for top-N values on the order of 10^3.The highest Fβ scores occurred for Weeks 10 to 11.
- Missing-data impact: Approximately 40% of tweets were captured, and bootstrapping indicated that missing data produced roughly 10% mislabeled false positives.The authors therefore characterize reported precision and recall as lower bounds.
- Predictor comparisons: The combined predictor usually outperformed isolated indices for most top-N choices, while Resource Allocation was strongest in isolation for selecting the top five links.This comparison motivated inclusion of a Resource Allocation baseline in cross-validation.
4. Discussion
The combined predictor performs strongly for Twitter reciprocal-reply link prediction and can outperform individual indices and some supervised-learning comparisons. Its evolved weights also suggest possible mechanisms underlying network evolution, while class imbalance and the linear-model assumption constrain interpretation.
- Predictor composition: The combined all16 predictor outperforms the topo12 predictor, with the largest difference for top N < 20.This supports combining topological and node-specific similarity indices for reciprocal-reply networks.
- Performance: AUC > 0.7 is reported for all validation weeks, compared with AUC < 0.6 in another Twitter link-prediction study.The comparison concerns Twitter networks with different data-completeness properties.
- Performance: 10^4 factor improvement is achieved over random link selection for the top 20 or fewer predicted links, with 10^3 improvement across several top-N ranges.The predictor is evaluated on Twitter reciprocal-reply networks.
- Comparisons: After standardizing network size, the reported factor improvement is an order of magnitude higher than the approximately 1.5×10^3 improvement reported for mobile-phone call data.The comparison requires rescaling because the networks differ in size.
- Limitations: Interpretation against industry-standard binary decision trees is limited, and unbalanced classes motivate future use of balanced classes in CMA-ES.The authors identify the linear model as another limitation because the optimal combination may not be linear.
- Interpretation: Resource Allocation receives large positive evolved weights, suggesting that users’ time and attention may limit interaction.The index assumes each node distributes its resource equally among neighbors.
- Implications: The method is presented as transparent and transferable, with future extensions including geospatial data, community structure, and link persistence or decay.These extensions are proposed as possible directions for improving link prediction and interpretation.
6. Appendix
The appendix documents the observed-data coverage and weekly reciprocal-reply network statistics, alongside simulations and coefficient rankings for CMA-ES predictors.
- Data coverage: Table A1 records that the database contains only a fraction of Twitter messages during the study period, while total tweet volume grows faster than the observed feed.The appendix uses message identifiers to estimate total monthly messages.
- Network statistics: Table A2 reports weekly network statistics, including users, average degree, assortativity, giant-component measures, maximum degree, and clustering.Average degree and giant-component measures remain fairly constant, while maximum degree varies and clustering slightly decreases.
- CMA-ES simulations: Figure A1 compares mean fitness across 100 CMA-ES simulations for four top-N settings and for individual, all16, topo12, and node4 predictors.The columns correspond to top N=20, 200, 2000, and 20,000.
- Coefficient rankings: Figures A2 and A3 rank evolved coefficient values across 100 CMA-ES runs using the percentage of correctly predicted links among top-N scores.Adamic-Adar is most frequently top-ranked, followed by common neighbors and resource allocation; LHN ranks lowest.