Change point analysis of events in social networks: An online convex optimization approach

Abstract: Nowadays, online social networks play a crucial role in shaping human communication in various life activities. Social Network Analysis (SNA) provides valuable insights for businesses, authorities, and platform owners. One of the challenging tasks in SNA is detecting sequential change points in observed events in social networks when the parameters of statistical distribution of post-change networks are unknown. This challenging problem is particularly prominent in various real-world network systems, especially when the events in the networks can be modeled through a Hawkes process. Identifying change points in the stream of social network data, where the underlying statistical properties undergo significant changes, necessitates the development of adaptive online algorithms. Additionally, in cases where the use of maximum likelihood estimators is impractical or when no exact recursive function for likelihood is available, addressing this issue becomes more complex. This paper proposes likelihood estimators using online convex optimization methods, incorporating the adaptive moment estimation (ADAM) algorithm. The proposed method is seamlessly integrated into the sequential anomaly detection procedure for events in social networks. Experimental results on monitoring time between events demonstrate lower Expected Delay Detection (EDD), indicating the superiority of the proposed algorithm in both synthetic and real-world datasets such as Facebook and contact networks of individuals causing disease transmission. The proposed robust solution provides an efficient practical tool in situations where traditional methods face limitations in swift detection with high accuracy.

How to cite this paper

 Karami, A & Niaki, S. (2024). Change point analysis of events in social networks: An online convex optimization approach.International Journal of Industrial Engineering Computations , 15(3), 755-772.

Refrences

