03 SNA Centrality

Question 1

Directed graph with edge semantics (a) ,,a votes for b” or (b) ,,a has convinced b”: What type of degree based centrality measure can be applied in case (a), what type in case (b)? (just note the two, no explanation required)

Answer 1

• (a) In-Degree
• (b) Out-Degree

Question 2

Give the mathematical definition for closeness centrality and motivate it in one sentence referring to the Minisum problem!

Answer 2

• Minisum Problem: We want to find nodes whose sum of distances to other nodes is minimal
• A possible resulting centrality index is the closeness centrality, as it shows which nodes have the minimal sum of distances (nodes with highest closeness centrality index)

Question 3

Give a mathematical definition for general Vitality! What is the basic intuition behind the vitality type of centrality indices? (1 sentence)

Answer 3

• Vitality v(x) of graph element x: v(x) = q(G) - q(G{x}).
• Measure importance of vertex (or edge) by the difference of a given quality measure q on G with or without the vertex (edge).

Question 4

Give a reason to use flow-based centrality measures instead of shortest-paths-based centralities!

Answer 4

• Resources (information, goods, work, rumors, …) do not flow along shortest paths only

Question 5

Newmans´s Randwom Walk Betweenness Centrality: We know that the transition matrix with
column t removed is defined as .
What is the probability that (starting at node s) we arrive after r steps in node j and then
transition to node i immediately afterwards?

Answer 5

Question 6

Derive an expression for the total number of times V we hit the graph´s nodes when doing a random walk starting at s and ending at t!
a random walk starting at s and ending at t!

Answer 6

Question 7

Prove that for a random surfer model with adjacency matrix A and Markov
transition matrix (pic) , is the stationary distribution!

Answer 7

Node is more central, the more central its neighbors are

Question 8

Explain the expression (pic) for eccentricity-based centrality

Answer 8

• e(u) is the max amount of distance the node u has to any other node v in the
  graph
• Center of graph are set of all nodes with minimum eccentricity and high
  centrality.
• Higher maximum distance means smaller centrality of node u