Link prediction via linear optimization

Abstract Link prediction is an elemental challenge in network science, which has already found applications in guiding laboratorial experiments, digging out drug targets, recommending online friends, probing network evolution mechanisms, and so on. With a simple assumption that the likelihood of the existence of a link between two nodes can be unfolded by a linear summation of neighboring nodes’ contributions, we obtain the analytical solution of the optimal likelihood matrix, which shows remarkably better performance in predicting missing links than the state-of-the-art algorithms for not only simple networks, but also weighted and directed networks. To our surprise, even some degenerated local similarity indices from the solution outperform well-known local indices, which largely refines our knowledge, for example, the number of 3-hop paths between two nodes more accurately predicts missing links than the number of 2-hop paths (i.e., the number of common neighbors), while in previous methods, longer paths are always considered to be less important than shorter paths.

• Publication year

  2018

• Venue

  Physica A: Statistical Mechanics and its Applications

• Publication date

  2018-03-31

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.physa.2019.121319arXiv 1804.00124
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Exploratory Social Network Analysis with Pajek: Revised and Expanded Edition for Updated Software

  2018cited by this paper
• Network-based prediction of protein interactions

  2018cited by this paper
• Mastering the game of Go without human knowledge

  2017cited by this paper
• Link prediction in complex networks via matrix perturbation and decomposition

  2017cited by this paper
• Predicting missing links and identifying spurious links via likelihood analysis

  2016cited by this paper
• Vital nodes identification in complex networks

  2016cited by this paper
• Link Prediction in Weighted Networks: A Weighted Mutual Information Model

  2016cited by this paper
• Influence of edge weight on node proximity based link prediction methods: An empirical analysis

  2016cited by this paper
• Link prediction via matrix completion

  2016cited by this paper
• A Review of Relational Machine Learning for Knowledge Graphs

  2015cited by this paper
• A positive-negative mode of population covariation links brain connectivity, demographics and behavior

  2015cited by this paper
• Toward link predictability of complex networks

  2015cited by this paper
• Predicting link directions using local directed path

  2015cited by this paper
• Prediction of Links and Weights in Networks by Reliable Routes

  2015cited by this paper
• Measuring multiple evolution mechanisms of complex networks

  2014cited by this paper
• Recommender Systems: Kembellec/Recommender Systems

  2014cited by this paper
• Similarity-based machine learning methods for predicting drug-target interactions: a brief review

  2014cited by this paper
• From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks

  2013cited by this paper
• Outsourcing Large Matrix Inversion Computation to A Public Cloud

  2013cited by this paper
• Network link prediction by global silencing of indirect correlations

  2013cited by this paper
• Friendship prediction and homophily in social media

  2012cited by this paper
• Recommender Systems

  2012cited by this paper
• Potential Theory for Directed Networks

  2012cited by this paper
• Sparse Subspace Clustering: Algorithm, Theory, and Applications

  2012cited by this paper
• Predicting link directions via a recursive subgraph-based ranking

  2012cited by this paper
• Evaluating network models: A likelihood analysis

  2011cited by this paper
• Supervised link prediction in weighted networks

  2011cited by this paper
• Networks: An Introduction

  2010cited by this paper
• Robust Recovery of Subspace Structures by Low-Rank Representation

  2010cited by this paper
• Link prediction in weighted networks: The role of weak ties

  2010cited by this paper
• Supervised random walks: predicting and recommending links in social networks

  2010cited by this paper
• Predicting positive and negative links in online social networks

  2010cited by this paper
• Link Prediction in Complex Networks: A Survey

  2010cited by this paper
• Governance in Social Media: A Case Study of the Wikipedia Promotion Process

  2010cited by this paper
• Missing and spurious interactions and the reconstruction of complex networks

  2009cited by this paper
• Similarity index based on local paths for link prediction of complex networks.

  2009cited by this paper
• Predicting missing links via local information

  2009cited by this paper
• Estimating the size of the human interactome

  2008influential reference
• Accurate and diverse recommendations via eliminating redundant correlations

  2008cited by this paper
• Hierarchical structure and the prediction of missing links in networks

  2008cited by this paper
• Link Prediction of Social Networks Based on Weighted Proximity Measures

  2007influential reference
• New uses for old drugs

  2007cited by this paper
• Relational Dependency Networks

  2007cited by this paper
• R1-PCA: rotational invariant L1-norm principal component analysis for robust subspace factorization

  2006cited by this paper
• Power-law strength-degree correlation from resource-allocation dynamics on weighted networks.

  2006cited by this paper
• Stochastic Relational Models for Discriminative Link Prediction

  2006cited by this paper
• Clustering in complex directed networks.

  2006cited by this paper
• Empirical Analysis of an Evolving Social Network

  2006cited by this paper
