Penn CIS 112 - Universal Network Structure and Generative Models

Unformatted text preview:

Universal Network Structure and Generative ModelsA Little Warm-Up…“Natural” Networks and UniversalitySome Interesting QuantitiesA “Canonical” Natural Network has…Some Models of Network FormationApproximate RoadmapProbabilistic Models of NetworksThe Erdos-Renyi ModelThe Erdos-Renyi (E-R) Model (Random Networks)Another Version of Erdos-RenyiThe Evolution of a Random NetworkMonotone Network PropertiesFormalizing Tipping for Monotone PropertiesSo… Which Properties Tip?More Precise…Erdos-Renyi SummaryThe Clustering Coefficient of a NetworkErdos-Renyi: Clustering Coefficient“Caveman and Solaria”Making it More Precise: the a-modelSlide 28Small Worlds and Occam’s RazorAn Alternative ModelMeanwhile, Back in the “Real” World…Slide 33Case 1: Kevin Bacon GraphCase 2: Western States Power GridCase 3: C. Elegans Nervous SystemTwo More ExamplesUniversal Network Structureand Generative ModelsNetworked LifeCIS 112Spring 2010Prof. Michael KearnsA Little Warm-Up…•Consider yourself “connected” to anyone in class whose first name you know (assume symmetric)•On the resulting network, let’s examine:•The degree distribution•The number and size of connected components•The diameter•The “clustering coefficient”“Natural” Networks and Universality•Consider the many kinds of networks we have examined:–social, technological, business, economic, content,…•These networks tend to share certain informal properties:–large scale; continual growth–distributed, organic growth: vertices “decide” who to link to–interaction (largely) restricted to links–mixture of local and long-distance connections–abstract notions of distance: geographical, content, social,…•Do natural networks share more quantitative universals?•What would these “universals” be?•How can we make them precise and measure them?•How can we explain their universality?•This is the domain of network scienceSome Interesting Quantities •Connected components:–how many, and how large?•Network diameter:–the small-world phenomenon•Clustering:–to what extent do links tend to cluster “locally”?–what is the balance between local and long-distance connections?–what roles do the two types of links play?•Degree distribution:–what is the typical degree in the network?–what is the overall distribution?•Etc. etc. etc.A “Canonical” Natural Network has…•Few connected components:–often only 1 or a small number (compared to network size)•Small diameter:–often a constant independent of network size (like 6…)–or perhaps growing only very slowly with network size–typically look at average; exclude infinite distances•A high degree of edge clustering:–considerably more so than for a random network–in tension with small diameter•A heavy-tailed degree distribution:–a small but reliable number of high-degree vertices–quantifies Gladwell’s connectors–often of power law formSome Models of Network Formation•Random graphs (Erdos-Renyi model):–gives few components and small diameter–does not give high clustering or heavy-tailed degree distributions–is the mathematically most well-studied and understood model•Watts-Strogatz and related models:–give few components, small diameter and high clustering–does not give heavy-tailed degree distributions•Preferential attachment:–gives few components, small diameter and heavy-tailed distribution–does not give high clustering•Hierarchical networks:–few components, small diameter, high clustering, heavy-tailed•Affiliation networks:–models group-actor formation•Nothing “magic” about any of the measures or modelsApproximate Roadmap•Examine a series of models of network formation –macroscopic properties they do and do not entail–tipping behavior during network formation–pros and cons of each model•Examine some “real life” case studies•Study some dynamics issues (e.g. seach/navigation)•Move on to an in-depth study of the web as networkProbabilistic Models of Networks•Network formation models we will study are probabilistic or statistical –later in the course: economic formation models•They can generate networks of any size–we will typically ask what happens when N is very large or N  infinity•They often have various parameters that can be set/chosen:–size of network generated–probability of an edge being present or absent–fraction of long-distance vs. local connections–etc. etc. etc.•The models each generate a distribution over networks•Statements are always statistical in nature:–with high probability, diameter is small–on average, degree distribution has heavy tailThe Erdos-Renyi ModelThe Erdos-Renyi (E-R) Model(Random Networks)•A model in which all edges: –are equally probable and appear independently•Two parameters: NW size N > 1 and edge probability p: –each edge (u,v) appears with probability p, is absent with probability 1-p–N(N-1)/2 independent trials of a biased coin flip–results in a probability distribution over networks of size N–especially easy to generate networks from this distribution•About the simplest (dumbest?) imaginable formation model•The usual regime of interest is when p ~ 1/N, N is large–e.g. p = 1/2N, p = 1/N, p = 2/N, p=150/N, p = log(N)/N, etc.–in expectation, each vertex will have a “small” number of neighbors (~ pN)•Gladwell’s “Magic Number 150” and cognitive bounds on degree•mathematical interest: just near the boundary of connectivity–will then examine what happens when N  infinity–can thus study properties of large networks with bounded degree•Degree distribution of a typical E-R network G:–draw G according to E-R with N, p; look at a random vertex u in G–what is Pr[deg(u) = k] for any fixed k? (or histogram of degrees)–Poisson distribution with mean  = p(N-1) ~ pN–Sharply concentrated; not heavy-tailedAnother Version of Erdos-Renyi•In Erdos-Renyi:–expected number of edges in the network = pN(N-1)/2 = m–actual number of edges will be ”extremely close” to m –so suppose we instead of fixing p, we fix the number of edges m•Incremental Erdos-Renyi model: –start with N vertices and no edges–at each time step, add a new edge, up to m edges total–choose new edge randomly from among all missing edges•Allows study of the evolution or emergence of properties:–as the number of edges m grows (in relation to


View Full Document

Penn CIS 112 - Universal Network Structure and Generative Models

Documents in this Course
Load more
Download Universal Network Structure and Generative 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 Universal Network Structure and Generative 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 Universal Network Structure and Generative 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?