Why Did the Shape of Your Network Change? (On Detecting Network Anomalies via Non-local Curvatures)
Why Did the Shape of Your Network Change? (On Detecting Network Anomalies via Non-local Curvatures)
复制标题
为什么你的网络的形状改变了？(On通过非局部曲率检测网络异常）
DOI：
10.1007/s00453-019-00665-7
复制
发表时间：
2020-01-22
期刊：
影响因子：
1.1
通讯作者：
Yahyanejad, Farzane
中科院分区：
文献类型：
--
作者：
DasGupta, Bhaskar;Janardhanan, Mano Vikash;Yahyanejad, Farzane
异常检测问题(也称为变点检测问题)是数据挖掘、统计学和计算机科学在过去几十年(主要是在非网络环境下)在医疗状况监测、天气变化检测和语音识别等应用中的研究成果。然而，最近几天，异常检测问题在网络科学的背景下变得越来越重要，因为生物学、金融和社会科学中的许多复杂系统的有用见解往往是通过网络来表示的。高维几何形状和拓扑空间的局部和非局部曲率的概念在描述这些高维实体的异常行为方面在物理和数学中起着基本的作用。然而，使用曲率度量来检测网络中的异常还不是很常见。为此，本文的一个主要目标是阐述和分析曲率分析方法，为系统地寻找关键组件和检测网络中的异常提供基础。为此，我们使用了两种网络曲率的度量，它们依赖于给定网络的非平凡全局属性，例如测地线的分布和节点之间的高阶相关性。基于这些度量，我们精确地描述了与静态和动态网络中的异常检测相关的几个计算问题，并为这些问题提供了非平凡的计算复杂性结果。这篇论文不能被看作是对特定曲率测量的适当性和适宜性的最终定论。相反，我们希望这篇论文将激励和激励进一步的理论或实证研究，关于来自网络和非网络区域的曲率概念之间令人兴奋的相互作用，这在我们看来是一个非常理想的目标。
Anomaly detection problems (also called change-point detection problems) have been studied in data mining, statistics and computer science over the last several decades (mostly in non-network context) in applications such as medical condition monitoring, weather change detection and speech recognition. In recent days, however, anomaly detection problems have become increasing more relevant in the context of network science since useful insights for many complex systems in biology, finance and social science are often obtained by representing them via networks. Notions of local and non-local curvatures of higher-dimensional geometric shapes and topological spaces play a fundamental role in physics and mathematics in characterizing anomalous behaviours of these higher dimensional entities. However, using curvature measures to detect anomalies in networks is not yet very common. To this end, a main goal in this paper to formulate and analyze curvature analysis methods to provide the foundations of systematic approaches to find critical components and detect anomalies in networks. For this purpose, we use two measures of network curvatures which depend on non-trivial global properties, such as distributions of geodesics and higher-order correlations among nodes, of the given network. Based on these measures, we precisely formulate several computational problems related to anomaly detection in static or dynamic networks, and provide non-trivial computational complexity results for these problems. This paper must not be viewed as delivering the final word on appropriateness and suitability of specific curvature measures. Instead, it is our hope that this paper will stimulate and motivate further theoretical or empirical research concerning the exciting interplay between notions of curvatures from network and non-network domains, a much desired goal in our opinion.