×

Change point detection in network models: preferential attachment and long range dependence. (English) Zbl 1391.60015

Summary: Inspired by empirical data on real world complex networks, the last few years have seen an explosion in proposed generative models to understand and explain observed properties of real world networks, including power law degree distribution and “small world” distance scaling. In this context, a natural question is how to understand the effect of change points–how abrupt changes in parameters driving the network model change structural properties of the network. We study this phenomenon in one popular class of dynamically evolving networks: preferential attachment models. We derive asymptotic properties of various functionals of the network including the degree distribution as well as maximal degree asymptotics, in essence showing that the change point does effect the degree distribution but does not change the degree exponent. This provides evidence for long range dependence and sensitive dependence of the evolution of the network on the initial evolution of the process. We propose an estimator for the change point and prove consistency properties of this estimator. The methodology developed highlights the effect of the nonergodic nature of the evolution of the network on classical change point estimators.

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)

Software:

GraphScope; OddBall
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Akoglu, L., McGlohon, M. and Faloutsos, C. (2012). Oddball: Spotting anomalies in weighted graphs. In Advances in Knowledge Discovery and Data Mining 410-421. Springer, Berlin.
[2] Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys.74 47-97.
[3] Athreya, K. B. and Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching processes and related limit theorems. Ann. Math. Stat.39 1801-1817. · Zbl 0185.46103
[4] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223
[5] Basseville, M. and Nikiforov, I. V. (1993). Detection of Abrupt Changes: Theory and Application. Prentice Hall, Englewood Cliffs, NJ. · Zbl 1407.62012
[6] Bhamidi, S., Evans, S. N. and Sen, A. (2012). Spectra of large random trees. J. Theoret. Probab.25 613-654. · Zbl 1255.05114
[7] Bhamidi, S., Steele, J. M. and Zaman, T. (2015). Twitter event networks and the superstar model. Ann. Appl. Probab.25 2462-2502. · Zbl 1334.60204
[8] Boas, R. P. Jr. (1977). Partial sums of infinite series, and how they grow. Amer. Math. Monthly 84 237-258. · Zbl 0355.65001
[9] Boccaletti, S., Bianconi, G., Criado, R., del Genio, C. I., Gómez-Gardeñes, J., Romance, M., Sendiña-Nadal, I., Wang, Z. and Zanin, M. (2014). The structure and dynamics of multilayer networks. Phys. Rep.544 1-122.
[10] Bollobás, B. (1985). Random Graphs. Academic Press, London.
[11] Bollobás, B. and Riordan, O. M. (2003). Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks 1-34. Wiley-VCH, Weinheim.
[12] Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 279-290.
[13] Brodsky, B. E. and Darkhovsky, B. S. (1993). Nonparametric Methods in Change-Point Problems. Mathematics and Its Applications 243. Kluwer Academic, Dordrecht. · Zbl 1274.62512
[14] Bubeck, S., Devroye, L. and Lugosi, G. (2017). Finding Adam in random growing trees. Random Structures Algorithms 50 158-172. · Zbl 1359.05110
[15] Bubeck, S., Mossel, E. and Rácz, M. Z. (2015). On the influence of the seed graph in the preferential attachment model. IEEE Trans. Netw. Sci. Eng.2 30-39.
[16] Carlstein, E. (1988). Nonparametric change-point estimation. Ann. Statist.16 188-197. · Zbl 0637.62041
[17] Carlstein, E., Müller, H.-G. and Siegmund, D., eds. (1994). Change-Point Problems (South Hadley, MA, 1992). Institute of Mathematical Statistics Lecture Notes—Monograph Series 23. IMS, Hayward, CA.
[18] Chandola, V., Banerjee, A. and Kumar, V. (2009). Anomaly detection: A survey. ACM Comput. Surv.41 Article No. 15.
[19] Chung, F. and Lu, L. (2006). Complex Graphs and Networks. CBMS Regional Conference Series in Mathematics 107. Amer. Math. Soc., Providence, RI. · Zbl 1114.90071
[20] Cooper, C. and Frieze, A. (2003). A general model of web graphs. Random Structures Algorithms 22 311-335. · Zbl 1018.60007
[21] Csörgő, M. and Horváth, L. (1997). Limit Theorems in Change-Point Analysis. Wiley, Chichester.
[22] Curien, N., Duquesne, T., Kortchemski, I. and Manolescu, I. (2015). Scaling limits and influence of the seed graph in preferential attachment trees. J. Éc. Polytech. Math.2 1-34. · Zbl 1320.05110
[23] Dorogovtsev, S. N. and Mendes, J. F. F. (2003). Evolution of Networks. Oxford Univ. Press, Oxford. · Zbl 1109.68537
[24] Duan, D., Li, Y., Jin, Y. and Lu, Z. (2009). Community mining on dynamic weighted directed graphs. In Proceedings of the 1 st ACM International Workshop on Complex Networks Meet Information & Knowledge Management 11-18.
[25] Durrett, R. (2007). Random Graph Dynamics. Cambridge Series in Statistical and Probabilistic Mathematics 20. Cambridge Univ. Press, Cambridge. · Zbl 1116.05001
[26] Durrett, R. and Resnick, S. I. (1978). Functional limit theorems for dependent variables. Ann. Probab.6 829-846. · Zbl 0398.60024
[27] Eagle, N. and Pentland, A. (2006). Reality mining: Sensing complex social systems. Personal and Ubiquitous Computing 10 255-268.
[28] Eberle, W. and Holder, L. (2007). Discovering structural anomalies in graph-based data. In Seventh IEEE International Conference on Data Mining Workshops (ICDMW 2007) 393-398.
[29] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley, New York. · Zbl 0592.60049
[30] Heard, N. A., Weston, D. J., Platanioti, K. and Hand, D. J. (2010). Bayesian anomaly detection methods for social networks. Ann. Appl. Stat.4 645-662. · Zbl 1194.62021
[31] Holme, P. and Saramäki, J. (2012). Temporal networks. Phys. Rep.519 97-125.
[32] Huang, Z. and Zeng, D. D. (2006). A link prediction approach to anomalous email detection. In 2006 IEEE International Conference on Systems, Man and Cybernetics 1131-1136.
[33] Jagers, P. (1975). Branching Processes with Biological Applications. Wiley-Interscience, London. · Zbl 0356.60039
[34] Jagers, P. and Nerman, O. (1984). The growth and composition of branching populations. Adv. in Appl. Probab.16 221-259. · Zbl 0535.60075
[35] Jagers, P. and Nerman, O. (1984). Limit theorems for sums determined by branching and other exponentially growing processes. Stochastic Process. Appl.17 47-71. · Zbl 0532.60081
[36] Liptser, R. and Shiryayev, A. N. (1989). Theory of Martingales. Mathematics and Its Applications (Soviet Series) 49. Kluwer Academic, Dordrecht. · Zbl 0728.60048
[37] Ma, W.-Y. and Manjunath, B. S. (1997). Edge flow: A framework of boundary detection and image segmentation. In Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition 744-749.
[38] Marangoni-Simonsen, D. and Xie, Y. (2015). Sequential changepoint approach for online community detection. IEEE Signal Process. Lett.22 1035-1039.
[39] McCulloh, I. and Carley, K. M. (2011). Detecting change in longitudinal social networks. DTIC Document.
[40] Moreno, S. and Neville, J. (2013). Network hypothesis testing using mixed Kronecker product graph models. In 2013 IEEE 13 th International Conference on Data Mining 1163-1168.
[41] Móri, T. F. (2007). Degree distribution nearby the origin of a preferential attachment graph. Electron. Commun. Probab.12 276-282. · Zbl 1136.60030
[42] Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev.45 167-256. · Zbl 1029.68010
[43] Newman, M. E. J. (2010). Networks: An Introduction. Oxford Univ. Press, Oxford. · Zbl 1195.94003
[44] Noble, C. C. and Cook, D. J. (2003). Graph-based anomaly detection. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 631-636.
[45] Norris, J. R. (1998). Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics 2. Cambridge Univ. Press, Cambridge. Reprint of 1997 original.
[46] Peel, L. and Clauset, A. (2014). Detecting change points in the large-scale structure of evolving networks. Available at arXiv:1403.0989.
[47] Priebe, C. E., Conroy, J. M., Marchette, D. J. and Park, Y. (2005). Scan statistics on enron graphs. Comput. Math. Organ. Theory 11 229-247. · Zbl 1086.68562
[48] Resnick, S. I. and Samorodnitsky, G. (2016). Asymptotic normality of degree counts in a preferential attachment model. Adv. in Appl. Probab.48 283-299.
[49] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 186-202.
[50] Sharpnack, J., Rinaldo, A. and Singh, A. (2012). Changepoint detection over graphs with the spectral scan statistic. Available at arXiv:1206.0773.
[51] Shiryaev, A. N. (2008). Optimal Stopping Rules. Stochastic Modelling and Applied Probability 8. Springer, Berlin.
[52] Siegmund, D. (1985). Sequential Analysis: Tests and Confidence Intervals. Springer, New York. · Zbl 0573.62071
[53] Simon, H. A. (1955). On a class of skew distribution functions. Biometrika 42 425-440. · Zbl 0066.11201
[54] Širjaev, A. N. (1963). Optimal methods in quickest detection problems. Teor. Verojatnost. i Primenen.8 26-51.
[55] Sun, J., Faloutsos, C., Papadimitriou, S. and Yu, P. S. (2007). Graphscope: Parameter-free mining of large time-evolving graphs. In Proceedings of the 13 th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 687-696.
[56] Szymański, J. (1987). On a nonuniform random recursive tree. In Random Graphs ’85 (Poznań, 1985). North-Holland Math. Stud.144 297-306. North-Holland, Amsterdam.
[57] Tsybakov, A. B. (1994). Multidimensional change-point problems and boundary estimation. In Change-Point Problems (South Hadley, MA, 1992). Institute of Mathematical Statistics Lecture Notes—Monograph Series 23 317-329. IMS, Hayward, CA. · Zbl 1163.62331
[58] van der Hofstad, R. (2016). Random Graphs and Complex Networks, Vol. 1. Cambridge Univ. Press, Cambridge. Available at http://www.win.tue.nl/rhofstad/NotesRGCN.pdf. · Zbl 1361.05002
[59] Yudovina, E., Banerjee, M. and Michailidis, G. (2015). Changepoint inference for Erdős-Rényi random graphs. In Stochastic Models, Statistics and Their Applications. Springer Proc. Math. Stat.122 197-205. Springer, Cham. · Zbl 1382.94178
[60] Yule, G. U. (1925). A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F.R.S. Philos. Trans. R. Soc. Lond. Ser. B 213 21-87.
[61] Zhang, W.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.