Predicting link directions via a recursive subgraph-based ranking

DOI10.1016/J.PHYSA.2013.03.025MaRDI QIDQ1673061zbMATH OpenOpenAlexFDO

Authors Fangjian Guo, Zimo Yang, Tao Zhou

Publication date 11 September 2018

Published in Physica A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.2199

zbMATH Keywords

rankinglink predictiondirected networksubgraphlinear ordering problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Neural networks for/in biological studies, artificial life and related topics (92B20) Network design and communication in computer systems (68M10)

Abstract: Link directions are essential to the functionality of networks and their prediction is helpful towards a better knowledge of directed networks from incomplete real-world data. We study the problem of predicting the directions of some links by using the existence and directions of the rest of links. We propose a solution by first ranking nodes in a specific order and then predicting each link as stemming from a lower-ranked node towards a higher-ranked one. The proposed ranking method works recursively by utilizing local indicators on multiple scales, each corresponding to a subgraph extracted from the original network. Experiments on real networks show that the directions of a substantial fraction of links can be correctly recovered by our method, which outperforms either purely local or global methods.

Recommendations

• Predicting unknown directed links of conserved networks from flow data
• Toward link predictability of complex networks
• Predicting missing links via local information
• Link prediction in networks using effective transitions
• Bi-scale link prediction on networks

Cites work

• Aggregating inconsistent information: ranking and clustering
• Authoritative sources in a hyperlinked environment
• Collective dynamics of `small-world' networks
• Entropy of dialogues creates coherent structures in e-mail traffic
• Predicting epidemics on directed contact networks
• Predicting missing links via local information
• Statistical mechanics of complex networks
• Synchronization on effective networks
• The Structure and Function of Complex Networks

Cited in

(5)

• Tensor decomposition for link prediction in temporal directed networks*
• Link prediction via linear optimization
• Predicting unknown directed links of conserved networks from flow data
• Directionality of real world networks as predicted by path length in directed and undirected graphs
• An evidential link prediction method and link predictability based on Shannon entropy

This page was built for publication: Predicting link directions via a recursive subgraph-based ranking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1673061)