A1113
Title: Quickest detection of the change of community via stochastic block models
Authors: Ruizhi Zhang - University of Georgia (United States) [presenting]
Abstract: Community detection is a fundamental problem in network analysis and has important applications in sensor networks and social networks. In many cases, the network's community structure may change at some unknown time. Thus, it is desirable to come up with efficient monitoring procedures that can detect the change as quickly as possible. The Erd\H{o}s-R\'{e}nyi model and the bisection stochastic block model (SBM) are used to model the pre-change and post-change distributions of the network, respectively. Initially, it is assumed there is no community in the network. However, at some unknown time, a change occurs, and two communities are formed in the network. An efficient monitoring procedure is proposed using the number of $k$-cycles in the graph. The asymptotic detection properties of the proposed procedure are derived when all parameters are known. A generalized likelihood ratio (GLR) type detection procedure and an adaptive CUSUM type detection procedure are constructed to address the problem when parameters are unknown.
