General Definitions for Network Statistics

Introduction

There are many useful metrics to describe a network, according to which we can judge some characters of the network. In the following we list the definitions of some common metrics for weighted and unweighted networks. A weighted network associates a label (weight) with every edge in the network. Weights are usually real numbers. They may be restricted to rational numbers or integers. For unweighted network there is no label (weight) with every edge in the netwrok.

1 General Definitions for Unweighted Network

For a graph $G:=(V,E)$ with $n$ vertices, let the matrix of bilateral values $W(G)=[w_{ij}]$ be a weight function on the edges, $w_{ij}$ is the edge value from vertex $i$ to vertex $j$.We assume that $w_{ij}>0,\; e_{ij}\in E$,for weighted graphs, and define $w_{ij}=1, \; e_{ij}\in E$, for unweighted graphs.

Define a path from $s \in V$ to $t \in V$ as an alternating sequence of vertices and edges, beginning with $s$ and ending with $t$, such that each edge connects its proceeding with its succeeding vertex. The length of a path is the sum of the weights of its edges. We can use $d_G(s,t)$ to denote the shortest path between vertices $s$ and $t$.

For an unweighted graph, the adjacency matrix $A(G)=[a_{ij}]$ assigns the value 1, if there is an edge starting in vertex $i$ and going to vertex $j$. If there is no edge starting in vertex $i$ and going to vertex $j$, then $A_{ij}=0$.

1.1 Average Indegree

Degree is the number of edges incident to a vertex, which is called degree of that vertex. Indegrees is the number of inward directed graph edges from a given graph vertex in a directed graph. Average Indegrees is the average value of the Indegrees of all the vertices in a directed graph. So the indegree of vertex $ i $ is:

\[\mbox{indegree}(i)=\sum\limits_{j=1}^n A(j,i)\]

The average indegree is:
\[\mbox{average indegree}(i)=\frac{\sum\limits_{i=1}^n \sum\limits_{j=1}^n A(j,i)}{n}\]

This is the simplest measure that we will use to characterize the role of vertices in the network, the bigger the value of average indegree is, the closer the relationship among the vertices in the network.

Example

Fig.1 A Directed Graph with Four Vertices

Fig.2 Another Directed Graph with Four Vertices

According to Fig.1 we can write the adjacency matrix as following:
\[A_1=\left[\begin{array}{cccc} 0&1&0&0\\ 1&0&1&0\\ 0&0&0&0\\ 0&1&1&0 \end{array}\right]\]
So we get
\[\mbox{indegree}_{Fig1}(1)=0+1+0+0=1,\]
\[\mbox{indegree}_{Fig1}(2)=1+0+0+1=2,\]
\[\mbox{indegree}_{Fig1}(3)=0+1+0+1=2,\]
\[\mbox{indegree}_{Fig1}(4)=0+0+0+0=0.\]
The value of average indegree of Fig.1 is:
\[\mbox{average indegree}_{Fig1}=\frac{1+2+2+0}{4}=1.25\]
Similarly, we can get the adjacency matrix of Fig.2:
\[A_2=\left[\begin{array}{cccc} 0&1&0&0\\ 1&0&1&1\\ 1&0&0&1\\ 0&1&1&0 \end{array}\right]\]
So we get
\[\mbox{indegree}_{Fig2}(1)=0+1+1+0=2,\]
\[\mbox{indegree}_{Fig2}(2)=1+0+0+1=2,\]
\[\mbox{indegree}_{Fig2}(3)=0+1+0+1=2,\]
\[\mbox{indegree}_{Fig2}(4)=0+1+1+0=2.\]
The value of average indegree of Fig.2 is:
\[\mbox{average indegree}_{Fig2}=\frac{2+2+2+2}{4}=2\]
Obviously, $\mbox{average indegree}_{Fig2}$ is bigger than $\mbox{average indegree}_{Fig1}$, which indicates that Fig.2 has more complex relations than Fig.1. It is also easy to be seen form the two graphs.

1.2 Diameter

Diameter $D$ is the max value of the shortest path between any two vertices in the network.

