Spectral Clustering and Biclustering E-Book

Marianna Bolla

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 537

Veröffentlichungsjahr: 2013

Beschreibung

Explores regular structures in graphs and contingency tables by spectral theory and statistical methods

This book bridges the gap between graph theory and statistics by giving answers to the demanding questions which arise when statisticians are confronted with large weighted graphs or rectangular arrays. Classical and modern statistical methods applicable to biological, social, communication networks, or microarrays are presented together with the theoretical background and proofs.

This book is suitable for a one-semester course for graduate students in data mining, multivariate statistics, or applied graph theory; but by skipping the proofs, the algorithms can also be used by specialists who just want to retrieve information from their data when analysing communication, social, or biological networks.

Spectral Clustering and Biclustering:

• Provides a unified treatment for edge-weighted graphs and contingency tables via methods of multivariate statistical analysis (factoring, clustering, and biclustering).
• Uses spectral embedding and relaxation to estimate multiway cuts of edge-weighted graphs and bicuts of contingency tables.
• Goes beyond the expanders by describing the structure of dense graphs with a small spectral gap via the structural eigenvalues and eigen-subspaces of the normalized modularity matrix.
• Treats graphs like statistical data by combining methods of graph theory and statistics.
• Establishes a common outline structure for the contents of each algorithm, applicable to networks and microarrays, with unified notions and principles.

Leseprobe

Contents

Cover

Title Page

Copyright

Dedication

Preface

Acknowledgements

List of Abbreviations

Introduction

References

Chapter 1: Multivariate Analysis Techniques for Representing Graphs and Contingency Tables

1.1 Quadratic Placement Problems for Weighted Graphs and Hypergraphs

1.2 SVD of Contingency Tables and Correspondence Matrices

1.3 Normalized Laplacian and Modularity Spectra

1.4 Representation of Joint Distributions

1.5 Treating Nonlinearities via Reproducing Kernel Hilbert Spaces

References

Chapter 2: Multiway Cuts and Spectra

2.1 Estimating Multiway Cuts via Spectral Relaxation

2.2 Normalized Cuts

2.3 The Isoperimetric Number and Sparse Cuts

2.4 The Newman–Girvan Modularity

2.5 Normalized Bicuts of Contingency Tables

References

Chapter 3: Large Networks, Perturbation of Block Structures

3.1 Symmetric Block Structures Burdened with Random Noise

3.2 Noisy Contingency Tables

3.3 Regular Cluster Pairs

References

Chapter 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

Chapter 5: Statistical Learning of Networks

5.1 Parameter Estimation in Random Graph Models

5.2 Nonparametric Methods for Clustering Networks

5.3 Supervised Learning

References

Appendix A Linear Algebra and Some Functional Analysis

A.1 Metric, Normed Vector, and Euclidean Spaces

A.2 Hilbert Spaces

A.3 Matrices

References

Appendix B Random Vectors and Matrices

B.1 Random Vectors

B.2 Random Matrices

References

Appendix 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

Index

This edition first published 2013

© 2013 John Wiley & Sons, Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data

Bolla, Marianna.

Spectral clustering and biclustering: learning large graphs and contingency tables / Marianna Bolla.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-34492-7 (hardback)

1. Multivariate analysis. 2. Contingency tables. 3. Graph theory. I. Title.

QA278.B65 2013

515′.35–dc23

2013011891

A catalogue record for this book is available from the British Library.

ISBN: 978-1-118-34492-7

To my son and students

Preface

When dealing with networks, statisticians want to explore the structure of the actual data set whatever it is. Meanwhile, we realized that statistical methods are not immediately applicable for graphs, as graph theory is mainly concerned with special structures which are too sensitive to minor changes. Therefore, we decided to bridge, at least partially, the gap between statistics and graph theory with ideas on how graphs and contingency tables can be considered as statistical data and how they can be treated by methods reminiscent of classical and modern techniques of multivariate statistical analysis. We want to provide answers to the demanding questions which arise when statisticians are confronted with large weighted graphs or rectangular arrays like microarrays. In contemporary data analysis, experts are striving to recover the structure of communication, social, and biological networks, or in other situations, to compare networks of different sizes and classify them based on a training sample. In the case of large data sets, random effects and measurement errors also have to be treated.

