Extracting persistent clusters in dynamic data via Möbius inversion. (English) Zbl 07851503
Summary: Identifying and representing clusters in time-varying network data is of particular importance when studying collective behaviors emerging in nature, in mobile device networks or in social networks. Based on combinatorial, categorical, and persistence theoretic viewpoints, we establish a stable functorial pipeline for the summarization of the evolution of clusters in a time-varying network. We first construct a complete summary of the evolution of clusters in a given time-varying network over a set of entities \(X\) of which takes the form of a formigram. This formigram can be understood as a certain Reeb graph \(\mathcal{R}\) which is labeled by subsets of \(X\). By applying Möbius inversion to the formigram in two different manners, we obtain two dual notions of diagram: the maximal group diagram and the persistence clustergram, both of which are in the form of an ‘annotated’ barcode. The maximal group diagram consists of time intervals annotated by their corresponding maximal groups – a notion due to Buchin et al., implying that we recognize the notion of maximal groups as a special instance of generalized persistence diagram by Patel. On the other hand, the persistence clustergram is mostly obtained by annotating the intervals in the zigzag barcode of the Reeb graph \(\mathcal{R}\) with certain merging/disbanding events in the given time-varying network. We show that both diagrams are complete invariants of formigrams (or equivalently of trajectory grouping structure by Buchin et al.) and thus contain more information than the Reeb graph \(\mathcal{R}\).
MSC:
| 55N31 | Persistent homology and applications, topological data analysis |
| 62R40 | Topological data analysis |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
Keywords:
persistence diagram; persistent homology; Möbius inversion; dynamic metric space; dynamic graph; clustering; Reeb graphReferences:
| [1] | Adams, H., Ghosh, D., Mask, C., Ott, W., Williams, K.: Efficient evader detection in mobile sensor networks. arXiv preprint arXiv:2101.09813 (2021) |
| [2] | Adams, H.; Carlsson, G., Evasion paths in mobile sensor networks, Int. J. Robot. Res., 34, 1, 90-104, 2015 |
| [3] | Azumaya, G., Corrections and supplementaries to my paper concerning Krull-Remak-Schmidt’s theorem, Nagoya Math. J., 1, 117-124, 1950 · Zbl 0040.01201 |
| [4] | Bauer, U., Ge, X., Wang, Y.: Measuring distance between Reeb graphs. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, pp. 464-473 (2014) · Zbl 1395.68288 |
| [5] | Bauer, U., Munch, E., Wang, Y.: Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs. In: Arge, L., Pach, J. (eds.) 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 34, pp. 461-475. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2015). doi:10.4230/LIPIcs.SOCG.2015.461. http://drops.dagstuhl.de/opus/volltexte/2015/5146 · Zbl 1382.58010 |
| [6] | Bauer, U.; Lesnick, M., Induced matchings and the algebraic stability of persistence barcodes, J. Comput. Geom., 6, 2, 162-191, 2015 · Zbl 1405.68398 |
| [7] | Benkert, M.; Gudmundsson, J.; Hübner, F.; Wolle, T., Reporting flock patterns, Comput. Geom., 41, 3, 111-125, 2008 · Zbl 1163.65011 |
| [8] | Birkhoff, G., Lattice Theory, 1948, Providence: American Mathematical Society, Providence · Zbl 0033.10103 |
| [9] | Bjerkevik, HB, On the stability of interval decomposable persistence modules, Discrete Comput. Geom., 66, 1, 92-121, 2021 · Zbl 1471.55006 |
| [10] | Bondy, J.; Murty, U., Graph Theory (Graduate Texts in Mathematics), 2008, New York: Springer, New York · Zbl 1134.05001 |
| [11] | Botnan, MB, Interval decomposition of infinite zigzag persistence modules, Proc. Am. Math. Soc., 145, 8, 3571-3577, 2017 · Zbl 1387.55011 |
| [12] | Botnan, M.; Lesnick, M., Algebraic stability of zigzag persistence modules, Algebraic Geom. Topol., 18, 6, 3133-3204, 2018 · Zbl 1432.55011 |
| [13] | Bredon, GE, Sheaf Theory, 2012, New York: Springer, New York |
| [14] | Bubenik, P.; Scott, JA, Categorification of persistent homology, Discrete Comput. Geom., 51, 3, 600-627, 2014 · Zbl 1295.55005 |
| [15] | Buchin, K.; Buchin, M.; van Kreveld, MJ; Speckmann, B.; Staals, F., Trajectory grouping structure, JoCG, 6, 1, 75-98, 2015 · Zbl 1387.68244 |
| [16] | Burago, D.; Burago, Y.; Ivanov, S., A Course in Metric Geometry. AMS Graduate Studies in Math., 2001, Providence: American Mathematical Society, Providence · Zbl 0981.51016 |
| [17] | Carlsson, G., Mémoli, F.: Multiparameter hierarchical clustering methods. In: Classification as a Tool for Research, pp. 63-70. Springer (2010) |
| [18] | Carlsson, G., Topology and data, Bull. Am. Math. Soc., 46, 2, 255-308, 2009 · Zbl 1172.62002 |
| [19] | Carlsson, G.; Mémoli, F., Characterization, stability and convergence of hierarchical clustering methods, J. Mach. Learn. Res., 11, 1425-1470, 2010 · Zbl 1242.62050 |
| [20] | Carlsson, G.; Mémoli, F., Classifying clustering schemes, Found. Comput. Math., 13, 2, 221-252, 2013 · Zbl 1358.62057 |
| [21] | Carlsson, G.; De Silva, V., Zigzag persistence, Found. Comput. Math., 10, 4, 367-405, 2010 · Zbl 1204.68242 |
| [22] | Carlsson, G.; Zomorodian, A., The theory of multidimensional persistence, Discrete Comput. Geom., 42, 1, 71-93, 2009 · Zbl 1187.55004 |
| [23] | Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L.J., Oudot, S.: Proximity of persistence modules and their diagrams. In: Proceedings of 25th ACM Symposium on Computational Geometry, pp. 237-246 (2009) · Zbl 1380.68387 |
| [24] | Chazal, F., Fasy, B.T., Lecci, F., Rinaldo, A., Wasserman, L.: Stochastic convergence of persistence landscapes and silhouettes. In: Proceedings of the Thirtieth Annual Symposium on Computational Geometry, pp. 474-483 (2014) · Zbl 1395.62187 |
| [25] | Chowdhury, S.; Mémoli, F., Explicit geodesics in Gromov-Hausdorff space, Electron. Res. Announc., 25, 48-59, 2018 · Zbl 1405.53066 |
| [26] | Clause, N., Kim, W.: Spatiotemporal Persistent Homology Computation Tool. https://github.com/ndag/PHoDMSs (2020) |
| [27] | Clause, N.: Zigzag Persistent Homology and Dynamic Networks. https://github.com/ndag/DynGraphZZ (2021) |
| [28] | Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 1, 103-120, 2007 · Zbl 1117.54027 |
| [29] | Curry, J.M.: Sheaves, cosheaves and applications. PhD thesis, University of Pennsylvania (2014) |
| [30] | Curry, J.; Patel, A., Classification of constructible cosheaves, Theory Appl. Categories, 35, 27, 1012-1047, 2020 · Zbl 1442.32039 |
| [31] | De Silva, V.; Ghrist, R., Coordinate-free coverage in sensor networks with controlled boundaries via homology, Int. J. Robot. Res., 25, 12, 1205-1222, 2006 · Zbl 1202.94174 |
| [32] | De Silva, V.; Munch, E.; Patel, A., Categorified Reeb graphs, Discrete Comput. Geom., 55, 4, 854-906, 2016 · Zbl 1350.68271 |
| [33] | De Silva, V., Ghrist, R., et al.: Homological sensor networks. Notices of the American mathematical society 54(1) (2007) · Zbl 1142.94006 |
| [34] | Dey, T.K., Hou, T.: Computing zigzag persistence on graphs in near-linear time. In: 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 189, pp. 30-13015. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, (2021). doi:10.4230/LIPIcs.SoCG.2021.30 |
| [35] | Dey, T.K., Hou, T.: Updating zigzag persistence and maintaining representatives over changing filtrations. arXiv preprint arXiv:2112.02352 (2021) |
| [36] | Di Fabio, B.; Landi, C., The edit distance for Reeb graphs of surfaces, Discrete Comput. Geom., 55, 2, 423-461, 2016 · Zbl 1332.05038 |
| [37] | Edelsbrunner, H.; Harer, J., Persistent homology—a survey, Contemp. Math., 453, 257-282, 2008 · Zbl 1145.55007 |
| [38] | Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 511-533, 2002 · Zbl 1011.68152 |
| [39] | Gabriel, P., Unzerlegbare darstellungen i, Manuscr. Math., 6, 1, 71-103, 1972 · Zbl 0232.08001 |
| [40] | Gamble, J., Chintakunta, H., Krim, H.: Applied topology in static and dynamic sensor networks. In: 2012 International Conference on Signal Processing and Communications (SPCOM), pp. 1-5 (2012). IEEE |
| [41] | Ghrist, R.; Riess, H., Cellular sheaves of lattices and the Tarski Laplacian, Homol. Homotopys. Appl., 24, 1, 325-345, 2022 · Zbl 1487.18001 |
| [42] | Gonzalez-Diaz, R., Jimenez, M.-J., Medrano, B.: Spatiotemporal barcodes for image sequence analysis. In: International Workshop on Combinatorial Image Analysis, pp. 61-70 (2015). Springer · Zbl 1486.68231 |
| [43] | Gudmundsson, J., van Kreveld, M.: Computing longest duration flocks in trajectory data. In: Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems, pp. 35-42 (2006). ACM |
| [44] | Gudmundsson, J.; van Kreveld, M.; Speckmann, B., Efficient detection of patterns in 2d trajectories of moving points, Geoinformatica, 11, 2, 195-215, 2007 |
| [45] | Hajij, M., Wang, B., Scheidegger, C., Rosen, P.: Visual detection of structural changes in time-varying graphs using persistent homology, 125-134 (2018). IEEE |
| [46] | Huang, Y., Chen, C., Dong, P.: Modeling herds and their evolvements from trajectory data. In: International Conference on Geographic Information Science, pp. 90-105 (2008). Springer |
| [47] | Hwang, S.-Y., Liu, Y.-H., Chiu, J.-K., Lim, E.-P.: Mining mobile group patterns: A trajectory-based approach. In: PAKDD, vol. 3518, pp. 713-718 (2005). Springer |
| [48] | Jardine, N.; Sibson, R., Mathematical Taxonomy, 286, 1971, London: Wiley, London · Zbl 0322.62065 |
| [49] | Jeung, H.; Yiu, ML; Zhou, X.; Jensen, CS; Shen, HT, Discovery of convoys in trajectory databases, Proc. VLDB Endow., 1, 1, 1068-1080, 2008 |
| [50] | Kalnis, P., Mamoulis, N., Bakiras, S.: On discovering moving clusters in spatio-temporal data. In: SSTD, vol. 3633, pp. 364-381 (2005). Springer |
| [51] | Kerber, M.; Morozov, D.; Nigmetov, A., Geometry Helps to Compare Persistence Diagrams, 2017, New York: ACM, New York · Zbl 1414.68129 |
| [52] | Kim, W., Mémoli, F., Smith, Z.: Analysis of dynamic graphs and dynamic metric spaces via zigzag persistence. In: Topological Data Analysis, pp. 371-389. Springer, (2020) · Zbl 1448.55008 |
| [53] | Kim, W., Mémoli, F., Smith, Z.: Clustering behavior summary of dynamic metric data (2017). https://research.math.osu.edu/networks/formigrams |
| [54] | Kim, W., Mémoli, F., Stefanou, A.: Interleaving by parts for persistence in a poset. arXiv preprint arXiv:1912.04366 (2019) |
| [55] | Kim, W., Mémoli, F.: Formigrams: Clustering summaries of dynamic data. In: Proceedings of 30th Canadian Conference on Computational Geometry (CCCG18) (2018) |
| [56] | Kim, W., Memoli, F.: Stable signatures for dynamic graphs and dynamic metric spaces via zigzag persistence. arXiv preprint arXiv:1712.04064v4 (2017) |
| [57] | Kim, W.; Mémoli, F., Generalized persistence diagrams for persistence modules over posets, J. Appl. Comput. Topol., 5, 4, 533-581, 2021 · Zbl 1500.55004 |
| [58] | Kim, W.; Mémoli, F., Spatiotemporal persistent homology for dynamic metric spaces, Discrete Comput. Geom., 66, 3, 831-875, 2021 · Zbl 1480.55007 |
| [59] | Li, Z.; Ding, B.; Han, J.; Kays, R., Swarm: mining relaxed temporal moving object clusters, Proc. VLDB Endow., 3, 1-2, 723-734, 2010 |
| [60] | Mac Lane, S., Categories for the Working Mathematician, 2013, New York: Springer, New York · Zbl 0232.18001 |
| [61] | McCleary, A.; Patel, A., Bottleneck stability for generalized persistence diagrams, Proc. Am. Math. Soc. U.S.A., 148, 7, 3149-3161, 2020 · Zbl 1446.55007 |
| [62] | McCleary, A.; Patel, A., Edit distance and persistence diagrams over lattices, SIAM J. Appl. Algebra Geom., 6, 2, 134-155, 2022 · Zbl 07516935 |
| [63] | Mémoli, F.: A distance between filtered spaces via tripods. arXiv preprint arXiv:1704.03965 (2017) |
| [64] | Mitchell, B., Theory of Categories, 1965, Washington, DC: Academic Press, Washington, DC · Zbl 0136.00604 |
| [65] | Morozov, D.; Beketayev, K.; Weber, G., Interleaving distance between merge trees, Discrete Comput. Geom., 49, 22-45, 2013 · Zbl 1272.68414 |
| [66] | Munch, E.: Applications of persistent homology to time varying systems. PhD thesis, Duke University (2013) |
| [67] | Parrish, JK; Hamner, WM, Animal Groups in Three Dimensions: How Species Aggregate, 1997, Cambridge: Cambridge University Press, Cambridge |
| [68] | Patel, A.: Reeb spaces and the robustness of preimages. PhD thesis, Duke University (2010) |
| [69] | Patel, A., Generalized persistence diagrams, J. Appl. Comput. Topol., 1, 3, 397-419, 2018 · Zbl 1398.18015 |
| [70] | Puuska, V., Erosion distance for generalized persistence modules, Homol. Homotopye Appl., 22, 1, 233-254, 2020 · Zbl 1436.55010 |
| [71] | Reynolds, CW, Flocks, herds and schools: a distributed behavioral model, ACM SIGGRAPH Comput. Graph., 21, 4, 25-34, 1987 |
| [72] | Rolle, A., Scoccola, L.: Stable and consistent density-based clustering. arXiv preprint arXiv:2005.09048 (2020) |
| [73] | Rossetti, G.; Cazabet, R., Community discovery in dynamic networks: a survey, ACM Comput. Surv., 51, 2, 1-37, 2018 |
| [74] | Rota, G-C, On the foundations of combinatorial theory i. theory of Möbius functions, Probab. Theory Relat. Fields, 2, 4, 340-368, 1964 · Zbl 0121.02406 |
| [75] | Rubenstein, M., Ahler, C., Nagpal, R.: Kilobot: A low cost scalable robot system for collective behaviors. In: 2012 IEEE International Conference on Robotics and Automation, pp. 3293-3298 (2012). IEEE |
| [76] | Schmiedl, F.: Shape matching and mesh segmentation. PhD thesis, Technische Universität München (2015) |
| [77] | Schmiedl, F., Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching, Discrete Comput. Geom., 57, 4, 854-880, 2017 · Zbl 1368.52017 |
| [78] | Sinhuber, M.; Ouellette, NT, Phase coexistence in insect swarms, Phys. Rev. Lett., 119, 17, 2017 |
| [79] | Sumpter, DJ, Collective Animal Behavior, 2010, Princeton: Princeton University Press, Princeton · Zbl 1229.92085 |
| [80] | Topaz, CM; Ziegelmeier, L.; Halverson, T., Topological data analysis of biological aggregation models, PLoS ONE, 10, 5, 0126383, 2015 |
| [81] | van Goethem, A., van Kreveld, M., Löffler, M., Speckmann, B., Staals, F.: Grouping Time-Varying Data for Interactive Exploration. In: 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, pp. 61-16116. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2016). doi:10.4230/LIPIcs.SoCG.2016.61.http://drops.dagstuhl.de/opus/volltexte/2016/5953 · Zbl 1387.68284 |
| [82] | van Kreveld, M.; Löffler, M.; Staals, F.; Wiratma, L., A refined definition for groups of moving entities and its computation, Int. J. Comput. Geom. Appl., 28, 2, 181-196, 2018 · Zbl 1397.68213 |
| [83] | Vehlow, C.; Beck, F.; Auwärter, P.; Weiskopf, D., Visualizing the evolution of communities in dynamic graphs, Comput. Graph. Forum, 34, 1, 277-288, 2015 |
| [84] | Vieira, M.R., Bakalov, P., Tsotras, V.J.: On-line discovery of flock patterns in spatio-temporal data. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 286-295 (2009). ACM |
| [85] | Wang, Y.; Lim, E-P; Hwang, S-Y, Efficient algorithms for mining maximal valid groups, VLDB J., 17, 3, 515-535, 2008 |
| [86] | Wikipedia: Formicarium—Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/wiki/Formicarium. Accessed 12 Dec 2021 |
| [87] | Wiratma, L., van Kreveld, M., Löffler, M., Staals, F.: An experimental evaluation of grouping definitions for moving entities. In: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 89-98 (2019) |
| [88] | Xian, L.; Adams, H.; Topaz, CM; Ziegelmeier, L., Capturing dynamics of time-varying data via topology, Found. Data Sci., 4, 1, 1-36, 2022 · Zbl 1501.37084 |
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.
