Statistical and Machine Learning Approaches for Network Analysis

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 ...