The computation time of small-world coefficient?

Software Support
,
1

Hi everyone,

I am in the process of calculating the small-world coefficient with NetworkX from Python.

This line of code “small_world_coefficient = nx.algorithms.smallworld.sigma(G, niter=100, nrand=10)” has cost me more than 50 hours for a single subject.

I am just wondering if this is normal to take this long to calculate this indicator.

Your suggestion will be highly appreciated. Thanks for your time and assistance in advance.

2

Hi @Wanrong, and welcome to Neurostars!

It would help to know what G is, e.g., how it was made and its size.

Best,
Steven

4

Hi Steven,

Thanks for your attention.

The G is a sparsified array matrix with a dimension of 300*300. The values of this matrix are the resting state functional connectivities.

Best,
Wan

5

Hi @Wanrong,

I tried that command and also found that it was taking a long time, try this instead (courtesy of ChatGPT)?

def small_world_coefficient(adj_matrix):
    G = nx.Graph(adj_matrix)
    L = nx.average_shortest_path_length(G)
    C = nx.average_clustering(G)
    
    # Random graph with the same number of nodes and edges
    random_graph = nx.erdos_renyi_graph(G.number_of_nodes(), G.number_of_edges() / (G.number_of_nodes() * (G.number_of_nodes() - 1) / 2))
    L_random = nx.average_shortest_path_length(random_graph)
    C_random = nx.average_clustering(random_graph)
    
    # Calculate small-world coefficient (sigma)
    sigma = (C / C_random) / (L / L_random)
    
    return sigma

where adj_matrix is a numpy array of the connectivity matrix.

Best,
Steven

6

Hi Steven:

Thank you very much for your recommendation and for sharing the command you found helpful.

I’ve reviewed the codes and noted their efficiency. However, they seem to calculate small world coefficient by comparing the real network to one single random network. Considering the randomness in generating a random network, it will inadvertently introduce system bias to this indicator. To address this, nx.algorithms.smallworld.sigma algorithm generates 100 random networks for comparison. Maybe that’s why this processing time is extensive, though more than 50 hours per subject seem unusually prolonged.

Your suggestion inspired me a lot. Motivated by your ideas, I’m planning to modify the codes that you provided to achieve these demands, hopefully. I will keep you in the loop if it works.

Thanks for your valuable input :slight_smile:

1 Like