research-article

Public Access

Pairwise link prediction

Authors:

Austin R. Benson,

David F. GleichAuthors Info & Claims

ASONAM '19: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Pages 386 - 393

https://doi.org/10.1145/3341161.3342897

Published: 15 January 2020 Publication History

Abstract

Link prediction is a common problem in network science that transects many disciplines. The goal is to forecast the appearance of new links or to find links missing in the network. Typical methods for link prediction use the topology of the network to predict the most likely future or missing connections between a pair of nodes. However, network evolution is often mediated by higher-order structures involving more than pairs of nodes; for example, cliques on three nodes (also called triangles) are key to the structure of social networks, but the standard link prediction framework does not directly predict these structures. To address this gap, we propose a new link prediction task called "pairwise link prediction" that directly targets the prediction of new triangles, where one is tasked with finding which nodes are most likely to form a triangle with a given edge. We develop two PageRank-based methods for our pairwise link prediction problem and make natural extensions to existing link prediction methods. Our experiments on a variety of networks show that diffusion based methods are less sensitive to the type of graphs used and more consistent in their results. We also show how our pairwise link prediction framework can be used to get better predictions within the context of standard link prediction evaluation.

References

[1]

D. Liben-Nowell and J. Kleinberg, "The link-prediction problem for social networks," Journal of the American Society for Information Science and Technology, vol. 58, no. 7, 2007.

[2]

L. Lü and T. Zhou, "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, vol. 390, no. 6, 2011.

[3]

A. Clauset, C. Moore, and M. E. J. Newman, "Hierarchical structure and the prediction of missing links in networks," Nature, vol. 453, pp. 98 EP -, May 2008. [Online]. Available

[4]

L. Backstrom and J. Leskovec, "Supervised random walks: Predicting and recommending links in social networks," ser. WSDM '11. New York, NY, USA: ACM, 2011, pp. 635--644.

Digital Library

[5]

C. A. Gomez-Uribe and N. Hunt, "The netflix recommender system: Algorithms, business value, and innovation," ACM Trans. Manage. Inf. Syst., vol. 6, no. 4, pp. 13:1--13:19, Dec. 2015.

Digital Library

[6]

C.-H. Lin, D. M. Konecki, M. Liu, S. J. Wilson, H. Nassar, A. D. Wilkins, D. R. Gleich, and O. Lichtarge, "Multimodal network diffusion predicts future diseasegenechemical associations," 10 2018.

[7]

R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: Simple building blocks of complex networks," Science, vol. 298, no. 5594, pp. 824--827, 2002. [Online]. Available: https://science.sciencemag.org/content/298/5594/824.full.pdf

[8]

R. Milo, "Superfamilies of evolved and designed networks," Science, vol. 303, no. 5663, pp. 1538--1542, mar 2004.

[9]

A. R. Benson, D. F. Gleich, and J. Leskovec, "Higher-order organization of complex networks," Science, vol. 353, no. 6295, pp. 163--166, Jul. 2016.

[10]

A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg, "Simplicial closure and higher-order link prediction," Proceedings of the National Academy of Sciences, nov 2018.

[11]

R. Lambiotte, M. Rosvall, and I. Scholtes, "From networks to optimal higher-order models of complex systems," Nature Physics, vol. 15, no. 4, pp. 313--320, Mar. 2019.

[12]

D. Easley, J. Kleinberg et al., Networks, crowds, and markets. Cambridge university press Cambridge, 2010, vol. 8.

[13]

P. W. Holland and S. Leinhardt, "A method for detecting structure in sociometric data," in Social Networks. Elsevier, 1977, pp. 411--432.

[14]

M. S. Granovetter, "The strength of weak ties," in Social Networks. Elsevier, 1977, pp. 347--367.

[15]

A. Rapoport, "Spread of information through a population with socio-structural bias: I. assumption of transitivity," The Bulletin of Mathematical Biophysics, vol. 15, no. 4, pp. 523--533, Dec. 1953.

[16]

L. A. Adamic and E. Adar, "Friends and neighbors on the web," Social Networks, vol. 25, no. 3, pp. 211 -- 230, 2003.

[17]

M. E. J. Newman, "Clustering and preferential attachment in growing networks," Phys. Rev. E, vol. 64, p. 025102, Jul 2001.

[18]

