The Bethe Hessian and Information Theoretic Approaches for Online Change-Point Detection in Network Data

Neil Hwang (), Jiarui Xu (), Shirshendu Chatterjee () and Sharmodeep Bhattacharyya ()
Additional contact information
Neil Hwang: City University of New York - Bronx Community College
Jiarui Xu: Oregon State University
Shirshendu Chatterjee: City University of New York - City College and Graduate Center
Sharmodeep Bhattacharyya: Oregon State University

Sankhya A: The Indian Journal of Statistics, 2022, vol. 84, issue 1, No 9, 283-320

Abstract: Abstract Sequences of networks are currently a common form of network data sets. Identification of structural change-points in a network data sequence is a natural problem. The problem of change-point detection can be classified into two main types - offline change-point detection and online or sequential change-point detection. In this paper, we propose three different algorithms for online change-point detection based on certain cusum statistics for network data with community structures. For two of the proposed algorithms, we use information theoretic measures to construct the statistic for the estimation of a change-point. In the third algorithm, we use eigenvalues of the Bethe Hessian matrix to construct the statistic for the estimation of a change-point. We show the consistency property of the estimated change-point theoretically under networks generated from the multi-layer stochastic block model and the multi-layer degree-corrected block model. We also conduct an extensive simulation study to demonstrate the key properties of the algorithms as well as their efficacy.

Keywords: Change-point detection; Bethe hessian operator; Spectral clustering; Community detection; Sparse networks; Variation of information.; Primary 62H30; 62F12; Secondary 91D30 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13171-021-00248-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sankha:v:84:y:2022:i:1:d:10.1007_s13171-021-00248-1

Ordering information: This journal article can be ordered from
http://www.springer.com/statistics/journal/13171

DOI: 10.1007/s13171-021-00248-1

Access Statistics for this article

Sankhya A: The Indian Journal of Statistics is currently edited by Dipak Dey

More articles in Sankhya A: The Indian Journal of Statistics from Springer, Indian Statistical Institute
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().