论文标题
批处理动态算法以查找K核和层次结构
Batch Dynamic Algorithm to Find k-Cores and Hierarchies
论文作者
论文摘要
在图中找到$ k $ cores是提取原本稀疏图的密集区域的宝贵而有效的策略。我们专注于在快速变化的动态图上维护核心的重要问题，其中需要快速处理边缘变化。先前的批次核心算法仅解决了维持内核问题的一半，即保持核心分解的问题。这发现了密集但不是区域的顶点。它错过了连接性。为了解决这个问题，我们将社区搜索的有效索引带入了核心域，即Shell树索引。我们开发了一种新型的动态批次算法来维持它，从而提高了对边缘处理的效率。我们实施了算法，并通过实验表明，可以在快速更改的图表上返回核心查询，以迅速用于交互式应用程序。对于100万边批次，在许多图表上，我们的价格超过$ 100 \ times $ $ $ $比处理边缘的处理，而从头开始重新计算。
Finding $k$-cores in graphs is a valuable and effective strategy for extracting dense regions of otherwise sparse graphs. We focus on the important problem of maintaining cores on rapidly changing dynamic graphs, where batches of edge changes need to be processed quickly. Prior batch core algorithms have only addressed half the problem of maintaining cores, the problem of maintaining a core decomposition. This finds vertices that are dense, but not regions; it misses connectivity. To address this, we bring an efficient index from community search into the core domain, the Shell Tree Index. We develop a novel dynamic batch algorithm to maintain it that improves efficiency over processing edge-by-edge. We implement our algorithm and experimentally show that with it core queries can be returned on rapidly changing graphs quickly enough for interactive applications. For 1 million edge batches, on many graphs we run over $100\times$ faster than processing edge-by-edge while remaining under re-computing from scratch.
