An Approach for Link Prediction in Directed Complex Networks based on Asymmetric Similarity-Popularity

• URL: http://arxiv.org/abs/2207.07399v1
• Date: Fri, 15 Jul 2022 11:03:25 GMT
• Title: An Approach for Link Prediction in Directed Complex Networks based on Asymmetric Similarity-Popularity
• Authors: Hafida Benhidour, Lama Almeshkhas, Said Kerrache
• Abstract summary: This paper introduces a link prediction method designed explicitly for directed networks. It is based on the similarity-popularity paradigm, which has recently proven successful in undirected networks. The algorithms approximate the hidden similarities as shortest path distances using edge weights that capture and factor out the links' asymmetry and nodes' popularity.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complex networks are graphs representing real-life systems that exhibit unique characteristics not found in purely regular or completely random graphs. The study of such systems is vital but challenging due to the complexity of the underlying processes. This task has nevertheless been made easier in recent decades thanks to the availability of large amounts of networked data. Link prediction in complex networks aims to estimate the likelihood that a link between two nodes is missing from the network. Links can be missing due to imperfections in data collection or simply because they are yet to appear. Discovering new relationships between entities in networked data has attracted researchers' attention in various domains such as sociology, computer science, physics, and biology. Most existing research focuses on link prediction in undirected complex networks. However, not all real-life systems can be faithfully represented as undirected networks. This simplifying assumption is often made when using link prediction algorithms but inevitably leads to loss of information about relations among nodes and degradation in prediction performance. This paper introduces a link prediction method designed explicitly for directed networks. It is based on the similarity-popularity paradigm, which has recently proven successful in undirected networks. The presented algorithms handle the asymmetry in node relationships by modeling it as asymmetry in similarity and popularity. Given the observed network topology, the algorithms approximate the hidden similarities as shortest path distances using edge weights that capture and factor out the links' asymmetry and nodes' popularity. The proposed approach is evaluated on real-life networks, and the experimental results demonstrate its effectiveness in predicting missing links across a broad spectrum of networked data types and sizes.

Related papers

• Fitting Low-rank Models on Egocentrically Sampled Partial Networks [4.111899441919165]
  We propose an approach to fit general low-rank models for egocentrically sampled networks. This method offers the first theoretical guarantee for egocentric partial network estimation. We evaluate the technique on several synthetic and real-world networks and show that it delivers competitive performance in link prediction tasks.
  arXiv  Detail & Related papers  (2023-03-09T03:20:44Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• TeleGraph: A Benchmark Dataset for Hierarchical Link Prediction [11.051062214108894]
  Link prediction is a key problem for network-structured data, attracting considerable research efforts owing to its diverse applications. We present a new benchmark dataset TeleGraph, a highly sparse and hierarchical telecommunication network associated with rich node attributes. Our empirical results suggest that most of the algorithms fail to produce a satisfactory performance on a nearly tree-like dataset.
  arXiv  Detail & Related papers  (2022-04-16T03:01:10Z)
• BScNets: Block Simplicial Complex Neural Networks [79.81654213581977]
  Simplicial neural networks (SNN) have recently emerged as the newest direction in graph learning. We present Block Simplicial Complex Neural Networks (BScNets) model for link prediction. BScNets outperforms state-of-the-art models by a significant margin while maintaining low costs.
  arXiv  Detail & Related papers  (2021-12-13T17:35:54Z)
• Adversarial Robustness of Probabilistic Network Embedding for Link Prediction [24.335469995826244]
  We study adversarial robustness of Conditional Network Embedding (CNE) for link prediction. We measure the sensitivity of the link predictions of the model to small adversarial perturbations of the network. Our approach allows one to identify the links and non-links in the network that are most vulnerable to such perturbations.
  arXiv  Detail & Related papers  (2021-07-05T11:07:35Z)
• Unveiling Anomalous Edges and Nominal Connectivity of Attributed Networks [53.56901624204265]
  The present work deals with uncovering anomalous edges in attributed graphs using two distinct formulations with complementary strengths. The first relies on decomposing the graph data matrix into low rank plus sparse components to improve markedly performance. The second broadens the scope of the first by performing robust recovery of the unperturbed graph, which enhances the anomaly identification performance.
  arXiv  Detail & Related papers  (2021-04-17T20:00:40Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Link prediction in multiplex networks via triadic closure [0.9329978164030673]
  Link prediction algorithms can help to understand the structure and dynamics of complex systems. We show that different kind of relational data can be exploited to improve the prediction of new links. We propose a novel link prediction algorithm by generalizing the Adamic-Adar method to multiplex networks composed by an arbitrary number of layers.
  arXiv  Detail & Related papers  (2020-11-16T20:25:08Z)
• Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction [69.1473775184952]
  We introduce a realistic problem of few-shot out-of-graph link prediction. We tackle this problem with a novel transductive meta-learning framework. We validate our model on multiple benchmark datasets for knowledge graph completion and drug-drug interaction prediction.
  arXiv  Detail & Related papers  (2020-06-11T17:42:46Z)
• Link Prediction for Temporally Consistent Networks [6.981204218036187]
  Link prediction estimates the next relationship in dynamic networks. The use of adjacency matrix to represent dynamically evolving networks limits the ability to analytically learn from heterogeneous, sparse, or forming networks. We propose a new method of canonically representing heterogeneous time-evolving activities as a temporally parameterized network model.
  arXiv  Detail & Related papers  (2020-06-06T07:28:03Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.