• Weak links : stabilizers of complex systems from proteins to social networks

  2006cited by this paper
• The political blogosphere and the 2004 U.S. election: divided they blog

  2005cited by this paper
• Analysis of weighted networks.

  2004cited by this paper
• Measuring ISP topologies with Rocketfuel

  2004cited by this paper
• Evaluating collaborative filtering recommender systems

  2004cited by this paper
• Korean university life in a network perspective: Dynamics of a large affiliation network

  2004cited by this paper
• The link prediction problem for social networks

  2003cited by this paper
• The architecture of complex weighted networks.

  2003cited by this paper
• Friends and neighbors on the Web

  2003cited by this paper
• Assortative mixing in networks.

  2002cited by this paper
• Measuring ISP topologies with rocketfuel

  2002cited by this paper
• Birds of a Feather: Homophily in Social Networks

  2001cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• Ridge Regression: Biased Estimation for Nonorthogonal Problems

  2000cited by this paper
• Emergence of scaling in random networks

  1999influential reference
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• The meaning and use of the area under a receiver operating characteristic (ROC) curve.

  1982cited by this paper
• A new status index derived from sociometric analysis

  1953cited by this paper
• Measurement of Diversity

  1949cited by this paper

• Predictability of complex systems

  2026cites this paper
• LDComKG: an LLM-powered dual-enhanced framework for community-aware knowledge graph completion in traditional Chinese medicine

  2026cites this paper
• Graph regularized symmetric non-negative matrix factorization with degree-related spectral clustering and topological structure for link prediction in complex network

  2025influential citation
• Dual graph regularized nonnegative matrix factorization with node attributes and higher-order structure for link prediction in attributed networks

  2025cites this paper
• Link prediction using motif-based dual graph-regularized autoencoder-like non-negative matrix factorization

  2025cites this paper
• Collaborative filtering enhanced subgraph embedding for link direction and sign prediction

  2025cites this paper
• SDN Controller Fault Recovery Strategy Based on Improved Sparrow Search Algorithm

  2025cites this paper
• LRTM: Left-Right Transition Matrices for Molecular Association Prediction

  2025cites this paper
• Link prediction in directed networks using Hits centrality and biased random walks

  2025cites this paper
• Quantifying discriminability of evaluation metrics in link prediction for real networks

  2025cites this paper
• Statistical link prediction comparison based on the similarity for MEG networks of epilepsy patients

  2025cites this paper
• Domain matters: Towards domain-informed evaluation for link prediction

  2025cites this paper
• Neighbor-Enhanced Link Prediction in Bipartite Networks

  2025cites this paper
• Pairwisely constrained symmetric non-negative matrix factorization for link prediction in complex networks using degree-related clustering coefficient and improved closeness centrality

  2025influential citation
• A unified temporal link prediction framework based on nonnegative matrix factorization and graph regularization

  2025cites this paper
• Hypergraph Foundation Model for Brain Disease Diagnosis

  2025cites this paper
• Common Neighbor Completion with Information Entropy for Link Prediction in Social Networks

  2025cites this paper
• Link prediction in bipartite networks via deep autoencoder-like nonnegative matrix factorization

  2025cites this paper
• An extended self-representation model of complex networks for link prediction

  2024cites this paper
• Hypergraph modeling and hypergraph multi-view attention neural network for link prediction

  2024cites this paper
• Uncovering multi-order Popularity and Similarity Mechanisms in Link Prediction by graphlet predictors

  2024cites this paper
• TLFSL: link prediction in multilayer social networks using trustworthy Lévy-flight semi-local random walk

  2024cites this paper
• Link prediction in protein-protein interaction network: A similarity multiplied similarity algorithm with paths of length three.

  2024cites this paper
• Link prediction using deep autoencoder-like non-negative matrix factorization with L21-norm

  2024cites this paper
• Graph regularized autoencoding-inspired non-negative matrix factorization for link prediction in complex networks using clustering information and biased random walk

  2024cites this paper
• Self-Similar Growth and Synergistic Link Prediction in Technology-Convergence Networks: The Case of Intelligent Transportation Systems

  2023cites this paper
• Link Prediction using GraphSAGE

  2023cites this paper
• Link prediction in bipartite networks via effective integration of explicit and implicit relations

  2023cites this paper
• Missing link prediction using path and community information

  2023cites this paper
• HEM: An Improved Parametric Link Prediction Algorithm Based on Hybrid Network Evolution Mechanism

  2023cites this paper
• Link prediction in complex network using information flow

  2023cites this paper
• Leveraging Node Attributes for Link Prediction via Meta-path Based Proximity

  2023cites this paper
• A Signed Subgraph Encoding Approach via Linear Optimization for Link Sign Prediction

  2023influential citation
