Efficient Core Propagation based Hierarchical Graph Clustering

Communities, formed by a subset of vertices that are densely connected to each other and loosely connected to outside community members, widely exist to represent functional modules in real-world complex systems. Most existing community detection and search methods aim at finding communities at one single level, neglecting the natural properties of overlapping and hierarchy in communities. Therefore, the discovery of hierarchical graph clustering (HGC) to find communities at different levels, which is particularly useful in many applications. However, existing HGC studies suffer from two significant limitations: 1) inefficiency over large-scale networks, and 2) generating too many levels of community hierarchy without distinguishing the hierarchy differences. To address the above limitations, we first formulate our HGC problem to admit three key properties of hierarchical communities. Based on the natural hierarchical structure of k-core, we develop an important technique of core propagation. We propose two core propagation approaches of top-down and bottom-up algorithms, in terms of different search directions of k-cores by increment and decrement on k, respectively. The top-down method can find a given level of hierarchical communities in O(tm) time, where t is an input of hierarchy levels and m is the graph size. To dismiss the users' hardness of input hierarchy parameter t, the bottom-up algorithm is equipped with a well-designed strategy of auto-adjusting hierarchical levels based on the graph structure itself. We also develop the coreness weight-based label propagation to ensure the accurate label voting of compressed communities at low levels. The bottom-up method runs fast in O(mlogδ(G)), where logδ(G) is a small integer of the maximum coreness in graph G. Extensive experiments conducted on real-world graphs with ground-truth HGCs validate the effectiveness and efficiency of our proposed core propagation methods against state-of-the-art methods.