Document Zbl 1477.62218

CUSUM multi-chart for detecting unknown abrupt changes under finite measure space for network observation sequences. (English) Zbl 1477.62218

Statistics 55, No. 3, 489-513 (2021).

Summary: This paper considers the model-based change-point problem with an unknown abrupt change for large-scale network observation sequences. To avoid the difficulty of calculating the normalization coefficients that let the axioms of probability hold, such as \(Z(\Lambda)\) in the Exponential Random Graphical Model (ERGM), we present the measure ratio statistics to replace the likelihood ratio statistics. Since the parameter difference reflecting the abrupt change for the network observation sequences is unknown, we first select the dimensions where the parameter difference exists through the \(L_1\)-norm penalized maximum likelihood estimation process, then propose a CUSUM multi-chart scheme based on the selected dimensions. Moreover, an optimal design of the CUSUM multi-chart is given when ARL\(_0\) (in-control Average Run length) is large. Two examples are used to illustrate the related theoretical results.

Cited in 1 Document

MSC:

62L10	Sequential statistical analysis
62L15	Optimal stopping in statistics
62G10	Nonparametric hypothesis testing
62K05	Optimal statistical designs
62H22	Probabilistic graphical models

Keywords:

CUSUM multi-chart; optimal design; finite measure space; penalized maximum likelihood estimation

Software:

ergm

Cite Review PDF

Full Text: DOI

References:

