First Stretch then Shrink and Bulk: A Two Phase Approach for Enumeration of Maximal $(\mathrm{\Delta },\gamma )$\mbox{-}Cliques of a Temporal Network

A \emph{Temporal Network} (also known as \emph{Link Stream} or \emph{Time-Varying Graph}) is often used to model a time-varying relationship among a group of agents. It is typically 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$. For analyzing the contact patterns of the agents forming a temporal network, recently the notion of classical $\mathit{\text{clique}}$ of a $\mathit{\text{static}}\mathit{\text{graph}}$ has been generalized as $\mathrm{\Delta }\mathit{\text{-Clique}}$ of a Temporal Network. In the same direction, one of our previous studies introduces the notion of $(\mathrm{\Delta },\gamma )\mathit{\text{-Clique}}$, which is basically a $\mathit{\text{vertex}}\mathit{\text{set}}$, $\mathit{\text{time}}\mathit{\text{interval}}$ pair, in which every pair of the clique vertices are linked at least $\gamma$ times in every $\mathrm{\Delta }$ duration of the time interval. In this paper, we propose a different methodology for enumerating all the maximal $(\mathrm{\Delta },\gamma )$\mbox{-}Cliques of a given temporal network. The proposed methodology is broadly divided into two phases. In the first phase, each temporal link is processed for constructing $(\mathrm{\Delta },\gamma )$\mbox{-}Clique(s) with maximum duration. In the second phase, these initial cliques are expanded by vertex addition to form the maximal cliques. From the experimentation carried out on $5$ real\mbox{-}world temporal network datasets, we observe that the proposed methodology enumerates all the maximal $(\mathrm{\Delta },\gamma )$\mbox{-}Cliques efficiently, particularly when the dataset is sparse. As a special case ($\gamma =1$), the proposed methodology is also able to enumerate $(\mathrm{\Delta },1)\equiv \mathrm{\Delta }$\mbox{-}cliques with much less time compared to the existing methods.