0:16

And what we'll do is we'll start with very simple versions of this where we'll work

Â with [INAUDIBLE] style networks.

Â And then we can talk about other kinds of networks as well, and what we can

Â say about how things like the degree distribution affect diffusion processes.

Â Okay, so we're bringing in the interaction structure now.

Â And the basic idea here is going to be that there's

Â some process going on in the network.

Â And we'll be thinking, one thing that's going to be important is thinking

Â about what's the right network to define.

Â And often in a lot of what we've been looking at,

Â we've just been sort of taking networks and links as a given and

Â not explore too much which particular network we want to be looking at, and

Â exactly what should be defining the nodes and the links.

Â So in this kind of situation, ultimately what's really going to be important is

Â when we think about a relationship or a link between two individuals,

Â we should think of two people being related if one has a chance of

Â passing something to the other in whatever our diffusion process is.

Â So if we're thinking about the flu, then we would think about, okay,

Â I'd be connected to all the individuals who I might infect, and so

Â that might be a very broad range of individuals.

Â 1:39

Whereas, if we're thinking about a political view or

Â some new technology that I might tell somebody about, it might be

Â a much narrower set of individuals who we might have that kind of interaction.

Â So, nodes are going to be linked if one would infect the other.

Â And one substantial simplification we're going to make to begin with is that

Â this is going to be sort of an independent and identical probability across links.

Â So, each person has an equal chance of infecting any one of their neighbors.

Â Whereas, that might not be true in reality where you might spend more time

Â interacting with some individuals than others, and have more of a chance

Â of a diffusion process proceeding across some links than others.

Â So, we'll define the links by

Â the interactions that are necessary for diffusion.

Â 2:35

So, when do we get diffusion?

Â What's the extent of the diffusion?

Â How does it depend on the process and the network structure?

Â Who's likely to be infected earliest?

Â These are the kinds of questions that we can begin to answer now

Â with the network analysis.

Â So, an important part of this is going to be understanding

Â what the component structure is.

Â So the reach of the contagion is going to be determined by the component structure

Â where what we think of is in terms of links,

Â as links being put down probabilistically according to whether or

Â not two individuals would actually transmit from one to another.

Â 3:27

Okay, so just to sort of remind you, this is a picture from Bear,

Â Moody, and Stovel's 2004 data as high school romances.

Â This would be something, if we were thinking about transmission of

Â mononucleosis or something, we could think about a network like this.

Â And what we end up with is the component structure will actually tell us a lot.

Â So if an initially infected individual ends up being in one of these nodes,

Â then if they end up being in the large component,

Â then things can spread quite extensively.

Â If they end up being in the small component,

Â then things can be quite limited.

Â And so, looking at the component structure will help us answer two questions.

Â First of all, what's the probability that we start a contagion?

Â And that's going to be the probability that we end up sort of hitting one of

Â these large components, the large component,

Â in this case the giant component, and then how extensive should it be.

Â And in this case, if we did hit somebody in the giant component,

Â then the reach of it could potentially be the size of the giant component.

Â So understanding what the component structure is will help us understand

Â both the probability of starting and the eventual reach conditional on that.

Â So, we'll think about getting nontrivial diffusion if somebody in

Â the giant component is infected adopts, so I'll use the word infected but

Â it could be adopting a new technology, and so forth.

Â And the size of the giant components can determine both likelihood and its extent.

Â And random network models are going to allow for giant component calculations.

Â And now, in terms of what we want to be thinking about in links now.

Â We could can say, okay, well, a lot of networks we actually look at in the real

Â world might be very well-connected and have links so that everyone can reach

Â everyone else in the world, and so the world is one giant component.

Â But the component structure we actually want to be thinking about are going to

Â have link probabilities that are associated with the likelihood that

Â one individual actually infects another.

Â So it might be that somebody just doesn't catch the flu because they

Â don't have interactions with people at the right times, and so forth.

Â So, the network again we're going to looking at is, our people going to

Â interact within a given time period when they're infected enough to transmit.

Â And that can actually have a much more fragmented network structure

Â than an overall long-term network that we would look at normally.

Â 5:55

Okay, so what we can do is a simple example of such a calculation.

Â And we'll start by working at Erdos-Renyi style random network, and

Â then we'll also talk about other degree distributions.

Â And the main question we're going to be answering is just,

Â what can we say about how big the giant component is in such a network?

Â Okay, so how big is a giant component if there is one?

Â And let's think about, so let's think about GNP as our starting model.

Â And if we think about that in terms of the starting model,

Â then the size of the giant component's going to be interesting.

Â When p is in the range where the giant component isn't, so

Â small that it doesn't exist or so large that we have almost full connection.

Â So the interesting region is going to be when p is somewhere between 1/n and

Â log(n)/n.

Â And otherwise, we're going to have basically isolated small components or

Â a fully-connected network.

Â 6:58

And if we remember from before, when p was smaller than 1,

Â sorry, expected degree is smaller than 1.

Â So that's what's in this range here with 50 nodes, p being .01,

Â each percentage has an expected range of half a neighbor.

Â Then we end up with not many people infecting each other, and so

Â we end up with lots of very tiny components.

Â Actually, only one that even has two links in it and lots of isolates.

Â So this kind of situation, if the interaction structure was so

Â limited we wouldn't see much of a contagion at all.

Â So, .02 is the point at which you have one unexpected neighbor above that,

Â you begin to get a giant component.

Â And here we would end up having about half the nodes,

Â a little more than half in the giant component.

Â And so it would be about half a probability of infecting, and

Â it would infect half of the population.

Â Once you get to about two and a half as an expected set of neighbors,

Â then we get almost the whole network, the whole population connected,

Â so we have a high probability of reaching everybody, and

Â a high number of people infected once one person is.

Â And then once we get here with 50 nodes, once we have an expected degree of 5,

Â we would pass the threshold for connection and we end up having a connected network.

Â And now, if the interaction structure resistance,

Â then you would expect a full contagion.

Â Okay, so what we're going to do is actually go through some calculations next

Â to give us more explicit numbers on some of these things, and

Â calculate the size, the expected size of the giant component

Â rather than just looking at these pictures.

Â So the pictures are based on these thresholds.

Â And indeed, when we go from the threshold below expected degree of one to a high

Â enough expected degree to have everybody connected,

Â we're going to hit the two extremes.

Â And the interesting part's going to be in-between, so

Â let's take a look at that next.

Â