Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints
Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints
复制标题
DOI：
10.1145/3309712
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Jose Cadena;Feng Chen;A. Vullikanti
中科院分区：
文献类型：
--
作者：
Jose Cadena;Feng Chen;A. Vullikanti
网络分析中的一个基本任务是检测网络中的“热点”或“异常”;也就是说，检测子图，其中存在比给定历史数据或一些基线过程所期望的显著更多的活动。扫描统计是一种常用的异常子图检测方法。该方法涉及在所有连通子图上最大化得分函数，这是一个具有挑战性的计算问题。针对这些问题，已经提出了许多解决方案，但它们不能提供任何质量保证。在这里，我们提出了一个框架，用于设计算法，以优化网络的一大类扫描统计，受连接约束。我们的算法在时间上运行，该时间与图的大小成线性关系，并取决于我们称之为“有效解大小”的参数，同时提供严格的近似保证。相比之下，大多数现有方法在图大小方面具有超线性运行时间。大量的经验证据表明，我们提出的算法的有效性和效率相比，国家的最先进的方法。相对于所有先前的方法，我们的方法提高了性能，分数增加了25%以上。此外，我们的算法可扩展到多达一百万个节点的网络，这是1- 2个数量级大于所有以前的应用程序。
One fundamental task in network analysis is detecting “hotspots” or “anomalies” in the network; that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we propose a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the “effective solution size,” while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1--2 orders of magnitude larger than all prior applications.