We plan to use existing knowledge on graph spectra and experiences in analyzing real-world data in the form of hypergraphs, weighted graphs, and contingency tables. At the end of the 1980s, together with my PhD advisor, Gábor Tusnády, we used spectral methods for a binary clustering problem, where the underlying matrix turned out to be the generalization of the graphs' Laplacian to hypergraphs. Then we defined the Laplacian for multigraphs and edge-weighted graphs, and went beyond the expanders by investigating gaps within the spectrum and used eigenvectors corresponding to some structural eigenvalues to find clusters of vertices. We also considered minimum multiway cuts with different normalizations that were later called ratio-and normalized cuts. In the 1990s, spectral clustering became a fashionable area and a lot of papers in this topic appeared, sometimes redefining or modifying the above notions, sometimes having a numerical flavor and suggesting algorithms without rigorous mathematical explanation.

At the turn of the millennium, thanks to the spread of the World Wide Web and the human genome project, there was a rush to investigate evolving graphs and random situations different from the classical Erds–Rényi one. Graph theorists, for example, László Lovász and co-authors, considered convergence of graph sequences and testable graph parameters, bringing –without their volition –statistical concepts into this discrete area. They also started to consider noisy graph and contingency table sequences, and testability of some balanced versions of the already defined minimum multiway cut densities. Meanwhile, physicists introduced other measures of characterizing a community structure of networks. In this book we discuss some penalized versions of the Newman–Girvan modularity and regular cuts which are present in situations when the network has clusters of vertices with a homogeneous information flow within or between them.

A wide array of classical and modern statistical methods are presented and adapted to weighted graphs and contingency tables. We recommend algorithms for recovering the structure of large networks burdened with random noise, further to clustering and classifying them. Through representations, we establish a common outline structure for the contents of each algorithm along with various fundamental elements which are combined via unified notions and principles. We only give a general treatment to the problems exposed; for more examples we refer to papers and also the supporting website (www.wiley.com/go/spectral) of the book. Hence, the book is a resource for professionals mining large datasets related to communication, social, biological, or industrial networks, and for students learning statistical methods applicable to networks.

Throughout the book we use advanced linear algebra, probability, and multivariate statistics. A collection of frequently used facts in these fields is to be found in the Appendices. However, a basic knowledge of graph theory and computer sciences suffices as we only consider statistical graph properties which are unaffected by minor perturbations of the vertex-or edge-weights, and we just touch upon the computational complexity of the proposed algorithms. We also discuss possible applications to real-life networks. However, the main contribution of this book is the well-motivated presentation and comparison of a great variety of statistical methods applicable to large networks or network sequences. Well-known facts from former books concerning graph spectra are not proven (references are given), but all other propositions and theorems are proven with mathematical precision. Therefore the book is suitable for a one-semester graduate course on this topic. For those who are interested only in the algorithms, these proofs can be skipped.

Marianna Bolla

Budapest, December 2012

Acknowledgements

I wish to express gratitude to persons whose books, papers, and lectures on spectral graph theory and multivariate statistics turned my interest to this field: F. Chung, D. M. Cvetkovic, M. Fiedler, A. J. Hoffman, B. Mohar, and C. R. Rao.

