Link Prediction in Complex Networks: A Survey

Abstract

Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labelled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms.

44 pages, 5 figures

References in corpus (28)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Synchronization in complex networks
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Multirelational Organization of Large-scale Social Networks in an Online World
• Missing and spurious interactions and the reconstruction of complex networks
• New Model of Internet Topology Using k-shell Decomposition
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Efficient routing on complex networks
• The Rich-Club Phenomenon In The Internet Topology
• Extracting the hierarchical organization of complex systems
• The spatial structure of networks
• Community detection in networks with positive and negative links
• Geographical dispersal of mobile communication networks
• Classes of complex networks defined by role-to-role connectivity profiles
• Gravity model in the Korean highway
• Personalized Recommendation via Integrated Diffusion on User-Item-Tag Tripartite Graphs
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Role models for complex networks
• Information filtering based on transferring similarity
• Uncovering missing links with cold ends
• Scale free networks from a Hamiltonian dynamics
• Self Organized Scale-Free Networks from Merging and Regeneration
• Emergent self-organized complex network topology out of stability constraints
• Role-similarity based functional prediction in networked systems: Application to the yeast proteome
• Similarity-Based Classification in Partially Labeled Networks
• Empirical study on clique-degree distribution of networks

Cited by in corpus (354)

• Graph Embedding Techniques, Applications, and Performance: A Survey
• A Review of Relational Machine Learning for Knowledge Graphs
• Recommender Systems
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Leaders in Social Networks, the Delicious Case
• Modern temporal network theory: A colloquium
• Simplicial Closure and higher-order link prediction
• Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations
• The Statistical Physics of Real-World Networks
• Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey
• VERSE: Versatile Graph Embeddings from Similarity Measures
• Evaluating Link Prediction Methods
• Random Walks: A Review of Algorithms and Applications
• Link Prediction Based on Graph Neural Networks
• Identifying Influential Spreaders by Weighted LeaderRank
• An Evolutionary Algorithm Approach to Link Prediction in Dynamic Social Networks
• Personalized Recommendation via Integrated Diffusion on User-Item-Tag Tripartite Graphs
• Nestedness in complex networks: Observation, emergence, and implications
• Ranking in evolving complex networks
• Hiding Individuals and Communities in a Social Network
• Rate-optimal graphon estimation
• Link prediction in complex networks: a local na\"ıve Bayes model
• Learning Discrete Structures for Graph Neural Networks
• Combining complex networks and data mining: why and how
• Tag-Aware Recommender Systems: A State-of-the-art Survey
• Network Mapping by Replaying Hyperbolic Growth
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Hidden geometric correlations in real multiplex networks
• Link Prediction in Complex Networks: A Mutual Information Perspective
• Potential Theory for Directed Networks
• Progresses and Challenges in Link Prediction
• Link Prediction with Node Clustering Coefficient
• Information filtering via biased heat conduction
• Predicting missing links and their weights via reliable-route-based method
• Link Prediction via Matrix Completion
• Link prediction via linear optimization
• Self-similar scaling of density in complex real-world networks
• Network-based recommendation algorithms: A review
• Information filtering via preferential diffusion
• Reconstruction methods for networks: the case of economic and financial systems
• The dynamical structure of political corruption networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• Network Geometry Inference using Common Neighbors
• Modeling Relation Paths for Representation Learning of Knowledge Bases
• Reconstructing networks with unknown and heterogeneous errors
• Networked relationships in the e-MID Interbank market: A trading model with memory
• Link Prediction in Multiplex Networks based on Interlayer Similarity
• Hierarchical Clustering Supported by Reciprocal Nearest Neighbors
• Removing spurious interactions in complex networks
• Finding missing edges in networks based on their community structure
• Developments in the theory of randomized shortest paths with a comparison of graph node distances
• Triple Trustworthiness Measurement for Knowledge Graph
• Learning Graph Representations with Embedding Propagation
• Reconstructing commuters network using machine learning and urban indicators
• How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction
• Link Prediction in Complex Networks: A Clustering Perspective
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• MODEL: Motif-based Deep Feature Learning for Link Prediction
• Big Networks: A Survey
• People are Strange when you're a Stranger: Impact and Influence of Bots on Social Networks
• Dynamic Evolution of Complex Networks: A Reinforcement Learning Approach Applying Evolutionary Games to Community Structure
• A Survey of Adversarial Learning on Graphs
• Evaluating user reputation in online rating systems via an iterative group-based ranking method
• Parallel Machine Learning for Forecasting the Dynamics of Complex Networks
• Link prediction based on path entropy
• Knowledge-based Biomedical Data Science 2019
• Prediction in complex systems: the case of the international trade network
• Scalable Text and Link Analysis with Mixed-Topic Link Models
• Uncovering missing links with cold ends
• Behavior patterns of online users and the effect on information filtering
• Bring Your Own View: Graph Neural Networks for Link Prediction with Personalized Subgraph Selection
• Personalized PageRank to a Target Node, Revisited
• Group-based ranking method for online rating systems with spamming attacks
• Multiscale dynamical embeddings of complex networks
• Community Detection in Complex Networks Using Density-based Clustering Algorithm
• Link prediction with hyperbolic geometry
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Recommender systems based on graph embedding techniques: A comprehensive review
• Review on Learning and Extracting Graph Features for Link Prediction
• SybilFrame: A Defense-in-Depth Framework for Structure-Based Sybil Detection
• HPRA: Hyperedge Prediction using Resource Allocation
• HMSG: Heterogeneous Graph Neural Network based on Metapath Subgraph Learning
• A vertex similarity index for better personalized recommendation
• A bag-of-paths framework for network data analysis
• Strong ties promote the epidemic prevalence in susceptible-infected-susceptible spreading dynamics
• Promoting cold-start items in recommender systems
• SketchGraphs: A Large-Scale Dataset for Modeling Relational Geometry in Computer-Aided Design
• Identifying Communities and Key Vertices by Reconstructing Networks from Samples
• Reconstructing networks
• Joint embedding of structure and features via graph convolutional networks
• Prediction of scientific collaborations through multiplex interaction networks
• Identifying significant edges via neighborhood information
• Inductive Matrix Completion Based on Graph Neural Networks
• Accuracy Test for Link Prediction in terms of Similarity Index: The Case of WS and BA Models
• Hypergraph reconstruction from dynamics
• Meta-Graph: Few Shot Link Prediction via Meta Learning
• Predicting missing links via significant paths
• Link prediction in multiplex networks via triadic closure
• Harnessing the Power of Ego Network Layers for Link Prediction in Online Social Networks
• Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation data
• SI-spreading-based network embedding in static and temporal networks
• Network representation learning systematic review: ancestors and current development state
• POLE: Polarized Embedding for Signed Networks
• Network Structure Inference, A Survey: Motivations, Methods, and Applications
• Exploiting the Structure of Bipartite Graphs for Algebraic and Spectral Graph Theory Applications
• Structural differences between open and direct communication in an online community
• Capturing Edge Attributes via Network Embedding
• Prediction Methods and Applications in the Science of Science: A Survey
• Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Predicting hyperlinks via hypernetwork loop structure
• The maximum capability of a topological feature in link prediction
• A new measure for community structures through indirect social connections
• Coloring in the Links: Capturing Social Ties as They are Perceived
• Predicting disease-related genes by path-based similarity and community structure in protein-protein interaction network
• Predicting link directions via a recursive subgraph-based ranking
• Link Prediction Adversarial Attack
• RobustECD: Enhancement of Network Structure for Robust Community Detection
• Bounded link prediction for very large networks
• A novel metric for community detection
• History-dependent percolation on multiplex networks
• Linkage Based Face Clustering via Graph Convolution Network
• Residual or Gate? Towards Deeper Graph Neural Networks for Inductive Graph Representation Learning
• AI-driven Hypergraph Network of Organic Chemistry: Network Statistics and Applications in Reaction Classification
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• Mapping flows on sparse networks with missing links
• Cold Start Similar Artists Ranking with Gravity-Inspired Graph Autoencoders
• Network Alignment
• Exact Single-Source SimRank Computation on Large Graphs
• Bipartite separability and non-local quantum operations on graphs
• Finding missing edges and communities in incomplete networks
• Lower bound of assortativity coefficient in scale-free networks
• A framework for second order eigenvector centralities and clustering coefficients
• Entropy-based link prediction in weighted networks
• How people make friends in social networking sites - A microscopic perspective
• Emergence of scale-free close-knit friendship structure in online social networks
• Influence, originality and similarity in directed acyclic graphs
• Collaborative Filtering Approach to Link Prediction
• Local degree blocking model for link prediction in complex networks
• Metabolic network modularity arising from simple growth processes
• Improving personalized link prediction by hybrid diffusion
• Entropy-based approach to missing-links prediction
• The Similarity of Global Value Chains: A Network-Based Measure
• A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
• Detecting Communities in Tripartite Hypergraphs
• Time series analysis of temporal networks
• Modeling mutual feedback between users and recommender systems
• Detection of core-periphery structure in networks by 3-tuple motifs
• Understanding the network formation pattern for better link prediction
• Counterfactual Learning on Graphs: A Survey
• Higher-order link prediction via local information
• Target Defense Against Link-Prediction-Based Attacks via Evolutionary Perturbations
• Deep Representation Learning for Social Network Analysis
• Predicting the evolution of complex networks via local information
• Neural Link Prediction with Walk Pooling
• Disruption and recovery of the US domestic airline networks during the COVID-19 pandemic
• Online matrix factorization for Markovian data and applications to Network Dictionary Learning
• Attack Tolerance of Link Prediction Algorithms: How to Hide Your Relations in a Social Network
• Embedding and trajectories of temporal networks
• GitHub open source project recommendation system
• Social Network Fusion and Mining: A Survey
• Derivative-variable correlation reveals the structure of dynamical networks
• Link prediction in dynamic networks using random dot product graphs
• Generalized linear models with low rank effects for network data
• Fast asynchronous updating algorithms for k-shell indices
• Link Prediction in Networks with Core-Fringe Data
• Link Prediction in Networks with Nodes Attributes by Similarity Propagation
• Network Representation Learning: Consolidation and Renewed Bearing
• Graph and Network Theory for the analysis of Criminal Networks
• BSAL: A Framework of Bi-component Structure and Attribute Learning for Link Prediction
• Hyperlink prediction via local random walks and Jensen-Shannon divergence
• Beyond Pairwise Interactions: Unveiling the Role of Higher-Order Interactions via Stepwise Reduction
• Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning
• Complex systems: features, similarity and connectivity
• Predicting Anchor Links between Heterogeneous Social Networks
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks
• Link prediction for egocentrically sampled networks
• SSNE: Effective Node Representation for Link Prediction in Sparse Networks
• Inference of Edge Correlations in Multilayer Networks
• Correlations Between Human Mobility and Social Interaction Reveal General Activity Patterns
• Detecting Communities in Complex Networks using an Adaptive Genetic Algorithm and node similarity-based encoding
• Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces
• Semi-supervised network inference using simulated gene expression dynamics
• The Strength of Structural Diversity in Online Social Networks
• Topic-Based Influence Computation in Social Networks under Resource Constraints
• Relation Matters in Sampling: A Scalable Multi-Relational Graph Neural Network for Drug-Drug Interaction Prediction
• Graph link prediction in computer networks using Poisson matrix factorisation
• Higher-order temporal network effects through triplet evolution
• Performance of Local Information Based Link Prediction: A Sampling Perspective
• Privacy Attacks on Network Embeddings
• From random walks to distances on unweighted graphs
• DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication
• Benchmarking Graph Neural Networks on Link Prediction
• Attributed Network Embedding for Incomplete Attributed Networks
• Formational bounds of link prediction in collaboration networks
• A novel similarity measure for mining missing links in long-path networks
• SNoRe: Scalable Unsupervised Learning of Symbolic Node Representations
• Information Evolution in Complex Networks
• Social Catalysts: Characterizing People Who Spark Conversations Among Others
• SkipGNN: Predicting Molecular Interactions with Skip-Graph Networks
• Missing links as a source of seemingly variable constants in complex reaction networks
• GraphAttacker: A General Multi-Task GraphAttack Framework
• Characterizing cycle structure in complex networks
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction
• A perturbation-based approach to identifying potentially superfluous network constituents
• Reconstructing supply networks
• A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions
• Iterative embedding and reweighting of complex networks reveals community structure
• Feature Engineering for Supervised Link Prediction on Dynamic Social Networks
• Towards the cycle structures in complex network: A new perspective
• Edge Balance Ratio: Power Law from Vertices to Edges in Directed Complex Network
• DecLiNe -- Models for Decay of Links in Networks
• Non-submodular Function Maximization subject to a Matroid Constraint, with Applications
• Roles of Ties in Spreading
• Asymmetry of social interactions and its role in link predictability: the case of coauthorship networks
• Extending modularity by capturing the similarity attraction feature in the null model
• Limitations and Alternatives for the Evaluation of Large-scale Link Prediction
• Characterizing Attitudinal Network Graphs through Frustration Cloud
• Edge Proposal Sets for Link Prediction
• Link Prediction in Graphs with Autoregressive Features
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Heterogeneous information network model for equipment-standard system
• Understanding and Predicting Links in Graphs: A Persistent Homology Perspective
• Predicting Small Group Accretion in Social Networks: A topology based incremental approach
• Fundamental Structures in Dynamic Communication Networks
• Automatic Discovery of Families of Network Generative Processes
• Link Prediction Under Imperfect Detection: Collaborative Filtering for Ecological Networks
• Vital Spreaders Identification in Complex Networks with Multi-Local Dimension
• Reconstructing Sparse Multiplex Networks with Application to Covert Networks
• Representative Methods of Computational Socioeconomics
• Time-Series Snapshot Network for Partner Recommendation: A Case Study on OSS
• Line Graph Neural Networks for Link Prediction
• Next Waves in Veridical Network Embedding
• Weighted network estimation by the use of topological graph metrics
• A Unified Framework for Community Detection and Network Representation Learning
• "Conjectural" links in complex networks
• RankMerging: A supervised learning-to-rank framework to predict links in large social network
• The graphical structure of respondent-driven sampling
• A generalized theory of preferential linking
• Correlation between social proximity and mobility similarity
• Sampled in Pairs and Driven by Text: A New Graph Embedding Framework
• Revealing missing parts of the interactome
• DeepNC: Deep Generative Network Completion
• Determinable and interpretable network representation for link prediction
• The Atlas for the Aspiring Network Scientist
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Projectivity revisited
• Link Prediction via controlling the leading eigenvector
• Whether Information Network Supplements Friendship Network
• A Mixture Model to Detect Edges in Sparse Co-expression Graphs
• Hybrid Movie Recommender System based on Resource Allocation
• TSAM: Temporal Link Prediction in Directed Networks based on Self-Attention Mechanism
• Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
• The NOESIS Network-Oriented Exploration, Simulation, and Induction System
• Predicting missing links via correlation between nodes
• Uncovering multi-technology convergence patterns with hypergraphs: Evolution and prediction using patent data
• Outlier Edge Detection Using Random Graph Generation Models and Applications
• Using Proximity to Predict Activity in Social Networks
• Dynamic patterns of knowledge flows across technological domains: empirical results and link prediction
• On consistent vertex nomination schemes
• Graphon Estimation from Partially Observed Network Data
• From the Grid to the Smart Grid, Topologically
• Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem
• A Friendship Privacy Attack on Friends and 2-Distant Neighbors in Social Networks
• Discriminative Link Prediction using Local Links, Node Features and Community Structure
• Community Specific Temporal Topic Discovery from Social Media
• Inferring High Quality Co-Travel Networks
• Predicting kills in Game of Thrones using network properties
• SimBins: An information-theoretic approach to link prediction in real multiplex networks
• Unsupervised Hierarchical Grouping of Knowledge Graph Entities
• Adaptive Similarity Function with Structural Features of Network Embedding for Missing Link Prediction
• Multiple predator based capture process on complex networks
• Inductive Subgraph Embedding for Link Prediction
• On the Role of Triadic Substructures in Complex Networks
• Adaptive Candidate Generation for Scalable Edge-discovery Tasks on Data Graphs
• Dynamical networks reconstructed from time series
• Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
• Link Prediction in Bipartite Networks
• Spline tie-decay temporal networks
• A generalized motif-based Naïve Bayes model for sign prediction in complex networks
• Learning-based Privacy-Preserving Graph Publishing Against Sensitive Link Inference Attacks
• A Complex Network Approach for Collaborative Recommendation
• Who will accept my request? Predicting response of link initiation in two-way relation networks
• Competition Between Homophily and Information Entropy Maximization in Social Networks
• Heuristics for Link Prediction in Multiplex Networks
• DINE: A Framework for Deep Incomplete Network Embedding
• TempNodeEmb:Temporal Node Embedding considering temporal edge influence matrix
• Data reliability in complex directed networks
• Meta-Path Constrained Random Walk Inference for Large-Scale Heterogeneous Information Networks
• NEW: A Generic Learning Model for Tie Strength Prediction in Networks
• Computation of K-Core Decomposition on Giraph
• NPGLM: A Non-Parametric Method for Temporal Link Prediction
• Signed Node Relevance Measurements
• Reconstructing propagation networks with temporal similarity metrics
• Estimating Failure in Brittle Materials using Graph Theory
• FCNHSMRA_HRS: Improve the performance of the movie hybrid recommender system using resource allocation approach
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks
• Transformation of Node to Knowledge Graph Embeddings for Faster Link Prediction in Social Networks
• Effective Model Integration Algorithm for Improving Link and Sign Prediction in Complex Networks
• Causal Effects with Hidden Treatment Diffusion on Observed or Partially Observed Networks
• High-order joint embedding for multi-level link prediction
• Limits of PageRank-based ranking methods in sports data
• Investigating Negative Interactions in Multiplex Networks: A Mutual Information Approach
• Community Preserved Social Graph Publishing with Node Differential Privacy
• How Random are Online Social Interactions?
• A comparative analysis of local network similarity measurements: application to author citation networks
• Complex network prediction using deep learning
• Detecting new edge types in a temporal network model
• A study on the performance of similarity indices and its relationship with link prediction: a two-state random network case
• Differentially Private Link Prediction With Protected Connections
• A Holistic Approach for Predicting Links in Coevolving Multilayer Networks
• Hierarchical Hyperlink Prediction for the WWW
• Enhancing Information Dissemination in Dynamic Wireless Network using Stability and Beamforming
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• Discriminative Distance-Based Network Indices with Application to Link Prediction
• GraphFederator: Federated Visual Analysis for Multi-party Graphs
• Nonparametric estimation of the preferential attachment function from one network snapshot
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods
• Dependence of variance on covariate design in nonparametric link regression
• Hidden space reconstruction inspires link prediction in complex networks
• Promotion and resignation in employee networks
• Hyperlink Regression via Bregman Divergence
• Inferring the time-varying functional connectivity of large-scale computer networks from emitted events
• Robustness of link prediction under network attacks
• Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
• A Game-Theoretic Algorithm for Link Prediction
• Semisupervised Learning on Heterogeneous Graphs and its Applications to Facebook News Feed
• Discrimination universally determines reconstruction of multiplex networks
• Adversarial Training Methods for Network Embedding
• Providing a Link Prediction Model based on Structural and Homophily Similarity in Social Networks
• From Cities to Series: Complex Networks and Deep Learning for Improved Spatial and Temporal Analytics*
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Enhancing countries' fitness with recommender systems on the international trade network
• Link Analysis meets Ontologies: Are Embeddings the Answer?
• LlamaFur: Learning Latent Category Matrix to Find Unexpected Relations in Wikipedia
• Can banks default overnight? Modeling endogenous contagion on O/N interbank market
• Spring-Electrical Models For Link Prediction
• Modeling Node Exposure for Community Detection in Networks
• A Fast Parallel Approach for Neighborhood-based Link Prediction by Disregarding Large Hubs
• PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction
• Log-Normal Matrix Completion for Large Scale Link Prediction
• DiffQue: Estimating Relative Difficulty of Questions in Community Question Answering Services
• Node similarity distribution of complex networks and its application in link prediction
• Feature Learning for Meta-Paths in Knowledge Graphs
• Multi-Class and Multi-Task Strategies for Neural Directed Link Prediction
• Network representation learning: A macro and micro view
• Impacts of Data Splitting Strategies on Parameterized Link Prediction Algorithms
• Domain matters: Towards domain-informed evaluation for link prediction
• A Survey on GNN-based Link Prediction: Techniques, Applications, and Challenges
• Measuring Contextual Relationships in Temporal Social Networks by Circle Link
• Personalized Degrees: Effects on Link Formation in Dynamic Networks from an Egocentric Perspective