A simplified algorithm for identifying abnormal changes in dynamic networks. (English) Zbl 07614964
Summary: Topological data analysis has recently been applied to the study of dynamic networks. In this context, an algorithm was introduced and helps, among other things, to detect early warning signals of abnormal changes in the dynamic network under study. However, the complexity of this algorithm increases significantly once the database studied grows. In this paper, we propose a simplification of the algorithm without affecting its performance. We give various applications and simulations of the new algorithm on some weighted networks. The obtained results show clearly the efficiency of the introduced approach. Moreover, in some cases, the proposed algorithm makes it possible to highlight local information and sometimes early warning signals of local abnormal changes.
MSC:
| 82-XX | Statistical mechanics, structure of matter |
| 55N35 | Other homology theories in algebraic topology |
| 55U99 | Applied homological algebra and category theory in algebraic topology |
| 91B84 | Economic time series analysis |
Software:
TDAReferences:
| [1] | Hewapathirana, I., Change detection in dynamic attributed networks, Data Min. Knowl. Discov., 9, Article e1286 pp. (2019) |
| [2] | Jeanneau, D., Failure Detectors in Dynamic Distributed Systems (2018), Sorbonne University, Available at https://tel.archives-ouvertes.fr/tel-01951975v2 |
| [3] | Li, H.-J.; Wang, Z.; Cao, J.; Pei, J.; Shi, Y., Optimal estimation of low-rank factors via feature level data fusion of multiplex signal systems, IEEE Trans. Knowl. Data Eng., 34, 2860-2871 (2022) |
| [4] | Li, H.-J.; Wang, L.; Zhang, Y.; Perc, M., Optimization of identifiability for efficient community detection, New J. Phys., 22, Article 063035 pp. (2020) |
| [5] | Li, H.-J.; Wang, L.; Bu, Z.; Cao, J.; Shi, Y., Measuring the network vulnerability based on markov criticality, ACM Trans. Knowl. Discov. Data, 16, 1-24 (2021) |
| [6] | Li, H.-J.; Xu, W.; Qiu, C.; Pei, J., Fast markov clustering algorithm based on belief dynamics, IEEE Trans. Cybern., 1-10 (2022) |
| [7] | Li, H.-J.; Xu, W.; Song, S.; Wang, W.-X.; Perc, M., The dynamics of epidemic spreading on signed networks, Chaos Solitons Fractals, 151, Article 111294 pp. (2021) · Zbl 1498.68022 |
| [8] | M. Gidea, Topological Data Analysis of Critical Transitions in Financial Networks, in: Proceedings of the Third International Winter School and Conference on Network Science, in: Springer Proceedings in Complexity, 2017. |
| [9] | Liu, Y.; Safavi, T.; Dighe, A.; Koutra, D., Graph summarization methods and applications: A survey, ACM Comput. Surv., 51 (2018), 62:1-62:34 |
| [10] | Shen, Z.; Ma, K.-L.; Eliassi-Rad, T., Visual analysis of large heterogeneous social networks by semantic and structural abstraction, IEEE Trans. Vis. Comput. Graphics, 12, 1427-1439 (2006) |
| [11] | Cheng-Te, L.; Shou-De, L., Egocentric information abstraction for heterogeneous social networks, (Proceedings of the International Conference on Advances in Social Network Analysis and Mining. Proceedings of the International Conference on Advances in Social Network Analysis and Mining, ASONAM’09 (2009), IEEE), 255-260 |
| [12] | Zhou, F.; Malher, S.; Toivonen, H., Network simplification with minimal loss of connectivity, (Proceedings of the 10th IEEE International Conference on Data Mining. Proceedings of the 10th IEEE International Conference on Data Mining, ICDM 2010 (2010), IEEE), 659-668 |
| [13] | Opsahl, T.; Agneessens, F.; Skvoretz, J., Node centrality in weighted networks, Generalizing degree and shortest paths, Soc. Netw., 32, 245-251 (2010) |
| [14] | B. Jean-Daniel, P. Siddharth, Edge Collapse and Persistence of Flag Complexes, in: Proceedings of the 36th International Symposium on Computational Geometry, SoCG 2020, Zurich, Switzerland, 2020. · Zbl 07760148 |
| [15] | Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 511-533 (2002) · Zbl 1011.68152 |
| [16] | Carlsson, G.; Zomorodian, A., Computing persistent homology, Discrete Comput. Geom., 33, 249-274 (2005) · Zbl 1069.55003 |
| [17] | Chazal, F.; Michel, B., Fundamental and practical aspects for data scientists, Front. Artif. Intell., 4, 1-28 (2021) |
| [18] | Bergomi, M. G.; Ferri, M.; Zuffi, L., Topological graph persistence, Commun. Appl. Ind. Math., 11, 72-87 (2020) · Zbl 1479.55011 |
| [19] | Edelsbrunner, H.; Harer, J., Computational Topology - An Introduction (2010), American Mathematical Society · Zbl 1193.55001 |
| [20] | Ghrist, R., Barcodes: the persistent topology of data, Bull. Am. Math. Soc. New Ser., 45, 61-75 (2008) · Zbl 1391.55005 |
| [21] | Fasy, B. T.; Kim, J.; Lecci, F.; Maria, C., Introduction to the R package TDA (2015), arXiv preprint arXiv:1411.1830v2 |
| [22] | Chatfield, C., The analysis of time series, (An Introduction with R (2019), Chapman and Hall) |
| [23] | Mantegna, R. N.; Stanley, H. E., An Introduction to Econophysics: Correlations and Complexity in Finance (2000), Cambridge University Press · Zbl 1138.91300 |
| [24] | Joe, H., Generating random correlation matrices based on partial correlations, J. Multivariate Anal., 97, 2177-2189 (2006) · Zbl 1112.62055 |
| [25] | Gidea, M.; Goldsmith, D.; Katz, Y.; Roldan, P.; Shmalo, Y., Topological recognition of critical transitions in time series of cryptocurrencies, Physica A, 548, Article 123843 pp. (2020) · Zbl 07530523 |
| [26] | Ismail, M. S.; Hussain, S. I.; Noorani, M. S.M., Detecting early warning signals of major financial crashes in bitcoin using persistent homology, IEEE Access, 8, 202042-202057 (2020) |
| [27] | P. Saengduean, S. Noisagool, F. Chamchod, Topological Data Analysis for Identifying Critical Transitions in Cryptocurrency Time Seriesy, in: Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management, IEEM, 2020, pp. 933-938. |
| [28] | Li, G.; Peng, H.; Zhang, J.; Zhu, L., Robust rank correlation based screening, Ann. Statist., 40, 1846-1877 (2012), a · Zbl 1257.62067 |
| [29] | B.T. Fasy, B. Wang, Exploring persistent local homology in topological data analysis, in: Proceedings of the 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, 2016, pp. 6430-6434. |
| [30] | U. Bauer, M. Kerber, J. Reininghaus, Distributed computation of persistent homology, in: Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, ALENEX, 2014, pp. 31-38. · Zbl 1429.68328 |
| [31] | N.O. Malott, R.R. Verma, R.P. Singh, P.A. Wilsey, Distributed Computation of Persistent Homology from Partitioned Big Data, in: Proceedings of the IEEE International Conference on Cluster Computing, CLUSTER, 2021, pp. 344-354. |
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.
