New perspectives and methods in link prediction
The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Abstract
This paper examines important factors for link prediction in networks and provides a general, high-performance framework for the prediction task. Link prediction in sparse networks presents a significant challenge due to the inherent disproportion of links that can form to links that do form. Previous research has typically approached this as an unsupervised problem. While this is not the first work to explore supervised learning, many factors significant in influencing and guiding classification remain unexplored. In this paper, we consider these factors by first motivating the use of a supervised framework through a careful investigation of issues such as network observational period, generality of existing methods, variance reduction, topological causes and degrees of imbalance, and sampling approaches. We also present an effective flow-based predicting algorithm, offer formal bounds on imbalance in sparse network link prediction, and employ an evaluation method appropriate for the observed imbalance. Our careful consideration of the above issues ultimately leads to a completely general framework that outperforms unsupervised link prediction methods by more than 30% AUC.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Breiman, L. (2001) · Machine Learning · doi:10.1023/a:1010933404324 · Cited by 133,538
SMOTE synthetic minority over-sampling technique
Chawla, N. V., Bowyer, K. W., Hall, L. O., & Kegelmeyer, W. P. (2002) · Journal of Artificial Intelligence Research · doi:10.1613/jair.953 · Cited by 32,865
Self-citationData Mining: Practical Machine Learning Tools and Techniques
(2011) · Elsevier eBooks · doi:10.1016/c2009-0-19715-5 · Cited by 25,437
(1992) · Cited by 23,431
Breiman, L. (1996) · Machine Learning · doi:10.1007/bf00058655 · Cited by 16,325
Witten, I. H. (2008) · Cited by 9,143
A New Status Index Derived from Sociometric Analysis
Katz, L. (1953) · Psychometrika · doi:10.1007/bf02289026 · Cited by 3,866
The link‐prediction problem for social networks
Liben‐Nowell, D., & Kleinberg, J. (2007) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.20591 · Cited by 3,043
Friends and neighbors on the Web
Adamic, L. A., & Adar, E. (2003) · Social Networks · doi:10.1016/s0378-8733(03)00009-1 · Cited by 2,954
Clustering and preferential attachment in growing networks
Newman, M. E. J. (2001) · Physical Review E · doi:10.1103/physreve.64.025102 · Cited by 2,093
Cited by
SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary
Fernandez, A., Garcia, S., Herrera, F., & Chawla, N. V. (2018) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.11192 · Cited by 2,219
Self-citationA survey of heterogeneous information network analysis
Shi, C., Li, Y., Zhang, J., Sun, Y., & Yu, P. S. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2598561 · Cited by 1,112
A Survey of Link Prediction in Complex Networks
Martínez, V., Berzal, F., & Cubero, J.-C. (2017) · ACM Computing Surveys · doi:10.1145/3012704 · Cited by 695
Human mobility, social ties, and link prediction
Wang, D., Pedreschi, D., Song, C., Giannotti, F., & Barabasi, A.-L. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020581 · Cited by 665
Link prediction in social networks: the state-of-the-art
Wang, P., Xu, B., Wu, Y., & Zhou, X. (2015) · Science China Information Sciences · doi:10.1007/s11432-014-5237-y · Cited by 548
Exploiting place features in link prediction on location-based social networks
Scellato, S., Noulas, A., & Mascolo, C. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020575 · Cited by 522
Link Prediction via Matrix Factorization
Menon, A. K., & Elkan, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-23783-6_28 · Cited by 520
Link prediction techniques, applications, and performance: A survey
Kumar, A., Singh, S. S., Singh, K., & Biswas, B. (2020) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2020.124289 · Cited by 516
Mining Heterogeneous Information Networks: Principles and Methodologies
Sun, Y., & Han, J. (2012) · Synthesis lectures on data mining and knowledge discovery · doi:10.2200/s00433ed1v01y201207dmk005 · Cited by 471
Co-author Relationship Prediction in Heterogeneous Bibliographic Networks
Sun, Y., Barber, R., Gupta, M., Aggarwal, C. C., & Han, J. (2011) · 2011 International Conference on Advances in Social Networks Analysis and Mining · doi:10.1109/asonam.2011.112 · Cited by 445
“Random walk measure along a meta path is defined as RWR(ai, aj) = PCR(ai,aj) PCR(ai,·) , which is a natural generalization of PropFlow [8].”
BackgroundMethodInfluentialRolX: structural role extraction & mining in large graphs
Henderson, K., Gallagher, B., Eliassi-Rad, T., Tong, H., Basu, S., Akoglu, L., Koutra, D., Faloutsos, C., & Li, L. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339723 · Cited by 376
Inferring anchor links across multiple heterogeneous social networks
Kong, X., Zhang, J., & Yu, P. S. (2013) · Proceedings of the 22nd ACM international conference on Information & Knowledge Management · doi:10.1145/2505515.2505531 · Cited by 356
Event-based social networks: linking the online and offline social worlds
Liu, X., He, Q., Tian, Y., Lee, W.-C., McPherson, J., & Han, J. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339693 · Cited by 299
Cross-domain collaboration recommendation
Tang, J., Wu, S., Sun, J., & Su, H. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339730 · Cited by 292
Inferring social ties across heterogenous networks
Tang, J., Lou, T., & Kleinberg, J. (2012) · Proceedings of the fifth ACM international conference on Web search and data mining · doi:10.1145/2124295.2124382 · Cited by 289
“Recently, [22] designs a flow based method for link prediction.”
MethodEvaluating link prediction methods
Yang, Y., Lichtenwalter, R. N., & Chawla, N. V. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-014-0789-0 · Cited by 287
Self-citationLink Prediction and Recommendation across Heterogeneous Social Networks
Dong, Y., Tang, J., Wu, S., Tian, J., Chawla, N. V., Rao, J., & Cao, H. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.140 · Cited by 280
Self-citationVERSE: Versatile Graph Embeddings from Similarity Measures
Tsitsulin, A., Mottin, D., Karras, P., & Müller, E. (2018) · Proceedings of the 2018 World Wide Web Conference on World Wide Web - WWW '18 · doi:10.1145/3178876.3186120 · Cited by 277
Zhou, Z.-H., Chawla, N. V., Jin, Y., & Williams, G. J. (2014) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2014.2350953 · Cited by 275
Self-citationBusiness Intelligence for Enterprise Systems: A Survey
Duan, L., & Xu, L. D. (2012) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2188804 · Cited by 254
It's who you know: graph mining using recursive structural features
Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020512 · Cited by 223
“One study approaches link prediction as a supervised learning problem [21].”
BackgroundExploiting Publication Contents and Collaboration Networks for Collaborator Recommendation
Kong, X., Jiang, H., Yang, Z., Xu, Z., Xia, F., & Tolba, A. (2016) · PLOS ONE · doi:10.1371/journal.pone.0148492 · Cited by 67
Li, Z. (., Fang, X., & Sheng, O. R. L. (2018) · ACM Transactions on Management Information Systems · doi:10.1145/3131782 · Cited by 65
“The SimRank score 𝑆𝑅 𝑖𝑗 between social entities 𝑣 𝑖 and 𝑣 𝑗 is defined as (Jeh and Widom 2002, Liben-Nowell and Kleinberg 2007, Liu and Lü 2010) where 𝛾 ∈ (0,1) is a decay factor.”
Tang, J., & Liu, H. (2015) · Synthesis Lectures on Information Security, Privacy, and Trust · doi:10.2200/s00657ed1v01y201507spt013 · Cited by 53
Metadata
- Authors
- Lichtenwalter, R. N., Lussier, J. T., & Chawla, N. V.
- Venue
- Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2010-07-25
- Pages
- 243-252
- OpenAlex
- W2003707464
- Cited by
- 664
- References
- 19
- FWCI
- 24.27
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.