Link Prediction for Egocentrically Sampled Networks

References

• Ali, M. M., and Dwyer, D. S. (2009), “Estimating Peer Effects in Adolescent Smoking Behavior: A Longitudinal Analysis,” Journal of Adolescent Health, 45, 402–408. DOI: 10.1016/j.jadohealth.2009.02.004.
   PubMed Web of Science ®Google Scholar
• Almquist, Z. W. (2012), “Random Errors in Egocentric Networks,” Social Networks, 34, 493–505. DOI: 10.1016/j.socnet.2012.03.002.
   PubMed Web of Science ®Google Scholar
• Anil, A., Kumar, D., Sharma, S., Singha, R., Sarmah, R., Bhattacharya, N., and Singh, S. R. (2015), “Link Prediction Using Social Network Analysis Over Heterogeneous Terrorist Network,” in 2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity), pp. 267–272. IEEE.
   Google Scholar
• Athreya, A., Tang, M., Park, Y., and Priebe, C. E. (2018), “On Estimation and Inference in Latent Structure Random Graphs,” arXiv preprint arXiv:1806.01401.
   Google Scholar
• Bandiera, O., and Rasul, I. (2006), “Social Networks and Technology Adoption in Northern Mozambique,” The Economic Journal, 116, 869–902.
   Web of Science ®Google Scholar
• Banerjee, A., Chandrasekhar, A. G., Duflo, E., and Jackson, M. O. (2013), “The Diffusion of Microfinance,” Science, 341, 1236498. DOI: 10.1126/science.1236498.
   PubMed Web of Science ®Google Scholar
• Batchelder, W. H., and Romney, A. K. (1988), “Test Theory Without an Answer Key,” Psychometrika, 53, 71–92.
   Web of Science ®Google Scholar
• Breiman, L. (2001), “Random Forests,” Machine Learning, 45, 5–32.
   Web of Science ®Google Scholar
• Butts, C. T. (2003), “Network Inference, Error, and Informant (in) Accuracy: A Bayesian Approach,” Social Networks, 25, 103–140.
   Web of Science ®Google Scholar
• Candès, E. J., and Plan, Y. (2010), “Matrix Completion with Noise,” in Proceedings of the IEEE.
   Google Scholar
• Candès, E. J., and Tao, T. (2010), “The Power of Convex Relaxation: Near-Optimal Matrix Completion,” IEEE Transactions on Information Theory, 56, 2053–2080.
   Web of Science ®Google Scholar
• Chandrasekhar, A., and Lewis, R. (2011), “Econometrics of Sampled Networks,” Unpublished manuscript, MIT.[422].
   Google Scholar
• Chatterjee, S. (2015), “Matrix Estimation by Universal Singular Value Thresholding,” The Annals of Statistics, 43, 177–214.
   Web of Science ®Google Scholar
• Chatterjee, S., and Diaconis, P. (2013), “Estimating and Understanding Exponential Random Graph Models,” The Annals of Statistics, 41, 2428–2461.
   Web of Science ®Google Scholar
• Chen, K., and Lei, J. (2018), “Network Cross-validation for Determining the Number of Communities in Network Data,” Journal of the American Statistical Association, 113, 241–251.
   Web of Science ®Google Scholar
• Chi, E. C., and Li, T. (2019), “Matrix Completion from a Computational Statistics Perspective,” Wiley Interdisciplinary Reviews: Computational Statistics, 11, e1469.
   Google Scholar
• Chung, F., and Lu, L. (2002), “The Average Distances in Random Graphs with Given Expected Degrees,” Proceedings of the National Academy of Sciences, 99, 15879–15882.
   PubMed Web of Science ®Google Scholar
• Cichocki, A., and Amari, S.-i. (2002), Adaptive Blind Signal and Image Processing: Learning Algorithms and Applications, Chichester: Wiley.
   Google Scholar
• Conley, T. G., and Udry, C. R. (2010), “Learning About a New Technology: Pineapple in Ghana,” American Economic Review, 100, 35–69.
   Web of Science ®Google Scholar
• Crane, H., and Dempsey, W. (2018), “Edge Exchangeable Models for Interaction Networks,” Journal of the American Statistical Association, 113, 1311–1326. DOI: 10.1080/01621459.2017.1341413.
   PubMed Web of Science ®Google Scholar
