Diffusion on Random Networks¶
Idea, disease, computer virus spreads via connections in the network
Nodes are linked if one would "infect" the other
- 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.
- 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.
Will an infection take hold?
How many nodes/people will it reach?
Questions¶
When do we get diffusion?
What is the extent of diffusion?
How does it depend on the particulars of the process as well as the network?
Who is likely to be infected earliest?
Component Structure¶
Reach of contagion is determined by the component structure
Some players or nodes are immune, some links fail to transmit...
What do components look like of those who are susceptible and given links that work
So understanding what the component structure is will help us understand both the probability of starting and the eventual reach conditional on that
Extend of Diffusion¶
Get nontrivial diffusion if someone in the giant component is infected/adopts
Size of the giant component determines likelihood of diffusion and its extent
Random network models allow for giant component calculations
what we can do
Simple example of such a calculation
Work with Erdos-Renyi random network
How big is the giant component??
Size of the Giant Component¶
How big is the giant component when there is one?
Size of the giant component when $1/n < p < log(n)/n$
[know that if p << 1/n all isolated, and if log(n)/n << p then all path connected]