Ali, F., El-Sappagh, S., Islam, S. M. R., Ali, A., Attique, M., Imran, M., & Kwak, K.-S. (2021). An intelligent healthcare monitoring framework using wearable sensors and social networking data. Future Generation Computer Systems, 114, 23–43.
Aminikhanghahi, S., & Cook, D. J. (2017). A survey of methods for time series change point detection. Knowledge and Information Systems, 51(2), 339–367.
Azoury, K. S., & Warmuth, M. K. (2001). Relative loss bounds for on-line density estimation with the exponential family of distributions. Machine Learning, 43, 211–246.
Cao, Y., Xie, L., Xie, Y., & Xu, H. (2018). Sequential change-point detection via online convex optimization. Entropy, 20(2), 108.
Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
Chen, X., Liu, S., Sun, R., & Hong, M. (2019). On the convergence of a class of Adam-type algorithms for non-convex optimization. 7th International Conference on Learning Representations, ICLR 2019.
Drury, B., Drury, S. M., Rahman, M. A., & Ullah, I. (2022). A social network of crime: A review of the use of social networks for crime and the detection of crime. Online Social Networks and Media, 30, 100211.
Fisch, A. T. M., Eckley, I. A., & Fearnhead, P. (2022). A linear time method for the detection of collective and point anomalies. Statistical Analysis and Data Mining: The ASA Data Science Journal, 15(4), 494–508.
He, F., Mao, T., Hu, T., & Shu, L. (2018). A new type of change-detection scheme based on the window-limited weighted likelihood ratios. Expert Systems with Applications, 94, 149–163.
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., & Hochreiter, S. (2017). Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in Neural Information Processing Systems, 30.
Karami, A., & Niaki, S. T. A. (2024). An Online Support Vector Machine Algorithm for Dynamic Social Network Monitoring. Neural Networks, 171, 497-511.
Karimi, M., & Sadjadi, S. J. (2024). Optimization of an economic ordering quantity model for non-instantaneous deteriorating items with ordering time constraint using dynamic programming. Journal of Industrial and Management Optimization, 20(3), 1114–1141.
Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. ArXiv Preprint ArXiv:1412.6980.
Kotłowski, W., & Grünwald, P. (2011). Maximum likelihood vs. sequential normalized maximum likelihood in on-line density estimation. Proceedings of the 24th Annual Conference on Learning Theory, 457–476.
Kovács, S., Bühlmann, P., Li, H., & Munk, A. (2023). Seeded binary segmentation: a general methodology for fast and optimal changepoint detection. Biometrika, 110(1), 249–256.
Lai, T. L., & Xing, H. (2010). Sequential change-point detection when the pre-and post-change parameters are unknown. Sequential Analysis, 29(2), 162–175.
Li, S., Xiao, S., Zhu, S., Du, N., Xie, Y., & Song, L. (2018). Learning temporal point processes via reinforcement learning. Advances in Neural Information Processing Systems, 31.
Lorden, G. (1971). Procedures for reacting to a change in distribution. The Annals of Mathematical Statistics, 1897–1908.
Mariani, S., & Cawley, P. (2021). Change detection using the generalized likelihood ratio method to improve the sensitivity of guided wave structural health monitoring systems. Structural Health Monitoring, 20(6), 3201–3226.
Mei, Y. (2006). Sequential change-point detection when unknown parameters are present in the pre-change distribution.
Miller, H., & Mokryn, O. (2020). Size agnostic change point detection framework for evolving networks. Plos One, 15(4), e0231035.
Pollak, M. (1985). Optimal detection of a change in distribution. The Annals of Statistics, 206–227.
Pollak, M. (1987). Average run lengths of an optimal method of detecting a change in distribution. The Annals of Statistics, 749–779.
Raginsky, M., Marcia, R. F., Silva, J., & Willett, R. M. (2009). Sequential probability assignment via online convex programming using exponential families. 2009 IEEE International Symposium on Information Theory, 1338–1342.
Raginsky, M., Willett, R. M., Horn, C., Silva, J., & Marcia, R. F. (2012). Sequential anomaly detection in the presence of noise and limited feedback. IEEE Transactions on Information Theory, 58(8), 5544–5562.
Romano, G., Eckley, I. A., Fearnhead, P., & Rigaill, G. (2023). Fast online changepoint detection via functional pruning CUSUM statistics. Journal of Machine Learning Research, 24, 1–36.
Ruggieri, E., & Antonellis, M. (2016). An exact approach to Bayesian sequential change point detection. Computational Statistics & Data Analysis, 97, 71–86.
Shiryaev, A. N. (1963). On optimum methods in quickest detection problems. Theory of Probability & Its Applications, 8(1), 22–46.
Shiryaev, A. N. (2010). Quickest detection problems: Fifty years later. Sequential Analysis, 29(4), 345–385.
Siegmund, D. O., & Yakir, B. (2008). Minimax optimality of the Shiryayev–Roberts change-point detection rule. Journal of Statistical Planning and Inference, 138(9), 2815–2825.
Song, G., Li, Y., Chen, X., He, X., & Tang, J. (2016). Influential node tracking on dynamic social network: An interchange greedy approach. IEEE Transactions on Knowledge and Data Engineering, 29(2), 359–372.
Tartakovsky, A. G., Rozovskii, B. L., Blazek, R. B., & Kim, H. (2006). A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods. IEEE Transactions on Signal Processing, 54(9), 3372–3382.
Wang, H., Xie, L., Xie, Y., Cuozzo, A., & Mak, S. (2023). Sequential Change-Point Detection for Mutually Exciting Point Processes. Technometrics, 65(1), 44–56.
Wang, T., & Resnick, S. I. (2021). Common Growth Patterns for Regional Social Networks: A Point Process Approach. Journal of Data Science, 1–24.
Xie, L., Moustakides, G. V, & Xie, Y. (2023). Window-limited CUSUM for sequential change detection. IEEE Transactions on Information Theory.
Zarepour, M., & Habibi, R. (2023). A quasi-Bayesian change point detection with exchangeable weights. Journal of Statistical Planning and Inference, 222, 226–240.
Zhu, X., Li, Y., Liang, C., Chen, J., & Wu, D. (2013). Copula based change point detection for financial contagion in chinese banking. Procedia Computer Science, 17, 619–626.