O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

images

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 bi for each graph vertex and then sums up over all vertices to define the second small-world connectivity index B2:

images

The distribution of the vertex bi descriptors, B2{b1, b2, b3,..., bk}, can then be considered an important integrated distribution of vertex connectivity ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required