is undeterministic SWP normal ?

[urancon]

Hello,

First of all, thanks a lot for the library. I was playing with it a bit to get to know how to use it, and I noticed that the SWP can change quite a lot from one call of small_world_propensity(...) to another.

Here is what I did:

import scipy.io as sio
import small_world_propensity as swp

cat = sio.loadmat('data/cat.mat')['CIJctx']
swp.small_world_propensity(cat, False)  # cat adjacency matrix is not binary

And here are some results:

>>> import small_world_propensity as swp
>>> import scipy.io as sio
>>> 
>>> cat = sio.loadmat('data/cat.mat')['CIJctx']
>>> swp.small_world_propensity(cat, False)
   Network C  Network L        ΔC        ΔL       SWP         α        δ  Regular C  Random C  Regular L  Random L
0   0.287849   0.400327  0.147906  0.529412  0.611314  1.298365  0.65313    0.31197  0.148886   0.411388  0.387883
>>> swp.small_world_propensity(cat, False)
   Network C  Network L        ΔC        ΔL       SWP         α         δ  Regular C  Random C  Regular L  Random L
0   0.287849   0.400327  0.155652  0.590909  0.567911  1.313236  0.672065   0.312009   0.15679   0.411639  0.383987
>>> swp.small_world_propensity(cat, False)
   Network C  Network L        ΔC        ΔL       SWP         α         δ  Regular C  Random C  Regular L  Random L
0   0.287849   0.400327  0.149944  0.567164  0.585176  1.312335  0.670917   0.311981  0.151044   0.411262  0.385998
>>> 

As you can see, the deltas can take quite different values, and therefore so can the SWP (0.06 of difference !).

This is not my original field -I only have basic knowledge in graph theory- so my question may seem naive (sorry in advance if that's the case), but is it a normal/expected behavior ? If that's just the cause of randomness in its calculation, I would expect the metric to be a bit more robust...! Is there a way to make it more robust ?

Thanks in advance for your insights, and thanks again anyways for the library.

[rkdan]

Hi there @urancon. Firstly, thanks so much for showing interest in the library, I hope that it can be of value to you!

There are two sources of randomness in the small_world_propensity calculation. One of these is in the creation of the random matrix function randomize_matrix, where edges are randomly rewired.

The second source of randomness is, perhaps surprisingly, in the regular_matrix_generator function, in an effort to preserve the degree distributions.

Unfortunately, there doesn't seem to be another way to produce these measures. I have previously tried using Watts-Strogatz graphs as the comparison graphs, but they do not preserve degree distributions.

You can either control the numpy random generator so that you get the same result each time, or (preferably) run multiple iterations so that you can get an average and a standard deviation. You should find that for the cat graph, the swp is $0.61 \pm 0.04$.

I'll leave this issue open for now, in case anybody else wants to weigh in.

[urancon]

Hello @rkdan, thanks a lot for your quick answer, it really helps ! :) I came to wonder whether the robustness of the SWP could depend with size of the adjacency matrix (the bigger the size, the less fluctuations). It seems to be verified experimentally with small tests I did on matrices of different sizes. Do you think it makes sense, more theoretically speaking ?

Last thing (a bit off-topic): I got a SWP of 1 for two big matrices (~300x300 and ~800x800, coeffs in [0, 1]), but I don't want to get overexcited. I guess that these matrices are "extremely small-world" and that their SWP is so close to 1 that your algorithm to calculate it ends up rounding it at 1. But is that even theoretically possible ? Have you ever heard of such values in the scientific literature ?

Thanks a lot again !