Graphs and Social Networks

Centrality Measures

Key actors in a social network can be identified through centrality measures. The question of what it means to be central has a number of different answers. Accordingly, in the context of social network analysis, a variety of different centrality measures have been developed.

Here we introduce, in addition to the degree centrality we have already seen, three more further measures:

  • eigenvector centrality, defined in terms of properties of the network’s adjacency matrix,

  • closeness centrality, defined in terms of a nodes distance to other nodes on the network,

  • betweenness centrality, defined in terms of shortest paths.

For simplicity, we assume here that the network under consideration is connected.

Recall, the degree centrality (or just the degree) $c_i^D$ of node $i$ in terms of the adjaceny matrix $A$ of the (undirected) network is

Eigenvector centrality

The centrality of a node is ($\lambda$-)proportional to the sum of the centralities of its neighbours.

That means, $A c^E = \lambda c^E$, making the vector $c^E = (c_i^E)$ an eigenvector for the eigenvalue $\lambda$ of the adjacency matrix $A$. But: which $\lambda$? Given that an $n \times n$-matrix $A$ in general has $n$ (complex) eigenvalues.

Luckily, the adjacency matrix $A$ of a connected undirected network is irreducible, i.e., under no permutation of its rows and columns it has the shape

and we have the following theorem from Linear Algebra

Theorem (Frobenius-Perron). Ṡuppose that $A$ is a non-negative irreducible $n \times n$-matrix, then

  • one of its eigenvalues is positive and, in absolute value, greater or equal to all other eigenvalues,

  • this eigenvalue has multiplicity $1$ (as root of the characteristic polynomial of $A$)

  • there is a positive eigenvector $u_1$ for this eigenvalue.

Define the eigenvector centrality $c_i^E$ of node $i$ as

Example …

Closeness Centrality

A node can be considered as important if it can quickly interact with many nodes on the network.

We have seen that BFS can be used to determine for node $i$ the distances $d_{ij}$ from nodes $j$ in the (connected) network.

Define the closeness centrality $c_i^C$ of node $i$ as

the reciprocal of the sum of the distances from $i$ to the other nodes.

(This measure can be normalized, using the fact that $(n-1) c_i^C$ is always a number between 0 and 1.

Example …

Betweenness Centrality

In addition to distances, BFS finds shortest paths. Assuming (for simplicity) that information travels (just) along shortest paths, a nodes centrality can be determined by the number (or proportion) of shortest paths it lies on.

Denote by $n_{jk}$ the number of shortest paths from node $j$ to node $k$ (which can be larger than $1$), and by $n_{jk}(i)$, the number of such paths that travel through node $i$.

Define the betweenness centrality $c_i^B$ of node $i$ as

Example …