Premium
DenGraph‐HO: a density‐based hierarchical graph clustering algorithm
Author(s) -
Schlitter Nico,
Falkowski Tanja,
Lässig Jörg
Publication year - 2014
Publication title -
expert systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.365
H-Index - 38
eISSN - 1468-0394
pISSN - 0266-4720
DOI - 10.1111/exsy.12046
Subject(s) - computer science , hierarchy , cluster analysis , graph , hierarchical clustering , theoretical computer science , algorithm , hierarchical network model , data mining , power graph analysis , clustering coefficient , artificial intelligence , economics , market economy
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 .