Unformatted text preview:

5.10 Network models5.10.1 Overview of network modelsA noticeable proportion of all probability modeling involves some background“graphical” or “network” structure, so let me give a brief overview of suchbackground models. Conceptually, there are two extremes. One is lattice orgeometric networks, in which vertices have positions in some space (we’ll alwaystake 2-dimensional space, though the models make sense in any dimension andoften even for abstract “metric spaces”), and where edges link vertices to nearbyvertices. The simplest example is the 2-dimensional lattice.! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !! ! ! ! ! ! ! ! ! ! ! ! ! !I drew a 14× 14 grid, but I want you to imagine a much larger M ×M grid, andthen imagine what you see in a small “window” centered on a typical vertex.Well, obviously what you see is" " " " " " "" " " " " " "" " " " " " "" " " " " " "" " " " " " "" " " " " " "" " " " " " "#(The purpose of this visualization exercise will become clear later). Of coursethere are many variations of such “geometric” structures; one could link to the90nearest 8 vertices instead of the nearest 4, or use a triangular or hexagonal grid,or use random points (a Poisson point process – xxx cross-ref) in the plane; onecould link only to some randomly-chosen nearby vertices, and so on.The other extreme in modeling is to ignore geometry – so each vertex hasa label but no intrinsic “position” – and then assume edges are random (insome particular sense, which determines the particular model). Call these non-geometric networks. Here is a typical hypothetical example, with n = 50 verticesand average degree (degree = number of edges at a vertex)¯d = 5.(xxx figure copied from [26] page 94 – should ask permission!).Note that the way any non-geometric network is drawn on paper is mostlyarbitrary, but driven by some algorithm seeking to minimize number of crossingedges or some other aesthetic convention.When the number n of vertices becomes larger – say 500 instead of 50 –it becomes hard to draw or mentally visualize the whole network. However,provided the average degree¯d remains small, then it turns out that the simplestnon-geometric models look “locally tree-like”. That is, as illustrated below,what we see in a small window around a typical vertex is a tree (graph withoutcycles).91xxx find better picture here!Let me emphasize that this locally tree-like behavior is usually an unrealisticfeature of real-world models. On the other hand this behavior makes themthe easiest models to analyze mathematically. In brief, many processes builtover a foundation of non-geometric random networks can be analyzed like theGalton-Watson branching processes described in section 5.6, and I give someexamples in section 5.10.4. More realistic models would involve both geometricand non-geometric aspects, and this topic has attracted substantial interest inthe theoretical research community (xxx describe realistic flu epidemic modelsomewhere).925.10.2 Overview of questions involving social networksxxx what question can one ask? A good textbook treatment is [26].xxx ideas, opinions, rumorsxxx infectious diseases (epidemics)xxx adopting new products, watching a weekly TV show or new movie5.10.3 Random networks with prescribed degree distribu-tionsAny given network has a degree distributionp∗i= proportion of vertices with degree iwhich we may regard as a descriptive statistic of the network. There is a classof models called random graphs with prescribed degree distributions in whicha distribution p∗=(p∗i) is a parameter and for each n we define a randomnetwork on n vertices whose degree distribution is approximately the given p∗:the conceptual idea is that (subject to this requirement) the network should be“as random as possible”. There are different ways one can define precise models– that’s why I wrote “class of models” – but the interesting aspects of theirbehavior as n →∞don’t depend on those details. One precise model isThe configuration model. Choose integers niwith ni≈ np∗iand!ini= nand!iinieven. For each i, create nivertices, each with i half-edges attached.There are now!iinihalf-edges; now form edges by inductively picking uni-formly two different unused half-edges and joining them to form an edge.For small n this is easy to simulate with playing cards, though for small n onesees features (multiple edges and self-loops) which are not seen in the “typicalwindow for large n” described below. For large n the whole graph looks verycomplex, as in Figure xxx above. But a key insight is that the “typical windowfor large n” has a particular structure, which I now describe.Take n very large. Recall p∗is the model parameter; write µ∗for the mean ofp∗. Pick a random vertex J – it has a random number of edges, with distributionp∗. Pick one of the neighboring vertices J". Because of the random way thatedges are attached, the chance that J"is a particular vertex v is proportionalto the degree of v – and so we can use our earlier “formula for size-biaseddistribution” to see that the distribution of the degree of J"is ˜pi= ip∗i/µ∗. Ofcourse one of the edges as J"goes back to J; it is more convenient to work withthe number of other edges at J", and this has distribution p =(pi) wherepi=(i + 1)p∗i+1/µ∗. (5.6)The same argument applies t a typical neighbor J""%= J of J", and leads to93The local GWBP approximation. For large n, the structure of a randomgraph with prescribed degree distribution p∗, in the neighborhood of a typicalvertex J, is like a Galton-Watson branching process in which the first generationoffspring distribution is p∗but subsequent generation offspring distributions arethe p defined by (5.6).This approximation enable us to do a variety of calculations, exemplifiedby the following. It is stated in abstract language, but in the next section were-intrepret it as a toy model involving social networks.A math calculation. Fix 0 < θ < 1. For each edge of a random graph withprescribed degree distribution p∗, independently retain the edge with chance θor delete it with chance 1 − θ. In


View Full Document

Berkeley STAT 157 - Network models

Download Network models
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 Network models 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 Network models 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?