Preface

Acknowledgements

List of Abbreviations

Introduction

1 Multivariate analysis techniques for representing graphs and contingency tables

1.1 Quadratic placement problems for weighted graphs and hypergraphs

1.1.1 Representation of edge-weighted graphs

1.1.2 Representation of hypergraphs

1.1.3 Examples for spectra and representation of simple graphs

1.2 SVD of contingency tables and correspondence matrices

1.3 Normalized Laplacian and modularity spectra

1.4 Representation of joint distributions

1.4.1 General setup

1.4.2 Integral operators between L2 spaces

1.4.3 When the kernel is the joint distribution itself

1.4.4 Maximal correlation and optimal representations

1.5 Treating nonlinearities via reproducing kernel Hilbert spaces

1.5.1 Notion of the reproducing kernel

1.5.2 RKHS corresponding to a kernel

1.5.3 Two examples of an RKHS

1.5.4 Kernel – based on a sample – and the empirical feature map

References

2 Multiway cut problems

2.1 Estimating multiway cuts via spectral relaxation

2.1.1 Maximum, minimum, and ratio cuts of edge-weighted graphs

2.1.2 Multiway cuts of hypergraphs

2.2 Normalized cuts

2.3 The isoperimetric number and sparse cuts

2.4 The Newman–Girvan modularity

2.4.1 Maximizing the balanced Newman–Girvan modularity

2.4.2 Maximizing the normalized Newman–Girvan modularity

2.4.3 Anti-community structure and some examples

2.5 Normalized bicuts of contingency tables

References

3 Large networks, perturbation of block structures

3.1 Symmetric block structures burdened with random noise

3.1.1 General blown-up structures

3.1.2 Blown-up multipartite structures

3.1.3 Weak links between disjoint components

3.1.4 Recognizing the structure

3.1.5 Random power law graphs and the extended planted partition model

3.2 Noisy contingency tables

3.2.1 Singular values of a noisy contingency table

3.2.2 Clustering the rows and columns via singular vector pairs

3.2.3 Perturbation results for correspondence matrices

3.2.4 Finding the blown-up skeleton

3.3 Regular cluster pairs

3.3.1 Normalized modularity and volume regularity of edgeweighted graphs

3.3.2 Correspondence matrices and volume regularity of contingency tables

3.3.3 Directed graphs

References

4 Testable graph and contingency table parameters

4.1 Convergent graph sequences

4.2 Testability of weighted graph parameters

4.3 Testability of minimum balanced multiway cuts

4.4 Balanced cuts and fuzzy clustering

4.5 Noisy graph sequences

4.6 Convergence of the spectra and spectral subspaces

4.7 Convergence of contingency tables

References

5 Statistical learning of networks

5.1 Parameter estimation in random graph models

5.1.1 EMalgorithmfor estimating the parameters of the block model

5.1.2 Parameter estimation in the _ and _ models

5.2 Nonparametric methods for clustering networks

5.2.1 Spectral clustering of graphs and biclustering of contingency tables

5.2.2 Clustering of hypergraphs

5.3 Supervised learning

References

A Linear algebra and some functional analysis

A.1 Metric, normed vector, and Euclidean spaces

A.2 Hilbert spaces

A.3 Matrices

References

B Random vectors and matrices

B.1 Random vectors

B.2 Random matrices

References

C Multivariate statistical methods

C.1 Principal Component Analysis

C.2 Canonical Correlation Analysis

C.3 Correspondence Analysis

C.4 Multivariate Regression and Analysis of Variance

C.5 The k-means clustering

C.6 Multidimensional Scaling

C.7 Discriminant Analysis

References

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.