CODEWITHSUNDEEP
pythonigraph
user299791
user299791

Reputation: 2070

k-regular small world network with igraph

I am using igraph to produce random networks where nodes have the same degree, using the K_Regular() function. I am wondering if there is an analogous function to have a Small World network where nodes share the same degree.

I wrote my own function, reasonably fast with <500 nodes, but somewhat slow when generating networks with 5000 nodes.

I start by generating a regular lattice, and then I take care of rewiring the edges with a small probability:

g = igraph.Graph.Lattice([1,5000], nei=8, directed=False, mutual=True, circular=True)
for e in g.es:
    # if we randomize this link
    if random.uniform(0,1) < 0.05:
        # pick the nodes
        end1 = e.tuple[0]
        # pool
        pool = [n for n in range(0, g.vcount())]
        #
        end2 = random.choice([i for i in pool if i != end1 and i not in g.neighbors(end1)])
        # create link end1-end2
        if end1 < end2:
            g.add_edge(end1, end2)
        else:
            g.add_edge(end2, end1)
        # rewire the other end of this link
        end3 = e.tuple[1]
        # 
        end4 = random.choice([i for i in pool if i != end3\
                              and i in g.neighbors(end2)\
                              and i not in g.neighbors(end3)])
        # create link end3-end4
        if end3 < end4:
            g.add_edge(end3, end4)
        else:
            g.add_edge(end4, end3)
        # delete old edge
        g.delete_edges((e))
        g.delete_edges((end2, end4))

I saw this but to be honest I don't get how to specify the rewiring probability...

So I guess it could be:

g = igraph.Graph.Lattice([1,5000], nei=8, directed=False, mutual=True, circular=True)
g.rewire(n=int(g.ecount()*0.05), mode="simple") # say you want a 0.05 prob

Upvotes: 0

Views: 599

Answers (1)

Paul Brodersen
Paul Brodersen

Reputation: 13031

"Small worldness" is not a rigorously defined quantity. So in some sense your question is unanswerable. That being said a plot of mean distance versus rewiring probability is usually quite informative as to what the minimum probability is that results in a graph with a short average distance. With p=0.05 you are definitely in a regime where the average distance is pretty small compared to the regular graph (~5 versus ~160 hops), and where increasing the rewiring probability yields strongly diminishing returns.

enter image description here

import numpy as np
import matplotlib.pyplot as plt
import igraph

rewiring_probability = np.logspace(-3., -1., 10.)
closeness_centrality = np.zeros_like(rewiring_probability)
g = igraph.Graph.Lattice([1,5000], nei=8, directed=False, mutual=True, circular=True)
E = g.ecount()

for ii, p in enumerate(rewiring_probability):
    print("Iteration {}, p = {}".format(ii, p))
    h = g.copy() # creates a deepcopy
    n = int(p * E)
    h.rewire(n=n, mode="simple")
    closeness_centrality[ii] = np.mean(h.closeness())

fig, ax = plt.subplots(1,1)
ax.plot(rewiring_probability, 1./closeness_centrality)
ax.set_xlabel('Rewiring probability')
ax.set_ylabel('Mean distance')
plt.show()

Upvotes: 0

Related Questions