Language:
English
繁體中文
Help
圖資館首頁
Login
Back
Switch To:
Labeled
|
MARC Mode
|
ISBD
Asymptotic properties of random geom...
~
Rai, Sanatan.
Asymptotic properties of random geometric graphs.
Record Type:
Electronic resources : Monograph/item
Title/Author:
Asymptotic properties of random geometric graphs.
Author:
Rai, Sanatan.
Description:
59 p.
Notes:
Adviser: Ashish Goel.
Notes:
Source: Dissertation Abstracts International, Volume: 66-08, Section: B, page: 4262.
Contained By:
Dissertation Abstracts International66-08B.
Subject:
Mathematics.
Online resource:
http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379
ISBN:
9780542286551
Asymptotic properties of random geometric graphs.
Rai, Sanatan.
Asymptotic properties of random geometric graphs.
- 59 p.
Adviser: Ashish Goel.
Thesis (Ph.D.)--Stanford University, 2005.
Our second result is that the spectral measure of the transition matrix of the simple random walk (SRW) on G( Xn ; r(n)) is concentrated, and in fact converges to that of the graph on the deterministic grid. This permits the approximation of various random walk based functionals on the random graph by their values on the graph on the grid. Conventional approaches from random matrix theory are inapplicable in this case because the entries are not independent. We have a novel approach to derive spectral concentration via proving concentration of the matrices in the Hilbert-Schmidt norm.
ISBN: 9780542286551Subjects--Topical Terms:
184409
Mathematics.
Asymptotic properties of random geometric graphs.
LDR
:02319nmm _2200277 _450
001
170776
005
20061228142242.5
008
090528s2005 eng d
020
$a
9780542286551
035
$a
00242806
040
$a
UnM
$c
UnM
100
0
$a
Rai, Sanatan.
$3
244806
245
1 0
$a
Asymptotic properties of random geometric graphs.
300
$a
59 p.
500
$a
Adviser: Ashish Goel.
500
$a
Source: Dissertation Abstracts International, Volume: 66-08, Section: B, page: 4262.
502
$a
Thesis (Ph.D.)--Stanford University, 2005.
520
#
$a
Our second result is that the spectral measure of the transition matrix of the simple random walk (SRW) on G( Xn ; r(n)) is concentrated, and in fact converges to that of the graph on the deterministic grid. This permits the approximation of various random walk based functionals on the random graph by their values on the graph on the grid. Conventional approaches from random matrix theory are inapplicable in this case because the entries are not independent. We have a novel approach to derive spectral concentration via proving concentration of the matrices in the Hilbert-Schmidt norm.
520
#
$a
Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0, 1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds and also present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. In fact, we prove that a random geometric graph is shown is a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.
590
$a
School code: 0212.
650
# 0
$a
Mathematics.
$3
184409
650
# 0
$a
Operations Research.
$3
227148
690
$a
0405
690
$a
0796
710
0 #
$a
Stanford University.
$3
212607
773
0 #
$g
66-08B.
$t
Dissertation Abstracts International
790
$a
0212
790
1 0
$a
Goel, Ashish,
$e
advisor
791
$a
Ph.D.
792
$a
2005
856
4 0
$u
http://libsw.nuk.edu.tw:81/login?url=http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379
$z
http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379
based on 0 review(s)
ALL
電子館藏
Items
1 records • Pages 1 •
1
Inventory Number
Location Name
Item Class
Material type
Call number
Usage Class
Loan Status
No. of reservations
Opac note
Attachments
000000002574
電子館藏
1圖書
學位論文
一般使用(Normal)
On shelf
0
1 records • Pages 1 •
1
Multimedia
Multimedia file
http://libsw.nuk.edu.tw:81/login?url=http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3186379
Reviews
Add a review
and share your thoughts with other readers
Export
pickup library
Processing
...
Change password
Login