\[D=\max_{s,t\in V}d_G (s,t)\]

This value can reflect the size of network, the bigger the value of diameter is, the closer the vertices in the network are.

Example

Fig.3 A Undirected Graph with Four Vertices

Fig.4 Another Undirected Graph with Four Vertices

According to Fig.3, we can compute the shortest path between any two vertices. The results are listed in the following:
\[d(1,2)=d(1,4)=d(2,3)=d(3,4)=1\]
\[d(1,3)=d(2,4)=2\]
So the diameter of Fig.3 is 2.

In Fig.4 any two vertices are connected, the distance of which all is 1. So the diameter of Fig.4 is 1. So the bigger the value of diameter, the closer the relations of the graph is.

1.3 Average distance

The average distance $L$ is defined as the average value of the shortest path between any two vertices in the graph. So

\[L=\frac{1}{\frac{1}{2}n(n-1)}\sum\limits_{s\ge t}d_G(s,t)\]

This value reflects the connection degree between two vertices in the network. The smaller is, the closer the vertices in the network are.

Example

We still use Fig.3 and Fig.4 to calculate the average distance.

The calculation of average distance $L$ of Fig.3 is:
\[L_{Fig3}=\frac{1}{\displaystyle \frac{1}{2}4\:(4-1)}(1+2+1+1+2+1)=1.333\]
However, the calculation of average distance $L$ of Fig.4 is:
\[L_{Fig4}=\frac{1}{\displaystyle \frac{1}{2}4\:(4-1)}(1+1+1+1+1+1)=1\]
So $L_{Fig3}>L_{Fig4}$, the graph of Fig.4 is closer than Fig.3. It is also easy to be seen from the two graphs.

1.4 Betweenness Centrality

The betweenness $C_B (v)$ for vertex $v$ is:

\[C_B (v)=\sum\limits_{\scriptstyle{s \neq v \neq t \in V \atop s \neq t}} \frac{\sigma_{st} (v)}{\sigma_{st}}\]

where $\sigma_{st}$ is the number of shortest paths from $s$ to $t$, and $\sigma_{st}(v)$ is the number of shortest parth from $s$ to $t$ that pass through a vertex $v$. This may be normalized by dividing through by the maximal value in the graph.

