An official website of the United States government
The monitoring of data streams with a network structure have drawn increasing attention due to its wide applications in modern process control. In these applications, high-dimensional sensor nodes are interconnected with an underlying network topology. In such a case, abnormalities occurring to any node may propagate dynamically across the network and cause changes of other nodes over time. Furthermore, high dimensionality of such data significantly increased the cost of resources for data transmission and computation, such that only partial observations can be transmitted or processed in practice. Overall, how to quickly detect abnormalities in such large networks with resource constraints remains a challenge, especially due to the sampling uncertainty under the dynamic anomaly occurrences and network-based patterns. In this paper, we incorporate network structure information into the monitoring and adaptive sampling methodologies for quick anomaly detection in large networks where only partial observations are available. We develop a general monitoring and adaptive sampling method and further extend it to the case with memory constraints, both of which exploit network distance and centrality information for better process monitoring and identification of abnormalities. Theoretical investigations of the proposed methods demonstrate their sampling efficiency on balancing between exploration and exploitation, as well as the detection performance guarantee. Numerical simulations and a case study on power network have demonstrated the superiority of the proposed methods in detecting various types of shifts. Note to Practitioners —Continuous monitoring of networks for anomalous events is critical for a large number of applications involving power networks, computer networks, epidemiological surveillance, social networks, etc. This paper aims at addressing the challenges in monitoring large networks in cases where monitoring resources are limited such that only a subset of nodes in the network is observable. Specifically, we integrate network structure information of nodes for constructing sequential detection methods via effective data augmentation, and for designing adaptive sampling algorithms to observe suspicious nodes that are likely to be abnormal. Then, the method is further generalized to the case that the memory of the computation is also constrained due to the network size. The developed method is greatly beneficial and effective for various anomaly patterns, especially when the initial anomaly randomly occurs to nodes in the network. The proposed methods are demonstrated to be capable of quickly detecting changes in the network and dynamically changes the sampling priority based on online observations in various cases, as shown in the theoretical investigation, simulations and case studies.
more »
« less
Modeling and detecting change in temporal networks via the degree corrected stochastic block model
Abstract In many applications, it is of interest to identify anomalous behavior within a dynamic interacting system. Such anomalous interactions are reflected by structural changes in the network representation of the system. We propose and investigate the use of the degree corrected stochastic block model (DCSBM) to model and monitor dynamic networks that undergo a significant structural change. We apply statistical process monitoring techniques to the estimated parameters of the DCSBM to identify significant structural changes in the network. We apply our surveillance strategy to a dynamic US Senate covoting network. We detect significant changes in the political network that reflect both times of cohesion and times of polarization among Republican and Democratic party members. Our analysis demonstrates that the DCSBM monitoring procedure effectively detects local and global structural changes in complex networks, providing useful insights into the modeled system. The DCSBM approach is an example of a general framework that combines parametric random graph models and statistical process monitoring techniques for network surveillance.
more »
« less
- Award ID(s):
- 1830547
- PAR ID:
- 10453335
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Quality and Reliability Engineering International
- Volume:
- 35
- Issue:
- 5
- ISSN:
- 0748-8017
- Page Range / eLocation ID:
- p. 1363-1378
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Applications in environmental monitoring, surveillance and patrolling typically require a network of mobile agents to collectively gain information regarding the state of a static or dynamical process evolving over a region. However, these networks of mobile agents also introduce various challenges, including intermittent observations of the dynamical process, loss of communication links due to mobility and packet drops, and the potential for malicious or faulty behavior by some of the agents. The main contribution of this paper is the development of resilient, fully-distributed, and provably correct state estimation algorithms that simultaneously account for each of the above considerations, and in turn, offer a general framework for reasoning about state estimation problems in dynamic, failure-prone and adversarial environments. Specifically, we develop a simple switched linear observer for dealing with the issue of time-varying measurement models, and resilient filtering techniques for dealing with worst-case adversarial behavior subject to time-varying communication patterns among the agents. Our approach considers both communication patterns that recur in a deterministic manner, and patterns that are induced by random packet drops. For each scenario, we identify conditions on the dynamical system, the patrols, the nominal communication network topology, and the failure models that guarantee applicability of our proposed techniques. Finally, we complement our theoretical results with detailed simulations that illustrate the efficacy of our algorithms in the presence of the technical challenges described above.more » « less
-
Abstract In an era where air pollution poses a significant threat to both the environment and public health, we present a network-based approach to unravel the dynamics of extreme pollution events. Leveraging data from 741 monitoring stations in the contiguous United States, we have created dynamic networks using time-lagged correlations of hourly particulate matter (PM2.5) data. The established spatial correlation networks reveal significant PM2.5anomalies during the 2020 and 2021 wildfire seasons, demonstrating the approach’s sensitivity to detecting regional pollution phenomena. The methodology also provides insights into smoke transport and network response, highlighting the persistence of air quality issues beyond visible smoke periods. Additionally, we explored meteorological variables’ impacts on network connectivity. This study enhances understanding of spatiotemporal pollution patterns, positioning spatial correlation networks as valuable tools for environmental monitoring and public health surveillance.more » « less
-
Percolation theory is essential for understanding disease transmission patterns on the temporal mobility networks. However, the traditional approach of the percolation process can be inefficient when analysing a large-scale, dynamic network for an extended period. Not only is it time-consuming but it is also hard to identify the connected components. Recent studies demonstrate that spatial containers restrict mobility behaviour, described by a hierarchical topology of mobility networks. Here, we leverage crowd-sourced, large-scale human mobility data to construct temporal hierarchical networks composed of over 175 000 block groups in the USA. Each daily network contains mobility between block groups within a Metropolitan Statistical Area (MSA), and long-distance travels across the MSAs. We examine percolation on both levels and demonstrate the changes of network metrics and the connected components under the influence of COVID-19. The research reveals the presence of functional subunits even with high thresholds of mobility. Finally, we locate a set of recurrent critical links that divide components resulting in the separation of core MSAs. Our findings provide novel insights into understanding the dynamical community structure of mobility networks during disruptions and could contribute to more effective infectious disease control at multiple scales. This article is part of the theme issue ‘Data science approaches to infectious disease surveillance’.more » « less
-
null (Ed.)Abstract Game-theoretic models of influence in networks often assume the network structure to be static. In this paper, we allow the network structure to vary according to the underlying behavioral context. This leads to several interesting questions on two fronts. First, how do we identify different contexts and learn the corresponding network structures using real-world data? We focus on the U.S. Senate and apply unsupervised machine learning techniques, such as fuzzy clustering algorithms and generative models, to identify spheres of legislation as context and learn an influence network for each sphere. Second, how do we analyze these networks to gain an insight into the role played by the spheres of legislation in various interesting constructs like polarization and most influential nodes? To this end, we apply both game-theoretic and social network analysis techniques. In particular, we show that game-theoretic notion of most influential nodes brings out the strategic aspects of interactions like bipartisan grouping, which structural centrality measures fail to capture.more » « less
