On Atomic Cliques in Temporal Graphs

Atomic cliques were introduced recently to analyze comorbidity graphs that vary over time. We consider the atomic counterpart of the classical maximum clique problem in this paper. Our main contribution is a polynomial-time algorithm that transforms the maximum atomic clique problem to the maximum clique problem on an auxiliary graph. We report results from our … Read more

On fault-tolerant low-diameter clusters in graphs

Cliques and their generalizations are frequently used to model “tightly knit” clusters in graphs and identifying such clusters is a popular technique used in graph-based data mining. One such model is the $s$-club, which is a vertex subset that induces a subgraph of diameter at most $s$. This model has found use in a variety … Read more

Interdicting Low-Diameter Cohesive Subgroups in Large-Scale Social Networks

The s-clubs model cohesive social subgroups as vertex subsets that induce subgraphs of diameter at most s. In defender-attacker settings, for low values of s, they can represent tightly-knit communities whose operation is undesirable for the defender. For instance, in online social networks, large communities of malicious accounts can effectively propagate undesirable rumors. In this … Read more

Graph Signatures: Identification and Optimization

We introduce a new graph-theoretic paradigm called a graph signature that describes persistent patterns in a sequence of graphs. This framework is motivated by the need to detect subgraphs of significance in temporal networks, e.g., social and biological networks that evolve over time. Because the subgraphs of interest may not all “look alike” in the … Read more