07 Complex Networks Properties and Models

Question 1

Informally define the term “Small World Effect“! (1 sentence)

Answer 1

Describes the phenomenon that every person is connected to every other person
in the world by a surprisingly short path (avg. 6 degrees of separation)

Question 2

What is the disadvantage of the expression
for the average path length in a network? (1 sentence)
Suggest an alternative expression avoiding this disadvantage!

Answer 2

• The expression doesn’t allow disconnected components (distance would be
  infinite)
• Harmonic mean:

Question 3

State the expression for the fraction of nodes with degree k (==the probability of a node
having degree k) in case of a power law degree distribution!

Answer 3

Question 4

If a power law distribution has an exponent of (-α): What is the exponent of the
corresponding cumulative distribution?

Answer 4

• -( α-1)

Question 5

Sketch a power law distribution in a log-log coordinate system!

Answer 5

linear graph!

Question 6

Give a precise expression for the degree distribution p_k in a Poisson Random Graph
model G_n,p! Qualitatively sketch p_k for n->∞, keeping the mean degree z
fixed! (Hint: the Poisson approximation for p_k is:

Answer 6

k = n, lambda = z
instead of putting numbers on the axis, put z in the middle of the n-axis and
sketch a random distribution

Question 7

Watts-Strogatz model: informally describe the model for D=1!

Answer 7

• A regular ring lattice that with periodic boundary cond.
• Each node is connected to neighbors at a maximum distance
• Some edges get rewired with a certain probability

Question 8

Watts-Strogatz model: Interpret / explain the following diagram in view of the
rewiring parameter p! (1-2 sentences)

Answer 8

• p works as a transition between regular lattice and something like a random
  graph
• with a small p (roughly < 0.1), the clustering coefficient is “ok” and there is no
  small world effect, with a greater p (roughly > 0.1) the graph becomes more
  similar to a random graph, has a better clustering coefficient and the small world
  effect gets more visible

Question 9

Watts Strogatz model, variant (2) (only additional shortcuts): degree distribution:
Why is p_j = 0 for j < 2k?
What is the meaning of the expression 2kp/L?

Answer 9

• For j < 2k the binomial part becomes 0
• 2kp = added random shortcuts
• L = number of nodes
• -> 2kp/L = added random shortcut per nod

Question 10

Model of Price: Informally motivate the terms on the right side of the recursion equation
for the net change of npk per added vertex:

Answer 10

• Mean number of nodes with in-degree k decreases because their in-degree
  changes to k+1
• Mean number of nodes with in-degree k also increases because of nodes having
  previously k-1 and now have k

Question 11

Network resilience: what is the difference in effect between randomly removing nodes
with (a) constant probability q or (b) removing the highest degree nodes? (Explain
informally in 1-2 sentences!

Answer 11

• Only a small fraction of the high degree nodes needs to be removed to destroy
  the giant component. Randomly removing nodes with constant probability is
  irrelevant for huge graphs and has no real effect on mean distances

Question 12

Models of Epidemiology: quantities: susceptibles s, infectives i, recovered r, infection
rate β, recovery rate γ: Explain the pragmatics of / interpret the following set of
differential equations:

Answer 12

• First equation: The rate at which the susceptibles s fall. Every dt there is an equal
  chance βi for every s to get infected. Every s who got infected loses the s status,
  therefore – βis
• Second equation: The rate at which the infectives i change. Every dt, the
  infectives increase by the amount of susceptibles infected (βis) but it also
  decreases by the amount of infectives that recovered (-γi)
• Third equation: The rate at which the recovered r increase. Every dt there is an
  equal chance γi for every infected to recover. Every i who recovered becomes a r.