2020/04/09 by Banerjee, Suman, Pal, Bithika
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Multiagent Systems (cs.MA)
paper · doi:10.48550/arxiv.2004.05935
A Temporal Network (also known as Link Stream or 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 clique of a static graph has been generalized as \textitΔ-Clique of a Temporal Network. In the same direction, one of our previous studies introduces the notion of \textit(Δ, γ)-Clique, which is basically a vertex set, time interval pair, in which every pair of the clique vertices are linked at least γ times in every Δ duration of the time interval. In this paper, we propose a different methodology for enumerating all the maximal (Δ, γ)-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 (Δ, γ)-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-world temporal network 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.