×

Robust hierarchical clustering for directed networks: an axiomatic approach. (English) Zbl 07430673

MSC:

68R10 Graph theory (including graph drawing) in computer science
68R12 Metric embeddings as related to computational problems and algorithms
62H30 Classification and discrimination; cluster analysis (statistical aspects)
91C20 Clustering in the social and behavioral sciences

Software:

ROCK; Algorithm 447
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] M. Ackerman and S. Ben-David, Measures of clustering quality: A working set of axioms for clustering, in Neural Information Processing Systems, 2008, pp. 121-128.
[2] L. N. F. Ana and A. K. Jain, Robust data clustering, in Proceedings of the Conference on Computer Vision and Pattern Recognition, Vol. 2, 2003, pp. 128-133.
[3] M.-F. Balcan, Y. Liang, and P. Gupta, Robust hierarchical clustering, J. Mach. Learn. Res., 15 (2014), pp. 3831-3871.
[4] S. Ben-David, U. Von Luxburg, and D. Pál, A sober look at clustering stability, in Proceedings of the Conference on Learning Theory, 2006, pp. 5-19. · Zbl 1143.68520
[5] J. P. Boyd, Asymmetric clusters of internal migration regions of France, IEEE Trans. Syst. Man Cybern., 2 (1980), pp. 101-104.
[6] D. Burago, Y. Burago, and S. Ivanov, A Course in Metric Geometry, AMS, Providence, RI, 2001. · Zbl 0981.51016
[7] G. Carlsson and F. Memoli, Characterization, stability and convergence of hierarchical clustering methods, J. Mach. Learn. Res., 11 (2010), pp. 1425-1470. · Zbl 1242.62050
[8] G. Carlsson and F. Memoli, Classifying clustering schemes, Found. Comput. Math., 13 (2013), pp. 221-252. · Zbl 1358.62057
[9] G. Carlsson, F. Memoli, A. Ribeiro, and S. Segarra, Alternative axiomatic constructions for hierarchical clustering of asymmetric networks, in Proceedings of GlobalSIP, 2013, pp. 791-794.
[10] G. Carlsson, F. Memoli, A. Ribeiro, and S. Segarra, Axiomatic construction of hierarchical clustering in asymmetric networks, in Proceedings of ICASSP, 2013, pp. 5219-5223.
[11] G. Carlsson, F. Memoli, A. Ribeiro, and S. Segarra, Hierarchical clustering methods and algorithms for asymmetric networks, in Proceedings of the Asilomar Conference on Signals, Systems, and Computers, 2013, pp. 1773-1777.
[12] G. Carlsson, F. Memoli, A. Ribeiro, and S. Segarra, Hierarchical quasi-clustering methods for asymmetric networks, in Proceedings of ICML, 2014, pp. 352-360. · Zbl 1414.91298
[13] G. Carlsson, F. Mémoli, A. Ribeiro, and S. Segarra, Hierarchical clustering of asymmetric networks, Adv. Data. Anal. Classif., 12 (2018), pp. 65-105. · Zbl 1414.91298
[14] K. Chaudhuri and S. Dasgupta, Rates of convergence for the cluster tree, in Advances in Neural Information Processing Systems, J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, eds., Curran Associates, 2010, pp. 343-351.
[15] B. Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, J. ACM, 47 (2000), pp. 1028-1047. · Zbl 1094.68606
[16] S. Chowdhury and F. Mémoli, Convergence of Hierarchical Clustering and Persistent Homology Methods on Directed Networks, preprint, arXiv:1711.04211, 2017.
[17] S. Chowdhury and F. Mémoli, Distances and Isomorphism Between Networks and the Stability of Network Invariants, preprint, arXiv:1708.04727, 2017.
[18] S. Chowdhury and F. Mémoli, The Metric Space of Networks, preprint, arXiv:1804.02820, 2018. · Zbl 1403.68154
[19] S. Chowdhury and F. Mémoli, Persistent path homology of directed networks, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2018, pp. 1152-1169. · Zbl 1403.68154
[20] R. N. Dave and R. Krishnapuram, Robust clustering methods: A unified view, IEEE Trans. Fuzzy Systems, 5 (1997), pp. 270-293.
[21] B. Eriksson, G. Dasarathy, A. Singh, and R. Nowak, Active clustering: Robust and efficient hierarchical clustering using adaptively selected similarities, in Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, G. Gordon, D. Dunson, and M. Dudik, eds., PMLR 15, 2011, pp. 260-268.
[22] H. Gabow, Z. Galil, T. Spencer, and R. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 6 (1986), pp. 109-122. · Zbl 0608.05027
[23] L. A. García-Escudero, A. Gordaliza, C. Matrán, and A. Mayo-Iscar, A review of robust clustering methods, Adv. Data Anal. Classif., 4 (2010), pp. 89-109. · Zbl 1284.62375
[24] S. Guha, R. Rastogi, and K. Shim, CURE: An efficient clustering algorithm for large databases, SIGMOD Rec., 27 (1998), pp. 73-84. · Zbl 1006.68661
[25] S. Guha, R. Rastogi, and K. Shim, Rock: A robust clustering algorithm for categorical attributes, Information Systems, 25 (2000), pp. 345-366.
[26] I. Guyon, U. V. Luxburg, and R. C. Williamson, Clustering: Science or art, in NIPS Workshop on Clustering Theory, 2009.
[27] J. Hopcroft and R. Tarjan, Algorithm 447: Efficient algorithms for graph manipulation, Commun. ACM, 16 (1973), pp. 372-378.
[28] L. Hubert, Min and max hierarchical clustering using asymmetric similarity measures, Psychometrika, 38 (1973), pp. 63-72. · Zbl 0251.92014
[29] A. K. Jain and R. C. Dubes, Algorithms for Clustering Data, Prentice Hall Advanced Reference Series, Prentice-Hall, Englewood Cliffs, NJ, 1988. · Zbl 0665.62061
[30] J. H. Ward, Jr., Hierarchical grouping to optimize an objective function, J. Amer. Statist. Assoc., 58 (1963), pp. 236-244.
[31] J. M. Kleinberg, An impossibility theorem for clustering, in Neural Information Processing Systems, 2002, pp. 446-453.
[32] T. V. Laarhoven and E. Marchiori, Axioms for graph clustering quality functions, J. Mach. Learn. Res., 15 (2014), pp. 193-215. · Zbl 1318.62222
[33] G. N. Lance and W. T. Williams, A general theory of classificatory sorting strategies 1: Hierarchical systems, Computer J., 9 (1967), pp. 373-380.
[34] S. Lattanzi, S. Leonardi, V. Mirrokni, and I. Razenshteyn, Robust hierarchical k-center clustering, in Proceedings of the Conference on Innovations in Theoretical Computer Science, 2015, pp. 211-218. · Zbl 1365.62240
[35] R. S. MacKay, S. Johnson, and B. Sansom, How directed is a directed network?, R. Soc. Open Sci., 7 (2020), 201138.
[36] A. G. Marques, S. Segarra, and G. Mateos, Signal processing on directed graphs: The role of edge directionality when processing and learning from network data, IEEE Signal Processing Magazine, 37 (2020), pp. 99-116.
[37] M. Meila, Comparing clusterings: An axiomatic view, in Proceedings of ICML, ACM, 2005, pp. 577-584.
[38] M. Meila and W. Pentney, Clustering by weighted cuts in directed graphs, Proceedings of the International Conference on Data Mining, SIAM, Philadelphia, 2007, pp. 135-144.
[39] F. Mémoli and G. V. F. Pinto, Motivic Clustering Schemes for Directed Graphs, preprint, arXiv:2001.00278, 2020.
[40] F. Murtagh, Multidimensional Clustering Algorithms, Compstat Lectures, Physica Verlag, Vienna, 1985. · Zbl 0601.62085
[41] M. Newman and M. Girvan, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99 (2002), pp. 7821-7826. · Zbl 1032.91716
[42] M. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E, 69 (2004), 026113.
[43] A. Ng, M. Jordan, and Y. Weiss, On spectral clustering: Analysis and an algorithm, in Neural Information Processing Systems, 2002, pp. 849-856.
[44] W. Pentney and M. Meila, Spectral clustering of biological sequence data, in National Conference on Artificial Intelligence, 2005, pp. 845-850.
[45] G. Punj and D. W. Stewart, Cluster analysis in marketing research: Review and suggestions for application, J. Marketing Res., 20 (1983), pp. 134-148.
[46] T. Saito and H. Yadohisa, Data Analysis of Asymmetric Structures: Advanced Approaches in Computational Statistics, CRC Press, Boca Raton, FL, 2004. · Zbl 1067.62006
[47] S. Segarra, G. Mateos, A. G. Marques, and A. Ribeiro, Blind identification of graph filters, IEEE Trans. Signal Process., 65 (2017), pp. 1146-1159. · Zbl 1414.94544
[48] J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22 (2000), pp. 888-905.
[49] P. B. Slater, Hierarchical internal migration regions of France, IEEE Trans. Syst. Man Cybern., 4 (1976), pp. 321-324.
[50] P. B. Slater, A partial hierarchical regionalization of 3140 US counties on the basis of 1965-1970 intercounty migration, Env. Plan. A, 16 (1984), pp. 545-550.
[51] R. E. Tarjan, An improved algorithm for hierarchical clustering using strong components, Inform. Process. Lett., 17 (1983), pp. 37-41. · Zbl 0509.68059
[52] U. Von Luxburg, A tutorial on spectral clustering, Stat. Comput., 17 (2007), pp. 395-416.
[53] U. Von Luxburg and S. Ben-David, Towards a statistical theory of clustering, in PASCAL Workshop on Statistics and Optimization of Clustering, 2005.
[54] D. Walsh and L. Rybicki, Symptom clustering in advanced cancer, Supp. Care Cancer, 14 (2006), pp. 831-836.
[55] D. Wishart, Mode analysis: A generalization of nearest neighbor which reduces chaining effects, in Numerical Taxonomy, Academic Press, New York, 1969, pp. 282-311.
[56] H. Yu and M. Gerstein, Genomic analysis of the hierarchical structure of regulatory networks, Proc. Natl. Acad. Sci. USA, 103 (2006), pp. 14724-14731.
[57] R. B. Zadeh and S. Ben-David, A uniqueness theorem for clustering, in Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, 2009, pp. 639-646.
[58] Y. Zhao and G. Karypis, Hierarchical clustering algorithms for document datasets, Data Min. Knowl. Discov., 10 (2005), pp. 141-168.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.