A.-L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509--512, 1999. [Online]. Available: https://science.sciencemag.org/content/286/5439/509.full.pdf

[19]

L. Katz, "A new status index derived from sociometric analysis," Psychometrika, vol. 18, no. 1, pp. 39--43, Mar 1953.

[20]

L. Page, S. Brin, R. Motwani, and T. Winograd, "The pagerank citation ranking: Bringing order to the web." Stanford InfoLab, Technical Report 1999-66, November 1999, previous number = SIDL-WP-1999-0120.

[21]

N. Eikmeier, A. S. Ramani, and D. F. Gleich, "The hyperkron graph model for higher-order features," in IEEE International Conference on Data Mining, ICDM 2018, Singapore, November 17--20, 2018, 2018.

[22]

H. Nassar, A. R. Benson, and D. F. Gleich, "Pairwise link prediction," arXiv, 2019. [Online]. Available: https://arxiv.org/pdf/1907.04503.pdf

[23]

R. Andersen, F. Chung, and K. Lang, "Local graph partitioning using PageRank vectors," in 2006 47th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2006.

[24]

D. F. Gleich, "PageRank beyond the web," SIAM Review, vol. 57, no. 3, pp. 321--363, Jan. 2015.

Digital Library

[25]

P. Lofgren, S. Banerjee, and A. Goel, "Personalized pagerank estimation and search: A bidirectional approach," in Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, ser. WSDM '16. New York, NY, USA: ACM, 2016, pp. 163--172.

Digital Library

[26]

A. Benson, D. F. Gleich, and L.-H. Lim, "The spacey random walk: a stochastic process for higher-order data," SIAM Review, vol. 59, no. 2, pp. 321--345, May 2017.

Digital Library

[27]

H. Nassar and D. Gleich, "Matrixnetworks.jl," https://github.com/nassarhuda/MatrixNetworks.jl, Oct. 2018.

[28]

C. Avin et al., "Core size and densification in preferential attachment networks," in International Colloquium on Automata, Languages, and Programming, ser. ICALP 2015. Berlin, Heidelberg: Springer-Verlag, 2015, pp. 492--503.

[29]

A. L. Traud, P. J. Mucha, and M. A. Porter, "Social structure of facebook networks," CoRR, vol. abs/1102.2166, 2011.

[30]

D. S. Wishart et al., "DrugBank 5.0: a major update to the DrugBank database for 2018," Nucleic Acids Research, Nov. 2017.

[31]

Stanford SNAP Group, "Miner: Gigascale multimodal biological network," https://github.com/snap-stanford/miner-data, 2017.

[32]

M. Agrawal, M. Zitnik, and J. Leskovec, "Large-scale analysis of disease pathways in the human interactome," in Pacific Symposium on Biocomputing, vol. 23. World Scientific, 2018, p. 111.

[33]

R. Guimerà, L. Danon, A. Daz-Guilera, F. Giralt, and A. Arenas, "Self-similar community structure in a network of human interactions," Phys. Rev. E, vol. 68, p. 065103, Dec 2003.

[34]

E. Eisenberg and E. Y. Levanon, "Preferential attachment in the protein network evolution," Phys. Rev. Lett., vol. 91, p. 138701, Sep 2003.

[35]

P. Panzarasa, T. Opsahl, and K. M. Carley, "Patterns and dynamics of users' behavior and interaction: Network analysis of an online community," Journal of the American Society for Information Science and Technology, vol. 60, no. 5, pp. 911--932, May 2009.

Digital Library

Cited By

Muro CLi BHe K(2024)LUSTC: A Novel Approach for Predicting Link States on Dynamic Attributed NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.325226111:1(1075-1085)Online publication date: Feb-2024
https://doi.org/10.1109/TCSS.2023.3252261
Xu ZYao YMa N(2024)Mutual information higher-order link prediction based on Naive Bayes2024 6th International Conference on Internet of Things, Automation and Artificial Intelligence (IoTAAI)10.1109/IoTAAI62601.2024.10692526(117-120)Online publication date: 26-Jul-2024
https://doi.org/10.1109/IoTAAI62601.2024.10692526
Besta MGrob RMiglioli CBernold NKwasniewski GGjini GKanakagiri RAshkboos SGianinazzi LDryden NHoefler TZhang ARangwala H(2022)Motif Prediction with Graph Neural NetworksProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539343(35-45)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539343
Show More Cited By

