Handbook of large-scale random networks
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.
- Average distance is submultiplicative and subadditive with respect to the strong product of graphs
- Preferential attachment without vertex growth: emergence of the giant component
- Random graphs and complex networks. Volume 1
- Pattern-based computing via sequential phase transitions in hierarchical mean field neuropercolation
- Quasispecies dynamics with network constraints
- Quasispecies dynamics on a network of interacting genotypes and idiotypes: formulation of the model
- Random graph dynamics
- Community detection in temporal multilayer networks, with an application to correlation networks
- Hierarchical random cellular neural networks for system-level brain-like signal processing
- Large triangle packings and Tuza's conjecture in sparse random graphs
- Closing the random graph gap in Tuza's conjecture through the online triangle packing process
- Convergence of Achlioptas processes via differential equations with unique solutions
- On the method of typical bounded differences
- The partial duplication random graph with edge deletion
- Dynamic concentration of the triangle‐free process
- Random Graphs and Complex Networks
- The coreness and H-index of random geometric graphs
This page was built for publication: Handbook of large-scale random networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q938590)
