Mining Low-Diameter Clusters Conserved in Graph Collections

Abstract

The analysis of social and biological networks often involves modeling clusters of interest as cliques or their graph-theoretic generalizations. The k-club model, which relaxes the requirement of pairwise adjacency in a clique to length-bounded paths inside the cluster, has been used to model cohesive subgroups in social networks and functional modules/complexes in biological networks. However, if the graphs are time-varying, or if they change under different (experimental) conditions, we may be interested in clusters that preserve their property over time or under changes in conditions. To model such clusters that are conserved in a collection of graphs, we consider a cross-graph k-club model, a subset of nodes that forms a k-club in every graph in the collection.

In this dissertation, we consider the canonical optimization problem of finding a cross-graph k-club of maximum cardinality. The overall goal of this dissertation is to develop integer programming approaches to solve the problem. We establish computational complexity of the problem and its related problems. We introduce a naive extension of the cut-like formulation for the maximum k-club problem and offer ideas to strengthen it. We introduce valid inequalities for the problem and extend existing inequalities valid for the single-graph problem to the cross-graph setting. We introduce algorithmic ideas to solve this problem using a decomposition branch-and-cut algorithm. For scale reduction, we explore preprocessing procedures and extended formulations. We assess computational effectiveness of the techniques we propose and evaluate their performance on benchmark instances.

We introduce and study in this dissertation, the maximum k-club signature problem, which aims to find a maximum cardinality cross-graph k-club in τ consecutive graphs in a sequence of graphs, where the parameter τ is specified by the user. We propose a “moving window” method that solves a sequence of several maximum cross-graph k-club problems, and assess the performance of the approaches we propose in solving the signature variant.