O'Reilly logo

Statistical and Machine Learning Approaches for Network Analysis by Subhash C. Basak, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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) equation

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) equation

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required