Handbook of Large-Scale Random Networks (eBook)

Title Page 4
Copyright Page 5
Table of Contents 6
Preface 10
Chapter 1 Random Graphs and Branching Processes 16
1. Introduction 17
2. Models 20
2.1. Classical models 20
2.2. Random graphs with a fixed degree sequence 24
2.3. Inhomogeneous models 27
2.4. Models with independence between edges 28
2.5. A general sparse inhomogeneous model 30
2.6. Independence and clustering 33
2.7. Further models 34
3. The Phase Transition in G(n, p) 35
3.1. Historical remarks 36
3.2. Local behaviour 41
3.3. The giant component 44
3.4. Stronger results for G(n, p) 47
3.5. The subcritical case 51
3.6. The supercritical case 61
4. The Phase Transition in Inhomogeneous Random Graphs 69
4.1. Graphs with a given degree sequence 69
4.2. Robustness of the BA or LCD model 71
4.3. The uniformly grown models and Dubins’ model 73
4.4. Graphs with independence between edges 77
4.5. Applications of non-Poisson branching processes 80
5. Branching Processes and Other Global Properties 85
5.1. Diameter 85
5.2. The k-core 88
6. Appropriateness of Models: Metrics on Graphs 91
6.1. The edit distance(s): dense case 92
6.2. The subgraph distance: dense case 95
6.3. The cut metric: dense case 97
6.4. The sparse case 99
6.5. New metrics and models 103
References 105
Chapter 2 Percolation, Connectivity, Coverage and Colouring of Random Geometric Graphs 117
1. Introduction 117
2. The Gilbert Disc Model 118
2.1. Percolation 119
2.2. Connectivity 120
2.3. Coverage 121
2.4. Colouring 123
2.5. Thin strips 125
3. The k-nearest Neighbour Model 128
3.1. Percolation 128
3.2. Connectivity 129
3.3. Sharp thresholds 131
4. Random Tessellations 132
4.1. Random Voronoi Percolation 133
4.2. Random Johnson–Mehl Percolation 137
5. Outlook 138
References 139
Chapter 3 Scaling Properties of Complex Networks and Spanning Trees 143
1. Random Graphs and Complex Networks 143
2. The Bollobás Configuration Model 145
3. Percolation on Random Graphs 146
3.1. Generating functions 147
3.2. Critical exponents 149
3.3. Fractal dimensions 151
4. Weighted Networks 154
4.1. Shortest paths in networks 154
4.2. Strong and Weak Disorder 155
4.3. Minimum Spanning Trees 156
4.4. Fractal properties of optimal paths 158
5. Fractal Networks 160
5.1. The cluster growing method 160
5.2. The box covering method 160
5.3. The fractal nature of scale free networks 161
6. Fractal Properties of Network Boundaries 163
6.1. Distribution of outer shells population 164
6.2. Component size distribution 165
7. Summary 165
References 166
Chapter 4 Random Tree Growth with Branching Processes – a Survey 170
1. Random Tree Model 170
1.1. Notation 171
1.2. The Model 172
1.2.1. Discrete Time Model 173
1.2.2. Continuous Time Model 173
1.3. Some Additional Notation 175
2. Local Properties 176
2.1. Statement of Results 176
2.2. Linear Weight Function 178
2.3. Proof of Convergence in Probability 179
3. Branching Processes 188
4. Global Properties 191
4.1. Notation and Question 191
4.2. Markov Property 193
4.3. Fragmentation of Mass 195
4.3.1. Linear Weight Function 195
4.3.2. Binary Tree 197
References 200
Chapter 5 Reaction-diffusion Processes in Scale-free Networks 202
1. Introduction 202
2. Analytical Description of Diffusion-annihilation Processes in Complex Networks 207
2.1. Heterogeneous mean-field formalism 207
2.2. Finite networks: Diffusion-limited regime 212
2.3. Infinite networks: Continuous degree approximation 214
3. Numerical Simulations 217
3.1. Density decay in uncorrelated networks 218
3.2. Depletion, segregation, and dynamical correlations 220
3.3. Degree effects on annihilation 225
3.4. Effects of the minimum degree of the network 227
3.5. Effects of a tree topology 229
4. Outlook 232
References 233
Chapter 6 Toward Understanding the Structure and Function of Cellular Interaction Networks 237
1. Definition of Cellular Interaction Networks 237
2. Detecting or Inferring Interactions 240
3. Network Measures 243
Degree and degree distribution 245
Clustering coefficient 245
Connectivity, paths, distances, efficiency, and graph components 246
Betweenness centrality, sources and sinks 247
4. Properties of Cellular Interaction Graphs 247
5. Graph Models 253
Erdos–Rényi (ER) random graphs 253
Scale-free random graphs 254
Evolving network models 254
Models of cellular network evolution 255
6. Modeling the Dynamics of Cellular Networks 256
7. Examples of Network-Based Dynamics Models 257
Modeling signal transduction in plants 257
Modeling the systems-level regulation of immune responses to Bordetella 262
8. Discussion 265
References 267
Chapter 7 Scale-Free Cortical Planar Networks 274
1. Introduction 275
1.1. The context of quantitative brain dynamics from psychology, biology and philosophy 275
1.2. The mathematical foundations shared by ODE and RGT 277
1.3. The applicability of ODE and RGT depends on the following properties of cortex 278
2. Allocortex: The Simplest Model for the Phase Transition in Criticality 282
2.1. Microscopic sensation and mesoscopic perception 282
2.2. The origin of the background activity in mutual excitation: positive feedback 285
2.3. Source of the repeated discontinuities facilitating phase transitions: Rayleigh noise 287
3. Application of RGT to Neocortex 289
3.1. Topology of large-scale neocortical connectivity: Generality versus specificity 289
3.1.1. Neocortical area and neuronal density 289
3.1.2. The large-scale embryological growth and development of neocortex 290
3.2. Evolution of heterogeneous cortical structures 292
3.2.1. Directedness in cortical networks 293
3.2.2. Sparseness in cortical networks 294
3.3. Topology of small-scale neocortical connectivity: Specificity 295
3.3.1. Structural connectivity: Emergence of neocortex from allocortex 295
3.3.2. Considerations of differences between allocortical and neocortical activity 297
3.3.3. Preferentiality in the assignment of probability of connections 298
4. Structure and Dynamics in Cortex Models 299
5. Requirements the Mathematical Models 301
6. Conclusions 302
7. Appendix: Mathematical Models 304
7.1. A general inhomogeneous model 305
7.2. The exponentially expanding graph model 308
References 315
Chapter 8 Reconstructing Cortical Networks: Case of Directed Graphs with High Level of Reciprocity 322
1. Introduction 323
2. Methods 326
2.1. General remarks on the method 326
2.2. The preference model 327
2.3. Measuring the accuracy of reconstruction 329
2.4. Fitting the preference model 330
2.4.1. Greedy optimization 330
2.4.2. Markov chain Monte Carlo sampling 331
2.5. Choosing the number of groups 334
2.6. Performance measurements 336
2.6.1. Fitting the model with given number of groups 337
2.6.2. Fitting the model without a predefined number of groups 339
2.7. Handling uncertain connections 341
3. Results and Discussion 342
3.1. Rapid mixing of the MCMC process 343
3.2. Methodological comparison with other prediction approaches 345
3.3. Visual cortex 346
3.4. Visuo-tactile cortex 351
3.5. Major structural changes after reconstruction 356
4. Conclusion 358
References 360
Chapter 9 k-clique Percolation and Clustering 366
1. Introduction 366
2. k-clique Percolation in the E-R-graph 368
2.1. Derivation of the critical point with heuristic arguments 369
2.2. Generating function formalism 370
2.3. Partial differential equation approach to k-clique percolation 374
2.4. Numerical simulations 376
3. Percolation of Weighted k-cliques 380
3.1. Definitions 380
3.2. Percolation transition in the weighted E-R graph 381
4. Directed k-clique Percolation 383
4.1. Definitions 383
4.2. Percolation transition in the directed E-R graph 385
5. Applications: Community Finding and Clustering 387
5.1. The CPM in practice 389
5.2. Applying the CPM to real networks 392
5.2.1. The graph of communities 392
5.2.2. Molecular biological networks 393
5.2.3. Social networks 395
5.2.4. Further results 398
References 400
Chapter 10 The Inverse Problem of Evolving Networks – with Application to Social Nets 406
1. Introduction 406
2. The Model Framework 408
2.1. Events 408
2.2. The Kernel Functions 409
2.3. The General Framework 411
3. Solving the Inverse Problem 412
3.1. The Frequentist Method 412
3.2. The Maximum Likelihood Method 414
4. Applications 423
4.1. The Dynamics of Scientific Collaboration Networks 423
4.2. Comparing Alternative Models 425
4.3. Validating Network Models 433
References 438
Chapter 11 Learning and Representation: From Compressive Sampling to the ‘Symbol Learning Problem’ 441
1. Introduction 441
1.1. Overview of the structure of the paper 444
2. Sparse Representation 445
2.1. Neural solution to distinct sparse representations 446
3. Factored Representation 449
3.1. Non-combinatorial independent subspace analysis 451
3.1.1. ISA separation 451
3.1.2. ISA with unknown components 452
3.1.3. ISA Generalizations 453
3.2. Model of the hippocampal formation 454
3.3. Declarative memory: The relevance of the hippocampal formation 455
3.3.1. Learning in the model hippocampus 455
4. Robust Control, Event Learning and Factored RL 456
4.1. Robust inverse dynamic controller with global stability properties 457
4.2. Inverse dynamics for robots 459
4.2.1. Inverse dynamics is easy to learn 460
4.2.2. Inverse dynamics can avoid combinatorial explosion 461
4.3. Markov Decision Processes 462
4.4. e-Markov Decision Processes 463
4.5. Formal description of event learning 463
4.5.1. Robust controller in event learning 465
4.5.2. Exact Value Iteration 465
4.5.3. Approximate value iteration 466
4.5.4. Convergent projection 467
4.6. Factored value iteration 468
4.6.1. Factored Markov decision processes 468
4.6.2. Exploiting factored structure in value iteration 470
4.7. The sampling advantage 472
4.8. The symbol learning problem: Core of the learning task 473
4.9. Information theoretic direction for the symbol learning problem 474
5. Summary 475
References 477
Chapter 12 Telephone Call Network Data Mining: A Survey with Experiments* 485
1. Introduction 486
1.1. Data sets 487
2. Link Prediction 489
2.1. Neighborhood based methods 490
2.2. Multi-step propagation: Methods based on path ensembles 491
2.3. Link prediction experiments 495
3. Network Topology: Navigation in the Small World 498
4. Clustering Algorithms 501
4.1. Two recent clustering methods 502
4.2. Cluster quality measures 506
4.3. Spectral clustering: a brief history 507
4.4. Small component redistribution heuristics 509
4.5. Spectral clustering: an experiment 511
5. Stacked Graphical Classification 515
5.1. Label propagation: a broader outlook 517
5.2. The stacked graphical learning framework 517
Conclusion 520
References 520
Index 527