[1]	Chen, H.; Zhang, N., Graph-based change-point detection, Ann Stat, 139-176 (2015) · Zbl 1308.62090
[2]	Chen, H, Sequential change-point detection based on nearest neighbors. Preprint 2018. Available at arXiv:1604.03611. · Zbl 1419.62201
[3]	Roy, RB; Sarkar, UK., A social network approach to change detection in the interdependence structure of global stock markets, Soc Netw Anal Min, 3, 269-283 (2013)
[4]	McCulloh, I, Carley, KM, Detecting change in human social behavior simulation. Technical Report CMU-ISR-08-135, Institute for Software Research, School of Computer Science, Carnegie Mellon University, Pittsburgh (PA); 2008a.
[5]	McCulloh, I, Carley, KM, Social network change detection. Technical Report CMU-ISR-08-116, Institute for Software Research, School of Computer Science, Carnegie Mellon University, Pittsburgh (PA); 2008b.
[6]	McCulloh, I.; Carley, KM., Detecting change in longitudinal social networks, J Soc Struct (2011)
[7]	Heard, NA; Weston, DJ; Platanioti, K., Bayesian anomaly detection methods for social networks, Ann Appl Stat, 4, 2, 645-662 (2010) · Zbl 1194.62021
[8]	Sparks, R. Social network monitoring: aiming to identify periods of unusually increased communications between parties of interest. In: Knoth S, Schmid W, editors. Frontiers in statistical quality control Vol. 11, Heidelberg: Springer-Verlag; 2015. p. 3-13. · Zbl 1331.62503
[9]	Frank, O.; Strauss, D., Markov graphs, J Am Stat Assoc, 81, 832-842 (1986) · Zbl 0607.05057
[10]	Wasserman, S.; Pattison, PE., Logit models and logistic regressions for social networks: I. An introduction to Markov graphs and p*, Psychometrika, 61, 401-425 (1996) · Zbl 0866.92029
[11]	Vu, DQ; Hunter, DR; Schweinberger, M., Model-based clustering of large networks, Ann Appl Stat, 7, 2, 1010-1039 (2013) · Zbl 1288.62106
[12]	Hanneke, S.; Fu, W.; Xing, E., Discrete temporal models of social networks, Electron J Stat, 4, 585-605 (2010) · Zbl 1329.91113
[13]	Krivitsky, PN; Handcock, MS., A separable model for dynamic networks, J R Stat Soc Ser B, 76, 1, 29-46 (2014) · Zbl 1411.90079
[14]	Montgomery, DC., Introduction to statistical quality control (1996), New York: Wiley, New York
[15]	Lai, TL., Sequential change-point detection in quality control and dynamic systems, J Roy Statist Soc Ser B, 57, 613-658 (1995) · Zbl 0832.62072
[16]	Qiu, P., Introduction to statistical process control (2014), Boca Raton (FL): Chapman & Hall/CRC, Boca Raton (FL)
[17]	Siegmund, D.; Venkatraman, ES., Using the generalized likelihood ratio statistic for sequential detection of a change-point, Ann Stat, 23, 255-271 (1995) · Zbl 0821.62044
[18]	Han, D.; Tsung, F., A generalized EWMA control chart and its comparison with the optimal EWMA, CUSUM and GLR schemes, Ann Stat, 32, 316-339 (2004) · Zbl 1105.62385
[19]	Hawkins, DM; Deng, Q., A nonparametric change point control chart, J Qual Technol, 42, 2, 165-173 (2010)
[20]	Lau, TS, Tay, WP, Veeravalli, VV, Quickest change detection with unknown post-change distribution. IEEE International Conference on Acoustics; IEEE. 2017.
[21]	Lorden, G., Procedures for reacting to a change in distribution, Ann Math Stat, 42, 1897-1908 (1971) · Zbl 0255.62067
[22]	Lucas, JM., Combined Shewhart-CUSUM quality control scheme, J Qual Tech, 14, 51-59 (1982)
[23]	Sparks, RS., CUSUM charts for signalling varying location shifts, J Qual Tech, 32, 157-171 (2000)
[24]	Han, D.; Tsung, F.; Hu, X., CUSUM and EWMA multi-charts for detection a range of mean shifts, Stat Sin, 17, 1139-1164 (2007) · Zbl 1133.62095
[25]	Han, D.; Tsung, F., Detection and diagnosis of unknown abrupt changes using CUSUM multi-chart schemes, Sequan Anal, 26, 3, 225-249 (2007) · Zbl 1116.62081
[26]	Capizzi, G.; Masarotto, G., Efficient control chart calibration by simulated stochastic approximation, IIE Trans, 48, 1, 57-65 (2016)
[27]	Geng, J, Bayraktar, E, Lai, L. Multi-chart detection procedure for Bayesian quickest change-point detection with unknown post-change parameters. Preprint 2017. Available at arXiv:1708.06901. · Zbl 1360.94109
[28]	Donoho, DL; Johnstone, IM., Ideal spatial adaptation by wavelet shrinkage, Biometrika, 3, 3, 425-455 (1994) · Zbl 0815.62019
[29]	Moustakides, GV., Optimal stopping times for detecting changes in distributions, Ann Stat, 14, 4, 1379-1387 (1986) · Zbl 0612.62116
[30]	Fan, J.; Li, R., Variable selection via nonconcave penalized likelihood and its oracle properties, J Am Stat Assoc, 96, 1348-1360 (2001) · Zbl 1073.62547
[31]	Siegmund, D., Sequential analysis: tests and confidence intervals (1985), New York: Springer-Verlag, New York · Zbl 0573.62071
[32]	Karrer, B.; Newman, MEJ., Stochastic blockmodels and community structure in networks, Phys Rev E, 83 (2011)
[33]	Erdos, P.; Rnyi, A., On random graphs I, Pub Math, 6, 290-297 (1959) · Zbl 0092.15705
[34]	Ryu, JH; Wan, HG; Kim, S., Optimal design of a CUSUM chart for a mean shift of unknown size, J Qual Technol, 42, 3, 19-20 (2010)
[35]	Gut, A., Stopping time random walks: limit theorems and applications (1988), New York: Springer, New York · Zbl 0634.60061
[36]	Barabsi, AL; Bonabeau, E., Scale-free networks, Sci Am, 288, 5, 60-9 (2003)
[37]	Castagliola, P.; Maravelakis P, E., A CUSUM control chart for monitoring the variance when parameters are estimated, J Stat Plan Inference, 141, 4, 1463-1478 (2011) · Zbl 1204.62189
[38]	Hunter, DR; Handcock, MS; Butts, CT., ergm: A package to fit, simulate and diagnose exponential-family models for networks, J Stat Softw (2008)
[39]	Erdos, P.; Rnyi, A., On the evolution of random graphs, Pub Math Inst Hungarian Acad Sci, 5, 17-61 (1960) · Zbl 0103.16301
[40]	Harris, JK. An introduction to exponential random graph modeling. California: Sage Publications; 2013.
[41]	Krapivsky, PL; Rodgers, GJ; Redner, S., Degree distributions of growing networks, Phys Rev Lett, 86, 23, 5401-4 (2001)
[42]	Koller, D.; Friedman, N., Probabilistic graphical models: principles and techniques (2009), MIT Press · Zbl 1183.68483
[43]	Qiao, L, Han, D, Optimal sequential tests for detection of changes under finite measure space for finite sequences of networks. Preprint 2019. Available at arXiv:1911.06545

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.