Limit distribution of the size of the giant component in a web random graph

Abstract : Consider random graph with $N+ 1$ vertices as follows. The degrees of vertices $1,2,\ldots, N$ are the independent identically distributed random variables $\xi_1, \xi_2, \ldots , \xi_N$ with distribution $\mathbf{P}\{\xi_1 \geq k\}=k^{− \tau},$ $k= 1,2,\ldots,$ $\tau \in (1,2)$,(1) and the vertex $N+1$ has degree $0$, if the sum $\zeta_N=\xi_1+ \ldots +\xi_N$ is even, else degree is $1$. From (1) we get that $p_k=\mathbf{P}\{\xi_1=k\}=k^{−\tau}−(k+ 1)^{−\tau}$, $k= 1,2,\ldots$ Let $G(k_1, \ldots , k_N)$ be a set of graphs with $\xi_1=k_1,\ldots, \xi_N=k_N$. If $g$ is a realization of random graph then $\mathbf{P}\{g \in G(k_1, \ldots , k_N)\}=p_{k_1} \cdot \ldots \cdot p_{k_N}$. The probability distribution on the set of graph is defined such that for a vector $(k_1, \ldots, k_N)$ all graphs, lying in $G(k_1, \ldots , k_N)$, are equiprobable. Studies of the past few years show that such graphs are good random graph models for Internet and other networks topology description (see, for example, H. Reittu and I. Norros (2004)). To build the graph, we have $N$ numbered vertices and incident to vertex $i \xi_i$ stubs, $i= 1, \ldots , N$. All stubs need to be connected to another stub to construct the graph. The stubs are numbered in an arbitrary order from $1$ to $\zeta_N$. Let $\eta_{(N)}$ be the maximum degree of the vertices.
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.435-436, 2006, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184692
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:16:30
Dernière modification le : mercredi 10 mai 2017 - 17:40:26
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:06:54

Fichier

dmAG0141.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184692, version 1

Collections

Citation

Yuri Pavlov. Limit distribution of the size of the giant component in a web random graph. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.435-436, 2006, DMTCS Proceedings. 〈hal-01184692〉

Partager

Métriques

Consultations de la notice

187

Téléchargements de fichiers

83