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