I am indebted to my PhD advisor, Gábor Tusnády with whom I have worked on several projects and applied statistical methods in real-life problems. I am grateful to László Lovász for valuable discussions on the spectral graph and graph convergence topics. I wish to thank many colleagues for their useful comments on the related research and applications: László Babai, András Benczur, Endre Boros, Imre Csiszár, Vill Csiszár, Zoltán Füredi, Ferenc Juhász, János Komlós, Vilmos Komornik, Tamás Lengyel, Nathan Linial, András Lukács, Péter Major, György Michaletzky, Dezs Miklós, Tamás F. Móri, Dénes Petz, Tomaz Pisanski, András Prékopa, András Recski, Lídia Rejt, Tamás Rudas, András Simonovits, Miklós Simonovits, Vera T. Sós, Domokos Szász, Gábor J. Székely, Endre Szemerédi, András Telcs, László Telegdi, Bálint Tóth, György Turán, and Katalin Vesztergombi. I am particularly indebted to Katalin Friedll, András Krámli, and János Tóth for promotive discussions, to Ákos Csizmadia for helping me to present the references of this book in a unified form; further, to Ibolya Barna, Miklós Gergi, and Péter István for their technical help.

I would like to thank my students at the Budapest University of Technology and Economics, Central European University, and Budapest Semester of Mathematics, who worked on the spectral clustering topic and helped me with questions, calculations, and processing computer programs: Andrea Bán, Erik Bodzsár, Brian Bullins, Sorathan Chaturapruek, Shiwen Chen, Ahmed Elbanna, Max Del Giudice, Haris Khan, Tamás Kói, Anett Lovas, Gábor Molnár–Sáska, Ildikó Priksz, Viktor Szabó, Zsolt Szabó, Joan Wang, and László Nagy who actually assisted me with preparing some figures for this book.

I am grateful to Károly Simon for encouraging me to write this book and letting me go on sabbatical two years ago when I assembled the pieces of this material together. The related research was partly supported by the Hungarian National Research Grant OTKA-KTIA 77778; and by the TÁMOP-4.2.2.C-11/1/KONV-2012-0001 project, sponsored by the European Union.

Introduction

‘Happy families are all alike; every unhappy family is unhappy in its own way.’

Leo Tolstoy: Anna Karenina

Graphs with a small spectral gap can be very different by their nature, indeed. Those with a large spectral gap have been frequently studied since Metropolis et al. (1953); Nash-Williams (1959) and Cheeger (1970), establishing a lot of equivalent or near equivalent advisable features of them. There are beautiful results about the relation between this gap and the expanding properties of the graph (see e.g., Hoory, Linial and Widgerson (2006)), including a random walk view of Azran and Ghahramani (2006); Diaconis and Stroock (1991) and connectivity (the first results are due to Fiedler (1973) and Hoffman (1970)). Roughly speaking, graphs with a large spectral gap are good expanders; the random walk goes through them very quickly with a high mixing rate and short commute time, see for example Lovász (1993); Lovász and Winkler (1995); they are also good magnifiers as their vertices have many neighbors; in other words, their vertex subsets have a large boundary compared to their volumes characterized by the isoperimetric number: see Mohar (1988); equivalently, they have high conductance and show quasirandom properties discussed in Chung, Graham and Wilson (1989) and Chung and Graham (2008). Because of these favorable characteristics, they are indispensable in communication networks; further, there is basically one eigenvalue responsible for this property.

However, less attention has been paid to graphs with a small spectral gap, when several cases can occur: among others, the graph can be a bipartite expander (see Alon (1986)) or its vertices can be divided into two sparsely connected clusters, but the clusters themselves can be good expanders (see Ng et al. (2001) and Newman (2003)). In the case of several clusters of vertices the situation is even more complicated. The pairwise relations between the clusters and the within-cluster relations of vertices of the same cluster show a great variety; not surprisingly, there is more than one eigenvalue responsible for these versatile properties. Depending on the number and sign of the so-called structural eigenvalues of the normalized modularity matrix, defined in Bolla (2011), we help enable the reader to decide the number of underlying clusters and the type of connection between them.

