Edré Moreira, Guilherme Oliveira Campos, Wagner Meira Jr.

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

Introduction

Weighted linking decomposition: mining denser and more compact hierarchies for bipartite graphs. Weighted Linking algorithm mines denser, more compact hierarchical decompositions for bipartite graphs. It outperforms state-of-the-art methods and introduces a novel scoring system.

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.

Full Text

Comments

You need to be logged in to post a comment.