\[C_B^' (v_j)=C_B(v_j)/\max(C_B(v_j))\]

where $\max(C_B(v_j))=(n_I -1)(n_O -1)(n_S -1)$, and $n_I$ is the number of vertices with incoming arcs, $n_O$ is the number of points with outgoing arcs, $n_S$ is the number of vertices with reciprocated arces.

We define the $C_B^'(p^*)$ as the largest centrality value associated with any vertices in the graph. Then we have the measure of betweennes centralization in the graph:

\[C_B^'=\frac{\sum\limits_{i=1}^n \left|C_B^'(p_k^*)-C_B^'(p_i)\right|}{n-1}\]

The value of betweenness centrality is an important index of centrality. If the value is bigger, it indicates that there is a central vertex, with which many other vertices connect.

Example

Fig.5 A Network with Six Vertices

Fig.6 Another Network with Six Vertices

Simply according to undirected network of Fig.5 we can get
\[\sigma_{st}=1, \qquad \mbox{for}\quad s,t\in {1,2,3,4,5,6}\]
and
\[\sigma_{st}(1)=1, \qquad \mbox{for}\quad s,t\in {2,3,4,5,6}\]
\[\sigma_{st}(v)=0, \qquad \mbox{for}\quad s,t \in {1,2,3,4,5,6}, \; v \in {2,3,4,5,6}\]
So for undirected network Fig.5

\[\max(C_B(v_j))=(6^2-3\times 6+2)/\,2=10\]
\[C_B(v)=C_5^2\times \frac{1}{1}=10, \qquad C_B^’=\frac{10}{10}=1 \qquad \mbox{and}\]
\[C_B(v)=C_B^’(v)=0, \qquad \mbox{for} \quad v=2,3,4,5,6\]
then we can get
\[C_B^’(Fig5)=\frac{|1-1|+|1-0|+|1-0|+|1-0|+|1-0|+|1-0|}{6-1}=1\]
Similarly according to undirected Fig.6, we firstly can get the number of shortest paths between any two vertices.

$\sigma_{12}=\sigma_{13}=\sigma_{14}=\sigma_{16}=\sigma_{23}=\sigma_{25}=\sigma_{34}=\sigma_{35}=\sigma_{36}=\sigma_{45}=\sigma_{56}=1$
$\sigma_{15}=\sigma_{26}=3$, $\sigma_{24}=\sigma_{46}=2$,
$\sigma_{23}(1)= \sigma_{25}(1)= \sigma_{34}(1)= \sigma_{35}(1)= \sigma_{36}(1)= \sigma_{45}(1)= \sigma_{56}(1)=0$, $\sigma_{24}(1)= \sigma_{26}(1)= \sigma_{46}(1)=1$,
$\sigma_{13}(2)= \sigma_{14}(2)= \sigma_{16}(2)= \sigma_{34}(2)= \sigma_{35}(2)= \sigma_{36}(2)= \sigma_{45}(2)= \sigma_{56}(2)=0$, $\sigma_{15}(2)=1$,
$\sigma_{12}(3)= \sigma_{14}(3)= \sigma_{16}(3)= \sigma_{25}(3)= \sigma_{56}(3)=0$, $\sigma_{15}(3)= \sigma_{24}(3)= \sigma_{26}(3)= \sigma_{45}(3)= \sigma_{46}(3)=1$,
$\sigma_{12}(4)= \sigma_{13}(4)= \sigma_{15}(4)= \sigma_{16}(4)= \sigma_{23}(4)= \sigma_{25}(4)= \sigma_{26}(4)= \sigma_{35}(4)= \sigma_{36}(4)= \sigma_{56}(4)=0$,
$\sigma_{12}(5)= \sigma_{13}(5)= \sigma_{14}(5)= \sigma_{16}(5)= \sigma_{23}(5)= \sigma_{24}(5)= \sigma_{34}(5)= \sigma_{36}(5)= \sigma_{46}(5)=0$, $\sigma_{26}(5)=1$
$\sigma_{12}(6)= \sigma_{13}(6)= \sigma_{14}(6)= \sigma_{23}(6)= \sigma_{24}(6)= \sigma_{25}(6)= \sigma_{34}(6)= \sigma_{35}(6)= \sigma_{45}(6)=0$, $\sigma_{15}(6)=1$.

The $\max(C_B(v_j))=(6^2-3\times 6+2)/2=10$,

and
\[C_B(1)=\frac{\sigma_{24}(1)}{\sigma_{24}}+\frac{\sigma_{26}(1)}{\sigma_{26}}+\frac{\sigma_{46}(1)}{\sigma_{46}}=\frac{1}{2}+\frac{1}{3}+\frac{1}{2}=\frac{4}{3}, \qquad C_B^’(1)=\frac{4}{3\times 10}=\frac{2}{15}\]
Similarly,
$C_B(2)=\displaystyle \frac{1}{3}$, $C_B^’=\displaystyle \frac{1}{3\times 10}=\displaystyle \frac{1}{30}$
$C_B(3)=\displaystyle \frac{1}{3}+\displaystyle \frac{1}{2}+\displaystyle \frac{1}{3}+\displaystyle \frac{1}{1}+\displaystyle \frac{1}{2}=\displaystyle \frac{8}{3}$, $C_B^’=\displaystyle \frac{8}{3\times 10}=\displaystyle \frac{4}{15}$
$C_B(4)=0$, $C_B^’(4)=0$
$C_B(5)=\displaystyle \frac{1}{3}$, $C_B^’(5)=\displaystyle \frac{1}{3\times 10}=\displaystyle \frac{1}{30}$
$C_B(6)=\displaystyle \frac{1}{3}$, $C_B^’(6)=\displaystyle \frac{1}{3\times 10}=\displaystyle \frac{1}{30}$

We can get

$C_B^’(Fig6)=\left((\displaystyle \frac{4}{15}-\displaystyle \frac{2}{15})+(\displaystyle \frac{4}{15}-\displaystyle \frac{1}{30})+(\displaystyle \frac{4}{15}-\displaystyle \frac{4}{15})+(\displaystyle \frac{4}{15}-0)+(\displaystyle \frac{4}{15}-\displaystyle \frac{1}{30})+(\displaystyle \frac{4}{15}-\displaystyle \frac{1}{30})\right)/\,(6-1)=0.22$

After comparing Fig.5 with Fig.6 we can see that Fig.5 is a high centered graph, vertex 1 is the center, and the centrality of Figure6 is not obvious. That point also can be got from comparing the values of $C_B^’$.

1.5 Cluster Coefficients

Let $\mbox{deg}(v)$ denotes degree of vertex $v$, $|E(G_1(v))|$ is number of lines among vertices in 1-neighborhood of vertex $v$, $MagDeg$ maximum degree of vertex in a network, and $|E(G_2(v))|$ is the number of lines among vertices in 1 and 2-neighborhood of vertex $v$.

$CC_1$ - coefficients considering only 1-neighborhood:

\[CC_1(v)=\frac{2|E(G_1(v))|}{\mbox{deg}(v)(\mbox{deg}(v)-1))} \; \; \qquad CC_1^'=\frac{\mbox{deg}(v)}{MaxDeg}CC_1(v) \]

$CC_2$ - coefficients considering only 2-neighborhood:

\[CC_2(v)=\frac{|E(G_1(v))|}{|E(G_2(v))|} \; \; \qquad CC_2^'=\frac{\mbox{deg}(v)}{MaxDeg}CC_2(v) \]

If $\mbox{deg}(v)\leq 1$, all coefficients for vertex $v$ are 0.

Cluster Coefficients $(CC)$ for a graph is the average of the $CC_1$ or $CC_2^'$ of all the vertices.

\[CC1=\frac{\sum\limits_{i=1}^nCC_1(i)}{n} \;\;\; \mbox{or}\]
\[ CC2=\frac{\sum\limits_{i=1}^nCC_2^'(i)}{n}\]

In words cluster coefficients $CC(v)$ answers the question “given two nodes that are both connected to node , what is the likelihood that these two nodes are connected to each other?” The bigger the value is, the closer the vertices are.

Example

We want to compare the change of the values of cluster coefficients of different graphs to reflect the character of cluster coefficients. Fig.5 and Fig.6 still are used here.

For Fig.5, we have

$\mbox{deg}(1)=5$, $\mbox{deg}(v)=1$, for $v=2,3,4,5,6$
and $E_{Fig5}(G_1(v))=0$, for $v=1,2,3,4,5,6$
Therefore, cluster coefficients ($CC$) of Fig.5 is 0.

For Fig.6, we have

$\mbox{deg}(1)=4, \;E(G_1(1))=3,\; E(G_2(1))=6,\; CC_1(1)=\displaystyle \frac{2\times 3}{4\times (4-1)}=0.5,\; CC_2^’(1)=\displaystyle \frac{4\times 3}{5\times 6}=0.4$
$\mbox{deg}(2)=3, \;E(G_1(2))=2,\; E(G_2(2))=7,\; CC_1(2)=\displaystyle \frac{2\times 2}{3\times (3-1)}=\displaystyle \frac{2}{3},\; CC_2^’(2)=\displaystyle \frac{3\times 2}{5\times 7}=\displaystyle \frac{6}{35}$
$\mbox{deg}(3)=5, \;E(G_1(3))=5,\; E(G_2(3))=5,\; CC_1(3)=\displaystyle \frac{2\times 6}{5\times (5-1)}=0.5,\; CC_2^’(3)=\displaystyle \frac{5\times 5}{5\times 5}=1$
$\mbox{deg}(4)=2, \;E(G_1(4))=1,\; E(G_2(4))=8,\; CC_1(4)=\displaystyle \frac{2\times 1}{2\times (2-1)}=0.5,\; CC_2^’(4)=\displaystyle \frac{2\times 1}{5\times 8}=0.05$
$\mbox{deg}(5)=3, \;E(G_1(5))=2,\; E(G_2(5))=7,\; CC_1(5)=\displaystyle \frac{2\times 2}{3\times (3-1)}=\displaystyle \frac{2}{3},\; CC_2^’(5)=\displaystyle \frac{3\times 2}{5\times 7}=\displaystyle \frac{6}{35}$
$\mbox{deg}(6)=3, \;E(G_1(6))=2,\; E(G_2(6))=7,\; CC_1(6)=\displaystyle \frac{2\times 2}{3\times (3-1)}=\displaystyle \frac{2}{3},\; CC_2^’(6)=\displaystyle \frac{3\times 2}{5\times 7}=\displaystyle \frac{6}{35}$
So $CC1_{Fig6}=\displaystyle \frac{0.5+2/3+0.5+1+2/3+2/3}{6}=0.667$
$CC2_{Fig6}=\displaystyle \frac{0.4+6/35+1+0.5+6/35+6/35}{6}=0.402$

By comparing the value of cluster coefficients we find that Fig.6 has bigger value, which indicates that the relations in Fig.6 are closer than Fig.5.

2 General Definitions for Weighted Network

2.1 Value Indegree and Outdegree Centralities

Since average indegree don’t take the size of edge value into account, it is worth defining measures to cope with the size of edge values. The value indegree centrality is:

\[vdc_{in}(i)=\frac{\sum_{j=1}^n w_{ji}}{\sum_{k=1}^n \sum_{j=1}^n w_{kj}}\]

The value outdegree centrality is:

\[vdc_{out}(i)=\frac{\sum_{j=1}^n w_{ij}}{\sum_{k=1}^n \sum_{j=1}^n w_{kj}}\]

These values reflect the total in-edges or out-edges values ratio to total edge values of total network. The bigger the value of $vdc_{in}(i)$ or $vdc_{out}(i)$, the more important the vertex $i$ in the network is.

Example

Fig.7 A Weighted Directed Network

We can calculate the value indegree and outdegree of Fig.7 as follows.
The weight matrix is that:
\[W=\left[\begin{array}{cccc} 0&3&1&2 \\ 0&0&2&0 \\ 0&3&0&1 \\ 1&2&0&0 \end{array} \right]\]
So we get
$vdc_{in}(1)=\displaystyle \frac{\sum_{j=1}^n w_{j1}}{\sum_{k=1}^n \sum_{j=1}^n w_{kj}}=\displaystyle \frac{0+0+0+1}{3+1+2+2+3+1+1+2}=0.067$, $vdc_{out}(1)=\displaystyle \frac{3+1+2}{15}=0.4$

Similarly,

$vdc_{in}(2)=0.533$, $vdc_{out}(2)=0.133$
$vdc_{in}(3)=0.2$, $vdc_{out}(3)=0.267$
$vdc_{in}(4)=0.2$, $vdc_{out}(4)=0.2$

According to the values of $vdc_{in}$ and $vdc_{out}$, we can see that vertex 2 is a important proceeding vertex, vertex 1 is a important succeeding vertex.

2.2 Domination Power

The domination power is a measure of centrality of a node in a network that takes the direction and the weight of the relations into account.

Domination power is measured using the generalized $\beta-$ measure:

\[\beta (i)=\sum\limits_{j=1}^n \frac{w_{ij}}{\lambda (j)}\]

where $\lambda (j)$ is the dominance weight of vertex $j$ given by:

\[\lambda (j)=\sum\limits_{i=1}^n w_{ij}\]

The generalized $\beta -$measure is a nice way of ordering network center in degree of importance.

Example

According to Fig.7 we can calculate correspondingly the domination power of any vertex as following:

$\lambda (1)=3+1+2=6$, $\lambda (2)=2$, $\lambda (3)=3+1=4$, $\lambda (4)=1+2=3$,
$\beta (1)=\displaystyle \frac{0}{6}+\displaystyle \frac{3}{2}+\displaystyle \frac{1}{4}+\displaystyle \frac{2}{3}=2.417$, $\beta (2)=\displaystyle \frac{0}{6}+\displaystyle \frac{0}{2}+\displaystyle \frac{2}{4}+\displaystyle \frac{0}{3}=0.5$
$\beta (3)=\displaystyle \frac{0}{6}+\displaystyle \frac{3}{2}+\displaystyle \frac{0}{4}+\displaystyle \frac{1}{3}=2.417$, $\beta (4)=\displaystyle \frac{1}{6}+\displaystyle \frac{2}{2}+\displaystyle \frac{0}{4}+\displaystyle \frac{0}{3}=1.167$

The value of $\beta (1)$ is the biggest, which indicate that vertex 1 has bigger domination power to other vertices.

2.3 Cluster Coefficients

For undirected graph, usually the weights are normalized to make $0\leq w_{ij} \leq 1$ .The weighted clustering coefficient for the vertex $k$ is defined as:

\[CC(k)=\frac{\sum_{i\neq k}\sum_{j \neq i,\: j\neq k}w_{ki}w_{ij}w_{jk}}{(\sum_{i\neq k}w_{ki})^2-\sum_{i\neq k}w_{ki}^2}\]

Schank and Wagner presented a single weighted clustering coefficient for the whole network as:

\[CC=\frac{1}{\sum_v\,w(v)}\sum\limits_v w(v)CC(v)\]

where $w(v)$ is a weight function for vertex $v$.

This method not only considers the weight for edges, but also considers the weight for vertices. The bigger the value of $CC$ is, the bigger connectivity the network is.

Example

Fig.8 A Weighted Undirected Graph

Fig.9 Another Weighted Undirected Graph

We can write the weight matrixes of Fig.8 and Fig.9 as following:

$W_{Fig8}=\left[\begin{array}{cccccc} 0&3&1&2&4&0 \\ 3&0&2&3&0&0 \\ 1&2&0&0&0&0 \\ 2&3&0&0&0&3 \\ 4&0&0&0&0&1 \\ 0&0&0&3&1&0 \end{array}\right]$, $W_{Fig9}=\left[\begin{array}{cccccc} 0&3&1&2&4&0 \\ 3&0&2&3&0&0 \\ 1&2&0&1&0&2 \\ 2&3&1&0&2&3 \\ 4&0&0&2&0&1 \\ 0&0&2&3&1&0 \end{array}\right]$

Normalize the above weight matrixes by dividing every element by the maximum. So

$W_{Fig8}=\left[\begin{array}{cccccc} 0&0.75&0.25&0.5&1&0 \\ 0.75&0&0.5&0.75&0&0 \\ 0.25&0.5&0&0&0&0 \\ 0.5&0.75&0&0&0&0.75 \\ 1&0&0&0&0&0.25 \\ 0&0&0&0.75&0.25&0 \end{array}\right]$ $W_{Fig9}=\left[\begin{array}{cccccc} 0&0.75&0.25&0.5&1&0 \\ 0.75&0&0.5&0.75&0&0 \\ 0.25&0.5&0&0.25&0&0.5 \\ 0.5&0.75&0.25&0&0.5&0.75 \\ 1&0&0&0.5&0&0.25 \\ 0&0&0.5&0.75&0.25&0 \end{array}\right]$

The calculations of cluster coefficients are listed in the following.

$CC_{Fig8}(1)=\displaystyle \frac{0.75 \times 0.5 \times 0.25+0.75 \times 0.75 \times 0.5+0.25\ times 0.5 \times 0.75+0.5 \times 0.75 \times 0.75 }{(0.75+0.25+0.5+1)^2-(0.75^2+0.25^2+0.5^2+1^2)}=0.171$

$CC_{Fig9}(1)=\displaystyle \frac{\begin{array}{c}0.75 \times 0.5 \times 0.25+0.75 \times 0.75 \times 0.5+0.25 \times 0.5 \times 0.75+0.5 \times 0.75 \times \\ 0.75 +0.25\times 0.25 \times 0.5+0.5\times 0.25\times 0.25+0.5\times 0.5\times 1+1\times 0.5\times 0.5 \end{array}}{(0.75+0.25+0.5+1)^2-(0.75^2+0.25^2+0.5^2+1^2)}=0.3$

Similarly,

$CC_{Fig8}(2)=0.286$, $CC_{Fig9}(2)=0.357$
$CC_{Fig8}(3)=0.75$, $CC_{Fig9}(3)=0.385$
$CC_{Fig8}(4)=0.214$, $CC_{Fig9}(4)=0.321$
$CC_{Fig8}(5)=0$, $CC_{Fig9}(5)=0.393$
$CC_{Fig8}(6)=0$, $CC_{Fig9}(6)=0.273$

Here we let $w(v)$ equal 1, for $v=1,\cdots,6$, then get
\[CC_{Fig8}=\frac{0.171+0.286+0.75+0.214+0+0}{6}=0.237\]
similarly,
\[CC_{Fig9}=0.338\]
The value of cluster coefficients of Fig.9 is bigger than Fig.8, which indicates that the connectivity of Fig.9 is better than Fig.8, and it is obvious when we observe the two graphs.

2.4 Betweenness

The weighted directed edge from sector $i$ to sector $j$ is given by the canonical element $w_{ij}$ of the $l\times l$ input-output matrix $W$. The degree of vertex $i$ is the total output of the sector:

\[d_i=\sum\limits_jw_{ij}\]

Newman shows that Kirchoff’ law of current conservation implies that, for a given impulse $(s,t)$, the voltage across each vertex satisfies his system of equations:

\[[D-W]v(s,t)=f(s,t) \qquad \qquad \qquad (1)\]

where $D=diag(d_1,\ldots,d_l)$, $W$ is again the input output matrix, and $v(s,t)$ is the $l \times 1$ vector of voltages at the vertices in the network. The $l \times 1$ vector $f(s,t)$ has elements defined by:

\[f_i(s,t)=\left\{\begin{array}{r@{\; \; \;}}1 & if & i=s \\ -1 & if & i=t \\ 0 & otherwise \end{array} \right.\]

The matrix $[D-W]$ is singular because the $l \times 1$ unit vector is an eigenvector whose eigenvalue is zero. Hence we use the Moore Penrose pseudo-inverse to find the minimum norm solutions to equation (1):

\[v(s,t)=[D-W]^+f(s,t) \qquad \qquad \qquad (2)\]

Equation (2) defines the voltage at each of the vertices in the economy for a given impulse $(s,t)$. Let $a_i (s,t)=\left|v(s,t)-1_{l \times 1}v_i(s,t)\right|$, where $1_{l \times 1}$ is the conformable unit vector. Newman explains that the current flow through each node proportional to the absolute values of current flowing along the edges of that vertex:

\[I_i(s,t)=W_i a_i(s,t)\]

for $i\neq s,t$ where $W_i$ is the ith row of weight matrix $W$. In the case where $i=s$ or $i=t$, the current flow is necessarily one unit, and we may write:

\[I_s(s,t)=I_t(s,t)=1\]

Finally, the definition of betweenness is the average current flow across all the pairs of sources and targets:

\[b_i=\frac{\sum\limits_s\sum\limits_{t \neq s} I_i(s,t)}{l\,(l-1)}\]

The bigger the value of the betweenness is, the more centrality the vertex is.

We can also define the $b_{P^*}$ as the largest centrality value associated with any vertices in the graph. Then we

have the measure of betweennes centralization in the graph:
\[b=\frac{\sum\limits_{p=1}^n |b_{p^*}-b_p|}{n-1}\]

Example

Fig.10 A Weighted Directed Graph

Fig.11 Another Weighted Directed Graph

According to the above two graphs we can calculate the betweenness as follows.
Firstly, we get

$W_{Fig10}=\left[\begin{array}{cccc} 0&0.3&0&0 \\ 0&0&0.6&0 \\ 0.3&0&0&0.5 \\ 0.2&0&0&0 \end{array}\right]$, $W_{Fig11}=\left[\begin{array}{cccc} 0&0.3&0.5&0.4 \\ 0.5&0&0.6&0 \\ 0.3&0.7&0&0.5 \\ 0.2&0&0.7&0 \end{array}\right]$

$D_{Fig10}=diag(0.3,0.6,0.8,0.2),$ $D_{Fig11}=diag(1.2,1.1,1.5,0.9)$

and

$[D_W]_{Fig10}^+ =\left[\begin{array}{cccc} 1.357&0.262&-0.116&-1.54 \\ -0.508&0.996&0.435&-0.164 \\ -0.141&-0.487&0.572&0.181 \\ -0.709&-0.771&-0.891& 1.253 \end{array}\right]$, $[D_W]_{Fig11}^+=\left[\begin{array}{cccc} 0.503&-0.169&-0.124&-0.123 \\ -0.056&0.588&-0.123&-0.371 \\ -0.178&-0.062&0.336&-0.170 \\ -0.269 &-0.357&-0.089&0.665 \end{array}\right]$

$f(1,2)=(1,-1,0,0)’$, $f(1,3)=(1,0,-1,0)’$, $f(1,4)=(1,0,0,-1)’$, $f(2,3)=(0,1,-1,0)’$, $f(2,4)=(0,1,0,-1)’$, $f(3,4)=(0,0,1,-1)’$

For Fig.10, we have

$v(1,2)=(1.095,-1.504,0.346,0.062)’$, $v(1,3)=(1.473,-0.943,-0.713,0.182)’$, $v(1,4)=(2.897,-0.344,-0.322,-2.232)’$, $v(2,3)=(0.378,0.561,-1.059,0.120)’$, $v(2,4)=(1.802,1.160,-0.668,-2.294)’$, $v(3,4)=(1.424,0.599,0.391,-2.414)’$

$a_3(1,2)=(0.749,1.850,0,0.284)’,\; a_4(1,2)=(1.033 ,1.566 ,0.284, 0)’,$
$a_2(1,3)=(2.416,0,0.230,1.125)’,\; a_4(1,3)=(1.291, 1.125, 0.895, 0)’,$
$a_2(1,4)=(3.241, 0, 0.022, 1.888)’, \; a_3(1,4)=(3.219, 0.022, 0, 1.910)’$
$a_1(2,3)=(0, 0.183, 1.437, 0.258)’,\; a_4(2,3)=(0.258, 0.441, 1.179, 0)’$
$a_1(2,4)=(0, 0.642, 2.470, 4.096)’,\; a_3(2,4)=(2.470, 1.828, 0, 1.626)’$
$a_1(3,4)=(0, 0.825, 1.033, 0.990)’, \; a_2(3,4)=(0.825, 0, 0.208, 2.805)’ $

So

$I_3(1,2)=0.38$, $I_4(1,2)=0..207$, $I_2(1,3)=0.138$, $I_4(1,3)=0.226$, $I_2(1,4)=0.013$, $I_3(1,4)=1.921$, $I_1(2,3)=0.055$, $I_4(2,3)=0.052$, $I_1(2,4)=0.193$, $I_3(2,4)=1.554$, $I_1(3,4)=0.248$, $I_2(3,4)=0.125$
The betweenness of the vertex 1 of Fig.10 is
$b_1=2 \times \sum_{s=1}^3\sum_{t>s}^4 I_1(s,t)/(4 \times (4-1))=0.583$

Similarly,

$b_2=0.546, \; b_3=1.143, \; b_4=0.581$

The average betweenness of Fig.10 is

\[b_{Fig10}=0.573\]

For Fig.11, we can similarly calculate the betweenness, and get

$b_1=0.815$, $b_2=0.710$, $b_3=0.966$, $b_4=0.632$.

The average betweenness of Fig.11 is

\[b_{Fig11}=0.247\]

We can see that the biggest values of betweenness of vertices of this two graphs are both the vertex 3, which indicate that the vertex 3 has high centralility. The value of average betweenness of Fig.11 is smaller than Fig.10, which indicate that the centrality of Fig.11 is smaller than Fig.10. It is obvious from these two graphs.