• Davenport, M. A., Plan, Y., Berg, E. V. D., Wootters, M., van den Berg, E., and Wootters, M. (2014), “1-bit Matrix Completion,” Information and Inference, 3, 189–223.
   Google Scholar
• Drineas, P., Kannan, R., and Mahoney, M. (2006), “Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition,” SIAM Journal on Computing, 36, 184–206.
   Web of Science ®Google Scholar
• Drineas, P., Mahoney, M., and Muthukrishnan, S. (2008), “Relative-Error CUR Matrix Decompositions,” SIAM Journal on Matrix Analysis and Applications, 30, 844–881.
   Web of Science ®Google Scholar
• Eldridge, J., Belkin, M., and Wang, Y. (2017), “Unperturbed: Spectral Analysis Beyond Davis-Kahan,” arXiv preprint arXiv:1706.06516.
   Google Scholar
• Fafchamps, M., and Lund, S. (2003), “Risk-Sharing Networks in Rural Philippines,” Journal of Development Economics, 71, 261–287.
   Web of Science ®Google Scholar
• Frank, O., and Strauss, D. (1986), “Markov Graphs,” Journal of the American Statistical Association, 81, 832–842.
   Web of Science ®Google Scholar
• Freeman, L. C. (1982), “Centered Graphs and the Structure of Ego Networks,” Mathematical Social Sciences, 3, 291–304.
   Web of Science ®Google Scholar
• Gao, M., Chen, L., Li, B., and Liu, W. (2018), “A Link Prediction Algorithm based on Low-Rank Matrix Completion,” Applied Intelligence, 48, 4531–4550.
   Web of Science ®Google Scholar
• Ghasemian, A., Hosseinmardi, H., Galstyan, A., Airoldi, E. M., and Clauset, A. (2020), “Stacking Models for Nearly Optimal Link Prediction in Complex Networks,” Proceedings of the National Academy of Sciences, 117, 23393–23400.
   PubMed Web of Science ®Google Scholar
• Golub, G. H., and Van Loan, C. F. (1989), Matrix Computations (2nd ed.), Baltimore, MD: The John Hopkins University Press.
   Google Scholar
• Handcock, M. S., and Gile, K. J. (2010), “Modeling Social Networks from Sampled Data,” The Annals of Applied Statistics, 4, 5–25. DOI: 10.1214/08-AOAS221.
   PubMed Web of Science ®Google Scholar
• Handcock, M. S., Hunter, D. R., Butts, C. T., Goodreau, S. M., Krivitsky, P. N., and Morris, M. (2019), ergm: Fit, Simulate and Diagnose Exponential-Family Models for Networks. The Statnet Project. R package version 3.10.4.
   Google Scholar
• Hastie, T., Tibshirani, R., Friedman, J. H., and Friedman, J. H. (2009), The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Vol. 2), New York: Springer.
   Google Scholar
• Hoff, P., Fosdick, B., and Volfovsky, A. (2020), amen: Additive and Multiplicative Effects Models for Networks and Relational Data, R package version 1.4.4.
   Google Scholar
• Hoff, P. D. (2009), “Multiplicative Latent Factor Models for Description and Prediction of Social Networks,” Computational and Mathematical Organization Theory, 15, 261–272.
   Web of Science ®Google Scholar
• Hoff, P. D., Raftery, A. E., and Handcock, M. S. (2002), “Latent Space Approaches to Social Network Analysis,” Journal of the American Statistical Association, 97, 1090–1098.
   Web of Science ®Google Scholar
• Holland, P. P. W., and Leinhardt, S. (1981), “An Exponential Family of Probability Distributions for Directed Graphs,” Journal of the American Statistical Association, 76, 33–50.
   Web of Science ®Google Scholar
• Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983), “Stochastic Blockmodels: First Steps,” Social Networks, 5, 109–137.
   Web of Science ®Google Scholar
• Holland, P. W., and Leinhardt, S. (1971), “Transitivity in Structural Models of Small Groups,” Comparative Group Studies, 2, 107–124.
   Web of Science ®Google Scholar
