Summary so far

  • Networks are prevalent and important in many interactions(labor markets, crime, garment industry, risk sharing...)

  • Although complex, social networks have identifiable characteristics:

    • "small" average and maximum path length
    • high clustering relative to Poission networks
    • degree distributions that exhibit different shapes
    • homophily - strong tendency to associate with own type
    • assortativity, strength of weak ties,...
    • a variety of centrality/influence/prestige measures...

  • Room for studies of methods...

Outline

  • Part 1: Background and Fundamentals

    • Definitions and Characteristics of Networks(1,2)
    • Empirical Background(3)

  • Part 2: Network Formation

    • Random Network Models (4,5)
    • Strategic Network Models (6,11)

  • Part 3: Networks and Behavior

    • Diffusion and Learning (7,8)
    • Games on Networks (9)

Questions

  • Which networks form?

    • random graph models - "How"
    • Economic / game theoretic models - "Why"

  • How does it depend on context?

Static Random Networks

  • Useful Benchmark
    • component structure
    • diameter
    • degree distribution
    • clustering...

So, in terms of the static random network models. why do we want to start with those? for two reasons. One is that they'll going to be a very useful benchmark. And again I've sort of emphasized this a little bit before but I wanted to repeat it. by, by looking at what would happen if things were just happening purely at random then we can look at what we do observe and differentiate that from what happens at random. or get some understanding of what, why it has similar features to what happens at random. So these benchmarks will tell us, you know, what component structures do we expect to see at random? What kind of diameters do we see at random? What kind of degree distributions do we see at random? What kind of clustering might we see at random? And so the, comparing things back to those uniform at random models will allow us to, to do some comparisons.

  • Tools and methods
    • properties and thresholds

E-R, Poission Random Networks: G(n,p)

  • independent probability $p$ of each link
  • probability that node has $d$ links is binomial (degree distribution) $$\frac{ (n-1)!}{d!(n-d-1)!}p^d(1-p)^{n-d-1}$$
  • Large $n$, small $p$, this is approximately a Poission distribution: $$\frac{(n-1)^d}{d!} p^d e^{-(n-1)p}$$

Properties of Network

  • Every network has some probability of forming
  • How to make sense of that?
  • Examine what happens for "large" networks

Specifying Properties

  • $G(N) = $ all the undirected networks on the set of nodes $N$
  • A property is $A(N)$ for each $N$ such that $A(N)$ is a subset of $G(N)$
    • a specification of which networks have that property

Examples of Properties

  • $A(N)$ = {$g|N_i(g)$ nonempty for all i in N }

    • $N_i(g)$: neighborhood of every node
    • property of no isolated nodes, every node has a nonempty neighborhood

  • $A(N)$ = {$g | I(i, j)$ finite for all i, j in N}

    • network is connected

  • $A(N)$ = {$g | I(i, j) < log(n) $ for all i, j in N}

    • diameter is less than log(n)

Monotone Properties

  • A property $A(N)$ is monotone if $g$ in $A(N)$ and $g$ subset $g'$ in $A(N)$

    an important class of properties are what is known as monotone properties. And so what is a monotone property? A monotone property is one such that if some network satisfies that property and we add extra links. So, we just increase the links in a network so that $g$ is a subset of the links in $g′$, then $g′$ also satisfies the property. So it just means adding extra things satisfies, keeps us satisfying a property.

  • All three of the previous properties are monotone

So it just means adding extra things satisfies, keeps us satisfying a property. you can go back and check every one of the properties we just talked about is a monotone property. Now something that wouldn't be a monotone property would be something like saying that there's an even number of links, so if I add an extra link, now it turns odd, it's no longer satisfying the property. So there could be somethings such aren't going to be monotone. But a lot of the properties you might be interested in so You know, it being connected. Well if I had more links it's still connected. so, you know, not having isolated nodes if I add more links it doesn't have isolated nodes. So that, that's a monotone property. That the path length is shorter than a certain amount. If I add extra lengths it still has a shorter path length. So these are nice properties that will be easier to work with. they don't sort of blink on and off, as we change the, the blink pattern.

Limiting Properties

  • In order to deduce things about random networks, we often look at "large" networks, by examining limits

  • Examing a sequence of Erdos-Renyi Poission random networks, with probability $p(n)$

    so what we'll be interested in then is limiting properties. So one way to keep track of these things is then to talk about large $n$, and then, so we can, for instance look at a sequence of Erdos-Renyi Poisson, or G(n, p) random graphs, and then have some probability, and then talk about what happens as a function of the size of the graph. So this is one way of representing properties, and now we can take a look at some of those properties, and understand what might be true or not true, of those. one of the really nice things about the Erdos-Renyi setting and the G(n, p) graphs, and part of the reason I think their work was so well known is that there are very sharp thresholds for which properties do or don't, are, aren't satisfied. So if we talk about how much does the average degree have to be, the average degree, if it's above some level, then a property will be sure, almost surely true as, as you get to large n, and if the degree is smaller than a certain level, it might not be true. And so the idea here is that, that we'll have nice thresholds which will sharply distinguish, when are properties true and when are properties not true, so we'll take a look at that next.