Python iGraph - community_infomap 图

Question

我用 networkx 制作了图形，保留了 70% 的大多数加权分支，然后转换为 igraph，以使用 community_infomap。图上的标签非常重要。如果比较图表和 community_infomap 的结果，您会发现一些奇怪的东西。在图表上很明显有 2 个社区 - 信号 1,2 和第二组 3.4.5.6.7.8 但是!在 infomap 之后它弄乱了标签，它将信号 3.2 和 1.4.5.6.7.8 分组。为什么，会发生什么？

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

要了解这里发生了什么，我们需要了解 igraph 的顶点索引行为。顶点索引不稳定，重新索引可能会在删除或添加顶点或边时发生。索引总是从 0 到 n-1。如果用整数元组初始化图，igraph 会将整数视为顶点索引。您的索引从 1 开始，因此 igraph 将引入索引为 0 的单例顶点，这对您来说是完全错误的，因为它不在您的原始网络中。

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()

像您一样尝试初始化 igraph.Graph 对象:

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()))

请注意索引为 0 的单个顶点，您随后删除了它，因此所有其他顶点碰巧以不可预知的方式重新编制了索引。

为避免这种情况，请使用 TupleList 构造函数初始化 Graph 对象:

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'])

现在一切看起来都与 NetworkX 中的一样。注意:这与 community_infomap 无关。如果您希望 igraph 中的顶点或边具有稳定的标识符，请将它们保存在顶点或边属性中。