Spectral Clustering and Biclustering

She is graduated from the Eötvös University of Budapest and holds a PhD (1984); further, a CSc degree (1993) from the Hungarian Academy of Sciences. Currently, she is a professor of the Institute of Mathematics, Budapest University of Technology and Economics and adjoint professor of the Central European University of Budapest. She also leads an undergraduate research course on Spectral Clustering in the Budapest Semester of Mathematics.Her fields of expertise are multivariate statistics, applied graph theory, and data mining of social, biological, and communication networks. She has been working in various national and European research projects related to networks and data analysis.She has published research papers in the Journal of Multivariate Analysis, Linear Algebra and  Its Applications, Discrete Mathematics, Discrete Applied Mathematics, European Journal of Combinatorics, and the Physical  Review E, among others.She is the coauthor of the textbook in Hungarian: Bolla, M., Krámli, A., Theory of statistical inference, Typotex, Budapest (first ed. 2005, second ed. 2012) and another Hungarian book on multivariate statistical analysis. She was the managing editor of the book Contests in Higher Mathematics (ed. G. J. Székely), Springer, 1996.

• Preface xiAcknowledgements xiiiList of abbreviations xvIntroduction xixReferences xxii1 Multivariate analysis techniques for representing graphs and contingency tables 11.1 Quadratic placement problems for weighted graphs and hypergraphs 11.1.1 Representation of edge-weighted graphs 21.1.2 Representation of hypergraphs 51.1.3 Examples for spectra and representation of simple graphs 81.2 SVD of contingency tables and correspondence matrices 121.3 Normalized Laplacian and modularity spectra 161.4 Representation of joint distributions 211.4.1 General setup 211.4.2 Integral operators between L2 spaces 221.4.3 When the kernel is the joint distribution itself 231.4.4 Maximal correlation and optimal representations 251.5 Treating nonlinearities via reproducing kernel Hilbert spaces 281.5.1 Notion of the reproducing kernel 291.5.2 RKHS corresponding to a kernel 321.5.3 Two examples of an RKHS 331.5.4 Kernel – based on a sample – and the empirical feature map 37References 402 Multiway cuts and spectra 442.1 Estimating multiway cuts via spectral relaxation 442.1.1 Maximum, minimum, and ratio cuts of edge-weighted graphs 452.1.2 Multiway cuts of hypergraphs 542.2 Normalized cuts 572.3 The isoperimetric number and sparse cuts 642.4 The Newman–Girvan modularity 762.4.1 Maximizing the balanced Newman–Girvan modularity 782.4.2 Maximizing the normalized Newman–Girvan modularity 812.4.3 Anti-community structure and some examples 842.5 Normalized bicuts of contingency tables 88References 913 Large networks, perturbation of block structures 963.1 Symmetric block structures burdened with random noise 963.1.1 General blown-up structures 993.1.2 Blown-up multipartite structures 1093.1.3 Weak links between disjoint components 1123.1.4 Recognizing the structure 1143.1.5 Random power law graphs and the extended planted partition model 1213.2 Noisy contingency tables 1243.2.1 Singular values of a noisy contingency table 1273.2.2 Clustering the rows and columns via singular vector pairs 1293.2.3 Perturbation results for correspondence matrices 1323.2.4 Finding the blown-up skeleton 1383.3 Regular cluster pairs 1423.3.1 Normalized modularity and volume regularity of edge-weighted graphs 1423.3.2 Correspondence matrices and volume regularity of contingency tables 1503.3.3 Directed graphs 156References 1574 Testable graph and contingency table parameters 1614.1 Convergent graph sequences 1614.2 Testability of weighted graph parameters 1644.3 Testability of minimum balanced multiway cuts 1664.4 Balanced cuts and fuzzy clustering 1724.5 Noisy graph sequences 1754.6 Convergence of the spectra and spectral subspaces 1774.7 Convergence of contingency tables 182References 1875 Statistical learning of networks 1895.1 Parameter estimation in random graph models 1895.1.1 EM algorithm for estimating the parameters of the block-model 1895.1.2 Parameter estimation in the α and β models 1925.2 Nonparametric methods for clustering networks 1975.2.1 Spectral clustering of graphs and biclustering of contingency tables 1995.2.2 Clustering of hypergraphs 2015.3 Supervised learning 203References 205Appendix A Linear algebra and some functional analysis 207A.1 Metric, normed vector, and Euclidean spaces 207A.2 Hilbert spaces 209A.3 Matrices 217References 233Appendix B Random vectors and matrices 235B.1 Random vectors 235B.2 Random matrices 239References 245Appendix C Multivariate statistical methods 246C.1 Principal component analysis 246C.2 Canonical correlation analysis 248C.3 Correspondence analysis 250C.4 Multivariate regression and analysis of variance 252C.5 The k-means clustering 255C.6 Multidimensional scaling 257C.7 Discriminant analysis 258References 261Index 263