Sunday, January 3, 2010

The same closeness, very different degrees!

At the moment, we are analyzing how innovations spread in social groups. For this task, we needed a graph family where two nodes have the same closeness centrality, but different degree centralities. We will use this graph family to understand whether the observed effect rather correlates with the degree or the closeness of a node. Since it might be of intereste for other processes as well, we present it here.

Corollary:
For each parameter k>0, there is a tree in which one node with degree k+1 and another with degree 2 both have the same closeness centrality of k*(k+1).

 Proof:
We start with the construction of the tree: first, 2k+1 nodes are connected to a chain, and labeled from v1 to v2k+1.Then, k nodes are added as neighbors to node v1. We will now determine the sum of distances distsum(v1) of node v1 to all other nodes in the tree. For each of the k added neighbors, the distance to v1 is 1. For the other nodes vi, the distance is i-1. Thus, distsum(v1) is given by k+1+2+...+2k =k+2k*(2k+1)/2 = k+2k^2+k=2k^2+2k=2k(k+1). Node vk+1 has two nodes in distance i each, for 1<=i<=k, summing up to 2*k(k+1)/2. The distance to the k additional neighbors of v1 is k+1, adding up to another summand of k*(k+1). Thus, distsum(vk+1) is also given by 2k(k+1).