Given a graph –simple or edge-weighted –that does not belong to the well manageable family of expanders, our task is to survey the numerous possibilities for this graph according to which it may have a structure. We wouldn't say that every such graph has its own structure, but there are types of relations between its vertices according to which they may form clusters. We prove and illustrate through random examples that based on the structural eigenvalues of the normalized modularity matrix, how the main types of intra-and inter-cluster relations can be established and the clusters themselves recovered via the corresponding eigenvectors. Our examples are mainly from the class of generalized random graphs. We deal with dense graphs as a statistical sample. Sparse graphs (like path, grid, or hypercube) are frequently used as examples where the minimum spectral gap shows up; however there are no sensible ways to divide their vertices into any number of clusters. Our methods are rather applicable to real-life situations when the number of edges is proportional to the square of the number of vertices; or in the edge-weighted graph setup, at least a linear number of weights in each row of the weight matrix differ from zero.

Spectra of graphs together with their application was discussed by several authors, for example, Biggs (1974); Chung (1997); Cvetkovic, Doob and Sachs (1979); von Luxburg (2007); Spielman (2007). There are quick numerical algorithms to find spectral or singular value decomposition (SD or SVD) of the graph or contingency table based matrix with normalization adopted to the objective function. Most of these algorithms use the k smallest (normalized or unnormalized) Laplacian eigenvalues which are capable to reveal a sparse k-way cut (see Lee et al. (2012); Louis et al. (2011)). We will not confine ourselves to the bottom of the Laplacian spectrum, but take into consideration the top eigenvalues as well, which together form the large absolute value (structural) eigenvalues of the normalized modularity matrix, introduced just for this convenience. As a statistician, I believe there must be a structure in each network. Theoretical results (like the Szemerédi's regularity lemma, see Komlós et al. (2002)) also support this, though sometimes with an enormously large number of clusters. There is a lot of knowledge about how some specific structures can be characterized by means of spectra, but little is known about how to recognize the structure itself. Sometimes the same continuous relaxation is used to optimize different types of cuts (see Ding et al. (2003)), sometimes it is noted that the result of the Laplacian-based clustering depends on the graph itself (see von Luxburg et al. (2008)). I plan to approach this problem from the opposite direction: first to be acquainted with the graph so as to apply the best possible clustering to it. This means that based on the spectrum (gaps between the structural and the bulk eigenvalues and the sign of the structural ones) we use the most appropriate eigenvectors for representation and clustering. We consider the graph as statistical data itself, find out which structure is expected, and then select the method.

Though spectral graph theory seems to be a versatile endless tale, we speak about it in the framework of a moderate length book. Of course, we cannot discuss all the details, but what we discuss is compatible with unified notation, and we just touch upon subjects (e.g., random walk view) that have been thoroughly discussed by other authors. However, there is reality behind every tale, and facing it helps us to unveil the problem. We learn, for example, that the reality behind the diabolic kernel trick – when using reproducing kernel Hilbert spaces – is the century old Riesz–Fréchet representation theorem, according to which linear functionals over a Hilbert space are in one-to-one correspondence with the space itself; here it is extended to non-linear functionals that are related to the elements of a more complicated Hilbert space (not the original one). Knowing this, the trick becomes a simple tool as to how the selection of an appropriate kernel helps us in discovering non-linearities in our data and separate clusters that cannot otherwise be separated by simply applying the k-means algorithm to it. We start the sections with a brief exposition of the problems and roughly explain the solution, but later on we encounter all the definitions and facts belonging to the issue. We elucidate everything with full precision and also point in new directions. The following explains the contents of the strongly interwined chapters.

Chapter 1 is devoted to multivariate analysis techniques for representing edge-weighted graphs and contingency tables. Different kinds of graph-based matrices are introduced together with spectra and spectral subspaces which optimize different quadratic placement problems subject to different constraints. Our purpose here is to develop tools for the unique treatment of the multiway cut problems of Chapter 2. These methods are reminiscent of classical methods of multivariate statistical analysis, like principal component analysis, correspondence analysis, or analysis of variance. As a result, we get low dimensional representation of the graph's vertices or rows and columns of the contingency table so that the representation somehow favors the classification criteria of Chapter 2. Non-linearities are treated by mapping the data into a feature space (reproducing kernel Hilbert space), which is a useful technique if we build a graph on given data points. We also generalize the notion of representation for joint distributions, and use it in Chapter 4 when convergence of normalized spectra is discussed.

In Chapter 2, minimum ratio and normalized multiway cut problems are presented together with modularity cuts. Since the optima of the corresponding objective functions are taken on partition vectors belonging to the hidden clusters, via Chapter 1, they are related to Laplacian, normalized Laplacian, or modularity spectra, whereas the precision of the estimates depends on the distance between the subspaces spanned by the corresponding eigenvectors and partition vectors. By an analysis of variance argument, this distance is the sum of the inner variances of the underlying clusters, the objective function of the k-means clustering. Therefore, instead of speaking about continuous relaxation of the discrete optimization tasks, we rather solve the combinatorial problems by using the same linear algebra machinery as in Chapter 1. In this way, estimates for minimal or maximal multiway cuts are obtained by relating the overall minima or maxima to those taken on partition vectors.

Chapter 3 applies the results of Chapters 1 and 2 for spectral clustering of large networks. Networks are modeled either by edge-weighted graphs or contingency tables, and usually subject to random errors due to their evolving and flexible nature. Asymptotic properties of SD and SVD of the involved matrices are discussed when not only the number of the graph's vertices or that of the rows and columns of the contingency table tends to infinity, but the cluster sizes also grow proportionally with them. Mostly, perturbation results for the SD and SVD of blown-up matrices—burdened with a Wigner-type error matrix—are investigated. Conversely, given a weight-matrix or rectangular array of nonnegative entries, we look for the underlying block-structure. We show that under very general circumstances, clusters of a large graph's vertices and simultaneously those of the rows and columns of a large contingency table can be identified with high probability. In this framework, so-called volume regular cluster pairs are also considered with homogeneous information flow within the clusters and between pairs of them; and their pairwise discrepancies are related to spectra.

In Chapter 4, the theory of convergent graph sequences and graphons, elaborated by graph theorists, is used for vertex-and edge-weighted graphs and contingency tables. The convergence can be formulated in terms of the cut-distance, and limit objects are defined. Testable parameters are nonparametric statistics defined on graphs and contingency tables that can be consistently estimated based on a smaller sample selected randomly from the underlying huge network. Real-word graphs or rectangular arrays are sometimes considered as samples from a large network, and we deduce the network's parameters from the same parameters of its smaller parts. The theory guarantees that this can be done if the investigated parameter is testable. We prove that certain balanced multiway cut densities are indeed testable, and the increasing noisy graph sequences of Chapter 3 converge in this sense too.

Chapter 5 presents parametric and nonparametric statistical methods to find the underlying clusters of a given network or to classify graphs or contingency tables given some distinct prototypes. In fact, the minimum multiway cuts or bicuts and maximum modularities of Chapter 2 are nonparametric statistics that are estimated by means of spectral methods. Algorithms for the representation-based spectral clustering are reviewed together with recommendations about the choice of the eigenvectors which are best capable to reveal the underlying structure. A special algorithm for finding disjoint clusters of the edges, and not necessarily disjoint clusters of the vertices of a hypergraph, is also presented. We also discuss parametric models and give maximum likelihood estimation for the parameters. Eventually, we discuss possible applications of discriminant analysis for classifying graphs and contingency tables.

Frequently used facts about linear operators, random matrices, and multivariate statistical methods are collected in the Appendices. We have relatively few illustrations as believe that instead of visualization, the step by step comprehension, rather than the delusive view, can lead to a deeper understanding of the topic.

References

Alon N. (1986) Eigenvalues and expanders. Combinatorica6, 83–96.

Azran A. and Ghahramani Z. 2006 Spectral methods for automatic multiscale data clustering. Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2006), New York NY, (eds Fitzgibbon A., Taylor C.J. and Lecun Y.), IEEE Computer Society, Los Alamitos, California, pp. 190–197.

