CS4423 - Networks

Prof. Götz Pfeiffer
School of Mathematics, Statistics and Applied Mathematics
NUI Galway

2. Centrality Measures

Lecture 7: Degree and Eigenvector Centrality

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.

Start by importing the necessary python libraries into this jupyter notebook. (Actually, networkx works with a number of useful python libraries, some of which are loaded automatically, while others have to be imported explicitly, depending on the circumstances. In the following, we will also make explicit use of Pandas and Numpy.)

In [ ]:
import networkx as nx
import matplotlib.pyplot as plt

Degree Centrality

The degree of a node is its number of neighbors in the graph. This number can serve as a simple measure of centrality.

Consider the following network of florentine families, linked by marital ties.

In [ ]:
G = nx.generators.florentine_families_graph()
list(G.nodes())

Unfortunately, this version of the graph misses the isolated node 'Pucci' of the original graph. Let's just add it and draw the resulting graph.

In [ ]:
cc = list(G.nodes())
G.add_node('Pucci')
In [ ]:
nx.draw(G, with_labels=True)

The large connected component can be drawn as a subgraph.

In [ ]:
nx.draw(G.subgraph(cc), with_labels=True)

Known indicators of the importance of these families are their wealth, and the number of seats on the city council (priorates). These measures can be compared with the node degree in the graph 'G'.

In [ ]:
wealth = {
  'Acciaiuoli': 10, 'Albizzi': 36, 'Barbadori': 55, 'Bischeri': 44,
  'Castellani': 20, 'Ginori': 32, 'Guadagni': 8, 'Lamberteschi': 42,
  'Medici': 103, 'Pazzi': 48, 'Peruzzi': 49, 'Pucci': 3,
  'Ridolfi': 27, 'Salviati': 10, 'Strozzi': 146, 'Tornabuoni': 48,
}

priorates = {
  'Acciaiuoli': 53, 'Albizzi': 65, 'Barbadori': 'n/a', 'Bischeri': 12,
  'Castellani': 22, 'Ginori': 'n/a', 'Guadagni': 21, 'Lamberteschi': 0,
  'Medici': 53, 'Pazzi': 'n/a', 'Peruzzi': 42, 'Pucci': 0,
  'Ridolfi': 38, 'Salviati': 35, 'Strozzi': 74, 'Tornabuoni': 'n/a',
}
In [ ]:
nx.set_node_attributes(G, wealth, 'wealth')
nx.set_node_attributes(G, priorates, 'priorates')
nx.set_node_attributes(G, dict(G.degree()), 'degree')
In [ ]:
dict(G.degree())
In [ ]:
G.nodes['Pazzi']
In [ ]:
G.nodes(data=True)
In [ ]:
import pandas as pd
In [ ]:
pd.DataFrame.from_dict(dict(G.nodes(data=True)), orient='index').sort_values('degree', ascending=False)
Definition (Degree Centrality). In a (simple) graph $G = (X, E)$, with $X = \{1, \dots, n\}$ and adjacency matrix $A = (a_{ij})$, the degree centrality $c_i^D$ of node $i \in X$ is defined as $$ c_i^D = k_i = \sum_j a_{ij}, $$ where $k_i$ is the degree of node $i$.
The normalized degree centrality $C_i^D$ of node $i \in X$ is defined as $$ C_i^D = \frac{k_i}{n-1} = \frac{c_i^D}{n-1}, $$ the degree centrality of node $i$ divided by its potential number of neighbors in the graph.

In a directed graph one distinguishes between the in-degree and the out-degree of a node and defines the in-degree centrality and the out-degree centrality accordingly.

In [ ]:
nx.set_node_attributes(G, nx.degree_centrality(G), '$C_i^D$')
In [ ]:
pd.DataFrame.from_dict(dict(G.nodes(data=True)), orient='index').sort_values('degree', ascending=False)

Eigenvectors and Centrality

Recall that a ($n$-dimensional) vector $v$ is called an eigenvector of a square ($n \times n$-)matrix $A$, if $$ A v = \lambda v $$ for some scalar (number) $\lambda$ (which is then called an eigenvalue of the matrix $A$)