• A comprehensive framework for link prediction in multiplex networks

  2023cites this paper
• Normalized L3-based link prediction in protein–protein interaction networks

  2023cites this paper
• Link prediction and its optimization based on low-rank representation of network structures

  2023cites this paper
• Personalized recommender systems based on social relationships and historical behaviors

  2023cites this paper
• Efficient link prediction model for real-world complex networks using matrix-forest metric with local similarity features

  2022cites this paper
• Path extension similarity link prediction method based on matrix algebra in directed networks

  2022cites this paper
• Multiple Order Local Information model for link prediction in complex networks

  2022cites this paper
• PWAF : Path Weight Aggregation Feature for link prediction in dynamic networks

  2022cites this paper
• Personalized recommendation system based on social relationships and historical behaviors

  2022cites this paper
• Forecasting the future of artificial intelligence with machine learning-based link prediction in an exponentially growing knowledge network

  2022cites this paper
• Hill Climbing-Based Efficient Model for Link Prediction in Undirected Graphs

  2022cites this paper
• On the complexity of quantum link prediction in complex networks

  2022cites this paper
• Generative Graph Neural Networks for Link Prediction

  2022cites this paper
• Prediction of virus-receptor interactions based on multi-view learning and link prediction

  2022cites this paper
• Progresses and challenges in link prediction

  2021influential citation
• Link prediction by deep non-negative matrix factorization

  2021cites this paper
• A Link Prediction Algorithm Combining Node Influence and New Biased Random Walk

  2021cites this paper
• Attributed Graph Neural Networks for Recommendation Systems on Large-Scale and Sparse Graph

  2021cites this paper
• Link Prediction Based on the Derivation of Mapping Entropy

  2021cites this paper
• A Social Network Link Prediction Method Based on Stacked Generalization

  2021cites this paper
• Diffusion profile embedding as a basis for graph vertex similarity

  2021cites this paper
• A Link Prediction Method Based on Neural Networks

  2021cites this paper
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks

  2021cites this paper
• How to predict crime — informatics-inspired approach from link prediction

  2021cites this paper
• Towards link inference attack against network structure perturbation

  2021cites this paper
• Link Prediction via controlling the leading eigenvector

  2021cites this paper
• Collaborative Filtering Approach to Link Prediction

  2021cites this paper
• NetSRE: Link predictability measuring and regulating

  2020cites this paper
• Identifying Influential Nodes in Social Networks Based on Social Strength

  2020cites this paper
• Path-based extensions of local link prediction methods for complex networks

  2020cites this paper
• SSNE: Effective Node Representation for Link Prediction in Sparse Networks

  2020cites this paper
• DeepEC: Adversarial attacks against graph structure prediction models

  2020cites this paper
• Missing links as a source of seemingly variable constants in complex reaction networks

  2020cites this paper
• Predicting missing links in directed complex networks: A linear programming method

  2020cites this paper
• Taxonomy of Link Prediction for Social Network Analysis: A Review

  2020cites this paper
• A Gaussian Kernel Similarity-Based Linear Optimization Model for Predicting miRNA-lncRNA Interactions

  2020cites this paper
• Graph embedding-based novel protein interaction prediction via higher-order graph convolutional network

  2020cites this paper
• Mining Missing Links in Directed Social Networks based on Significant Motifs

  2020cites this paper
• Hybrid link prediction via model averaging

  2020cites this paper
• Predicting missing links in directed networks based on local network structure and investment theory

  2020cites this paper
• Protein Interface Complementarity and Gene Duplication Improve Link Prediction of Protein-Protein Interaction Network

  2020influential citation
• Link prediction techniques, applications, and performance: A survey

  2020cites this paper
• Link prediction in complex networks based on Significance of Higher-Order Path Index (SHOPI)

  2020cites this paper
• Relative-path-based algorithm for link prediction on complex networks using a basic similarity factor.

  2020cites this paper
• Link prediction based on linear dynamical response

  2019cites this paper
• LNRLMI: Linear neighbour representation for predicting lncRNA‐miRNA interactions

  2019cites this paper
• Structural Predictability Optimization Against Inference Attacks in Data Publishing

  2019cites this paper
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms

  2019cites this paper
• Temporal Link Prediction: A Survey

  2019cites this paper
• Alignment of Protein Interaction Networks and Disease Prediction: A Survey

  2019cites this paper
• Quantum Link Prediction in Complex Networks

  2019influential citation
• LOMDA: Linear optimization for miRNA-disease association prediction

  2019cites this paper
• Network-based prediction of protein interactions

  2018cites this paper
• Network Reconstruction and Controlling Based on Structural Regularity Analysis

  2018cites this paper
• ODU Digital Commons ODU Digital Commons

  year unknowncites this paper