A Two-Phase Approach for Enumeration of Maximal (Δ, γ) -Cliques of a Temporal Network

Abstract

A Temporal Network is a graph whose topology is changing over time and represented as a collection of triplets of the form (u, v, t) that denotes the interaction between the agents u and v at time t. Analyzing and enumerating different structural patterns of such networks are important in different domains including social network analysis, computational biology, etc. In this paper, we study the problem of enumerating one such pattern: maximal (Δ, γ) -Clique. Given a temporal network G(V, E, T), a (Δ, γ) -Clique is a vertex subset, time interval pair (X, [ ta, tb] ) such that between every pair of vertices of X, there exist at least γ links in each Δ duration in [ ta, tb]. The proposed methodology is broadly divided into two phases. In the first phase, each temporal link is processed for constructing (Δ, γ) -Clique(s) with maximum duration. In the second phase, these initial cliques are expanded by vertex addition to form the maximal cliques. We show that the proposed methodology is correct, and running time, space requirement analysis has been done. From the experimentation on three real datasets, we observe that the proposed methodology enumerates all the maximal (Δ, γ) -Cliques efficiently, particularly when the dataset is sparse. As a special case (γ= 1 ), the proposed methodology is also able to enumerate (Δ, 1 ) ≡ Δ -cliques with much less time compared to the existing methods. © 2021, Springer Nature Switzerland AG.