Link Prediction for Egocentrically Sampled Networks

Abstract

Link prediction in networks is typically accomplished by estimating or ranking the probabilities of edges for all pairs of nodes. In practice, especially for social networks, the data are often collected by egocentric sampling, which means selecting a subset of nodes and recording all of their edges. This sampling mechanism requires different prediction tools than the typical assumption of links missing at random. We propose a new computationally efficient link prediction algorithm for egocentrically sampled networks, estimating the underlying probability matrix by estimating its row space. We empirically evaluate the method on several synthetic and real-world networks and show that it provides accurate predictions for network links. Supplemental materials including the code for experiments are available online.

KEYWORDS:

• Binary data analysis
• Machine learning
• Network modeling

Supplementary Materials

The following are included in the supplementary materials available online.

Appendix (Appendix.pdf): References about empirical studies involving egocentric sampling of networks, proof of Theorem 2.1 and additional simulation results.

Code (Code.zip): Code for experiments of the article. Each subfolder in the file has its own Readme.txt about the files and examples.

Acknowledgments

We would like to thank the Editor, Associate Editor, and the referees for their constructive and helpful feedback.

Disclosure Statement

The authors declare that they have no financial or nonfinancial interests that relate to the research described in this article.

Additional information

Funding

T. Li’s research is supported in part by NSF DMS grant 2015298 and the 3Caverliers Award at the University of Virginia. E. Levina’s research is supported in part by NSF DMS grants 1521551 and 1916222. J. Zhu’s research is supported in part by NSF DMS grant 1407698 and 1821243.