• Hunter, D. R. (2007), “Curved Exponential Family Models for Social Networks,” Social Networks, 29, 216–230. DOI: 10.1016/j.socnet.2006.08.005.
   PubMed Web of Science ®Google Scholar
• Hurlbert, J., Beggs, J., and Haines, V. (2005), “Bridges Over Troubled Waters: What are the Optimal Networks for Katrina’s Victims,” in Online Forum and Essays]–Social Science Research Council.
   Google Scholar
• Ikehara, K., and Clauset, A. (2017), “Characterizing the Structural Diversity of Complex Networks Across Domains,” arXiv preprint arXiv:1710.11304.
   Google Scholar
• Keshavan, R., Montanari, A., and Oh, S. (2010), “Matrix Completion from Noisy Entries,” Journal of Machine Learning Research, 11, 2057–2078.
   Web of Science ®Google Scholar
• Kitsak, M., Voitalov, I., and Krioukov, D. (2020), “Link Prediction with Hyperbolic Geometry,” Physical Review Research, 2, 043113.
   Google Scholar
• Krivitsky, P. N., and Morris, M. (2017), “Inference for Social Network Models from Egocentrically Sampled Data, with Application to Understanding Persistent Racial Disparities in HIV Prevalence in the US,” The Annals of Applied Statistics, 11, 427–455. DOI: 10.1214/16-AOAS1010.
   PubMed Web of Science ®Google Scholar
• Laumann, E. O., Gagnon, J. H., Michael, R. T., and Michaels, S. (1995), National Health and Social Life Survey, Chicago, IL: University of Chicago and National Opinion Research Center.
   Google Scholar
• Lauritzen, S., Rinaldo, A., and Sadeghi, K. (2018), “Random Networks, Graphical Models and Exchangeability,” Journal of the Royal Statistical Society, Series B, 80, 481–508.
   Google Scholar
• Lei, J., and Rinaldo, A. (2015), “Consistency of Spectral Clustering in Stochastic Block Models,” The Annals of Statistics, 43, 215–237.
   Web of Science ®Google Scholar
• Li, T., and Le, C. M. (2021), “Network Estimation by Mixing: Adaptivity and More,” arXiv preprint arXiv:2106.02803.
   Google Scholar
• Li, T., Levina, E., and Zhu, J. (2020a), “Community Models for Networks Observed through Edge Nominations,” arXiv e-prints, page arXiv:2008.03652.
   Google Scholar
• Li, T. (2020b), “Network Cross-Validation by Edge Sampling,” Biometrika, 107, 257–276.
   Web of Science ®Google Scholar
• Liben-Nowell, D., and Kleinberg, J. (2007), “The Link-Prediction Problem for Social Networks,” Journal of the American Society for Information Science and Technology, 58, 1019–1031.
   Web of Science ®Google Scholar
• Lichtenwalter, R. N., Lussier, J. T., and Chawla, N. V. (2010), “New Perspectives and Methods in Link Prediction,” in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 243–252.
   Google Scholar
• Lin, Z., Chen, M., and Ma, Y. (2010), “The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices,” arXiv preprint arXiv:1009.5055.
   Google Scholar
• Little, R. J., and Rubin, D. B. (2019), Statistical Analysis with Missing Data (Vol. 793), Hoboken, NJ: Wiley.
   Google Scholar
• Lü, L., and Zhou, T. (2011), “Link Prediction in Complex Networks: A Survey,” Physica A: Statistical Mechanics and its Applications, 390, 1150–1170.
   Web of Science ®Google Scholar
• Mahoney, M. W., and Drineas, P. (2009), “CUR Matrix Decompositions for Improved Data Analysis,” Proceedings of the National Academy of Sciences of the United States of America, 106, 697–702. DOI: 10.1073/pnas.0803205106.
   PubMed Web of Science ®Google Scholar
• Manresa, E. (2013), “Estimating the Structure of Social Interactions using Panel Data,” Unpublished Manuscript. CEMFI, Madrid.
   Google Scholar
• Mara, A. C., Lijffijt, J., and De Bie, T. (2020), “Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?” in 2020 IEEE 7th International Conference on Data Science and Advanced Analytics (DSAA), pp. 138–147, IEEE.
   Google Scholar
