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,
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 ...
Get Statistical and Machine Learning Approaches for Network Analysis now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.