Predicting Missing Links via Local Information

Abstract

Missing link prediction of networks is of both theoretical interest and practical significance in modern science. In this paper, we empirically investigate a simple framework of link prediction on the basis of node similarity. We compare nine well-known local similarity measures on six real networks. The results indicate that the simplest measure, namely common neighbors, has the best overall performance, and the Adamic-Adar index performs the second best. A new similarity measure, motivated by the resource allocation process taking place on networks, is proposed and shown to have higher prediction accuracy than common neighbors. It is found that many links are assigned same scores if only the information of the nearest neighbors is used. We therefore design another new measure exploited information of the next nearest neighbors, which can remarkably enhance the prediction accuracy.

For International Workshop: "The Physics Approach To Risk: Agent-Based Models and Networks", http://intern.sg.ethz.ch/cost-p10/

References in corpus (32)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Efficient Behavior of Small-World Networks
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• The architecture of complex weighted networks
• Hierarchical organization of modularity in metabolic networks
• Evolution of networks
• Specificity and stability in topology of protein networks
• Characterization of complex networks: A survey of measurements
• Hierarchical structure and the prediction of missing links in networks
• Hierarchical Organization in Complex Networks
• Attack vulnerability of complex networks
• How to project a bipartite network?
• Detecting rich-club ordering in complex networks
• Vertex similarity in networks
• Synchronization reveals topological scales in complex networks
• Modeling the Internet's Large-Scale Topology
• The Rich-Club Phenomenon In The Internet Topology
• The spatial structure of networks
• Statistical Analysis of Airport Network of China
• Traffic on complex networks: Towards understanding global statistical properties from microscopic density fluctuations
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Effect of initial configuration on network-based recommendation
• Scale-free networks without growth
• Information filtering based on transferring similarity
• Structural constraints in complex networks
• Synchronization on community networks
• Disassortative mixing in online social networks
• A general model for collaboration networks

Cited by in corpus (204)

