PaperlayerView exact revision on arXiv

Source-linked AI summary

Link Prediction in Complex Networks: A Mutual Information Perspective

Fei Tan, Yongxiang Xia, Boyao Zhu

arXiv:1405.4341v2cs.SIphysics.soc-ph

TL;DR

Link prediction is a long-standing practical problem, while Common Neighbors overlooks differences in the contributions of shared neighbors. The paper proposes a mutual-information approach to network structures and reports that its framework outperforms other prediction methods.

  • Problem

    Common Neighbors counts shared neighbors without distinguishing their contributions, while feature-extraction methods depend on node attributes that are generally hidden and difficult to obtain.

    Source: Introduction · p. 2

  • Method

    The paper presents a general link-prediction approach based on the mutual information of network structures.

    Source: Introduction · p. 3

  • Results

    The proposed framework outperforms other prediction methods greatly.

    Source: Introduction · p. 3

  • Takeaways & Limitations

    The paper treats mutual information of network structures as a practical approach to predicting missing links.

    Source: Introduction · p. 3

    Feature-extraction methods depend on node attributes, which are generally hidden and difficult to obtain.

    Source: Introduction · p. 2

Abstract

from arXiv · show

Topological properties of networks are widely applied to study the link-prediction problem recently. Common Neighbors, for example, is a natural yet efficient framework. Many variants of Common Neighbors have been thus proposed to further boost the discriminative resolution of candidate links. In this paper, we reexamine the role of network topology in predicting missing links from the perspective of information theory, and present a practical approach based on the mutual information of network structures. It not only can improve the prediction accuracy substantially, but also experiences reasonable computing complexity.

Introduction

Link prediction is framed as a long-standing practical problem; the paper recasts topology-based prediction through mutual information and reports that its framework outperforms other prediction methods.

Introduction

  • Link prediction is a long-standing practical issue, and accurate prediction is preferable to blindly checking costly latent interactions.The introduction also notes potential uses in recommending friends and modeling network evolution.Source: Introduction · pp. 1–2
  • Feature-extraction methods in computer science depend on node attributes, which are generally hidden and difficult to obtain.The introduction identifies social and textual features as examples of such attributes.Source: Introduction · p. 2
  • Common Neighbors is a low-complexity, high-accuracy precursor, but it counts common neighbors without distinguishing their contributions.This limitation motivated variants that adjust how neighboring nodes contribute.Source: Introduction · p. 2
  • Adamic-Adar and Resource Allocation weight low-degree common neighbors more heavily, while other methods distinguish neighbor roles or centrality.The introduction also describes preferential attachment and hierarchical structure as prediction signals.Source: Introduction · p. 2
  • The mutual-information framework outperforms other prediction methods greatly.The paper presents it as a general prediction approach based on network structures.Source: Introduction · p. 3

Materials and Methods

The section defines the link-prediction task and evaluation protocol, reviews common-neighbor baselines, and introduces mutual information (MI) as a way to estimate link likelihood using common neighbors. It also illustrates how MI distinguishes candidate links by accounting for shared-neighbor counts and differences in how nodes reduce link uncertainty.

Data and Problem Description

  • Evaluation uses ten datasets from various areas, each with a giant component larger than 1,000 nodes; only giant components are analyzed as undirected simple networks, with links divided 90/10, and AUC used for assessment.Source: Data and Problem Description · pp. 3–4

Previous Prediction Methods

  • The comparison set comprises CN, RA, LNB-CN and LNB-RA, and CAR and CRA.These six methods are presented as common-neighbor-based predictors.Source: Previous Prediction Methods · p. 5

A Mutual Information Approach to Link Prediction

Results and Discussion

The mutual-information (MI) approach generally improves link-prediction accuracy, while CAR-based indices can outperform it in some settings at higher computational cost. The results show MI’s trade-off across AUC, precision, and complexity.

Results and Discussion

  • MI’s AUC exceeds 0.9 on EPA and INT, while the six indices are around 0.6.The authors suggest this difference may arise because previous methods cannot distinguish node pairs without common neighbors.Source: Results and Discussion · pp. 10–11
  • MI has much higher AUC than all six indices on real-world networks except Grid.Table 2 reports AUC averaged across 100 runs with 90% training and 10% probe data.Source: Results and Discussion · p. 10, Table 2 · p. 11
  • MI has much higher precision than CN, RA, LBN-CN, and LNB-RA on all networks, while CAR-based indices exceed MI on some.Table 3 reports top-100 precision averaged across 100 runs with 90% training and 10% probe data.Source: Table 3 · p. 11, Results and Discussion · p. 12
  • More than 99% of node pairs in INT have no common neighbors, a setting that occurs often in real-world networks.The authors note that this can limit methods that cannot distinguish pairs without common neighbors.Source: Results and Discussion · p. 11
  • CAR-based indices perform worst among the ten networks for pairs with few common neighbors because they emphasize links among those neighbors.Pairs with fewer than two common neighbors receive the same likelihood when there are no links among their common neighbors.Source: Results and Discussion · pp. 11–12
  • CAR-based indices can outperform MI for top-ranked links in networks with notable link communities; Wikivote is one example.The authors relate CAR-based indices’ advantage over MI positively to link communities and identify Wikivote as a high-average-degree case.Source: Results and Discussion · p. 12
  • MI has complexity O(N^2·⟨k⟩^4), versus O(N^2·⟨k⟩^6) for CAR and CRA; CAR-based indices can cost ⟨k⟩^2 times as much.For Wikivote, with average degree above 28, the authors estimate CAR-based indices’ complexity is about three orders of magnitude higher than MI’s.Source: Results and Discussion · p. 12
  • Overall, MI offers a good trade-off among AUC, precision, and computing complexity.CAR-based indices outperform MI on some networks, but have higher computing complexity.Source: Results and Discussion · p. 12

Conclusions

The paper proposes a mutual-information framework for uncovering missing network edges, derived strictly from information theory. Across ten networks, its simulations report stronger prediction performance than six typical indices and lower computing time than CAR-based indices.

Conclusions

  • The paper develops a framework for uncovering missing edges from network-topology mutual information, derived strictly from information theory.It compares the model with six typical prediction indices on ten networks from disparate fields.Source: Conclusions · p. 12
  • Simulations on ten networks show the MI model outperforming the six typical prediction indices.The conclusion reports the comparison across networks from disparate fields.Source: Conclusions · pp. 12–13
  • The MI approach is less time-consuming than CAR-based indices.Source: Conclusions · p. 13
Loading 1405.4341v2…