NetSpot：动态网络中显著异常区域的识别

如何在动态网络中如道路网络、通信网络和社交网络中识别和总结异常现象？异常事件，如交通事故、拒绝服务攻击或化学泄漏，可能会影响附近的多个边，并使其在连续的多个时间点上异常行为。我们专注于识别和总结这些显著的异常区域，跨越空间（即附近的边）和时间。我们的第一个贡献是问题的公式化，即寻找所有这样的显著异常区域（SAR）。下一个贡献是新算法的设计：一种耗时的穷举算法，以及一种称为NETSPOT的高效近似算法。与穷举算法相比，NETSPOT在真实数据上快了一个数量级，同时实现了低于4%的平均相对误差率。在合成数据集上，它快了30倍以上，并解决了原本不可行的大规模问题实例。最后，贡献是对真实数据的验证：我们展示了NETSPOT在推断道路网络事故和检测维基百科子网络异常访问模式方面的实用性。我们还研究了NETSPOT在大型社交、交通和合成演化网络中的扩展性，总计可覆盖多达5000万个边。