Biggs N.L. 1974 Algebraic Graph Theory, Cambridge University Press, Cambridge.

Bolla M. 2011 Penalized versions of the Newman–Girvan modularity and their relation to multi-way cuts and k-means clustering. Phys. Rev. E84, 016108.

Cheeger J. 1970 A lower bound for the smallest eigenvalue of the Laplacian, in Problems in Analysis (ed. R. C. Gunning), Princeton Univ. Press, Princeton NJ, pp. 195–199.

Chung F. 1997 Spectral Graph Theory, CBMS Regional Conference Series in Mathematics 92. American Mathematical Society, Providence RI.

Chung F, Graham R.L. and Wilson R.K. 1989 Quasi-random graphs. Combinatorica9, 345–362.

Chung F. and Graham R. 2008 Quasi-random graphs with given degree sequences, Random Struct. Algorithms12, 1–19.

Cvetkovic D.M., Doob M. and Sachs H. 1979 Spectra of Graphs, Academic Press, New York.

Diaconis P. and Stroock D. 1991 Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab.1, 36–62.

Ding C., He X., Zha H., Gu M. and Simon H.D. 2003 A Minmax Cut Spectral Method for Data Clustering and Graph Partitioning. Technical Report 54111, Lawrence Berkeley National Laboratory.

