Python iGraph - community_infomap graph

Question

I made graph with networkx, kept 70% of most weighted branches and then converted to igraph, to use community_infomap. Labels on graph are very important. If you compare graph and result of community_infomap, you can see something strange. On graph it is obvious that there are 2 communities- signals 1,2 and second group 3.4.5.6.7.8 BUT! after infomap it mess up labels, it grouped signals 3.2 and 1.4.5.6.7.8. Why, what could happend?

def nlargest_indices_orig(full, n):
full = full.copy()
x = np.zeros(n)
y = np.zeros(n)

for idx in range(n):
    x[idx] = np.unravel_index(full.argmax(), full.shape)[0]
    y[idx] = np.unravel_index(full.argmax(), full.shape)[1]
    full[full == full.max()] = 0.

return x, y

labels=[1,2,3,4,5,6,7,8]
o1 = scipy.io.loadmat('out.mat')
X=(o1['out'])
K=np.zeros((8,8))
m, n = np.shape(X)
G = nx.Graph()
for i in range(8):
    for j in range(8):
        if X[i,j]>0:
            s=labels[i]
            b=labels[j]
            w=X[i,j]
            G.add_edge(s,b,weight=w)
B=G.edges()
ND=len(B)
print('Grana ukupno')
procenat=round(0.7*ND)
x,y=nlargest_indices_orig(X, procenat)
s1=x
s2=y
for i in range(len(s2)):
    K[s1[i],s2[i]]=X[s1[i],s2[i]]
np.fill_diagonal(K, 0)
F = nx.Graph()

for i in range(8):
    for j in range(8):
        if K[i,j]>0:
            s=labels[i]
            b=labels[j]
            w=X[i,j]
            F.add_edge(s,b,weight=w)
edgewidth=[]
edgelabels={}
pos = nx.spring_layout(F) # position the nodes by force layout
plt.figure()
plt.axis('off')
print('Weighted graph')
for (u,v,d) in F.edges(data=True):
    print(u,v,d)
    edgewidth.append(d['weight'])
    edgelabels[(u,v)] = d['weight']
nx.draw_networkx_edges(F,pos,width=edgewidth,edge_color='r')
nx.draw_networkx_nodes(F,pos, alpha=0.8, node_size=400,node_color='w',scale=100)
nx.draw_networkx_labels(F,pos, font_size=12)
pylab.savefig('Graf--odabrani-sum imf.png')
plt.show()
edges = F.edges()
nodes=F.nodes()
cg = ig.Graph(edges)
cg.vs['label'] = labels
singletons = cg.vs.select(_degree = 0)
cg.delete_vertices(singletons)
degree = 0
community = cg.community_infomap()
print(len(community))
b=ig.plot(community,'infomap-odabrani-sum imf-.png')

Answer 1

To find out what happens here, we need to understand igraph's vertex indexing behaviour. Vertex indices are not stable, reindexing might happen at deletion or addition of vertices or edges. Indices always go from 0 to n-1. If you initialize a graph with integer tuples, igraph will consider the integers to be vertex indices. Your indices start from 1, so igraph will introduce a singleton vertex with index 0, which is completely wrong for you as it was not in your original network.

import igraph as ig
import networkx as nx
import pylab as plt

_edges = [
    (1, 2), 
    (3, 4), (3, 5), (3, 6), (3, 8),
    (4, 5), (4, 6), (4, 7), (4, 8),
    (5, 6), (5, 7), (5, 8),
    (6, 7), (6, 8),
    (7, 8)
]

G = nx.Graph()

for e in _edges:
    G.add_edge(e[0], e[1], weight = 1)

pos = nx.spring_layout(G)
plt.figure()
plt.axis('off')
nx.draw_networkx_edges(G, pos, edge_color='r')
nx.draw_networkx_nodes(G, pos, alpha=0.8, node_size=400, node_color='w', scale=100)
nx.draw_networkx_labels(G, pos, font_size=12)
plt.show()
plt.savefig('nx_graph1.png')

edges_from_nx = G.edges()

Try to initialize the igraph.Graph object as you did:

g = ig.Graph(edges_from_nx)

g.vcount() # returns 9. why? we supplied integers to igraph,
           # what it considered as vertex indices

'name' in g.vs.attributes() # returns False: vertices do not have names

ig.plot(g, vertex_label = range(g.vcount()))

Notice the single vertex with index 0, what you have subsequently deleted, so all the other vertices happened to be reindexed in an unpredictable way.

To avoid this, initialize the Graph object with the TupleList constructor:

g = ig.Graph.TupleList(edges_from_nx)
g.vcount() # returns 8. this looks fine!
'name' in g.vs.attributes() # returns True: good, labels are assigned
                            # to the `name` vertex attribute
ig.plot(g, vertex_label = g.vs['name'])

Now everything looks the same as in NetworkX. Note: this has nothing to do with community_infomap. If you want stable identifiers for your vertices or edges in igraph, keep them in vertex or edge attributes.