|
Large deviation properties of random graphs| old_uid | 13997 |
|---|
| title | Large deviation properties of random graphs |
|---|
| start_date | 2017/05/31 |
|---|
| schedule | 14h |
|---|
| online | no |
|---|
| location_info | salle 384 |
|---|
| summary | When describing random objects or statistical processes, within analytical and numerical simulations one often just studies the behavior of means or variances. Nevertheless, as for any random process, a complete description is only given if the full distribution of the measurable quantity is available. Here sophisticated large-deviation algorithms are used to obtain the distributions of properties of ensembles of random graphs. Probabilities as small as 10^-180 are accessed using an artificial finite-temperature (Boltzmann) ensemble.
First, distributions of the size of the largest component, in particular the large-deviation tail, are studied numerically for two graph ensembles, for Erdoes-Renyi random graphs with finite connectivity and for two-dimensional bond percolation. The distributions for the Erdoes-Renyi ensemble agree well with previously obtained analytical results. The results for the percolation problem, where no analytical results are available, are qualitatively similar, but the shapes of the distributions are somehow different and the finite-size corrections are sometimes much larger. Similar results are shown for a stochastic block model, which is often used to model communities structures in social networks. Here, also the distribution of the size of the largest component is studied and the role of the shape of the distribution with respect to the detectability threshold is elucidated.
Finally, the distributions of the diameter are presented. Here, partial analytic results are available from previous studies for Erdoes-Renyi random graphs in the small connectivity region. The numerical results follow a Gumbel distribution and agree well with the analytics. For higher connectivities, where no analytic results are available, the simulation results show that the distributions are qualitatively different from the low connectivity region. |
|---|
| responsibles | Marinica |
|---|
| |
|