This section presents an enumerative approach to identify cluster patterns in undirected weighted graphs and networks . In this context, a cluster is defined as a set of densely interacting nodes, also called module or community. The algorithm makes use of a paradigm called reverse search, which has been introduced by Avis and Fukuda . Several extensions are described, including output filtering and integration of additional constraints. We first introduce some notation and give a precise mathematical formulation of the dense cluster mining problem; then, we explain the algorithm and analyze its computational complexity; finally, we outline extensions that facilitate systematic data analysis and interpretation.
Let us consider an undirected weighted graph with node set V. For notational convenience, we assume that V is a set of consecutive indices starting from 1, that is,
where I is a positive natural number. Further, we denote by |V| the size or cardinality of the node set, that is, the number of nodes (here, |V| = I). The corresponding interaction weight matrix is written as
It contains for each pair of nodes an entry, which corresponds to the weight of the ...