Analysis of Complex Networks

3.2 The Small-World Connectivity Descriptors (Bourgas Indices, BI)

The simplest way to integrate the information on network connectivity and distances is to use the ratio of the network total adjacency and total distance, A and D [29, 32]:

The rationale for Equation (3.5) is straightforward: the graph (or network) complexity increases with the increase in the number of edges (links) E, where for undirected graphs A = 2E, and with the more compact “smallworld” type of structure organization, that is with a smaller graph radius, and smaller total graph distance D.

The B1 index is a fast approximate measure of graph complexity, which will be illustrated by some examples in Figures 3.1 and 3.2. However, due to the fact that both A and D are additive functions, the same values could emerge from different vertex degree and vertex distance distributions. This partial degeneracy of B1 can be avoided (or at least very strongly reduced) if instead of using directly A and D, one proceeds with such vertex degree/vertex distance ratios b_i for each graph vertex and then sums up over all vertices to define the second small-world connectivity index B2:

The distribution of the vertex b_i descriptors, B2{b₁, b₂, b₃,..., b_k}, can then be considered an important integrated distribution of vertex connectivity ...