Network Growth and Link Prediction Through an Empirical Lens

Qingyun Liu
Shiliang Tang
Xinyi Zhang
Xiaohan Zhao
Haitao Zheng
Ben Y. Zhao

Proceedings of the Proceedings of the 16th ACM SIGCOMM Internet Measurement Conference (IMC 2016)

Paper Abstract

Link prediction in dynamic networks is a well studied topic. Yet until recently, validation of algorithms has been hampered by limitations in the size and realism of empirical datasets. In this work, we seek to revisit and reassess the value and accuracy of prediction methods, by leveraging our access to several large, detailed traces of dynamics in online social networks (Facebook, Renren, YouTube). Our goals are to understand the absolute and comparative accuracy of existing prediction algorithms, and to develop techniques to improve them using insights from analysis of network dynamics.

We implement and evaluate 18 link prediction algorithms, labeled as either "metric-based" (those that predict potential links using a single similarity or proximity metric) or "classification-based" (those that use machine learning classifiers with multiple metrics as input features). Despite poor performance in absolute terms, SVM classifiers consistently perform the best across all our traces. Its accuracy is occasionally matched by metric-based algorithms, but never consistently across datasets. Finally, we use observations of network dynamics to build "filters" that dramatically reduce the search space for link candidates. Augmenting current algorithms with our filters dramatically improves prediction accuracy across all traces and algorithms.