Pairwise link prediction
1. Information systems
  1. Information systems applications

Recommendations

Link prediction using time series of neighborhood-based node similarity scores

We propose a link prediction method for evolving networks. Our method first computes a number of different node similarity scores (e.g. Common Neighbor, Preferential Attachment, Adamic---Adar, Jaccard) and their weighted versions, for different past ...
HM-EIICT: Fairness-aware link prediction in complex networks using community information
Abstract
The evolution of online social networks is highly dependent on the recommended links. Most of the existing works focus on predicting intra-community links efficiently. However, it is equally important to predict inter-community links with high ...
h-Index-based link prediction methods in citation network

Link prediction implies the mining of the missing links in networks or prediction of the next node pair to be connected by a link. Link prediction is useful for mining information in citation networks, and most of the existing related studies commonly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '19: Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

August 2019

1228 pages

ISBN:9781450368681

DOI:10.1145/3341161

Editors:
Francesca Spezzano
Boise State University
,
Wei Chen
Microsoft Research, China
,
Xiaokui Xiao
National University of Singapore, Singapore

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 January 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ASONAM '19

Sponsor:

SIGKDD

ASONAM '19: International Conference on Advances in Social Networks Analysis and Mining

August 27 - 30, 2019

British Columbia, Vancouver, Canada

Acceptance Rates

ASONAM '19 Paper Acceptance Rate 41 of 286 submissions, 14%;

Overall Acceptance Rate 116 of 549 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
530
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)21

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Muro CLi BHe K(2024)LUSTC: A Novel Approach for Predicting Link States on Dynamic Attributed NetworksIEEE Transactions on Computational Social Systems10.1109/TCSS.2023.325226111:1(1075-1085)Online publication date: Feb-2024
https://doi.org/10.1109/TCSS.2023.3252261
Xu ZYao YMa N(2024)Mutual information higher-order link prediction based on Naive Bayes2024 6th International Conference on Internet of Things, Automation and Artificial Intelligence (IoTAAI)10.1109/IoTAAI62601.2024.10692526(117-120)Online publication date: 26-Jul-2024
https://doi.org/10.1109/IoTAAI62601.2024.10692526
Besta MGrob RMiglioli CBernold NKwasniewski GGjini GKanakagiri RAshkboos SGianinazzi LDryden NHoefler TZhang ARangwala H(2022)Motif Prediction with Graph Neural NetworksProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539343(35-45)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539343
Xiong TZhou LZhao YZhang X(2022)Mining semantic information of co-word network to improve link prediction performanceScientometrics10.1007/s11192-021-04247-9127:6(2981-3004)Online publication date: 4-Jan-2022
https://doi.org/10.1007/s11192-021-04247-9
Noel SSwarup V(2022)Dependency-Based Link Prediction for Learning Microsegmentation PolicyInformation and Communications Security10.1007/978-3-031-15777-6_31(569-588)Online publication date: 24-Aug-2022
https://doi.org/10.1007/978-3-031-15777-6_31
Xie FZhao ZYang P(2022)Higher Order Preference on the Evolution of Cooperation on Barabási–Albert Scale-Free NetworkAdvances in Natural Computation, Fuzzy Systems and Knowledge Discovery10.1007/978-3-030-89698-0_15(137-149)Online publication date: 4-Jan-2022
https://doi.org/10.1007/978-3-030-89698-0_15
Li PWang YWang HLeskovec JLarochelle HRanzato MHadsell RBalcan MLin H(2020)Distance encodingProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496099(4465-4478)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496099
Khoshmanesh SLutz R(2020)Does Link Prediction Help Find Feature Interactions in Software Product Lines?2020 IEEE Seventh International Workshop on Artificial Intelligence for Requirements Engineering (AIRE)10.1109/AIRE51212.2020.00020(87-90)Online publication date: Sep-2020
https://doi.org/10.1109/AIRE51212.2020.00020
Nassar HBenson AGleich D(2020)Neighborhood and PageRank methods for pairwise link predictionSocial Network Analysis and Mining10.1007/s13278-020-00671-610:1Online publication date: 30-Jul-2020
https://doi.org/10.1007/s13278-020-00671-6

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents