论文标题
有效的算法从时间图中挖掘出最大跨度检查者
Efficient Algorithms to Mine Maximal Span-Trusses From Temporal Graphs
论文作者
论文摘要
在过去的十年中，人们对时间表的兴趣越来越多，这是由于来自社会，生物和金融网络的时间通知的网络数据的越来越多。尽管重要的是分析复杂的时间网络，但可用于研究大型静态图的一组定义，算法和工具之间仍然存在巨大差距。时间图分析中的一个重要任务是挖掘致密结构，即识别高密度子图以及观察到高密度的跨度。在本文中，我们介绍了$（k，δ）$ - 桁架（Span-truss）的概念，这是对$ k $ - truss的时间概括，其中$ k $捕获了有关密度的信息，$Δ$捕获了该密度所持的时间跨度。然后，我们提出了新颖而有效的算法来识别最大跨度检查者，即既不以其他任何Span-truss的主导，又不以$ k $的顺序或间隔$δ$主导，并在许多公共可用数据集中对其进行评估。
Over the last decade, there has been an increasing interest in temporal graphs, pushed by a growing availability of temporally-annotated network data coming from social, biological and financial networks. Despite the importance of analyzing complex temporal networks, there is a huge gap between the set of definitions, algorithms and tools available to study large static graphs and the ones available for temporal graphs. An important task in temporal graph analysis is mining dense structures, i.e., identifying high-density subgraphs together with the span in which this high density is observed. In this paper, we introduce the concept of $(k, Δ)$-truss (span-truss) in temporal graphs, a temporal generalization of the $k$-truss, in which $k$ captures the information about the density and $Δ$ captures the time span in which this density holds. We then propose novel and efficient algorithms to identify maximal span-trusses, namely the ones not dominated by any other span-truss neither in the order $k$ nor in the interval $Δ$, and evaluate them on a number of public available datasets.
