Structure in complex networks / J. Reichardt.

Format:

Book

Author/Creator:

Reichardt, J. (Jörg)

Series:

Lecture notes in physics ; 766.

The lecture notes in physics, 0075-8450 ; 766

Language:

English

Subjects (All):

Cluster analysis.

Data mining.

Pattern recognition systems.

Graph theory.

Statistical physics.

Physical Description:

xiii, 151 pages : illustrations ; 24 cm.

Place of Publication:

Berlin : Springer, [2009]

Summary:

In the modern world of gigantic datasets, which scientists and practioners of all fields of learning are confronted with, the availability of robust, scalable and easy-to-use methods for pattern recognition and data mining are of paramount importance, so as to be able to cope with the avalanche of data in a meaningful way. This concise and pedagogical research monograph introduces the reader to two specific aspects - clustering techniques and dimensionality reduction - in the context of complex network analysis. The first chapter provides a short introduction into relevant graph theoretical notation; chapter 2 then reviews and compares a number of cluster definitions from different fields of science. In the subsequent chapters, a first-principles approach to graph clustering in complex networks is developed using methods from statistical physics and the reader will learn, that even today, this field significantly contributes to the understanding and resolution of the related statistical inference issues. Finally, an application chapter examines real-world networks from the economic realm to show how the network clustering process can be used to deal with large, sparse datasets where conventional analyses fail.

Contents:

1 Introduction to Complex Networks 1

1.1 Graph Theoretical Notation 2

1.2 Random Graphs 3

1.3 Six Degrees of Separation 4

1.4 Scale-Free Degree Distributions 5

1.5 Correlations in Networks 6

1.6 Dynamics on Networks 7

1.7 Patterns of Link Structure 8

2 Standard Approaches to Network Structure: Block Modeling 13

2.1 Positions, Roles and Equivalences 13

2.2 Block Modeling 14

2.3 Cohesive Subgroups or Communities as Block Models 18

2.3.1 Sociological Definitions 18

2.3.2 Definitions from Physicists 20

2.4 Algorithms for Community Detection 21

2.4.1 Comparing a Quality Function 21

2.4.2 Hierarchical Algorithms 22

2.4.3 Semi-hierarchical 25

2.4.4 Non-hierarchical 25

2.4.5 Optimization Based 26

3 A First Principles Approach to Block Structure Detection 31

3.1 Mapping the Problem 31

3.1.1 Dimensionality Reduction with Minimal Squared Error 31

3.1.2 Squared Error for Multivariate Data and Networks 33

3.2 A New Error Function 34

3.2.1 Fitting Networks to Image Graphs 37

3.2.2 The Optimal Image Graph 37

3.2.3 Maximum Value of the Fit Score 38

3.2.4 Choice of a Penalty Function and Null Model 39

3.2.5 Cohesion and Adhesion 40

3.2.6 Optimizing the Quality Function 40

4 Diagonal Block Models as Cohesive Groups 45

4.1 Equivalence with Newman-Girvan Modularity and Spin Glass Energy 45

4.1.1 Properties of the Ground State 46

4.1.2 Simple Divisive and Agglomerative Approaches to Modularity Maximization 48

4.1.3 Finding the Community Around a Given Node 51

4.2 Comparison with Other Definitions of Communities 51

4.2.1 Hierarchy and Overlap of Community Assignments 52

4.3 Benchmarking the Algorithm 56

4.4 Community Detection and Graph Partitioning 60

4.4.1 Expectation Values for the Modularity 61

4.4.2 Theoretical Limits of Community Detection 66

5 Modularity of Dense Random Graphs 69

5.1 Analytical Developments 69

5.2 Numerical Experiments 80

6 Modularity of Sparse Random Graphs 87

6.1 Graph Partitioning Using the Cavity Method 87

6.1.1 Cavity Method at Zero Temperature 88

6.1.2 Symmetry Conditions 91

6.1.3 Bi-partitioning 92

6.1.4 Limit of Dense Graphs with Poissonian Degree Distribution 97

6.1.5 q-Partitioning of a Bethe Lattice with three Links per Node 98

6.1.6 Population Dynamics Approximation 101

6.2 Recovering Planted Cluster Structures 102

6.2.1 Symmetry Conditions 104

6.2.2 Graphs with Two Clusters 106

6.2.3 Onset of Detectable Cluster Structure 109

6.2.4 Graphs with More than Two Clusters 111

6.2.5 Bethe Lattice with k = 3 112

6.2.6 Population Dynamics Formulation of the Cavity Equations 112

7 Applications 119

7.1 Block Modeling the World Trade Network 119

7.2 Communities of Common Interest among eBay Users 126

7.2.1 Data Set 129

7.2.2 User Activity 130

7.2.3 User Networks 132

7.2.4 Market Segmentation 136.

Notes:

Includes bibliographical references.

ISBN:

9783540878322

3540878327

3540878335

9783540878339

OCLC:

248993741