Fiedler M. 1973 Algebraic connectivity of graphs. Czech. Math. J.23 (98), 298–305.

Hoffman A.J. 1970 On eigenvalues and colorings of graphs. In Graph Theory and its Applications (ed. Harris B), pp. 79–91. Academic Press, New York.

Hoory S., Linial N. and Widgerson A. 2006 Expander graphs and their applications. Bull. Amer. Math. Soc. (N. S.)43 (4), 439–561.

Komlós J., Shokoufanden A., Simonovits M. and Szemerédi E. 2002 Szemerédi's Regularity Lemma and its Applications in Graph Theory, in Lecture Notes in Computer Science, Springer, Berlin, vol 2292, pp. 84–112.

Lee J.R., Gharan S.O. and Trevisan L. 2012 Multi-way spectral partitioning and higher-order Cheeger inequalities, in Proc. 44th Annual ACM Symposium on the Theory of Computing (STOC 2012), New York NY, pp. 1117–1130.

Louis A., Raghavendra P., Tetali P. and Vempala S. 2011 Algorithmic extension of Cheeger's inequality to higher eigenvalues and partitions, in Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science (eds Goldborg LA, Jansen K, Ravi R and Rolim JDP), Vol. 6845, Springer, pp. 315–326.

Lovász L. 1993 Random walks on graphs: a survey, in Combinatorics, Paul Erds is Eighty. János Bolyai Society, Mathematical Studies, Keszthely, Hungary, vol. 2, pp. 1–46.

Lovász L. and Winkler P. 1995 Exact mixing in an unknown Markov chain. Electron. J. Comb.2, Paper R15, 1–14.

Metropolis N., Rosenblut A., Rosenbluth M., Teller A. and Teller E. 1953 Equation of state calculation by fast computing machines. J. Chem. Physics21, 1087–1092.

Mohar B. 1988 Isoperimetric inequalities, growth and the spectrum of graphs. Linear Algebra Appl.103, 119–131.

Nash-Williams CStJA 1959 Random walks and electronic currents in networks. Proc. Cambridge Phil. Soc.55, 181–194.

Newman M.E.J 2003 Mixing patterns in networks. Phys. Rev. E67, 026126.

Ng A.Y. Jordan M.I. and Weiss Y. 2001 On spectral clustering: analysis and an algorithm. Proc. 14th Neural Information Processing Systems Conference (NIPS 2001) (Dietterich T.G., Becker S. and Ghahramani Z. eds), MIT Press, Cambridge, MA, pp. 849–856.

Spielman D.A. 2007 Spectral graph theory and its applications. Proc. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), Providence, RI, IEEE Computer Society, Los Alamitos, California, pp. 29–38.

von Luxburg U 2007 A tutorial on spectral clustering. Stat. Comput.17 (4), 395–416.

von Luxburg U., Belkin M. and Bousquet O. 2008 Consistency of spectral clustering. Ann. Stat.36 (2), 555–586.