08 Social Relations in Time and Space

Question 1

Describe the function of the parameters q1 and q2 and α in the Kleinberg model!

Answer 1

• Each node i: connected to all nodes with r(i, j) <= q1 (regular local contacts)
• Each node i: Additional q2 other “long range” edges (random other contacts)
• Probability of edge to node j is dependent on α

Question 2

Define “local knowledge“ in the context of a “greedy network routing algorithm with only
local knowledge“ (e.g. in connection with the Kleinberg model)

Answer 2

• Each node only knows:
• adjacent nodes
• grids principle structure
• position of target node on the grid
• positions and long-range contacts of nodes on the message path so far

Question 3

In a two-dimensional Kleinberg model, the following statements concerning the expected
number of delivery steps are true: “PIC”

For which value of α is efficient delivery possible?
Give a semi-formal explanation for this behavior! (1-2 sentences)

Answer 3

• For α = 2 is efficient delivery possible
• If grid has dimension D, α = D is necessary for efficient delivery

Question 4

dentify and shortly explain a conceptual similarity between the Kleinberg Model with
greedy routing with only local knowledge and the decentralized routing in the Chord
Peer-to-Peer protocol!

Answer 4

• In both concepts the nodes only know their direct neighbors and some random
  other nodes
• Another similarity is that in both concepts the nodes know the general structure of
  the graph (grid vs. ring)

Question 5

For a 2-dimensional Kleinberg model, α=2 is required for efficient delivery with greedy
routing with only local knowledge. Liben-Nowell‘s finding from 2005 investigating greedy
routing with only local knowledge on a real social network found that α ≈ 1 and efficient
delivery is nevertheless possible. What is a possible explanation? (1 short sentence)

Answer 5

• Geographic density of people is not uniform (e.g. urban vs. mid-west) as
  assumed in the Kleinberg grid