Multiple change points detection and clustering in dynamic networks. (English) Zbl 1405.62076
Summary: The increasing amount of data stored in the form of dynamic interactions between actors necessitates the use of methodologies to automatically extract relevant information. The interactions can be represented by dynamic networks in which most existing methods look for clusters of vertices to summarize the data. In this paper, a new framework is proposed in order to cluster the vertices while detecting change points in the intensities of the interactions. These change points are key in the understanding of the temporal interactions. The model used involves non-homogeneous Poisson point processes with cluster-dependent piecewise constant intensity functions and common discontinuity points. A variational expectation maximization algorithm is derived for inference. We show that the pruned exact linear time method, originally developed for change points detection in univariate time series, can be considered for the maximization step. This allows the detection of both the number of change points and
their location. Experiments on artificial and real datasets are carried out, and the proposed approach is compared with related methods.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 62G10 | Nonparametric hypothesis testing |
| 90B15 | Stochastic network models in operations research |
Keywords:
dynamic networks; non-homogeneous Poisson point processes; stochastic block model; variational EM; PELT; clusteringReferences:
| [1] | Achab, M., Bacry, E., Gaïffas, S., Mastromatteo, I., Muzy, J.F.: Uncovering causality from multivariate Hawkes integrated cumulants. ArXiv preprint arXiv:1607.06333 (2016) · Zbl 1472.62076 |
| [2] | Airoldi, E; Blei, D; Fienberg, S; Xing, E, Mixed membership stochastic blockmodels, J. Mach. Learn. Res., 9, 1981-2014, (2008) · Zbl 1225.68143 |
| [3] | Boullé, M.: Optimum simultaneous discretization with data grid models in supervised classification: a Bayesian model selection approach. Adv. Data Anal. Classif. 3(1), 39-61 (2009) · Zbl 1231.62030 |
| [4] | Casteigts, A; Flocchini, P; Quattrociocchi, W; Santoro, N, Time-varying graphs and dynamic networks, Int. J. Parallel Emerg. Distrib. Syst., 27, 387-408, (2012) · doi:10.1080/17445760.2012.668546 |
| [5] | Corneli, M; Latouche, P; Rossi, F, Block modelling in dynamic networks with non-homogeneous Poisson processes and exact ICL, Soc. Netw. Anal. Min., 6, 1-14, (2016) · doi:10.1007/s13278-016-0368-3 |
| [6] | Corneli, M; Latouche, P; Rossi, F, Exact ICL maximization in a non-stationary temporal extension of the stochastic block model for dynamic networks, Neurocomputing, 192, 81-91, (2016) · doi:10.1016/j.neucom.2016.02.031 |
| [7] | Daley, D.J., Vere-Jones, D.: An Introduction to the Theory of Point Processes. Volume I: Elementary Theory and Methods. Springer, Berlin (2003) · Zbl 1026.60061 |
| [8] | Daudin, JJ; Picard, F; Robin, S, A mixture model for random graphs, Stat. Comput., 18, 173-183, (2008) · doi:10.1007/s11222-007-9046-7 |
| [9] | Dempster, A.P., Rubin, D.B., Laird, N.M.: Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. Ser. B (Methodol.) 39(1), 1-38. http://www.jstor.org/stable/2984875 (1977) · Zbl 0364.62022 |
| [10] | Dubois, C., Butts, C., Smyth, P.: Stochastic block modelling of relational event dynamics. In: International Conference on Artificial Intelligence and Statistics, Volume 31 of the Journal of Machine Learning Research Proceedings, pp. 238-246 (2013) |
| [11] | Durante, D; Dunson, DB; etal., Locally adaptive dynamic networks, Ann. Appl. Stat., 10, 2203-2232, (2016) · Zbl 1454.62495 · doi:10.1214/16-AOAS971 |
| [12] | Fortunato, S, Community detection in graphs, Phys. Rep., 486, 75-174, (2010) · doi:10.1016/j.physrep.2009.11.002 |
| [13] | Friel, N., Rastelli, R., Wyse, J., Raftery, A.E.: Interlocking directorates in Irish companies using a latent space model for bipartite networks. In: Proceedings of the National Academy of Sciences, vol. 113, no. 24, pp. 6629-6634. doi:10.1073/pnas.1606295113. http://www.pnas.org/content/113/24/6629.full.pdf (2016) |
| [14] | Guigourès, R., Boullé, M., Rossi, F.: A triclustering approach for time evolving graphs. In: Co-clustering and Applications, IEEE 12th International Conference on Data Mining Workshops (ICDMW 2012), Brussels, Belgium, pp. 115-122. doi:10.1109/ICDMW.2012.61 (2012) |
| [15] | Guigourès, R., Boullé, M., Rossi, F.: Discovering patterns in time-varying graphs: a triclustering approach. In: Advances in Data Analysis and Classification, pp. 1-28. doi:10.1007/s11634-015-0218-6 (2015) |
| [16] | Hanneke, S; Fu, W; Xing, EP; etal., Discrete temporal models of social networks, Electron. J. Stat., 4, 585-605, (2010) · Zbl 1329.91113 · doi:10.1214/09-EJS548 |
| [17] | Hawkes, A.G.: Point spectra of some mutually exciting point processes. J. R. Stat. Soc. Ser. B (Methodol.) 33(3), 438-443 (1971) · Zbl 0238.60094 |
| [18] | Ho, Q., Song, L., Xing, E.P.: Evolving cluster mixed-membership blockmodel for time-evolving networks. In: International Conference on Artificial Intelligence and Statistics, pp. 342-350 (2011) |
| [19] | Hoff, P; Raftery, A; Handcock, M, Latent space approaches to social network analysis, J. Am. Stat. Assoc., 97, 1090-1098, (2002) · Zbl 1041.62098 · doi:10.1198/016214502388618906 |
| [20] | Jackson, B., Sargle, J., Barnes, D., Arabhi, S., Alt, A., Giomousis, P., Gwin, E., Sangtrakulcharoen, P., Tan, L., Tsai, T.: An algorithm for optimal partitioning of data on an interval. In: Signal Processing Letters, pp. 105-108 (2005) |
| [21] | Jernite, Y; Latouche, P; Bouveyron, C; Rivera, P; Jegou, L; Lamassé, S, The random subgraph model for the analysis of an ecclesiastical network in Merovingian gaul, Ann. Appl. Stat., 8, 55-74, (2014) · Zbl 1454.62539 · doi:10.1214/13-AOAS691 |
| [22] | Killick, R; Fearnhead, P; Eckley, IA, Optimal detection of changepoints with a linear computational cost., J. Am. Stat. Assoc., 107, 1590-1598, (2012) · Zbl 1258.62091 · doi:10.1080/01621459.2012.737745 |
| [23] | Kim, M; Leskovec, J, Nonparametric multi-group membership model for dynamic networks, Adv. Neural Inf. Process. Syst., 25, 1385-1393, (2013) |
| [24] | Kolda, TG; Bader, BW, Tensor decompositions and applications., SIAM Rev., 51, 455-500, (2009) · Zbl 1173.65029 · doi:10.1137/07070111X |
| [25] | Krivitsky, PN; Handcock, MS, A separable model for dynamic networks, J. R. Stat. Soc. Ser. B (Stat. Methodol.), 76, 29-46, (2014) · Zbl 1411.90079 · doi:10.1111/rssb.12014 |
| [26] | Latouche, P., Birmelé, E., Ambroise, C.: Overlapping stochastic block models with application to the French political blogosphere. Ann. Appl. Stat., 5(1) 309-336 (2011) · Zbl 1220.62083 |
| [27] | Lewis, P; Shedler, G, Simulation of nonhomogeneous poison processes by thinning, Naval Res. Logist. Q., 26, 403-413, (1979) · Zbl 0497.60003 · doi:10.1002/nav.3800260304 |
| [28] | Matias, C., Miele, V.: Statistical clustering of temporal networks through a dynamic stochastic block model. J. R. Stat. Soc. Ser. B 79(4), 1119-1141 (2017) · Zbl 1373.62312 |
| [29] | Matias, C., Rebafka, T., Villers, F.: Estimation and clustering in a semiparametric Poisson process stochastic block model for longitudinal networks. arXiv:1512.07075 e-prints (2015) · Zbl 1499.62213 |
| [30] | Nouedoui, L., Latouche, P.: Bayesian non parametric inference of discrete valued networks. In: 21-th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2013), Bruges, Belgium, pp. 291-296 (2013) |
| [31] | Nowicki, K; Snijders, T, Estimation and prediction for stochastic blockstructures, J. Am. Stat. Assoc., 96, 1077-1087, (2001) · Zbl 1072.62542 · doi:10.1198/016214501753208735 |
| [32] | Rand, WM, Objective criteria for the evaluation of clustering methods, J. Am. Stat. Assoc., 66, 846-850, (1971) · doi:10.1080/01621459.1971.10482356 |
| [33] | Robins, G; Pattison, P; Kalish, Y; Lusher, D, An introduction to exponential random graph (\(p\)*) models for social networks, Soc. Netw., 29, 173-191, (2007) · doi:10.1016/j.socnet.2006.08.002 |
| [34] | Sarkar, P; Moore, AW, Dynamic social network analysis using latent space models, ACM SIGKDD Explor. Newsl., 7, 31-40, (2005) · doi:10.1145/1117454.1117459 |
| [35] | Sewell, DK; Chen, Y, Latent space models for dynamic networks, J. Am. Stat. Assoc., 110, 1646-1657, (2015) · Zbl 1373.62580 · doi:10.1080/01621459.2014.988214 |
| [36] | Sewell, DK; Chen, Y, Latent space models for dynamic networks with weighted edges, Soc. Netw., 44, 105-116, (2016) · doi:10.1016/j.socnet.2015.07.005 |
| [37] | Snijders, TA, Stochastic actor-oriented models for network change, J. Math. Sociol., 21, 149-172, (1996) · Zbl 0883.92038 · doi:10.1080/0022250X.1996.9990178 |
| [38] | Luxburg, U, A tutorial on spectral clustering, Stat. Comput., 17, 395-416, (2007) · doi:10.1007/s11222-007-9033-z |
| [39] | Wang, Y; Wong, G, Stochastic blockmodels for directed graphs, J. Am. Stat. Assoc., 82, 8-19, (1987) · Zbl 0613.62146 · doi:10.1080/01621459.1987.10478385 |
| [40] | Xing, EP; Fu, W; Song, L, A state-space mixed membership blockmodel for dynamic network tomography, Ann. Appl. Stat., 4, 535-566, (2010) · Zbl 1194.62133 · doi:10.1214/09-AOAS311 |
| [41] | Xu, H., Farajtabar, M., Zha, H.: Learning granger causality for Hawkes processes. In: Proceedings of the 33rd International Conference on Machine Learning, pp. 1717-1726 (2016) |
| [42] | Xu, K.S., Hero III, A.O.: Dynamic stochastic blockmodels for time-evolving social networks. IEEE J Sel Top Signal Process. 8(4), 552-562 (2014) |
| [43] | Yang, T; Chi, Y; Zhu, S; Gong, Y; Jin, R, Detecting communities and their evolutions in dynamic social networks a Bayesian approach, Mach. Learn., 82, 157-189, (2011) · Zbl 1237.91189 · doi:10.1007/s10994-010-5214-7 |
| [44] | Zreik, R; Latouche, P; Bouveyron, C, The dynamic random subgraph model for the clustering of evolving networks, Comput. Stat., 32, 501-533, (2016) · Zbl 1417.62182 · doi:10.1007/s00180-016-0655-5 |
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.
