PaperlayerView exact revision on arXiv

Source-linked AI summary

Common neighbours and the local-community-paradigm for link prediction in bipartite networks

Simone Daminelli, Josephine Maria Thomas, Claudio Durán, Carlo Vittorio Cannistraci

arXiv:1504.07011v2cs.SInlin.AOphysics.soc-ph

TL;DR

A general framework for local-based link prediction directly in bipartite networks is missing. The paper formalizes bipartite common-neighbour and local-community approaches, then reports significant prediction improvements across many bipartite networks.

Abstract

from arXiv · show

Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index (CN) and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.

INTRODUCTION

The introduction formalizes common neighbours and local-community links for bipartite networks and presents parameter-free neighbourhood- and LCP-based prediction models for undirected, unweighted bipartite networks, using quadrangular closure and interactions among common neighbours. It also describes comparison methods and six evaluation networks.

INTRODUCTION

  • Triangle-closing topological methods, including CN and its related indices, are not defined for bipartite networks because of their structural properties.The paper presents the bipartite definitions as addressing this gap.Source: INTRODUCTION · p. 4
  • LCP-theory holds that link prediction should use both common-neighbour information and the topology of interactions among those neighbours, which form a local community.The links among common neighbours are termed local-community links.Source: INTRODUCTION · p. 4
  • The paper defines the bipartite LCP-theory and local-based link-prediction models for undirected, unweighted bipartite networks, including a formal definition of the previously undefined CN index.The authors identify this definition as a necessary first step in extending LCP-theory to bipartite topologies.Source: INTRODUCTION · p. 5

METHODS Definition of CNs and LCP-theory in bipartite networks

  • In bipartite networks, CNs are nodes involved in quadrangular closures between nonadjacent seed nodes, and LCLs are links between those CNs.Quadrangular closure is the bipartite equivalent of triangular closure.Source: METHODS Definition of CNs and… · p. 5
  • For adjacent seed nodes, common neighbours are nodes involved in existing quadrangles through the seeds, and local-community links are links between those common neighbours.Source: METHODS Definition of CNs and… · pp. 5–6

Classical node-neighbourhood-based and LCP-based models for link prediction.

  • The new neighbourhood- and LCP-based bipartite prediction indices are introduced for the first time and are parameter-free.The passages note that only PA and P3 had previously been applied as node-neighbourhood-based local models in bipartite networks.Source: Classical node-neighbourhood-based and… · p. 7

State-of-the-art link prediction methods based on the one-mode-network projections.

  • One-mode projections can lose original bipartite topological information, so the comparisons include projection-based methods and spatial-distance measures.The listed methods include NBI (ProbS), BPR, Jaccard, Euclidean, Cosine, and Pearson.Source: State-of-the-art link prediction… · p. 8

Bipartite Local Model (BLM) for drug-target prediction

  • The Bipartite Local Model predicts novel drug-target interactions as a supervised binary-classification problem using an SVM and interaction kernels.Chemical and protein-sequence similarities inform local models that estimate link likelihood from a drug’s or target’s local neighbours.Source: Bipartite Local Model (BLM) for… · p. 9

Data description

  • Evaluations covered six bipartite networks spanning technological, social, and biological systems, treating directed links as undirected and weighted links as unweighted.The highlighted Ipums network has 267 × 513 nodes and 18,088 interactions.Source: Data description · p. 9

RESULTS AND DISCUSSION

LCP-based predictors significantly outperform classical and one-mode-projection methods across many tested bipartite networks. Their effectiveness is linked to a strong correlation between common neighbours (CNs) and local-community links (LCLs).

