Handbook of large-scale random networks (Q938590): Difference between revisions

This book is intended to give an overview of various recent methods for the study of large-scale complex networks. It comes in two main parts, the first emphasising relevant mathematical theory, the second a discussion of applications, mainly in biology/brain modelling, but also in (e.g.) physics, computer networks and social science. Chapter 1 by Bollobás and Riordan, discusses various random graph models, including a very general model of random graphs with independence studied by these two authors and S. Janson. Much attention is paid to the the idea that the set of vertices in a sparse Erdős-Rényi random graph \(G(n,c/n)\) at distance \(i\) from a fixed vertex can be approximated by the \(i\)th generation of a branching process with offspring size having Poisson distribution with parameter \(c\), which underlies the idea of a giant (linear in the number \(n\) of vertices) component forming when \(c>1\), only small components forming if \(c<1\) and medium sized components for \(c=1\) (the `phase transition'), and some discussion of the generalisations of this idea to other models, e.g. that of Bollobás-Janson-Riordan. Chapter 2 by Balister, Bollobás and Sarkar discussses random geometric graphs where one has a Poisson process of rate 1 in \({\mathbb R}^{2}\) and two points are adjacent if and only if the distance between them is less than \(r\) (closely related to the model discussed in M. D. Penrose's book Random Geometric Graphs). It also discusses the \(k\)-nearest neighbour model where instead each point of the process is joined to its \(k\) nearest neighbours, and various random tessellation models. Again thresholds, where the qualitative behaviour of the system changes suddenly are discussed. Chapter 3 by Cohen and Havlin discusses (not always fully rigorously) links between systems at a threshold -- corresponding to \(c=1\) in the second paragraph -- and the distance between vertices. In particular, the so-called scale free graphs, where (roughly) the probability of a vertex having a given degree obeys a power law distribution, have anomalous behaviour in this respect. Chapter 4 by Rudas and Tóth discusses random trees under the preferential attachment model whereby new vertices are more likely to be attached to those vertices already present of high degree, via some weight function (a new webpage is more likely to have a link to GOOGLE than to a webpage selected uniformly at random). By passing to continuous time a link with branching processes is established, leading to results on these random trees. Part II, being more driven by the application areas, is in some sense harder to summarise: we merely give a sentence or two about each chapter. Chapter 5 by Catanzaro, Boguna and Pastor-Satorras discusses mainly simulation results on reaction-diffusion equations in scale-free networks. Chapter 6 by Thakar, Christensen and Albert discusses cellular interaction graphs, aiming to create a dialogue between systems biologists and graph theorists. Chapter 7 by Freeman and Kozma (with an appendix by Bollobás and Riordan on a suitable mathematical model for the problem) discusses random graphs as models of the brain cortex, and Chapter 8 by Nepusz, Négyessy, Tusnády and Bazsó, is about the reconstruction of cortical networks, (roughly, predicting where connections will be). Chapter 9 by Palla, Ábel, Farkas, Pollner, Derényi and Vicsek deals with \(k\)-clique percolation, i.e. the question of the component structure of the graph \(H\) whose vertices are the complete subgraphs of order \(k\) in a fixed graph \(G\) and where two vertices of \(H\) are adjacent if and only if the corresponding cliques of \(G\) have \(k-1\) vertices in common, the practical aim being to understand how social and similar networks evolve. Chapter 10 by Csárdi, Strandburg, Tobochnik and Érdi deals with the `inverse problem' of observing some real evolving network and trying to find the best stochastic mechanism from some family which describes the evolution. Chapter 11 by Lőrincz is on neurocognitive modelling, with the central constraints being provided by the theory of reinforcement learning, and Chapter 12 by Kurucz, Lukács, Siklósi, Benczúr, Csalogány and Lukács, deals with attempts to data mine telephone call networks.