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 (FrobeniusPerron). Ṡuppose that $A$ is a nonnegative 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 $(n1) 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 …