Extracting hierarchical backbones from bipartite networks

Abstract

We propose a method for extracting hierarchical backbones from a bipartite network. Our method leverages the observation that a hierarchical relationship between two nodes in a bipartite network is often manifested as an asymmetry in the conditional probability of observing the connections to them from the other node set. Our method estimates both the importance and direction of the hierarchical relationship between a pair of nodes, thereby providing a flexible way to identify the essential part of the networks. Using semi-synthetic benchmarks, we show that our method outperforms existing methods at identifying planted hierarchy while offering more flexibility. Application of our method to empirical datasets---a bipartite network of skills and individuals as well as the network between gene products and Gene Ontology (GO) terms---demonstrates the possibility of automatically extracting or augmenting ontology from data.

arXiv comment8 pages, 4 figures

References in corpus (15)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• The structure of scientific collaboration networks
• Hierarchical structure and the prediction of missing links in networks
• Link communities reveal multiscale complexity in networks
• Structure and tie strengths in mobile communication networks
• Why social networks are different from other types of networks
• How to project a bipartite network?
• Extracting the multiscale backbone of complex weighted networks
• Efficiently inferring community structure in bipartite networks
• Robust classification of salient links in complex networks
• Information filtering in complex weighted networks
• Hierarchical networks of scientific journals
• Extracting tag hierarchies
• Time evolution of the hierarchical networks between PubMed MeSH terms