# 10.3 Dense Cluster Enumeration in Weighted Interaction Networks

This section presents an enumerative approach to identify cluster patterns in undirected weighted graphs and networks [1]. 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 [89]. 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.

## 10.3.1 Notation and Problem Definition

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,

(10.1)

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

(10.2)

It contains for each pair of nodes an entry, which corresponds to the weight of the ...