RESULTS AND DISCUSSION

  • AUPR assesses how highly a method ranks all removed edges and is considered a more complete and robust performance estimate than precision.The paper cautions that ROC area can be deceptive relative to AUPR.Source: RESULTS AND DISCUSSION · p. 10
  • 123% improvement in precision over classical models and 186% over one-mode-projection methods were reported, with LCP-based models significantly outperforming state-of-the-art methods (p-value <0.001).Improvements evaluated by AUPR were even larger.Source: RESULTS AND DISCUSSION · pp. 10–11
  • Across the three drug-target networks analyzed, LCP-based models provided noteworthy link-prediction performance, despite an expectation that BLM would perform significantly better; BLM uses local network topology plus chemical and sequence similarities.Source: RESULTS AND DISCUSSION · p. 11
  • Across the analyzed bipartite networks, LCP-DP revealed a strong CN–LCL correlation (LCP-corr): LCP theory requires both CNs and LCLs to be high, unlike classical models' CN-only condition.The authors identify this organization as the basis for LCP predictors' effectiveness.Source: RESULTS AND DISCUSSION · p. 12
  • Ion-Channel and Enzymes networks showed nonlinear, irregular LCP-DP structure with discontinuities and large holes, attributed to unsaturation and substantial missing information.Pearson and Spearman correlations were similar in the other analyzed networks.Source: RESULTS AND DISCUSSION · pp. 12–13
  • In Ion-Channel and Enzymes networks, classical methods' performance decreased while LCP-based predictors maintained good performance.The authors present topology-only prediction of molecular interactions as a proof of concept that could inform future hybrid methods using network-level priors for molecular-structure predictions.Source: RESULTS AND DISCUSSION · pp. 11, 13

CONCLUSION

The paper introduces a local-community account of bipartite network structure and a framework for neighborhood-based link prediction directly in the bipartite domain. It presents bipartite common-neighbour and LCP-based methods and notes their potential practical applications.

CONCLUSION

  • The proposed theory identifies the local-community-paradigm (LCP) as a typical organization in many bipartite networks, based on node-neighbourhood connectivity orbiting existing links.Source: CONCLUSION · p. 13
  • Because a general framework for local link prediction in bipartite networks was missing, the authors provide a formalism for neighborhood-based prediction in the bipartite domain for LCP-organized networks.Source: CONCLUSION · p. 13
  • The paper presents first-time bipartite formulations of CN and classical and LCP-based methods, contributing to topological prediction and local-based link-prediction theory in the bipartite domain.Source: CONCLUSION · p. 13
  • The parameter-free models are convenient to apply and may support practical link-formation forecasts, including improving e-commerce or accelerating related processes.Source: CONCLUSION · p. 13

FIGURES

The figures define bipartite common-neighbour and local-community concepts, then visualize link-prediction evaluation and comparisons across networks. Supplementary figures extend the precision and AUPR evaluations, while a supplementary table lists network topology statistics.

FIGURES

  • Figure 1 defines common neighbours and local community links as the nodes and links forming a local community, with bipartite common neighbours providing quadrangular closure.The figure also shows the corresponding monopartite triangular-closure example.Source: Figure 1 · p. 17, FIGURES · p. 17
  • Figures 2 and 3 visualize precision and AUPR for link prediction, including comparisons across six networks and with a baseline supervised method.Figure 2 evaluates prioritization of 10% randomly removed edges over 100 repetitions; Figure 3 reports mean precision and AUPR across six networks and biological-network AUPR comparisons.Source: Figure 2 · p. 18, Figure 3 · p. 19
  • Figure 4 compares mean precision and AUPR for LCP-based methods against classical and one-mode-projection methods across six networks.The captions identify Mann–Whitney testing and note that all compared LCP-based and classical methods except PA are newly proposed for bipartite networks.Source: Figure 4 · p. 20, FIGURES · p. 20
  • Figure 5 plots each existing link by its seed nodes’ common-neighbour count and the number of local-community links between those neighbours.Each plot title reports Pearson and Spearman correlation values.Source: Figure 5 · p. 21, FIGURES · p. 21

SUPPLEMENTARY INFORMATION

  • Supplementary Figure 1 reports precision for recovery of randomly removed edges, averaged over 100 repetitions for each network.The caption defines precision as the ratio of correctly recovered edges among the removed edges.Source: SUPPLEMENTARY INFORMATION · p. 22
  • Supplementary Figures 2 and 3 present AUPR for Enzymes and precision across three biological networks, while Supplementary Table S1 lists topological statistics for six networks.The AUPR and precision means are computed over 100 iterations per network.Source: SUPPLEMENTARY INFORMATION · pp. 23–24, Table S1 · p. 25
Loading 1504.07011v2…