Proximity-based Methods for Link Prediction in Graphs with R package 'linkprediction'

• Authors: Bojanowski Michał , Chroł Bartosz
• Languages of publication: EN

Abstracts

EN

Link prediction is a problem of predicting future edges of an undirected graph based on a single snapshot of data of that graph. Vertex proximity measures are indicies giving numerical scores for every pair of vertices in a graph that can be used for predicting future edges. This short note describes an R package 'linkprediction' implementing 20 different vertex similarity and proximity measures from the literature. The article provides the definitions of implemented measures, describes the main user-facing functions, and illustrates the use of the methods with a problem of predicting future co-authorship relations between researchers of the University of Warsaw.

• Publisher: Institute of Philosophy and Sociology, Polish Academy of Sciences
• Journal: ASK. Research and Methods
• Year: 2020
• Volume: 29
• Issue: 1
• Pages: 5-28

Contributors

author

Bojanowski Michał

author

Chroł Bartosz

References

• Adamic, Lada, and Eytan Adar. 2001. “Friends and Neighbors on the Web.” Social Networks 25: 211–30. https://doi.org/10.1016/S0378-8733(03)00009-1
• Backstrom, Lars, and Jure Leskovec. 2011. “Supervised Random Walks: Predicting and Recommending Links in Social Networks.” In Proceedings of the Fourth Acm International Conference on Web Search and Data Mining, 635–44. ACM. https://doi.org/10.1145/1935826.1935914
• Barabási, Albert-László. 2016. Network Science. Cambridge University Press.
• Barabási, Albert-László, and Réka Albert. 1999. “Emergence of Scaling in Random Networks.”Science286 (5439): 509–12. https://doi.org/10.1126/science.286.5439.509
• Bojanowski, Michał, and Rense Corten. 2014. “Measuring Segregation in Social Networks.” Social Networks 39: 14–32. https://doi.org/10.1016/j.socnet.2014.04.001
• Brandes, Ulrik, Garry Robins, Ann McCranie, and Stanley Wasserman. 2013. “What Is Network Science?” Network Science 1 (1): 1–15. https://doi.org/10.1017/nws.2013.2
• Brin, Sergey, and Lawrence Page. 1998. “The Anatomy of a Large-Scale Hypertextual Web Search Engine.” Computer Networks and ISDN Systems 30 (1–7): 107–17. https://doi.org/10.1016/S0169-7552(98)00110-X
• Butts, Carter T. 2008. “Network: A Package for Managing Relational Data in R.” Journal of Statistical Software 24 (2). https://doi.org/10.18637/jss.v024.i02 —. 2015. Network: Classes for Relational Data. The Statnet Project (http://statnet.org). http://CRAN.R-project.org/package=network.
• Chebotarev, P. Yu., and E. V. Shamis. 1997. “The Matrix-Forest Theorem and Measuring Relations in Small Social Groups.” Automation and Remote Control 58 (9): 1505–14.
• Clauset, Aaron, Cristopher Moore, and Mark EJ Newman. 2008. “Hierarchical Structure and the Prediction of Missing Links in Networks.” Nature 453 (7191): 98. https://doi.org/10.1038/nature06830
• Csardi, Gabor, and Tamas Nepusz. 2006. “The Igraph Software Package for Complex Network Research.” InterJournal Complex Systems: 1695. http://igraph.org.
• Desmarais, Bruce A, and Skyler J Cranmer. 2013. “Forecasting the Locational Dynamics of Transnational Terrorism: A Network Analytic Approach.” Security Informatics 2 (1): 8. https://doi.org/10.1186/2190-8532-2-8
• Ferligoj, Anuška, Luka Kronegger, Franc Mali, Tom AB Snijders, and Patrick Doreian. 2015. “Scientific Collaboration Dynamics in a National Scientific System.” Scientometrics 104 (3): 985–1012. https://doi.org/10.1007/s11192-015-1585-7
• Fouss, Francois, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. 2007. “Random-Walk Computation of Similarities Between Nodes of a Graph with Application to Collaborative Recommendation.” IEEE Transactions on Knowledge and Data Engineering 19 (3): 355–69. https://doi.org/10.1109/TKDE.2007.46
• Goyal, Sanjeev. 2012. Connections: An Introduction to the Economics of Networks. Princeton University Press.
• Hanneke, Steve, Wenjie Fu, and Eric P. Xing. 2010. “Discrete Temporal Models of Social Networks.” Electronic Journal of Statistics 4: 585–605. https://doi.org/10.1214/09-EJS548
• Jaccard, Paul. 1912. “The Distribution of the Flora in the Alpine Zone.” New Phytologist 11 (2): 37–50. https://doi.org/10.1111/j.1469-8137.1912.tb05611.x
• Jackson, Matthew O. 2010. Social and Economic Networks. Princeton University Press.
• Katz, Leo. 1953. “A New Status Index Derived from Sociometric Analysis.” Psychometrika 18 (1): 39–43. https://doi.org/10.1007/BF02289026
• Klein, Douglas J, and Milan Randić. 1993. “Resistance Distance.” Journal of Mathematical Chemistry 12 (1): 81–95. https://doi.org/10.1007/BF01164627
• Krivitsky, Pavel N, and Mark S Handcock. 2014. “A Separable Model for Dynamic Networks.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76 (1): 29–46. https://doi.org/10.1111/rssb.12014
• Krivitsky, Pavel N., and Mark S. Handcock. 2018. Tergm: Fit, Simulate and Diagnose Models for Network Evolution Based on Exponential-Family Random Graph Models. The Statnet Project (http://www.statnet.org). https://CRAN.R-project.org/package=tergm.
• Leicht, E. A., Petter Holme, and M. E. J. Newman. 2006. “Vertex Similarity in Networks.” Phys. Rev. E 73 (2): 026120. https://doi.org/10.1103/PhysRevE.73.026120
• Liben-Nowell, David, and Jon Kleinberg. 2007. “The Link-Prediction Problem for Social Networks.” Journal of the American Society for Information Science and Technology 58 (7): 1019–31. https://doi.org/10.1002/asi.20591
• Lü, Linyuan, and Tao Zhou. 2011. “Link Prediction in Complex Networks: A Survey.” Physica A 390 (6): 1150–70. https://doi.org/10.1016/j.physa.2010.11.027
• McPherson, Miller, Lynn Smith-Lovin, and James M Cook. 2001. “Birds of a Feather: Homophily in Social Networks.” Annual Review of Sociology 27 (1): 415–44. https://doi.org/10.1146/annurev.soc.27.1.415
• Neuwirth, Erich. 2014. RColorBrewer: ColorBrewer Palettes. https://CRAN.R-project.org/package=RColorBrewer.
• Newman, Mark. 2010. Networks: An Introduction. Oxford University Press. https://doi.org/10.1093/acprof:oso/9780199206650.003.0001
• Newman, M. E. J. 2001. “Clustering and Preferential Attachment in Growing Networks.” Phys. Rev. E 64 (2): 025102. https://doi.org/10.1103/PhysRevE.64.025102PBN. 2017. “Polska Bibliografia Naukowa (Polish Scholarly Bibliography).” 2017. https://pbn.nauka.gov.pl/.
• Ravasz, E., A. L. Somera, D. A. Mongru, Z. N. Oltvai, and Albert-László Barabási. 2002. “Hierarchical Organization of Modularity in Metabolic Networks.” Science 297 (5586): 1551–5. https://doi.org/10.1126/science.1073374
• Michal Bojanowski and Bartosz Chrol (2020). linkprediction: Link Prediction Methods. R package version 1.0-1. https://github.com/recon-icm/linkprediction
• Ripley, Ruth M., Tom A. B. Snijders, Zsofia Boda, András Vörös, and Paulina Preciado. 2018. “Manual for Siena Version 4.0.” Oxford: University of Oxford, Department of Statistics; Nuffi eld College.
• Sing, T., O. Sander, N. Beerenwinkel, and T. Lengauer. 2005. “ROCR: Visualizing Classifier Performance in R.” Bioinformatics 21 (20): 7881. https://doi.org/10.1093/bioinformatics/bti623
• Snijders, Tom A. B. 1996. “Stochastic Actor-Oriented Models for Network Change.” Journal of Mathematical Sociology 21 (1-2): 149–72. https://doi.org/10.1080/0022250X.1996.9990178
• Sørensen, Thorvald. 1948. “A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species Content and Its Application to Analyses of the Vegetation on Danish Commons.” Biologiske Skrifter 5: 1–34.
• Van de Bunt, Gerhard G, Marijtje AJ Van Duijn, and Tom AB Snijders. 1999. “Friendship Networks Through Time: An Actor-Oriented Dynamic Statistical Network Model.” Computational & Mathematical Organization Theory 5 (2): 167–92. https://doi.org/10.1023/A:1009683123448
• Wasserman, Stanley, and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge university press. https://doi.org/10.1017/CBO9780511815478
• Wickham, Hadley, Romain François, Lionel Henry, and Kirill Müller. 2018. Dplyr: A Grammar of Data Manipulation. https://CRAN.R-project.org/package=dplyr.
• Wickham, Hadley, and Lionel Henry. 2018. Tidyr: Easily Tidy Data with ’Spread()’ and ’Gather()’ Functions. https://CRAN.R-project.org/package=tidyr.
• Zhou, Tao, Linyuan Lü, and Yi-Cheng Zhang. 2009. “Predicting Missing Links via Local Information.” The European Physical Journal B 71 (4): 623–30. https://doi.org/10.1140/epjb/e2009-00335-8