Structure and dynamics of complex networks Flashcards
Giant component
How can we studythe existence of giant components? What are the main assumptions?
With the generating function formalism.
Main assumptions:
- We know the degree distribution p(k).
- No degree correlation.
- We approach the critial point of the percolation transition from below.
Below means from the dispersed phase where the network is sparse and can be assumed to be localy tree-like.
Giant component
What are the discrete distributions needed for this study?
- p(k): degree distribution
- I(k) = P(a rand. chosen node is in a component of size k)
- H(k) = P(a rand. chosen link has a components size k at one end)
- H(m)(k) = P(sum of comp.s at one end of m rand. chosen links adds up to k)
Giant component
How can we calculate G(H)(1)?
- Introducing q(k) = P(we can proceed to k further links at one end of a rand. chosen link)
- In terms of an equation: H(k) = ∑(m=0,∞) q(m)H(m)(k − 1)
- Taking the generating function of both sides: G(H)(x) = xG(q)(G(H)(x)) —» G’(H)(1) = 1/(1 – G’(q)(1))
- Substituting back: S = 1 + ⟨k⟩G′(H)(1) = 1 + ⟨k⟩/[1 − G′(q)(1)]
The critical point is where G’(q)(1) = 1
Giant component
How can we calculate G(q)(x) and G’(g)(1)?
It can be expressed based on the degree distribution: q(k) = P( we have a node with degree k + 1 at one end of a rand.
chosen link)
- q(k) = (k + 1)/⟨k⟩ p(k + 1) —» G(q)(x) = G′(x)/⟨k⟩
G’(g)(1) is closely related to the expected value of the number of second neighbours
- n2(k) = P(the number of 2nd neighbours of a rand. chosen node is k)
- z2 = ⟨n2⟩ —» G′(q)(1) = z2/⟨k⟩ = z2/z1
Giant component
How can we determine the critical point of percolation?
The expected value of the components size: ⟨S⟩ = 1 + z1²/(z1 – z2)
- z1 > z2: small, isolated clusters
- z1 = z2: critial point
- z1 < z2: giant components
This is quite intuitive but it came from all the analytical calculations.
Giant component
What is the percolation like in an E-R model?
he degree distribution can be approximated by a Poisson distribution: G(x) = exp[⟨k⟩(x−1)] —» G(q)(x) = G(x).
- the critical point: G′(q)(1) = G′(1) = ⟨k⟩ = 1
Giant components
What does being scale-free mean for the existence of giant components?
It guarantees it, so scale-free networks will always contain a giant component.
- z2 = z1G′(q)(1) = ⟨k²⟩ − ⟨k⟩, where ⟨k²⟩ diverges for scale-free networks
Percolation and robustness
What is the physics analogy for the emergence of a giant component in the E-R model? Why is this important?
The emergence of a giant component at ⟨k⟩ = 1 is like a phase transition.
- order parameter: relative size S (S = 0: “disordered phase”, S ≠ 0: “ordered phase”)
- control parameter: ⟨k⟩ (by changing this, we can transition from one phase into another)
Phase transitions have several universal features, and we can discuss them in a more or less uniform framework.
Percolation and robustness
What’s the basis of the percolation model?
We are modeling the structure of a porous material with a lattice and each point can be occupied by a cavity with probability p. Adjacent cavities are assumed to be connected to each other.
- cavities are placed at random
Two phases:
* for large p: small cavities make up a large connected cavity (cluster), going from one side of the lattice to the other —» possible to percolate liquid through the material
* for small p: smaller, isolated cavities
* transition from one to the other: percolation transition
Percolation models are theoretical models for the large scale structures made up by small cavities in porous materials.
Percolation and robustness
What is percolation transition characterized by?
A spanning cluster emerges at p(c) and the control parameter is p, order parameter is the relative size of the largest connected cluster.
Analogy between peroclation and emergence of a giant component in the E-R graph:
- phase I.: no giant cluster ↔ no giant component
- phase II.: giant cluster ↔ giant component
- control param.: p, site occup. prob. ↔ ⟨k⟩, average degree
- order param.: rel. size of giant cluster ↔ rel. size of giant comp
The transition of an E-R network is referred to as the percolation transition of the E-R graph.
Percolation and robustness
What does susceptibility characterize?
Near the transition point the system can show extreme large sensitivity to outside perturbations that drive the system towards the other phase. Susceptibility measures the sensitivity os the system.
- single flip of a spin in a magnet can cause the build up of macroscopig magnetism «—» insertion of a single link can cause the emergence of a giant component
- susceptibility is defined different for each network
- strong, sharp peak at the transition point (when plotted against the control parameter), can be divergent
- useful when empirically determining the transition point
Percolation and robustness
How is susceptibility defined for the E-R model?
We pick two nodes from different components and connect them with an extra link. The susceptibility is the expected change in the component size for the initially separated components that are connected with the extra link.
- second moment of the component size distribution: χ = ∑(s≠s(max))s²p(s) = ⟨s²⟩
- the giant component should be left out of the formula for χ (otherwise we’d get extreme values for χ after the transition point)
Percolation and robustness
What does robustness entail in networks?
Parts of the network are “down” but the system as a whole still functions. Robustness is imagined as a random node removal process, imitating the breakdown of malfunctioning nodes, so we can define it as the resilience against random node removal.
- as long as a giant component exists, the network is considered still functional
- nodes are removed uniformly at random
- at critical f(c) the giant component is destroyed
- small f(c): fragile network, large f(c): robust network
- “inverse percolation transition”
f(c): the # of removed nodes
Functioning network: the existence of the giant component ensures that most of the nodes can reach each other.
Percolation and robustness
What is the condition for the existence of a giant component?
⟨k²⟩/⟨k⟩ ≥ 2
- f(c) = 1/(⟨k²⟩/⟨k⟩ – 1)
- since ⟨k²⟩ is diverging in scale-free networks, this condition is automatically fulfilled: f(c) —» 1 (extreme robustness)
In scale-free networks, we’d basically need to remove all nodes to destroy the giant components. Having an inhomogenous degree distribution provides an extremely robust netrwork.
Percolation and robustness
What’s the “price” of extreme robustness in scale-free networks?
They are fragile against targeted attacks, since taking out the HUBS is producing a lot of damage.
- how to attack a scale-free network: removing nodes in order of node degree
Spreading
What are the basic assumptions of epidemic models?
There are a few assumed dicrete states that are possible:
- susceptible (healthy) – S
- infected (sick) – I
- removed (immune/dead) – R
The transitions bewteen them:
- S —» I: infection
- I —» S, R —» S: recovery
- I —» R: removal
R —» S recovery is possible if immunity disappears and the subject becomes susceptible.
Spreading
What are assumptions of the homogenous SIS model?
- Homogenous mixing hypothesis: homogenous network every node has more or less ⟨k⟩ degrees, same probability to get linked with an infected one for every node
- λ: spreading rate —» probability of transaction per unit time
- μ: probability of recovery per unit time
- At t = 0: ρ(t = 0) = ρ0 «_space;1 fraction of infected nodes
Diff. equation for the time evolution of ρ(t): logistic equation
dρ/dt = λ⟨k⟩ρ (1 – ρ) – μρ
- ⟨k⟩ρ: probability that a randomly chosen node is linked to an infected one
- λ⟨k⟩ρ: probability of infection tranferring
- μρ: recovery term (negative because it lowers ρ)
- 1 – ρ: probability of not being infected
SIS: the R state is absent
Spreading
What the solution to the diff.eq. for the homogenous SIS model?
ρ(t) ~ exp[(λ⟨k⟩ – μ)t]
- epidemic threshold: λ(c) = μ/⟨k⟩
- λ⟨k⟩ > μ: exponential increase —» λ > λ(c): outbreak
- λ⟨k⟩ < μ: exponential decrease —» λ < λ(c): decay
If μ = 1: λ(c) = 1/⟨k⟩ —» becomes intuitive in discrete dynamics
- the threshold is set by the average degree
- an infected node recovers in one time step
- λ⟨k⟩ < 1: infection dies out quickly
- λ⟨k⟩ > 1: infection spreads exponentially
Spreading
What are the assumptions for the inhomogenous SIS model?
The network is inhomogenous, i.e. scale-free, so the hubs and ordinary nodes need to be treated separately.
- defining degree classes: ρ(k), fraction of infected nodes w/ degree k —» ρ = Σ(k) ρ(k)p(k)
- Γ: probability of a link pointing to an infected node, depends only on ρ
The diff. equation for the time evolution of ρ(k):
dρ(k)/dt = λkΓ [1 – ρ(k)] – μρ(k)
Spreading
What the solution to the diff.eq. for the inhomogenous SIS model?
We assume we reach a stationary phase: dρ(k)/dt = 0 —» ρ(k) = λkΓ/(μ + λkΓ)
- excess degree distribution: P(k) = kp(k)/⟨k⟩ —» Γ = Σ(k) ρ(k)P(k)
- self consistent equation for Γ modyfying P(k): Γ = (1/⟨k⟩) Σ(k) (k – 1)p(k) [λkΓ/(μ + λkΓ)]
The condition for a non-trivial (Γ ≠ 0) solution:
d/dΓ{(1/⟨k⟩) Σ(k) (k – 1)p(k) [λkΓ/(μ + λkΓ)]} ≥ 1 —» (⟨k²⟩ – ⟨k⟩)/⟨k⟩ λ/μ ≥ 1
- epidemic threshold: λ/μ ≥ ⟨k⟩/(⟨k²⟩ – ⟨k⟩)
- for μ in networks with diverging ⟨k²⟩: λ(c) = 0
Scale-free networks with γ>3 have an epidemic threshold of zero!
- no matter how small the initial fraction of infection is, most nodes will get infected eventually
Spreading
How can we treat the SIS model in a matrix approach?
Collecting the nodes into a vector: r(i) = 1 if infected, 0 if not. IDE ÍRNI
Spreading
What are the assumption of the SIR model?
S and R are the fractions of nodes in states S and R and we have diff.equations for S, ρ and R as well, similar to the SIS model.
- the number of susceptible nodes decreases exponentially, so after a point ther will be barely any nodes to infect
- the infection rate rises and then start decreasing after a peak
- the recovery rate increases expoentially as well
Quantitatively the threshold will be the same for homogenous and inhomogenous systems as for the SIS model.
Here we have an R state as well.
