Unformatted text preview:

IntroductionProximity graphsNetwork distanceIn progressIntroductionProximity graphsNetwork distanceIn progressSpatial random networksDavid AldousOctober 14, 2009David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progress“Sideways” talk – broad range of topics.Theorems exist but are peripheral to the most interesting conceptualissues.These slides and a draft paper write-up “Models for Connected Networksover Random Points and a Route-Length Statistic” (with Julian Shun)are on my web page.Two central points.Models for connected spatial networks have been rather neglected.Two different ways to resolve a certain “paradox”.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressDavid Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressL =1.25¯d =2.5Punctured latticeL =1.32¯d =3L =1.50¯d =3L =1.61¯d =3L =2.00¯d =4Square latticeL =2.71¯d =5L =2.83¯d =4Diagonal latticeL =3.22¯d =6Triangular latticeL =3.41¯d =6Figure 4. Variant square, triangular and hexagonal lattices.Drawn so that the density of cities is the same in each diagram, and ordered byvalue of L.10David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressRelative neighborhood network on 500 cities.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressInstead of vertices and edges let me say cities and roads. The figureshows the relative neighborhood network on 500 random cities. Thisnetwork is defined by: (d denotes Euclidean distance)there is a road between two cities x, y if and only if there is no othercity z with max(d(z, x), d(z, y)) < d(x, y).This particular network is interesting because (loosely speaking) it is thesparsest connected graph that can be defined by a simple local rule. It isconnected because it contains the MST.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressThis relative neighborhood network is part of a family:Proximity graphsWrite v−and v+for the points (−12, 0) and (12, 0). The lune is theintersection of the open discs of radii 1 centered at v−and v+. So v−and v+are not in the lune but are on its boundary. Define a template Ato be a subset of R2such that(i) A is a subset of the lune;(ii) A contains the line segment (v−, v+);(iii) A is invariant under reflection (left - right and top - bottom)(iv) A is open.For arbitrary points x, y in R2, define A(x, y) to be the image of A underthe transformation (translation, rotation and scaling) that takes (v−, v+)to (x, y).David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressDavid Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressDefinition. Given a template A and a locally finite set x of vertices, theassociated proximity graph G has edges defined by: for each x, y ∈ x,(x, y) is an edge of G iff A(x, y) contains no vertex of x.There are two “named” special cases.If A is the lune then G is the relative neighborhood network.If A is the disc centered at the origin with radius 1/2 then G is called theGabriel network.Note that replacing A by a subset A0can only increase the edge-set.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressGabriel network on 500 cities.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressLet’s consider GA, the proximity graph associated with a Poisson pointprocess of rate 1 on R2. To indicate that GAis at least somewhattractable, noteLemmaWrite a = area(A). Then for GAmean edge-length per unit area =π3/24a3/2mean vertex degree =πa.One could continue along the lines of the Lemma to write downcomplicated integral expressions for (e.g.) the mean number of trianglesper unit area in GA. In contrast to random geometric graphs [see Penrosemonograph] there seems only one known non-elementary result about GA– the model deserves more study.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressThe aspect of spatial networks that interests me is network distance(minimum route-length) `(ξ, ξ0) between cities at Euclidean distanced(ξ, ξ0). For any translation- and rotation-invariant spatial network wecan defineρ(d) =E(network distance between cities at distance d)d− 1.Suppose we want to design a network where having short networkdistances is a major goal. Obviously there’s a tradeoff between this andthe (normalized) network length L.Here are (simulation) results.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progress1 2 3Normalized distance d4 50.10.2ρ(d)0.30.4qqqqqqqqqqqqqqqqqq qqqqq qqGabrielaaaaaaaaaaaaaaaaaaaaaaaaaRelative n’hoodaaaaaaaaaaaaaaaaaaaaaaaaaDelaunayDavid Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressThis Figure is the central theme of the talk . . . . . .The same characteristic shape appears in all “reasonable” theoreticalnetworks we have studied.Here’s some real data: the road network linking the 20 largest cities in aState.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progress00.10.20.30.40.50.60.70.80.90 1 2 3 4 5r(i,!j)Normalized!Distance!d(i,j)CaliforniaR*Weighted!R*00.050.10.150.20.250.30.350.40 1 2 3 4 5 6r(i,j)Normalized!Distance!d(i,j)TexasR*Weighted!R*David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressNatural to conjecture that for any reasonable connected network on aPoisson point process, the limit limd→∞ρ(d) exists and is finite. But thisrequires some further conditions, because for the MST (minimumspanning tree) the limit is infinite.We consider connected networks whose edges are defined by atranslation-invariant deterministic rule (applied to Poisson points); therule need not be local and need not be rotation-invariant.For technical reasons we replace ρ(d) by the more tractable “integratedout” form. Write U for unit square centered at origin, for z ∈ R2writez + U for unit square centered at z; set˜ρ(z) = EXξ∈UXξ0∈z+U`(ξ, ξ0)where the ξ are the Poisson points and `(·) is network distance. Note˜ρ(z) not normalized.David Aldous Spatial random networksIntroductionProximity graphsNetwork distanceIn progressWhen do we have a linear upper bound˜ρ(z) = O(|z|) as |z| → ∞. (1)It turns out that


View Full Document

Berkeley STAT 157 - Spatial random networks

Download Spatial random networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Spatial random networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Spatial random networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?