Finding Conserved Low-Diameter Subgraphs in Social and Biological Networks

Abstract

The analysis of social and biological networks often involves modeling clusters of interest as cliques or their graph-theore-tic generalizations. The $k$-club model, which relaxes the requirement of pairwise adjacency in a clique to length-bound-ed paths inside the cluster, has been used to model cohesive subgroups in social networks and functional modules or complexes in biological networks. However, if the graphs are time-varying, or if they change under different 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 paper, we consider the canonical optimization problem of finding a cross-graph $k$-club of maximum cardinality in a graph collection. We develop integer programming approaches to solve this problem. Specifically, we introduce strengthened formulations, valid inequalities, and branch-and-cut algorithms based on delayed constraint generation. The results of our computational study indicate the significant benefits of using the approaches we introduce.