Diffusion Approximation for the Components in Critical Inhomogeneous Random Graphs of Rank 1.
(2013) In Random Structures & Algorithms 43(4). p.486-539- Abstract
- Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 < infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min{1, x(i)x(j)/n (1 + a/n(1/3))}. We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2/3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3/EX s. In particular, we conclude that the size of the largest... (More)
- Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 < infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min{1, x(i)x(j)/n (1 + a/n(1/3))}. We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2/3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3/EX s. In particular, we conclude that the size of the largest connected component is of order n(2/3). (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486-539, 2013 (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4157898
- author
- Turova, Tatyana LU
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Critical Random Graph, Martingale, Connected Components
- in
- Random Structures & Algorithms
- volume
- 43
- issue
- 4
- pages
- 486 - 539
- publisher
- John Wiley & Sons Inc.
- external identifiers
-
- wos:000326026400005
- scopus:84886443897
- ISSN
- 1098-2418
- DOI
- 10.1002/rsa.20503
- language
- English
- LU publication?
- yes
- id
- 3c29ccfd-2955-4ce9-b223-09e452d3888f (old id 4157898)
- date added to LUP
- 2016-04-01 10:17:16
- date last changed
- 2022-04-04 08:33:13
@article{3c29ccfd-2955-4ce9-b223-09e452d3888f, abstract = {{Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 < infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min{1, x(i)x(j)/n (1 + a/n(1/3))}. We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2/3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3/EX s. In particular, we conclude that the size of the largest connected component is of order n(2/3). (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486-539, 2013}}, author = {{Turova, Tatyana}}, issn = {{1098-2418}}, keywords = {{Critical Random Graph; Martingale; Connected Components}}, language = {{eng}}, number = {{4}}, pages = {{486--539}}, publisher = {{John Wiley & Sons Inc.}}, series = {{Random Structures & Algorithms}}, title = {{Diffusion Approximation for the Components in Critical Inhomogeneous Random Graphs of Rank 1.}}, url = {{http://dx.doi.org/10.1002/rsa.20503}}, doi = {{10.1002/rsa.20503}}, volume = {{43}}, year = {{2013}}, }