• Link Prediction in Complex Networks: A Survey
• Recommender Systems
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Link Prediction Based on Local Random Walk
• Identifying influential spreaders in complex networks based on gravity formula
• Link Prediction Based on Graph Neural Networks
• An Evolutionary Algorithm Approach to Link Prediction in Dynamic Social Networks
• Link prediction in complex networks: a local na\"ıve Bayes model
• Identify influential spreaders in complex networks, the role of neighborhood
• Stacking Models for Nearly Optimal Link Prediction in Complex 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
• Ultra accurate personalized recommendation via eliminating redundant correlations
• Network-based recommendation algorithms: A review
• Information filtering via preferential diffusion
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Bridgeness: A Local Index on Edge Significance in Maintaining Global Connectivity
• Collaborative filtering with diffusion-based similarity on tripartite graphs
• Link Prediction in Multiplex Networks based on Interlayer Similarity
• Predicting the Future of AI with AI: High-quality link prediction in an exponentially growing knowledge network
• Removing spurious interactions in complex networks
• Finding missing edges in networks based on their community structure
• Collaboration-Aware Graph Convolutional Network for Recommender Systems
• Link Prediction in Complex Networks: A Clustering Perspective
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• People are Strange when you're a Stranger: Impact and Influence of Bots on Social Networks
• Big Networks: A Survey
• Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
• Evaluating user reputation in online rating systems via an iterative group-based ranking method
• Highly accurate recommendation algorithm based on high-order similarities
• Link prediction based on path entropy
• Data Mining on Social Interaction Networks
• Uncovering missing links with cold ends
• Solving the accuracy-diversity dilemma via directed random walks
• Link prediction with hyperbolic geometry
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Review on Learning and Extracting Graph Features for Link Prediction
• HPRA: Hyperedge Prediction using Resource Allocation
• A vertex similarity index for better personalized recommendation
• Information filtering via hybridization of similarity preferential diffusion processes
• Attacking Similarity-Based Link Prediction in Social Networks
• Effect of user tastes on personalized recommendation
• A trust-based recommendation method using network diffusion processes
• Reconstructing networks
• An improved HeatS+ProbS hybrid recommendation algorithm based on heterogeneous initial resource configurations
• M-Evolve: Structural-Mapping-Based Data Augmentation for Graph Classification
• Accuracy Test for Link Prediction in terms of Similarity Index: The Case of WS and BA Models
• Data Augmentation for Graph Classification
• ECMdd: Evidential c-medoids clustering with multiple prototypes
• Predicting missing links via significant paths
• Similarity-Based Classification in Partially Labeled Networks
• Harnessing the Power of Ego Network Layers for Link Prediction in Online Social Networks
• Coarse Graining for Synchronization in Directed Networks
• E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction
• Structural differences between open and direct communication in an online community
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks
• A Unified Method of Detecting Core-Periphery Structure and Community Structure in Networks
• Prediction Methods and Applications in the Science of Science: A Survey
• The maximum capability of a topological feature in link prediction
• Degree correlation effect of bipartite network on personalized recommendation
• GraphWorld: Fake Graphs Bring Real Insights for GNNs
• Personalized recommendation with corrected similarity
• Predicting link directions via a recursive subgraph-based ranking
• Link Prediction Adversarial Attack
• Bounded link prediction for very large networks
• RobustECD: Enhancement of Network Structure for Robust Community Detection
• Linkage Based Face Clustering via Graph Convolution Network
• Enhancing community detection by local structural information
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling
• Entropy-based link prediction in weighted networks
• Finding missing edges and communities in incomplete networks
• LPFormer: An Adaptive Graph Transformer for Link Prediction
• Diffusion-like recommendation with enhanced similarity of objects
• Link Prediction via Graph Attention Network
• A multi-class approach for ranking graph nodes: models and experiments with incomplete data
• A similarity-based community detection method with multiple prototype representation
• Collaborative Filtering Approach to Link Prediction
• Local degree blocking model for link prediction in complex networks
• Improving personalized link prediction by hybrid diffusion
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
• The Similarity of Global Value Chains: A Network-Based Measure
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Understanding the network formation pattern for better link prediction
• Target Defense Against Link-Prediction-Based Attacks via Evolutionary Perturbations
• Predicting the evolution of complex networks via local information
• Measuring similarity in co-occurrence data using ego-networks
• GitHub open source project recommendation system
• Attack Tolerance of Link Prediction Algorithms: How to Hide Your Relations in a Social Network
• Generalized linear models with low rank effects for network data
• Social Network Fusion and Mining: A Survey
• Network Representation Learning: Consolidation and Renewed Bearing
• Gravity Effects on Information Filtering and Network Evolving
• Beyond Pairwise Interactions: Unveiling the Role of Higher-Order Interactions via Stepwise Reduction
• Complex systems: features, similarity and connectivity
• BSAL: A Framework of Bi-component Structure and Attribute Learning for Link Prediction
• Data Considerations in Graph Representation Learning for Supply Chain Networks
• Manipulating Node Similarity Measures in Networks
• Graph Convolutional Gaussian Processes For Link Prediction
• SSNE: Effective Node Representation for Link Prediction in Sparse Networks
• Detecting Communities in Complex Networks using an Adaptive Genetic Algorithm and node similarity-based encoding
• SNoRe: Scalable Unsupervised Learning of Symbolic Node Representations
• Learning Scalable Structural Representations for Link Prediction with Bloom Signatures
• Higher-order temporal network effects through triplet evolution
• Graph-Revised Convolutional Network
• Benchmarking Graph Neural Networks on Link Prediction
• Performance of Local Information Based Link Prediction: A Sampling Perspective
• B-Rank: A top N Recommendation Algorithm
• Towards the cycle structures in complex network: A new perspective
• Inferring network topology via the propagation process
• Learning to Cluster Faces via Transformer
• A comparative study of similarity-based and GNN-based link prediction approaches
• SCGG: A Deep Structure-Conditioned Graph Generative Model
• Asymmetry of social interactions and its role in link predictability: the case of coauthorship networks
• Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• EMH: Extended Mixing H-index centrality for identification important users in social networks based on neighborhood diversity
• Roles of Ties in Spreading
• Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction
• Cliques in complex networks reveal link formation and community evolution
• "Conjectural" links in complex networks
• RankMerging: A supervised learning-to-rank framework to predict links in large social network
• Line Graph Neural Networks for Link Prediction
• A Unified Framework for Community Detection and Network Representation Learning
• Whether Information Network Supplements Friendship Network
• Hybrid Movie Recommender System based on Resource Allocation
• Stability of similarity measurements for bipartite networks
• Link Prediction via controlling the leading eigenvector
• Improving link prediction accuracy of network embedding algorithms via rich node attribute information
• The Atlas for the Aspiring Network Scientist
• Selection Bias Explorations and Debias Methods for Natural Language Sentence Matching Datasets
• Image Retrieval for Structure-from-Motion via Graph Convolutional Network
• Synthetic graphs for link prediction benchmarking
• NODDLE: Node2vec based deep learning model for link prediction
• A generalized method toward drug-target interaction prediction via low-rank matrix projection
• The NOESIS Network-Oriented Exploration, Simulation, and Induction System
• Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
• Uncovering multi-technology convergence patterns with hypergraphs: Evolution and prediction using patent data
• Dynamic patterns of knowledge flows across technological domains: empirical results and link prediction
• Using Proximity to Predict Activity in Social Networks
• Predicting missing links via correlation between nodes
• Adaptive Similarity Function with Structural Features of Network Embedding for Missing Link Prediction
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Bert4XMR: Cross-Market Recommendation with Bidirectional Encoder Representations from Transformer
• Link Prediction and the Role of Stronger Ties in Networks of Face-to-Face Proximity
• Mining Essential Relationships under Multiplex Networks
• Evidential relational clustering using medoids
• SimBins: An information-theoretic approach to link prediction in real multiplex networks
• Reconstructing propagation networks with temporal similarity metrics
• Consistence beats causality in recommender systems
• Measure the similarity of nodes in the complex networks
• Learning-based link prediction analysis for Facebook100 network
• Transforming Graph Representations for Statistical Relational Learning
• Understanding the Design Principles of Link Prediction in Directed Settings
• Block-Approximated Exponential Random Graphs
• Exploring Social Networks for Optimized User Association in Wireless Small Cell Networks with Device-to-Device Communications
• Multi-Label Classification Using Link Prediction
• Evaluating link prediction: New perspectives and recommendations
• Measuring multiple evolution mechanisms of complex networks
• Target Privacy Preserving for Social Networks
• Providing a Link Prediction Model based on Structural and Homophily Similarity in Social Networks
• Effective Model Integration Algorithm for Improving Link and Sign Prediction in Complex Networks
• Correlation-Based Community Detection
• A study on the performance of similarity indices and its relationship with link prediction: a two-state random network case
• Tie Strength in Online Social Networks and its Applications: A Brief Study
• DSSLP: A Distributed Framework for Semi-supervised Link Prediction
• Reducing Controversy by Connecting Opposing Views
• A Holistic Approach for Predicting Links in Coevolving Multilayer Networks
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks
• A Fast Parallel Approach for Neighborhood-based Link Prediction by Disregarding Large Hubs
• Dynamic Clustering and User Association in Wireless Small Cell Networks with Social Considerations
• PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction
• Towards Understanding Link Predictor Generalizability Under Distribution Shifts
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• Robustness of link prediction under network attacks
• Estimating Thematic Similarity of Scholarly Papers with Their Resistance Distance in an Electric Network Model
• Measuring Quadrangle Formation in Complex Networks
• A novel method based on node correlation to evaluate the important nodes in complex networks
• Link prediction on multi-relational graphs from an influence propagation perspective
• Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
• Domain matters: Towards domain-informed evaluation for link prediction
• Role of Weak Ties in Link Prediction of Complex Networks
• A comparative analysis of local network similarity measurements: application to author citation networks
• Node similarity distribution of complex networks and its application in link prediction
• A Novel Methodologyof Router-To-ASMapping inspired by Community Discovery
• Higher-Order Relations Skew Link Prediction in Graphs
• Causal Effects with Hidden Treatment Diffusion on Observed or Partially Observed Networks
• Topological and Temporal Stability Analysis of the Lightning Network
• Impacts of Data Splitting Strategies on Parameterized Link Prediction Algorithms
• Investigating Negative Interactions in Multiplex Networks: A Mutual Information Approach
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods
• Correlation Analysis of Nodes Identifies Real Communities in Networks
• Influence Prediction in Collaboration Networks: An Empirical Study on arXiv
• Graph Neural Networks Based Analog Circuit Link Prediction
• Graph Algorithms for Multiparallel Word Alignment