Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs

Bipartite graph is a widely used model to describe relationships between two different types of entities. Exploring graph hierarchy with cohesive subgraphs has been extensively studied on unipartite graphs, while only a few works focus on bipartite graphs. In this paper, we propose the bipartite hierarchy, which is the first model to discover the hierarchical structure of bipartite graphs based on the concept of $(\alpha_{2}\beta){-}$ core and graph connectivity. Notably, $(\alpha, \beta)-\text{core}$ is a vertex- centric model that conforms to the special structure of bipartite graphs (i.e., formed by two different vertex layers). Accordingly, the bipartite hierarchy has two parts (i.e., the upper and lower hierarchies) to record the hierarchical relationships among upper and lower vertices, respectively. We theoretically prove that the bipartite hierarchy is space-efficient (i.e., its space cost is linear to the graph size) and clearly illustrate its structure via visualization. In addition, efficient algorithms for building the bipartite hierarchy are proposed by utilizing the nested property of $(\alpha, \beta)-\text{core}$ . Since bipartite graphs can be dynamically changed in real-world scenarios, we also study the bipartite hierarchy maintenance algorithms against the edge insertion/deletion cases. These algorithms can effectively identify the affected regions to limit computation scope and avoid re-building the bipartite hierarchy from scratch. Extensive experiments on 10 real-world graphs not only demonstrate the effectiveness of the proposed bipartite hierarchy but also validate the efficiency of our hierarchy construction and maintenance algorithms.