We discussed this topic in previous posts:

• Graph theory: connections in the market. To understand what a graph is and the elements it has.
• World connections using financial indexes. In this other post, you can learn how to create a graph using the correlation matrix between financial indexes from different countries of the world.

Once the graph is created, there are different statistics and measures we can use to extract a lot of information and get a better understanding of our portfolio. In this first post, we are going to learn the theory behind these concepts and measures.  Let’s start defining the different terms:

• [latex]V[/latex] is a set of vertices or nodes. [latex]v_i \in V[/latex] is the i-th vertex.
• [latex]E[/latex] is a set of edges. [latex]e_{v_i, v_j} \in E[/latex] is the edge between the vertices [latex]v_i, v_j \in V[/latex].
• The graph is represented by [latex]G(V,E)[/latex].
• [latex]n = |V|[/latex] is the number of vertices of the graph.
• [latex]m = |E|[/latex] is the number of edges of the graph.

Adjacency matrix

The adjacency matrix, [latex]A_G[/latex], represents the different connections between the vertices of the graph G(V,E). If the vertex [latex]v_i \in V[/latex] is connected with the vertex [latex]v_j \in V[/latex] through the edge [latex]e_{v_i, v_j} \in E[/latex], then the positions (i, j) and (j, i) of the matrix are 1; if not both are 0. The adjacency matrix is symmetric and it is defined as follows:

[latex]A_G = a_{i,j} = \left\{ \begin{matrix} 1 & if & e_{v_i, v_j} \in E \\ 0 & if & e_{v_i, v_j} \not\in E \end{matrix} \right. \quad \forall v_i,v_j \in V[/latex]

In the next example we can see the adjacency matrix of a simple graph.

Neighbours of a vertex

The neighbours of a vertex [latex]v_i \in V[/latex] is a subset of V, [latex]N_{v_i} \in V[/latex], including all the vertices connected with it.

[latex]N_{v_i} = \left\{ v_j \; : \; v_j \in V \wedge e_{v_i, v_j} \in E \right\} \quad \forall v_j \in V [/latex]

Degree of a vertex

The degree of a vertex [latex]v_i \in V[/latex] is the number of connected vertices or neighbours this vertex has.

[latex]deg\left( v_i \right) = {\delta}_{v_i} = \left| N_{v_i} \right| [/latex]

The maximum and minimum degree of a graph G are represented by [latex]\Delta(G)[/latex] y [latex]\delta(G)[/latex], respectively. They could be defined as follows:

[latex]\Delta(G) = max\left({\delta}_{v_i}\right) \quad \forall v_i \in V[/latex]

[latex]\delta(G) = min\left({\delta}_{v_i}\right) \quad \forall v_i \in V[/latex]

Degree matrix

The degree matrix, [latex]{\Delta}_G[/latex], has 0 in all its elements except the diagonal in which it is shown the degree for each vertex.

[latex]{\Delta}_G = d_{i,j} = \left\{ \begin{matrix} {\delta}_{v_i} & if & i=j \\ 0 & if & i \neq j \end{matrix} \right. \quad \forall v_i \in V [/latex]

In the next example we can see the degree matrix of the same simple graph.

Clustering coefficient

[latex]C_{v_i}[/latex] is the clustering coefficient of the vertex [latex]v_i \in V[/latex] and it is a real number in the interval [latex]\left[0, 1\right][/latex]. This measure quantifies the number of existing connections between the neighbours of that vertex [latex]v_i[/latex] in comparison to the number of posible connections, i.e., it shows if there are triple connections (triangles). It is said that there is a strong clustering around the vertex [latex]v_i[/latex] when this measure is close to 1.

[latex]C_{v_i}=\frac{2}{{\delta}_{v_i}\left({\delta}_{v_i}-1\right)}\left|t_{v_i}\right| \quad : \quad {\delta}_{v_i} > 1[/latex]

Where [latex]t_{v_i}[/latex] is the set of edges that connect [latex]v_j[/latex] and [latex]v_k[/latex] and both vertices are neighbours of [latex]v_i[/latex] ([latex]v_j,v_k \in N_{v_i}, \, e_{v_j, v_k} \in E[/latex]).

The clustering coefficient of a graph G, [latex]C(G)[/latex], is an equally-weighted mean of the clustering coefficients of each vertex of the graph. When the clustering coefficient, [latex]C(G)[/latex], is close to 1 it shows that all the vertices are inter-connected and all possibles triple connections exists. A high clustering coefficient shows a high robustness.

[latex]C(G) = \frac{1}{N} \sum_{v_i \in V; {\delta}_{v_i}>1} C_{v_i}[/latex]

Distance between two vertices

The distance between two vertices [latex]v_i, v_j \in V[/latex] is the minimum number of edges necessary to go from one vertex to the other. It is represented by [latex]d_{v_i, v_j}[/latex]. The BFS or Breadth-first search algorithm calculates this measure in complex graphs.

Distance matrix

The distance matrix of a graph G is symmetric and contains the minimum distances between each pair of vertices. It is represented by [latex]D_G[/latex] and the diagonal is 0.

[latex]D_G = d_{i,j} = \left\{ \begin{matrix} d_{v_i, v_j} & if & i \neq j \\ 0 & if & i=j \end{matrix} \right. \quad \forall v_i,v_j \in V[/latex]

Average distance

The average distance of a graph G, [latex]\bar{d}(G)[/latex], is defined as follows:

[latex]\bar{d}(G) = \frac{2}{n(n-1)}\sum_{i=1}^{n} \sum_{j=i+1}^{n} d_{v_i, v_j} \quad \forall v_i, v_j \in V [/latex]

Diameter

The diameter, [latex]{d}^{max}(G)[/latex], is the maximum of the minimum existing distances between two vertices of the graph G:

[latex]d^{max}(G) = max \left( \left\{d_{v_i, v_j}, \, \forall v_i, v_j \in V, \, v_i \neq v_j \right\} \right)[/latex]

The lower the value of these measures, the greater the robustness of the graph.

Efficiency

The graph efficiency is a measure that shows the effectiveness in the information exchange between two vertices. The average graph efficiency of a graph is defined as follows:

[latex]E(G) = \frac{2}{n(n-1)}\sum_{i=1}^{n} \sum_{j=i+1}^{n} \frac{1}{d_{v_i, v_j}} \quad \forall v_i, v_j \in V[/latex]

Connection density or cost

The connection density or cost is the number of existing edges, m, in the graph G in relation to the total number of possible edges. It is the simplest estimator of the physical cost of a network.

[latex]D(G) = \frac{2m}{n(n-1)}[/latex]

Intermediation

The intermediation of a vertex [latex]v_i[/latex] or an edge [latex]e_{v_i, v_j}[/latex] is the number of shortest paths between two vertices [latex]v_k, v_l \in V[/latex] that include the vertex [latex]v_i[/latex] or the edge [latex]e_{v_i, v_j}[/latex].

Average intermediation of vertices

The average intermediation of a vertex is defined as follows:

[latex]\bar{b}_v (G) = \frac{1}{2}(n-1)\left(\bar{d}(G)+1\right)[/latex]

Average intermediation of an edge

The average intermediation of an edge is defined as follows:

[latex]\bar{b}_e (G) = \frac{n(n-1)}{2m}\bar{d}(G)[/latex]

In the next Graph Theory post we will see an example of how to apply these statistics and measures to a real case. They will be useful to analyse the universe of our portfolio and check its diversification.