The basic idea of eigenvector centrality is that a node's ranking in a network should relate to the rankings of the nodes it is connected to. More specifically, up to some scalar $\lambda$, the centrality $c_i^E$ of node $i$ should be equal to the sum if the centralities $c_j^E$ of its neighbor nodes $j$. In terms of the adjacency matrix $A = (a_{ij})$, this relationship is expressed as $$ \lambda c_i^E = \sum_j a_{ij} c_j^E, $$ which in turn, in matrix language is $$ \lambda c^E = A c_E, $$ for the vector $c^E = (c_i^E)$, which then is an eigenvector of $A$.

How to find $c^E$? Or $\lambda$? Linear Algebra:

  1. Find the characteristic polynomial $p_A(x)$ of $A$ (as determinant of the matrix $x I - A$, where $I$ is the $n \times n$-identity matrix);
  2. Find the roots $\lambda$ of $p_A(x)$ (i.e. scalars $\lambda$ such that $p_A(\lambda) = 0$;
  3. Find a nontrivial solution of the linear system $(\lambda I - A)c = 0$ (where $0$ stands for an all-$0$ column vector, and $c = (c_1, \dots, c_n)$ is a column of unknowns).
In [ ]:
A = nx.adjacency_matrix(G)
In [ ]:
import numpy as np
B = np.array([[2,2],[3,1]])
poly = np.poly(B)
l, v = np.linalg.eig(B)
vv = v.transpose()
print(poly)
print(l); print (vv); print(vv[0])
print(B*vv[0], l[0]*vv[0])
In [ ]:
print(np.matmul(B, vv[0]))
In [ ]:
print(A.todense())
In [ ]:
np.poly(A.todense())

Numerical Linerar Algebra: forget algebraic precision, use the Power method:

  1. start with $u = (1, 1, \dots, 1)$, say;
  2. keep replacing $u \gets Au$ until $u/\|u\|$ becomes stable ...

If $A$ has a dominant eigenvalue $\lambda_0$ then $u$ will converge to an eigenvector for the eigenvalue $\lambda_0$.

In [ ]:
u = [1 for x in A]
print(u)
print(u/np.linalg.norm(u))
In [ ]:
v = A*u
print(v)
print(v/np.linalg.norm(v))
In [ ]:
for i in range(40):
    u = A * u
    u = u/np.linalg.norm(u)
In [ ]:
v = A *u
l = v[2]/u[2]
v = v/np.linalg.norm(v)
print(u/np.linalg.norm(u))
print(v/np.linalg.norm(v))
print("||v - u|| = ", np.linalg.norm(v - u))
print("l = ", l)
In [ ]:
l, w = np.linalg.eig(A.todense())
print (l)
print (w.transpose()[0])
In [ ]:
eigen_cen = nx.eigenvector_centrality(G.subgraph(cc))
eigen_cen

Time's up. Save the graph for future use.

In [ ]:
nx.write_yaml(G, "florentine.yml")

The theoretical foundation for this approach is provided by the following Linear Algebra theorem from 1907/1912.

Theorem. (Perron-Frobenius for irreducible matrices.) Suppose that $A$ is a square, nonnegative, irreducible matrix. Then: * $A$ has a real eigenvalue $\lambda > 0$ with $\lambda \geq |\lambda'|$ for all eigenvalues $\lambda'$ of $A$; * $\lambda$ is a simple root of the characteristic polynomial of $A$; * there is a $\lambda$-eigenvector $v$ with $v > 0$.

Here, a matrix $A$ is called reducible if, for some simultaneous permutation of its rows and columns, it has the block form $$ A = \left( \begin{array}{cc} A_{11} & A_{12} \\ 0 & A_{21} \end{array} \right). $$ And $A$ is irreducible if it is not reducible.

The incidence matrix of a simple graph $G$ is irreducible if and only if $G$ is connected.

**Definition (Eigenvector centrality).** In a simple, connected graph $G$, the **eigenvector centrality** $c_i^E$ of node $i$ is defined as $$ c_i^E = u_i, $$ where $u = (u_1, \dots, u_n)$ is the (unique) normalized eigenvector of the adjacency matrix $A$ of $G$ with eigenvalue $\lambda$, and where $\lambda > |\lambda'|$ for all eigenvalues $\lambda'$ of $A$. The **normalised eigenvector centrality** of node $i$ is defined as $$ C_i^E = \frac{c_i^E}{C^E}, $$ where $C^E = \sum_j c_j^E$.
In [ ]: