Finding Conserved Low-Diameter Subgraphs in Social and Biological Networks


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.

Under 2nd Round Review at Networks, March 2024
Yajun Lu
Yajun Lu
Assistant Professor of Analytics & Operations Management

My research interests are in Network Optimization, Graph-based Data Mining, Data Analytics of Complex Networks with applications in Healthcare, and Social Network Analysis.