Abcdefghijklmnopqrstuvwxyz BCDEFGHIJKLMNOPQRSTUVWXYZ ...

Abcdefghijklmnopqrstuvwxyz BCDEFGHIJKLMNOPQRSTUVWXYZ ...

Algorithmic and Economic Aspects of Networks Nicole Immorlica Random Graphs What is a random graph?

Erdos-Renyi Random Graphs Specify number of vertices n edge probability p G(n,p) For each pair of vertices i < j,

create edge (i,j) w/prob. p Erdos-Renyi Random Graphs What does random graph G(n,p) look like? (as a function of p)

Random Graph Demo GiantComponent Properties of G(n,p) p < 1/n disconnected, small treelike components

p > 1/n a giant component emerges containing const. frac. of nodes Proof Sketch 1. Percolation 2. Branching processes

3. Growing spanning trees Percolation 1. Infinite graph 2. Distinguished node i 3. Probability p Each link gets ``open with probability p

Q. What is size of component of i? Percolation Demo Percolation

Percolation on Binary Trees V = {0,1}* E = (x,y) s.t. y = x0 or y00=0 x101 10 distinguished node 1 11

Def. Let (p) = Pr[comp() is infinite]. The critical threshold is pc = sup { p | (p) = 0}. Critical Threshold Def. Let (p) = Pr[comp() is infinite]. The critical threshold is pc = sup { p |

(p) = 0}. Thm. Critical threshold of binary trees is pc = . Prf. On board. Critical Threshold (p) 1

0 1/k p Thm. Critical threshold of k-ary trees is pc = 1/k.

Branching Processes Node i has Xi children distributed as B(n,p): Pr[Xi = k] = (n choose k) pk (1-p)(n-k) Q. What is probability species goes extinct? A. By percolation, if p > (1+)/n, live forever. Note extinction Exists i, X1 + + Xi < i.

Erdos-Renyi Random Graphs We will prove (on board) (1) If p = (1-)/n, then there exists c1 s.t. Pr[G(n,p) has comp > c1 log n] goes to zero (2) If p = (1+2)/n, then there exists c2 s.t. Pr[G(n,p) has comp > c2 n] goes to one First show (on board) (3) If p = (1+2)/n, then there exists c2, c3 s.t.

Pr[G(n,p) has comp > c2 n] > c3 Emergence of Giant Component Theorem. Let np = c < 1. For G G(n, p), w.h.p. the size of the largest connected component is O(log n). Theorem. Let np = c > 1. For G G(n,

p), w.h.p. G has a giant connected component of size ( + o(n))n for constant = c; w.h.p, the remaining components have size O(log n). Application Suppose the world is connected by G(n,p)

someone gets sick with a deadly disease all neighbors get infected unless immune a person is immune with probability q Analysis

1. Generate G(n,p) 2. Delete qn nodes uniformly at random 3. Identify component of initially infected individual Analysis Equivalently,

1. Generate G((1-q)n, p) 2. Identify component of initially infected individual Analysis By giant component threshold, p(1-q)n < 1 disease dies p(1-q)n > 1 we die

E.g., if everyone has 50 friends on average, need prob. of immunity = 49/50 to survive! Summary Random graphs G(n, c/n) for c > 1 have unique giant component

small (logarithmic) diameter low clustering coefficient (= p) Bernoulli degree distribution A model that better mimics reality? In real life

Friends come and go over time. Growing Random Graphs On the first day, God created m+1 nodes who were all friends And on the (m+i)th day, He created

a new node (m+i) with m random friends Mean Field Approximation Estimate distribution of random variables by distribution of expectations.

E.g., degree dist. of growing random graph? Degree Distribution Ft(d) = 1 exp[ -(d m)/m ] (on board) This is exponential, but social networks

tend to look more like power-law deg. distributions In real life The rich get richer much faster than the poor.

Preferential Attachment Start: m+1 nodes all connected Time t > m: a new node t with m friends distributed according to degree Pr[link to j] = m x deg(j) / deg(.) = m x deg(j) / (2mt) = deg(j) / (2t)

Degree Distribution Cumulative dist.: Ft(d) = 1 m2/d2 Density function: ft(d) = 2m2/d3 (heuristic analysis on board, for precise analysis, see Bollobas et al) A power-law! Assignment:

Readings: Social and Economic Networks, Chapters 4 & 5 M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics 1, No 2, 226-251, 2005. D.J. Watts, and S.H. Strogatz. Collective dynamics of small-world networks. Nature 393, 440-442, 1998.

Reactions: Reaction paper to one of research papers, or a research paper of your choice Presentation volunteer?

Recently Viewed Presentations

  • MFJ-226 Antenna analyzer

    MFJ-226 Antenna analyzer

    INTRODUCTION. The MFJ-226 is part of the Times Technology Series of analyzers and is a compact single-port Vector Network Analyzer (VNA) that characterizes complex RF loads in 50-Ohm systems with a high degree of accuracy.
  • Ready at 5 Summer Packet

    Ready at 5 Summer Packet

    Draw a cone with 8 scoops. Label the flavor of each scoop. Ask your child to name her favorite flavor. 4 Independence Day! Talk about the colors in the flag and count the stripes. Count the stars too! Have your...
  • The North Richmond Shoreline Community Visioning Results The

    The North Richmond Shoreline Community Visioning Results The

    The North Richmond Shoreline. Community Visioning Results. The Watershed Project. Juliana Gonzalez and Jesse Brown. Hello, I'm Jesse Brown and this is Juliana, we're from the watershed project, and we're going to pick up where we left off from the...
  • Febrile seizure - QUMS

    Febrile seizure - QUMS

    and that occur in the absence of a history of prior afebrile seizures. Febrile Seizures. A simple febrile seizure is a primary generalized, usually tonic-clonic, attack associated with fever, lasting for a maximum of 15 min, and not recurrent within...
  • The 21st Century Challenge of Privacy and Confidentiality for ...

    The 21st Century Challenge of Privacy and Confidentiality for ...

    A statistical database can be reconstructed with a small number of random queries. Previous work showed that query privacy could only be assured: By tracking every query. Even then, it was exponentially hard. Dinur & Nissim proposed a generalized solution...
  • GCSE Philosophy &amp; Ethics

    GCSE Philosophy & Ethics

    Dingbats. Islam - The Shahadah ... In the Bible it states . . . The impact of this belief on Christians might be . . This is important because . . . . This belief might influence the Christian community...
  • A noun or a pronoun. Follows an action

    A noun or a pronoun. Follows an action

    A noun or a pronoun. Follows an action verb. Receives the action of a verb. A direct object can be found by asking Whom? or What? about an action verb.
  • Analogies - Mrs. Miranda&#x27;s Classroom Website

    Analogies - Mrs. Miranda's Classroom Website

    Part to whole - the second word (solider) is part of the first word (platoon) Varying degree - the first word (hot) is the extreme of the second word (scalding) Antonym Object to function - gills are used to breathe...