• Mcauley, J., and Leskovec, J. (2012), “Learning to Discover Social Circles in Ego Networks,” in Advances in Neural Information Processing Systems (Vol. 25), pp. 539–547.
   Google Scholar
• Morris, M., Kurth, A. E., Hamilton, D. T., Moody, J., and Wakefield, S. (2009), “Concurrent Partnerships and HIV Prevalence Disparities by Race: Linking Science and Public Health Practice,” American Journal of Public Health, 99, 1023–1031.
   PubMed Web of Science ®Google Scholar
• Newman, M. (2018), “Network Structure from Rich but Noisy Data,” Nature Physics, 14, 542–545.
   Web of Science ®Google Scholar
• Newman, M. E. J. (2003), “Ego-Centered Networks and the Ripple Effect,” Social Networks, 25, 83–95.
   Web of Science ®Google Scholar
• Page, L., Brin, S., Motwani, R., and Winograd, T. (1999), “The Pagerank Citation Ranking: Bringing Order to the Web,” Technical report, Stanford InfoLab.
   Google Scholar
• Pech, R., Hao, D., Pan, L., Cheng, H., and Zhou, T. (2017), “Link Prediction via Matrix Completion,” EPL (Europhysics Letters), 117, 38002.
   Google Scholar
• Peixoto, T. P. (2015), “Inferring the Mesoscale Structure of Layered, Edge-Valued, and Time-Varying Networks,” Physical Review E, 92, 042807.
   Web of Science ®Google Scholar
• Peixoto, T. P. (2018), “Reconstructing Networks with Unknown and Heterogeneous Errors,” Physical Review X, 8, 041011.
   Web of Science ®Google Scholar
• Robins, G., Snijders, T., Wang, P., Handcock, M., and Pattison, P. (2007), “Recent Developments in Exponential Random Graph (p*) Models for Social Networks,” Social Networks, 29, 192–215.
   Web of Science ®Google Scholar
• Rohe, K. (2019), “A Critical Threshold for Design Effects in Network Sampling,” The Annals of Statistics, 47, 556–582.
   Web of Science ®Google Scholar
• Rohe, K., Chatterjee, S., and Yu, B. (2011), “Spectral Clustering and the High-Dimensional Stochastic Blockmodel,” The Annals of Statistics, 39, 1878–1915.
   Web of Science ®Google Scholar
• Romney, A. K., Weller, S. C., and Batchelder, W. H. (1986), “Culture as Consensus: A Theory of Culture and Informant Accuracy,” American Anthropologist, 88, 313–338.
   Web of Science ®Google Scholar
• Rubin, D. B. (1976), “Inference and Missing Data,” Biometrika, 63, 581–592.
   Web of Science ®Google Scholar
• Shalizi, C. R., and Rinaldo, A. (2013), “Consistency Under Sampling of Exponential Random Graph Models,” The Annals of Statistics, 41, 508–535. DOI: 10.1214/12-AOS1044.
   PubMed Web of Science ®Google Scholar
• Vershynin, R. (2018), High-Dimensional Probability: An Introduction with Applications in Data Science (Vol. 47), Cambridge: Cambridge University Press.
   Google Scholar
• Watts, D. J., and Strogatz, S. H. (1998), “Collective Dynamics of “Small-World” Networks,” Nature, 393, 440–442.
   PubMed Web of Science ®Google Scholar
• Yao, Y., Pirš, G., Vehtari, A., and Gelman, A. (2021), “Bayesian Hierarchical Stacking,” arXiv preprint arXiv:2101.08954.
   Google Scholar
• Young, S. J., and Scheinerman, E. R. (2007), “Random Dot Product Graph Models for Social Networks,” in International Workshop on Algorithms and Models for the Web-Graph, pp. 138–149, Springer.
   Google Scholar
• Zhang, Y., Levina, E., and Zhu, J. (2017), “Estimating Network Edge Probabilities by Neighbourhood Smoothing,” Biometrika, 104, 771–783.
   Web of Science ®Google Scholar
• Zhao, Y., Wu, Y.-J., Levina, E., and Zhu, J. (2017), “Link Prediction for Partially Observed Networks,” Journal of Computational and Graphical Statistics, 26, 725–733.
   Web of Science ®Google Scholar