I am studying small-world networks and I came across the formula of Small World Propensity (reference: https://doi.org/10.1371/journal.pone.0216146.s001). And I am having trouble understanding the Lattice in the formula. Please find the detailed problem after the definition.
Definition: The small-world propensity measures the extent to which a network is characterized by high levels of local clustering and low average path length. It is defined as follows:
$\Phi = 1-\sqrt{\frac{{\Delta_T}^2+{\Delta_L}^2}{2}}$
where
$\Delta_T = \frac{T_{lattice}-T_{observed}}{T_{lattice}-T_{random}}$
and
$\Delta_L = \frac{L_{observed}-L_{random}}{L_{lattice}-L_{random}}$
with
$L$ being the path length of a network, i.e. the average shortest path length between all node pairs, and $T$ representing the network clustering (transitivity) coefficient, defined as the average of node-specific clustering coefficient values.
Problem: I am trying to code this using the python-igraph
library and my understanding is that the we have to calculate $T$ and $L$ values using –
- random graph for $T_{random}$ and $L_{random}$
- k-regular graph for $T_{lattice}$ and $L_{lattice}$
but when I checked the documentation of igraph
I noticed that apart from K_Regular(n, k)
function (ref. page no. 123 in the pdf) there is a separate function called Lattice(dim)
(ref. page no. 124 in the pdf) that generates a regular lattice. Screenshots attached below, in case this pdf is removed in the future.
Now, I am confused that should I use K_Regular(n, k)
or Lattice(dim)
to calculate $T_{lattice}$ and $L_{lattice}$? And what is the difference between these two functions?
Best Answer
Apparently, my understanding of creating the regular graphs was wrong in the case of Small World Propensity.
I did a discussion with people working in the field of brain connectivity and with the help of this paper (in this Small World Propensity is originally discussed), I was able to figure out the meaning of lattice used in this context.
Below I am quoting a few points from the paper that helped me figure it out.
In section Generating Weighted Small-World Networks
In Figure 3a shows that the initial lattice is a circular graph in which every node is connected to
n
neighbours both on left and right.Now, this confirmed that I needed to use
Lattice(dim)
for generating the initial lattice, but now a second question arose - what should be the value ofdim
?This was answered in this paper, Figure 2a has explained that such a lattice is A periodic one-dimensional ( D = 1 ) lattice (i.e. a ring) where each vertex is connected to its n neighbours on left and right.
and the documentation of
igraph
forLattice
confirmed that I need to put a list containing 1 element (1 dimension), and the value of that element should be the number of nodes to be generated, further, I need to put the number of neighbours on either side to directly connect.So, If I need 20 nodes and connect 3 neighbours in each direction (so total of 6 neighbours will be connected), function should be:
This generates the following graph.