An Evolutionary Algorithm Approach to Link Prediction in Dynamic Social Networks
arXiv:1304.6257 · doi:10.1016/j.jocs.2014.01.003
Abstract
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 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.
arXiv comment17 pages, 12 figures, 4 tables, Submitted to the Journal of Computational Science
References in corpus (14)
- Fast unfolding of communities in large networks
- Twitter mood predicts the stock market
- Hierarchical organization of modularity in metabolic networks
- Link Prediction in Complex Networks: A Survey
- Evolution of the social network of scientific collaborations
- Clustering and preferential attachment in growing networks
- Predicting Missing Links via Local Information
- Temporal patterns of happiness and information in a global social network: Hedonometrics and Twitter
- Validation of Dunbar's number in Twitter conversations
- Happiness and the Patterns of Life: A Study of Geolocated Tweets
- Supervised Random Walks: Predicting and Recommending Links in Social Networks
- On the Interplay between Social and Topical Structure
- The Directed Closure Process in Hybrid Social-Information Networks, with an Analysis of Link Formation on Twitter
- Shadow networks: Discovering hidden nodes with models of information flow
Cited by in corpus (19)
- Progresses and Challenges in Link Prediction
- Estimation of global network statistics from incomplete data
- Prediction of scientific collaborations through multiplex interaction networks
- Link prediction in multiplex networks via triadic closure
- Mining and Forecasting Career Trajectories of Music Artists
- Bayesian Fused Lasso regression for dynamic binary networks
- Local degree blocking model for link prediction in complex networks
- A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
- Evolving Twitter: an experimental analysis of graph properties of the social graph
- Simulation and Augmentation of Social Networks for Building Deep Learning Models
- More than Meets the Tie: Examining the Role of Interpersonal Relationships in Social Networks
- Shadow networks: Discovering hidden nodes with models of information flow
- Automatic Discovery of Families of Network Generative Processes
- RankMerging: A supervised learning-to-rank framework to predict links in large social network
- Investigating Competition in Financial Markets: A Sparse Autologistic Model for Dynamic Network Data
- Mining Unfollow Behavior in Large-Scale Online Social Networks via Spatial-Temporal Interaction
- Into the Battlefield: Quantifying and Modeling Intra-community Conflicts in Online Discussion
- Heuristics for Link Prediction in Multiplex Networks
- Predicting links in ego-networks using temporal information