Statistical and Machine Learning Approaches for Network Analysis

10.4 Dense Cluster Enumeration in Higher-Order Association Data

So far, we have assumed undirected weighted networks as input data for the dense cluster enumeration approach. Figure 10.7 illustrates generalizations of this setting that are addressed in this section [3,4]. While the basic network case deals with symmetric weight matrices and extracts submatrix patterns of large average weight, a similar task can be defined for asymmetric two-way weight matrices with a different set of entities in each dimension. It can be considered as an instance of bicluster mining approaches that focus on the strength or density of associations between entity subsets (see Section 10.2.4, Refs. 49,65,67,111). Beyond that, we look at higher-order input data, which can be represented as n-way weight arrays, also known as tensors. A higher-order or n-way cluster is then a subtensor described by specifying a non-empty subset of indices in each dimension. From a graph-theoretic point of view, an n-way tensor corresponds to a weighted n-partite hypergraph, where each hyperedge connects n nodes, exactly one node from each partition. If different dimensions of the tensor share the same entity set, the corresponding hypergraph has less partitions, and inherent symmetry relationships can exist. After introducing the problem of n-way dense cluster enumeration and a generalized reverse search algorithm that solves it, we consider its extension to symmetric scenarios.

Figure 10.7 Generalization of cluster ...