Adapting the Bron–Kerbosch algorithm for enumerating maximal cliques in temporal graphs
Adapting the Bron–Kerbosch algorithm for enumerating maximal cliques in temporal graphs
复制标题
DOI：
10.1007/s13278-017-0455-0
复制
发表时间：
2016-05
影响因子：
2.8
通讯作者：
Anne-Sophie Himmel;Hendrik Molter;R. Niedermeier;Manuel Sorge
中科院分区：
文献类型：
--
作者：
Anne-Sophie Himmel;Hendrik Molter;R. Niedermeier;Manuel Sorge
相互作用的动力学在复杂网络的分析中起着越来越重要的作用。一个建模框架来捕捉这是时间图，它由一组顶点（网络中的实体）和一组顶点之间的时间戳二进制交互组成。我们专注于枚举Δ-团，团的概念扩展到时间图：对于给定的时间段Δ，时间图中的Δ-团是一组顶点和时间间隔，使得所有顶点至少在时间间隔内的每个Δ时间步长之后相互作用。Viard，Latterfly，and Magnien（ASONAM 2015，TCS 2016）提出了一种贪婪算法，用于枚举时间图中的所有最大Δ-团。与此相反，这种方法，我们适应布朗-Kerbosch算法-一个有效的，递归回溯算法，列举了所有最大的集团在静态图的时间设置。我们得到了令人鼓舞的结果，无论是在理论上（关于最坏情况下的运行时间分析的基础上的参数“Δ片退化”的基础图形），以及在实践中与实验的真实世界的数据。后者最终在最有趣的Δ值有关的运行时间相比，Viard的算法，Latterfly，和Magnien的改进。
Dynamics of interactions play an increasingly important role in the analysis of complex networks. A modeling framework to capture this is temporal graphs which consist of a set of vertices (entities in the network) and a set of time-stamped binary interactions between the vertices. We focus on enumerating Δ-cliques, an extension of the concept of cliques to temporal graphs: for a given time period Δ, a Δ-clique in a temporal graph is a set of vertices and a time interval such that all vertices interact with each other at least after every Δ time steps within the time interval. Viard, Latapy, and Magnien (ASONAM 2015, TCS 2016) proposed a greedy algorithm for enumerating all maximal Δ-cliques in temporal graphs. In contrast to this approach, we adapt the Bron–Kerbosch algorithm—an efficient, recursive backtracking algorithm which enumerates all maximal cliques in static graphs—to the temporal setting. We obtain encouraging results both in theory (concerning worst-case running time analysis based on the parameter “Δ-slice degeneracy” of the underlying graph) as well as in practice with experiments on real-world data. The latter culminates in an improvement for most interesting Δ-values concerning running time in comparison with the algorithm of Viard, Latapy, and Magnien.