论文标题
首先伸展然后收缩和散装：最大$（δ，γ）$ \ mbox { - }临时网络的两期方法
First Stretch then Shrink and Bulk: A Two Phase Approach for Enumeration of Maximal $(Δ, γ)$\mbox{-}Cliques of a Temporal Network
论文作者
论文摘要
\ emph {暂时网络}（也称为\ emph {link stream}或\ emph {时变图}）通常用于建模一组代理之间的时间变化关系。它通常表示为表单$（u，v，t）$的三胞胎集合，表示代理商$ u $和$ v $在时间$ t $上的相互作用。为了分析形成时间网络的代理的接触模式，最近已将\ textit {static Graph}的经典\ textit {clique}的概念推广为\ textit {$ textit {$Δ$ \ mbox { - }临时网络的clique}。在同一方向上，我们以前的一项研究介绍了\ textit {$（δ，γ）$ \ mbox { - } clique}的概念，这基本上是一个\ textit {vertex set}，\ textit {time Intertion {time Interestal}，对每一个clique clique the Clique the Clique the Clique clique nivertiation the $γ$ uper每次$γ$δ在本文中，我们提出了另一种方法来列举给定时间网络的所有最大$（δ，γ）$ \ mbox { - }集团。所提出的方法将大致分为两个阶段。在第一阶段，处理每个时间链接，用于构造$（δ，γ）$ \ mbox { - } clique（s），并具有最大持续时间。在第二阶段，这些初始集团通过顶点添加扩展，以形成最大簇。从对$ 5 $ real \ mbox { - }世界时间网络数据集进行的实验中，我们观察到，所提出的方法列举了所有最大$（δ，γ）$ \ mbox { - } cliques cliques cliques有效，尤其是当数据集稀疏时。作为一种特殊情况（$γ= 1 $），与现有方法相比，所提出的方法还能够列举$（δ，1）\equivΔ$ \ mbox { - } cliques { - } cliques的时间要少得多。
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 \textit{clique} of a \textit{static graph} has been generalized as \textit{$Δ$\mbox{-}Clique} of a Temporal Network. In the same direction, one of our previous studies introduces the notion of \textit{$(Δ, γ)$\mbox{-}Clique}, which is basically a \textit{vertex set}, \textit{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 $(Δ, γ)$\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 $(Δ, γ)$\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 $(Δ,γ)$\mbox{-}Cliques efficiently, particularly when the dataset is sparse. As a special case ($γ=1$), the proposed methodology is also able to enumerate $(Δ,1) \equiv Δ$\mbox{-}cliques with much less time compared to the existing methods.
