Joint modeling of change-point identification and dependent dynamic community detection. (English) Zbl 07901848
Summary: The field of dynamic network analysis has recently seen a surge of interest in community detection and evolution. However, existing methods for dynamic community detection do not consider dependencies between edges, which could lead to a loss of information when detecting community structures. In this study, we investigate the problem of identifying a change-point with abrupt changes in the community structure of a network. To do so, we propose an approximate likelihood approach for the change-point estimator and for identifying node membership that integrates marginal information and dependencies of network connectivities. We propose an expectation-maximization-type algorithm that maximizes the approximate likelihood jointly over change-point and community membership evolution. From a theoretical viewpoint, we establish estimation consistency under the regularity condition, and show that the proposed estimators achieve a higher convergence rate than those of their marginal likelihood counterparts, which do not incorporate dependencies between edges. We demonstrate the validity of the proposed method by applying it to the ADHD-200 data set to detect brain functional community changes over time.
MSC:
| 62-XX | Statistics |
References:
| [1] | Arnsten, A. F. and Li, B.-M. (2005). Neurobiology of executive functions: Catecholamine influences on prefrontal cortical functions. Biological Psychiatry 57, 1377-1384. Standford University Press, Stanford. |
| [2] | Bahadur, R. R. (1961). A representation of the joint distribution of responses to n dichotomous items. In Studies in Item Analysis and Prediction, 169-176. Standford University Press, Stanford. · Zbl 0103.36702 |
| [3] | Bhattacharjee, M., Banerjee, M. and Michailidis, G. (2020). Change point estimation in a dynamic stochastic block model. Journal of Machine Learning Research 21, 1-59. · Zbl 1524.62409 |
| [4] | Blondel, V. D., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, P10008. · Zbl 1459.91130 |
| [5] | Bush, G., Valera, E. M. and Seidman, L. J. (2005). Functional neuroimaging of attention-deficit/hyperactivity disorder: A review and suggested future directions. Biological Psychiatry 57, 1273-1284. |
| [6] | Carmona, S., Vilarroya, O., Bielsa, A., Tremols, V., Soliva, J., Rovira, M. et al. (2005). Global and regional gray matter reductions in ADHD: A voxel-based morphometric study. Neuroscience Letters 389, 88-93. |
| [7] | Cary, R. P., Ray, S., Grayson, D. S., Painter, J., Carpenter, S., Maron, L. et al. (2017). Network structure among brain systems in adult ADHD is uniquely modified by stimulant administration. Cerebral Cortex 27, 3970-3979. |
| [8] | Castellanos, F. X., Lee, P. P., Sharp, W., Jeffries, N. O., Greenstein, D. K., Clasen, L. S. et al.(2002). Developmental trajectories of brain volume abnormalities in children and adolescents with attention-deficit/hyperactivity disorder. JAMA 288, 1740-1748. |
| [9] | Celisse, A., Daudin, J.-J. and Pierre, L. (2012). Consistency of maximum-likelihood and variational estimators in the stochastic block model. Electronic Journal of Statistics 6, 1847-1899. · Zbl 1295.62028 |
| [10] | Chen, Y., Li, X. and Xu, J. (2018). Convexified modularity maximization for degree-corrected stochastic block models. The Annals of Statistics 46, 1573-1602. · Zbl 1410.62105 |
| [11] | Cheng, J., Levina, E., Wang, P. and Zhu, J. (2014). A sparse Ising model with covariates. Biometrics 70, 943-953. · Zbl 1393.62057 |
| [12] | Dubey, P. and Müller, H.-G. (2020). Fréchet change-point detection. The Annals of Statistics 48, 3312-3335. · Zbl 1461.62243 |
| [13] | Fassbender, C., Schweitzer, J. B., Cortes, C. R., Tagamets, M. A., Windsor, T. A., Reeves, G. M. et al. (2011). Working memory in attention deficit/hyperactivity disorder is characterized by a lack of specialization of brain function. PloS One 6, e27240. |
| [14] | Frank, O. and Strauss, D. (1986). Markov graphs. Journal of the American Statistical Association 81, 832-842. · Zbl 0607.05057 |
| [15] | Gao, C., Ma, Z., Zhang, A. Y. and Zhou, H. H. (2018). Community detection in degree-corrected block models. The Annals of Statistics 46, 2153-2185. · Zbl 1408.62116 |
| [16] | Garrett Fitzmaurice, G. V. G. M. and Marie Davidian (2009). Longitudinal Data Analysis: Handbooks of Modern Statistical Methods. CRC Press. · Zbl 1144.62087 |
| [17] | Gibberd, A. J. and Nelson, J. D. (2017). Regularized estimation of piecewise constant Gaussian graphical models: The group-fused graphical Lasso. Journal of Computational and Graphical Statistics 26, 623-634. |
| [18] | He, Y., Lim, S., Fortunato, S., Sporns, O., Zhang, L., Qiu, J. et al.(2018). Reconfiguration of cortical networks in MDD uncovered by multiscale community detection with fMRI. Cerebral Cortex 28, 1383-1395. |
| [19] | Heaukulani, C. and Ghahramani, Z. (2013). Dynamic probabilistic models for latent feature propagation in social networks. In Proceedings of the 30th International Conference on Machine Learning PMLR 28, 275-283. |
| [20] | Hilger, K. and Fiebach, C. J. (2019). ADHD symptoms are associated with the modular structure of intrinsic brain networks in a representative sample of healthy adults. Network Neuroscience 3, 567-588. |
| [21] | Kolar, M., Song, L., Ahmed, A. and Xing, E. P. (2010). Estimating time-varying networks. The Annals of Applied Statistics 4, 94-123. · Zbl 1189.62142 |
| [22] | Le, C. M., Levin, K. and Levina, E. (2018). Estimating a network from multiple noisy realizations. Electronic Journal of Statistics 12, 4697-4740. · Zbl 1409.62115 |
| [23] | Levin, K., Lodhia, A. and Levina, E. (2019). Recovering low-rank structure from multiple networks with unknown edge distributions. arXiv:1906.07265. |
| [24] | Liu, G., Wang, Y. and Orgun, M. A. (2011). Trust transitivity in complex social networks. In Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI 2011. San Francisco. |
| [25] | Marangoni-Simonsen, D. and Xie, Y. (2015). Sequential changepoint approach for online community detection. IEEE Signal Processing Letters 22, 1035-1039. |
| [26] | Matias, C. and Miele, V. (2017). Statistical clustering of temporal networks through a dynamic stochastic block model. Journal of the Royal Statistical Society. Series B (Statistical Methodology) 79, 1119-1141. · Zbl 1373.62312 |
| [27] | Mei, Q. and Zhai, C. (2005). Discovering evolutionary theme patterns from text: An exploration of temporal text mining. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, 198-207. ACM. |
| [28] | Palla, G., Barabási, A.-L. and Vicsek, T. (2007). Quantifying social group evolution. Nature 446, 664-667. |
| [29] | Park, H. and Lee, K. (2014). Dependence clustering, a method revealing community structure with group dependence. Knowledge-Based Systems 60, 58-72. |
| [30] | Peng, J., Wang, P., Zhou, N. and Zhu, J. (2009). Partial correlation estimation by joint sparse regression models. Journal of the American Statistical Association 104, 735-746. · Zbl 1388.62046 |
| [31] | Robins, G., Pattison, P., Kalish, Y. and Lusher, D. (2007a). An introduction to exponential random graph (p * ) models for social networks. Social Networks 29, 173-191. |
| [32] | Robins, G., Snijders, T., Wang, P., Handcock, M. and Pattison, P. (2007b). Recent developments in exponential random graph (p * ) models for social networks. Social Networks 29, 192-215. |
| [33] | Sarkar, P. and Moore, A. W. (2006). Dynamic social network analysis using latent space models. In Advances in Neural Information Processing Systems, 1145-1152. |
| [34] | Sewell, D. K. and Chen, Y. (2017). Latent space approaches to community detection in dynamic networks. Bayesian Analysis 12, 351-377. · Zbl 1384.62203 |
| [35] | Toplak, M. E., Dockstader, C. and Tannock, R. (2006). Temporal information processing in ADHD: Findings to date and new methods. Journal of Neuroscience Methods 151, 15-29. |
| [36] | Toyoda, M. and Kitsuregawa, M. (2003). Extracting evolution of web communities from a series of web archives. In Proceedings of the 14th ACM Conference on Hypertext and Hypermedia, 28-37. ACM. |
| [37] | van der Vaart, A. W. (2000). Asymptotic Statistics. Cambridge University Press. · Zbl 0943.62002 |
| [38] | Wang, D., Yu, Y. and Rinaldo, A. (2018). Optimal change point detection and localization in sparse dynamic networks. arXiv:1809.09602. |
| [39] | Wang, S., Arroyo, J., Vogelstein, J. T. and Priebe, C. E. (2019). Joint embedding of graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 43, 1324-1336. |
| [40] | Wang, Y., Chakrabarti, A., Sivakoff, D. and Parthasarathy, S. (2017a). Fast change point detection on dynamic social networks. arXiv:1705.07325. |
| [41] | Wang, Y., Chakrabarti, A., Sivakoff, D. and Parthasarathy, S. (2017b). Hierarchical change point detection on dynamic networks. In Proceedings of the 2017 ACM on Web Science Conference, 171-179. ACM. |
| [42] | Wilson, J. D., Stevens, N. T. and Woodall, W. H. (2019). Modeling and detecting change in temporal networks via the degree-corrected stochastic block model. Quality and Reliability Engineering International 35, 1363-1378. |
| [43] | Xia, M., Wang, J. and He, Y. (2013). BrainNet viewer: A network visualization tool for human brain connectomics. PloS One 8, e68910. |
| [44] | Xing, E. P., Fu, W. and Song, L. (2010). A state-space mixed membership blockmodel for dynamic network tomography. The Annals of Applied Statistics 4, 535-566. · Zbl 1194.62133 |
| [45] | Xu, K. S. and Hero, A. O. (2014). Dynamic stochastic blockmodels for time-evolving social networks. IEEE Journal of Selected Topics in Signal Processing 8, 552-562. |
| [46] | Yang, J. and Peng, J. (2018). Estimating time-varying graphical models. arXiv:1804.03811. |
| [47] | Yang, T., Chi, Y., Zhu, S., Gong, Y. and Jin, R. (2011). Detecting communities and their evolutions in dynamic social networks-a Bayesian approach. Machine Learning 82, 157-189. · Zbl 1237.91189 |
| [48] | Yapeng, L., Yuanyuan, Q., Xi, C., Wei, L. and Gianluigi, F. (2013). Exploring the functional brain network of alzheimer’s disease: Based on the computational experiment. Plos One 8, e73186. |
| [49] | Yuan, Y. and Qu, A. (2021). Community detection with dependent connectivity. The Annals of Statistics 49, 2378-2428. · Zbl 1480.62259 |
| [50] | Zhao, Z., Chen, L. and Lin, L. (2019). Change-point detection in dynamic networks via graphon estimation. arXiv:1908.01823. |
| [51] | Diqing Li School of Statistics and Mathematics, Zhejiang Gongshang University, Zhejiang 310018, China. E-mail: dqli@mail.zjgsu.edu.cn Yubai Yuan Department of Statistics, The Pennsylvania State University, PA 16802, USA. |
| [52] | E-mail: yvy5509@psu.edu Xinsheng Zhang Department of Statistics and Data Science, Fudan University, Shanghai 200433, China. E-mail: xszhang@fudan.edu.cn |
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.