"Chapter 1 Random Graphs and Branching Processes (p. 15-16)

B´ELA BOLLOB´AS and OLIVER RIORDAN

During the past decade or so, there has been much interest in generating and analyzing graphs resembling large-scale real-world networks such as the world wide web, neural networks, and social networks. As these large-scale networks seem to be ‘random’, in the sense that they do not have a transparent, well-de?ned structure, it does not seem too unreasonable to hope to ?nd classical models of random graphs that share their basic properties.

Such hopes are quickly dashed, however, since the classical random graphs are all homogeneous, in the sense that all vertices (or indeed all k-sets of vertices) are a priori equivalent in the model. Most real-world networks are not at all like this, as seen most easily from their often unbalanced (power-law) degree sequences. Thus, in order to model such graphs, a host of inhomogeneous random graph models have been constructed and studied.

In this paper we shall survey a number of these models and the basic results proved about the inhomogeneous sparse (bounded average degree) random graphs they give rise to. We shall focus on mathematically tractable models, which often means models with independence between edges, and in particular on the very general sparse inhomogeneous models of Bollob´as, Janson and Riordan. The ?rst of these encompasses a great range of earlier models of this type; the second, the inhomogeneous clustering model, goes much further, allowing for the presence of clustering while retaining tractability.

We are not only interested in our inhomogeneous random graphs themselves, but also in the random subgraphs obtained by keeping their edges with a certain probability p. Our main interest is in the phase transition that takes place around a certain critical value p0 of p, when the component structure of the random subgraph undergoes a sudden change. The quintessential phase transition occurs in the classical binomial random graph G(n, c/n) as c grows from less than 1 to greater than 1 and, as shown by Erd?os and R´enyi, a unique largest component, the giant component, is born.

A ubiquitous theme of our paper is the use of branching processes in the study of random graphs. This ‘modern’ approach to random graphs is crucial in the study of the very general models of inhomogeneous random graphs mentioned above. To illustrate the power of branching processes, we show how they can be used to reprove sharp results about the classical random graph G(n, c/n), ?rst proved by Bollob´as and Luczak over twenty years ago. When it comes to inhomogeneous models, we shall have time only to sketch the connection to branching processes. Finally, we close by discussing the question of how to tell whether a given model is appropriate in a given situation. This leads to many fascinating questions about metrics for sparse graphs, and their relationship to existing models and potential new models."