Fall School on random graphs Cargèse

Cargèse fall school on random graphs

Cargèse (Corsica), September 20-26, 2015

The school is supported by the following institutions:

Overview of the subject

Random graphs is the general term that refers to probability distributions on graphs. There are many different models of random graphs studied in the literature some of them being application driven, i.e. motivated by problems in practice, whereas others are inspired by foundational issues in Mathematics and Computer Science. Thanks to the emergence of big networks that can be modelled by random graphs, to the availability of big data, the interest in this field has been rapidly growing in recent decades, both from theoretical as well as from practical points of view.

Short history of the subject

The theory of random graphs was founded by Erdős and Rényi [Erd59, Erd60] after Erdős had discovered that the probabilistic method is useful in attacking problems of extremal graph theory. The breakthrough result of Erdős and Rényi was that giant components in random graphs appear suddenly: they showed that almost all graphs with few edges (relatively to their size) have only small components, whereas almost all graphs with many edges have one big component, and that the transition between the two phases is short. In parallel to Erdős and Rényi, and independently of Erdős and Rényi, Gilbert [Gil59] also introduced the same model G(n,p), where each edge appears independently with probability p. Two excellent monographs [Bol01] and [JLR00] describe the G(n,p) model in detail. Shortly afterwards, Gilbert [Gil61] introduced the random model of the Gilbert disc, nowadays known as random geometric graphs (see also the book by Penrose, [Pen03]). Another classic model is the model of random d-regular graphs whose study was initiated by Read [Rea59] to count the number of such graphs. More recently, with the idea to model networks, many new random graph models have been designed, such as the Preferential Attachment Model, the SPA model, geometric protean graphs, or inhomogeneous random geometric graphs, to mention just a few (see [CFP14, BJR07]).

Some applications

The main application of random graphs stems from modelling complex networks in the following areas with different types of random graph models:
Telecommunication networks: here the vertices represent radio antennae, and there is an edge between vertices if the two antennae are so close that sending on the same frequency would cause interferences. Random geometric graphs are often used to model such a network.
Computer networks: computers are represented by vertices, and if two computers are directly connected by a cable or a wireless connection, there is an edge between the corresponding vertices. Information has to be exchanged between different computers, but some connections may fail. The classical G(n,p) model can be used to analyse these networks.
Neural networks: Vertices represent networks, and interactions between them is explained by edges. The classical G(n,p) model together with extensions that allow for the existence of thresholds upon which one neuron may fire are used to analyse long-term-interactions.
The World Wide Web: the vertices represent websites, and there is a (directed) edge between two vertices if one site links to the other one. Since this network features many properties not present in classical random graph models, such as high clustering coefficient, Power-law distribution of nodes, or small diameter, models such as the Preferential Attachment Model, the SPA model or geometric protean graphs model well these networks.
Sociology: the vertices represent people, and there is an edge between two vertices if the two people know each other. The famous chain experiment of Milgram [Mil67] showed that two arbitrary people are at distance at most 6 from each other. The friendship relations on facebook or twitter share similar characteristics, and as before, the Preferential Attachment model or the SPA model is among the most popular random graph models used for analyzing theoretically these networks.
Epidemiology: Vertices represent people possibly being susceptible to infections, and vertices are connected by an edge if the corresponding people are close to transmit infections. Starting from one infected person (that might or might not recover) one studies the spread of epidemics. Random geometric graphs together with percolation models and branching processes are used to study the modelling of such infectious diseases.
Biology – Protein-Protein-Interaction Networks: vertices represent proteins, and if two proteins interact with each other, the corresponding vertices are linked by an edge.
Semantic networks: vertices represent concepts, and (directed) edges explain links between these.
Interbank payment networks: vertices represent banks, edges payments between banks.

References

[BJR07]: Bollobás, B., Janson, S., Riordan, O.: The phase transition in inhomogeneous random graphs, Random Structures and Algorithms 31 (2007), 3-122.
[Bol01]: Bollobás, B. Random Graphs, Cambridge studies in advanced mathematics, 2001.
[CFP14]: Cooper, C., Frieze, A., Prałat, P.: Some typical properties of the Spatial Preferred Attachment model, Internet Mathematics 10 (2014), 27-47.
[Erd59]: Erdős, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6, 290-297, 1959.
[Erd60]: Erdős, P., Rényi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61, 1960.
[Gil59]: Gilbert, E. N.: Random graphs, Ann. Math. Statist. 30, 1141-1144, 1959.
[Gil61]: Gilbert, E. N.: Random plane networks, J. Soc. Ind. Appl. Math. 9, 533-543, 1961.
[JLR00]: Janson, S., Łuczak, T., Ruciński, A.: Random graphs, John Wiley and Sons, New York, 2000.
[Mil67]: Milgram, S: The Small-World Problem, Psychology today, 1 (1) 1967, 61-67.
[Pen03]: Penrose, M.: Random Geometric Graphs, Oxford Studies in Probability, 2003.
[Rea59]: Read, R. C.: The enumeration of locally restricted graphs (I), J. Lond. Math. Soc. 34, 417-436, 1959.