Prof. Götz Pfeiffer

School of Mathematics, Statistics and Applied Mathematics

NUI Galway

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 `import`

ed 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
```

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)
```

The

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)
```

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:

- 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); - Find the
*roots*$\lambda$ of $p_A(x)$ (i.e. scalars $\lambda$ such that $p_A(\lambda) = 0$; - 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**:

- start with $u = (1, 1, \dots, 1)$, say;
- 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.

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 [ ]:

```
```