Effective and Efficient Similarity Index for Link Prediction of Complex Networks

Abstract

Predictions of missing links of incomplete networks like protein-protein interaction networks or very likely but not yet existent links in evolutionary networks like friendship networks in web society can be considered as a guideline for further experiments or valuable information for web users. In this paper, we introduce a local path index to estimate the likelihood of the existence of a link between two nodes. We propose a network model with controllable density and noise strength in generating links, as well as collect data of six real networks. Extensive numerical simulations on both modeled networks and real networks demonstrated the high effectiveness and efficiency of the local path index compared with two well-known and widely used indices, the common neighbors and the Katz index. Indeed, the local path index provides competitively accurate predictions as the Katz index while requires much less CPU time and memory space, which is therefore a strong candidate for potential practical applications in data mining of huge-size networks.

8 pages, 5 figures, 3 tables

References in corpus (17)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Finding community structure in networks using the eigenvectors of matrices
• Evolution of networks
• Characterization of complex networks: A survey of measurements
• Hierarchical structure and the prediction of missing links in networks
• Clustering and preferential attachment in growing networks
• Predicting Missing Links via Local Information
• How to project a bipartite network?
• Vertex similarity in networks
• Heat Conduction Process on Community Networks as a Recommendation Model
• Effect of initial configuration on network-based recommendation
• Recommendation model based on opinion diffusion
• Information filtering based on transferring similarity
• Role-similarity based functional prediction in networked systems: Application to the yeast proteome

Cited by in corpus (71)

• Link Prediction in Complex Networks: A Survey
• Recommender Systems
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• Link Prediction Based on Local Random Walk
• Link prediction in complex networks: a local na\"ıve Bayes model
• Progresses and Challenges in Link Prediction
• Link Prediction with Node Clustering Coefficient
• Predicting missing links and their weights via reliable-route-based method
• Link Prediction via Matrix Completion
• Link prediction via linear optimization
• Information filtering via preferential diffusion
• Removing spurious interactions in complex networks
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• A new information dimension of complex networks
• Link prediction based on path entropy
• Highly accurate recommendation algorithm based on high-order similarities
• Uncovering missing links with cold ends
• Playing the role of weak clique property in link prediction: A friend recommendation model
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Review on Learning and Extracting Graph Features for Link Prediction
• Attacking Similarity-Based Link Prediction in Social Networks
• Reconstructing networks
• An improved HeatS+ProbS hybrid recommendation algorithm based on heterogeneous initial resource configurations
• Similarity-Based Classification in Partially Labeled Networks
• Predicting missing links via significant paths
• Coarse Graining for Synchronization in Directed Networks
• Improving link prediction in complex networks by adaptively exploiting multiple structural features of networks
• The maximum capability of a topological feature in link prediction
• Predicting disease-related genes by path-based similarity and community structure in protein-protein interaction network
• RobustECD: Enhancement of Network Structure for Robust Community Detection
• Improving local clustering based top-L link prediction methods via asymmetrical link clustering information
• Enhancing community detection by local structural information
• A Network Science perspective of Graph Convolutional Networks: A survey
• Finding missing edges and communities in incomplete networks
• Entropy-based link prediction in weighted networks
• Collaborative Filtering Approach to Link Prediction
• 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
• Understanding the network formation pattern for better link prediction
• Time series analysis of temporal networks
• Information Filtering on Coupled Social Networks
• Predicting the evolution of complex networks via local information
• Optimal transport on supply-demand networks
• Inferring Network Structure with Unobservable Nodes from Time Series Data
• A novel similarity measure for mining missing links in long-path networks
• Information Evolution in Complex Networks
• Higher-order temporal network effects through triplet evolution
• Performance of Local Information Based Link Prediction: A Sampling Perspective
• SkipGNN: Predicting Molecular Interactions with Skip-Graph Networks
• Limitations and Alternatives for the Evaluation of Large-scale Link Prediction
• Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network
• Cliques in complex networks reveal link formation and community evolution
• Link Prediction via controlling the leading eigenvector
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• Predicting missing links via correlation between nodes
• A generalized method toward drug-target interaction prediction via low-rank matrix projection
• Recommending Given Names
• Learning-based link prediction analysis for Facebook100 network
• Understanding the Design Principles of Link Prediction in Directed Settings
• Link Prediction in Bipartite Networks
• SimBins: An information-theoretic approach to link prediction in real multiplex networks
• Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks
• Differentially Private Link Prediction With Protected Connections
• Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
• Robustness of link prediction under network attacks
• Node similarity distribution of complex networks and its application in link prediction
• Co-embedding of Nodes and Edges with Graph Neural Networks
• Domain matters: Towards domain-informed evaluation for link prediction
• A Preference Random Walk Algorithm for Link Prediction through Mutual Influence Nodes in Complex Networks
• Hierarchical Hyperlink Prediction for the WWW
• Sparse Nonnegative Matrix Factorization for Multiple Local Community Detection