DenGraph-HO: a density-based hierarchical graph clustering algorithm

DenGraph‐HO is an extension of the density‐based graph clustering algorithm DenGraph. It is able to detect dense groups of nodes in a given graph and produces a hierarchy of clusters, which can be efficiently computed. The generated hierarchy can be used to investigate the structure and the characteristics of social networks. Each hierarchy level provides a different level of detail and can be used as the basis for interactive visual social network analysis. After a short introduction of the original DenGraph algorithm, we present DenGraph‐HO and its top‐down and bottom‐up approaches. We describe the data structures and memory requirements and analyse the run‐time complexity. Finally, we apply the DenGraph‐HO algorithm to the real‐world datasets obtained from the online music platform Last.fm and from the former US company Enron.