Weighted Linking Decomposition: Mining Denser and More Compact Hierarchies for Bipartite Graphs

Abstract

Dense subgraph detection is a well-known problem in graph theory.
The hierarchical organization of graphs as dense subgraphs, however, goes beyond simple clustering, as it allows the analysis of the network at different scales.
Although there are several hierarchical decomposition methods for unipartite graphs, only a few approaches for the bipartite case have been proposed.
In this work, we explore the problem of hierarchical decomposition for bipartite graphs.
We propose an algorithm called Weighted Linking that identifies denser and more compact hierarchies than the state of the art approach.
We also propose a new score to help choose the best between two hierarchical decompositions of the same graph.
The proposed algorithm was evaluated experimentally using six real-world datasets and identified smaller and denser hierarchies on most of them.