论文标题
逃逸时间进行子图检测和图形分区
Escape times for subgraph detection and graph partitioning
论文作者
论文摘要
我们提供了一种基于重排的算法，用于快速检测$ k $顶点的子图，并为有指导性或无向网络提供长时间的逃生时间。我们的方法补充了其他最密集的子图和图形切割的概念，是基于随机助行器留下指定套装并击中补充所需的平均打击时间。我们提供了这种在给定子图上打破时间的概念的新放松，并利用这种放松来构建快速子图检测算法，并将其概括为$ k $ - 分区方案。使用对每个组件上的子图检测器的修改，我们提出了一个图形分区仪，该图形分区仪可以确定在相当大的时间内随机行走的区域。重要的是，我们的方法隐含地尊重有向图的数据的定向性质，同时也适用于无向图。我们将分区方法应用于社区检测到大量的模型和现实世界数据集。
We provide a rearrangement based algorithm for fast detection of subgraphs of $k$ vertices with long escape times for directed or undirected networks. Complementing other notions of densest subgraphs and graph cuts, our method is based on the mean hitting time required for a random walker to leave a designated set and hit the complement. We provide a new relaxation of this notion of hitting time on a given subgraph and use that relaxation to construct a fast subgraph detection algorithm and a generalization to $K$-partitioning schemes. Using a modification of the subgraph detector on each component, we propose a graph partitioner that identifies regions where random walks live for comparably large times. Importantly, our method implicitly respects the directed nature of the data for directed graphs while also being applicable to undirected graphs. We apply the partitioning method for community detection to a large class of model and real-world data sets.
