IDEAS home Printed from https://ideas.repec.org/a/spr/sankha/v84y2022i1d10.1007_s13171-021-00248-1.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Neil Hwang & Jiarui Xu & Shirshendu Chatterjee & Sharmodeep Bhattacharyya, 2022. "The Bethe Hessian and Information Theoretic Approaches for Online Change-Point Detection in Network Data," Sankhya A: The Indian Journal of Statistics, Springer;Indian Statistical Institute, vol. 84(1), pages 283-320, June.
    • Handle: RePEc:spr:sankha:v:84:y:2022:i:1:d:10.1007_s13171-021-00248-1
    DOI: 10.1007/s13171-021-00248-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s13171-021-00248-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s13171-021-00248-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Peter J. Bickel & Purnamrita Sarkar, 2016. "Hypothesis testing for automated community detection in networks," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(1), pages 253-273, January.
    2. Jushan Bai & Pierre Perron, 1998. "Estimating and Testing Linear Models with Multiple Structural Changes," Econometrica, Econometric Society, vol. 66(1), pages 47-78, January.
    3. Petter Holme, 2015. "Modern temporal network theory: a colloquium," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 88(9), pages 1-30, September.
    4. Haeran Cho & Piotr Fryzlewicz, 2015. "Multiple-change-point detection for high dimensional time series via sparsified binary segmentation," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 77(2), pages 475-507, March.
    5. Sandipan Sikdar & Niloy Ganguly & Animesh Mukherjee, 2016. "Time series analysis of temporal networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 89(1), pages 1-11, January.
    6. Sandipan Sikdar & Niloy Ganguly & Animesh Mukherjee, 2016. "Time series analysis of temporal networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 89(1), pages 1-11, January.
    7. Cho, Haeran & Fryzlewicz, Piotr, 2015. "Multiple-change-point detection for high dimensional time series via sparsified binary segmentation," LSE Research Online Documents on Economics 57147, London School of Economics and Political Science, LSE Library.
    8. Staudacher, M. & Telser, S. & Amann, A. & Hinterhuber, H. & Ritsch-Marte, M., 2005. "A new method for change-point detection developed for on-line analysis of the heart beat variability during sleep," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 349(3), pages 582-596.
    9. Zhao, Longfeng & Wang, Gang-Jin & Wang, Mingang & Bao, Weiqi & Li, Wei & Stanley, H. Eugene, 2018. "Stock market as temporal network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 1104-1112.
    10. Sandipan Roy & Yves Atchadé & George Michailidis, 2017. "Change point estimation in high dimensional Markov random-field models," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(4), pages 1187-1206, September.
    11. Gerhard G. Van De Bunt & Marijtje A.J. Van Duijn & Tom A.B. Snijders, 1999. "Friendship Networks Through Time: An Actor-Oriented Dynamic Statistical Network Model," Computational and Mathematical Organization Theory, Springer, vol. 5(2), pages 167-192, July.
    12. David S. Matteson & Nicholas A. James, 2014. "A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 109(505), pages 334-345, March.
    13. Marko Popović & Hrvoje Štefančić & Borut Sluban & Petra Kralj Novak & Miha Grčar & Igor Mozetič & Michelangelo Puliga & Vinko Zlatić, 2014. "Extraction of Temporal Networks from Term Co-Occurrences in Online Textual Sources," PLOS ONE, Public Library of Science, vol. 9(12), pages 1-29, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cho, Haeran & Kirch, Claudia, 2024. "Data segmentation algorithms: Univariate mean change and beyond," Econometrics and Statistics, Elsevier, vol. 30(C), pages 76-95.
    2. Pang, Tianxiao & Du, Lingjie & Chong, Terence Tai-Leung, 2021. "Estimating multiple breaks in nonstationary autoregressive models," Journal of Econometrics, Elsevier, vol. 221(1), pages 277-311.
    3. Holger Dette & Theresa Eckle & Mathias Vetter, 2020. "Multiscale change point detection for dependent data," Scandinavian Journal of Statistics, Danish Society for Theoretical Statistics;Finnish Statistical Society;Norwegian Statistical Association;Swedish Statistical Association, vol. 47(4), pages 1243-1274, December.
    4. Jiang, Feiyu & Zhao, Zifeng & Shao, Xiaofeng, 2023. "Time series analysis of COVID-19 infection curve: A change-point perspective," Journal of Econometrics, Elsevier, vol. 232(1), pages 1-17.
    5. Fryzlewicz, Piotr, 2020. "Detecting possibly frequent change-points: Wild Binary Segmentation 2 and steepest-drop model selection," LSE Research Online Documents on Economics 103430, London School of Economics and Political Science, LSE Library.
    6. Brault, Vincent & Ouadah, Sarah & Sansonnet, Laure & Lévy-Leduc, Céline, 2018. "Nonparametric multiple change-point estimation for analyzing large Hi-C data matrices," Journal of Multivariate Analysis, Elsevier, vol. 165(C), pages 143-165.
    7. Cui, Junfeng & Wang, Guanghui & Zou, Changliang & Wang, Zhaojun, 2023. "Change-point testing for parallel data sets with FDR control," Computational Statistics & Data Analysis, Elsevier, vol. 182(C).
    8. Liu, Bin & Zhang, Xinsheng & Liu, Yufeng, 2022. "High dimensional change point inference: Recent developments and extensions," Journal of Multivariate Analysis, Elsevier, vol. 188(C).
    9. Holger Dette & Dominik Wied, 2016. "Detecting relevant changes in time series models," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(2), pages 371-394, March.
    10. Bin Liu & Cheng Zhou & Xinsheng Zhang & Yufeng Liu, 2020. "A unified data‐adaptive framework for high dimensional change point detection," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 82(4), pages 933-963, September.
    11. Otilia Boldea & Bettina Drepper & Zhuojiong Gan, 2020. "Change point estimation in panel data with time‐varying individual effects," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 35(6), pages 712-727, September.
    12. Ma, Chenchen & Tu, Yundong, 2023. "Group fused Lasso for large factor models with multiple structural breaks," Journal of Econometrics, Elsevier, vol. 233(1), pages 132-154.
    13. Shu, Lei & Chen, Yu & Zhang, Weiping & Wang, Xueqin, 2022. "Spatial rank-based high-dimensional change point detection via random integration," Journal of Multivariate Analysis, Elsevier, vol. 189(C).
    14. Hajra Siddiqa & Sajid Ali & Ismail Shah, 2021. "Most recent changepoint detection in censored panel data," Computational Statistics, Springer, vol. 36(1), pages 515-540, March.
    15. Oleksandr Gromenko & Piotr Kokoszka & Matthew Reimherr, 2017. "Detection of change in the spatiotemporal mean function," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(1), pages 29-50, January.
    16. Simon Bussy & Mokhtar Z. Alaya & Anne‐Sophie Jannot & Agathe Guilloux, 2022. "Binacox: automatic cut‐point detection in high‐dimensional Cox model with applications in genetics," Biometrics, The International Biometric Society, vol. 78(4), pages 1414-1426, December.
    17. Barigozzi, Matteo & Trapani, Lorenzo, 2020. "Sequential testing for structural stability in approximate factor models," Stochastic Processes and their Applications, Elsevier, vol. 130(8), pages 5149-5187.
    18. Steland, Ansgar, 2020. "Testing and estimating change-points in the covariance matrix of a high-dimensional time series," Journal of Multivariate Analysis, Elsevier, vol. 177(C).
    19. Qing Yang & Yu-Ning Li & Yi Zhang, 2020. "Change point detection for nonparametric regression under strongly mixing process," Statistical Papers, Springer, vol. 61(4), pages 1465-1506, August.
    20. Li, Degui, 2024. "Estimation of Large Dynamic Covariance Matrices: A Selective Review," Econometrics and Statistics, Elsevier, vol. 29(C), pages 16-30.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:sankha:v:84:y:2022:i:1:d:10.1007_s13171-021-00248-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.