的igraph无效顶点标识

Question

我尝试使用下面的代码运行的igraph快速贪婪社区检测算法：

G = Graph() 

L = [] 
V = [] 
for row in cr: 

    try: 
     l = [] 
     source = int((row[0]).strip()) 
     target = int((row[1]).strip()) 
     weight = int((row[2]).strip()) 
     l.append(source) 
     l.append(target) 

     if l not in L: 
      L.append(l) 

     if source not in V: 
      V.append(source) 

     if target not in V: 
      V.append(target) 
    except ValueError: 
     print "Value Error" 
     continue 

    if weight == 1: 
     continue 

G.add_vertices(max(V)) 
G.add_edges(L) 
cl = G.community_fastgreedy(weights=weight).as_clustering(10); 

但是，这是我得到的错误： igraph._igraph.InternalError：错误的type_indexededgelist.c：272：无法添加边缘，无效的顶点编号

我发现这个：Cannot add edges, Invalid vertex ID in IGraph所以我尝试添加所有的顶点，然后所有的边缘，但我仍然得到一个错误。

请问上面的代码做同样的事情：

tupleMapping = [] 
for row in cr: 
    if int(row[2]) < 10: 
     continue 

    l = [row[0], row[1], row[2]] 
    tupleMapping.append(tuple(l)) 

g = Graph.TupleList(tupleMapping) 
cl = g.community_fastgreedy().as_clustering(20) 

我没有明确地说G.community_fastgreedy（权重=体重）吧？

我还有另外一个问题;当我尝试以下列方式增加更多的集群：

cl = g.community_fastgreedy().as_clustering(10) 
cl = g.community_fastgreedy().as_clustering(20) 

我得到两个大型集群和集群的其余部分构成一个元素。当我尝试将群集大小设置为5/10/20时，会发生这种情况，是否有任何方法可以使群集更加平均分配？我需要超过2个集群用于我的数据集。

这是我试图从CSV文件中读取，这样我可以生成图形，然后运行该社区检测算法的数据的一个小片段： 202,580,11 87,153,7 227,459,6 263,524,11

谢谢。

Answer 1

没错，第二个代码也是这样。在第一个例子中，问题是当你添加边时，你引用igraph的内部顶点ID，它始终从0开始，直到N-1。无论你自己的顶点名称是整数，你都需要将它们翻译为igraph顶点ID。

这里的igraph.Graph.TupleList()方法要方便得多。但是，您需要指定元组的第三个元素是重量。您可以通过weights = True或edge_attrs = ['weight']参数做到这一点：

import igraph 

data = '''1;2;34 
1;3;41 
1;4;87 
2;4;12 
4;5;22 
5;6;33''' 

L = set([]) 

for row in data.split('\n'): 
    row = row.split(';') 
    L.add(
     (row[0].strip(), row[1].strip(), int(row[2].strip())) 
    ) 

G = igraph.Graph.TupleList(L, edge_attrs = ['weight']) 

然后，您可以创建词典来的igraph顶点ID和你原来的名称之间进行转换：

vid2name = dict(zip(xrange(G.vcount()), G.vs['name'])) 
name2vid = dict((name, vid) for vid, name in vid2name.iteritems()) 

然而，第一个是没有那么多需要，因为您始终可以使用G.vs[vid]['name']。

对于fastgreedy，我认为你应该指定权重，至少文档不会告诉它是否会自动考虑名为weight的属性（如果此属性存在）。

fg = G.community_fastgreedy(weights = 'weight') 
fg_clust_10 = fg.as_clustering(10) 
fg_clust_20 = fg.as_clustering(20) 

如果fastgreedy只给你2个大集群，我只能推荐尝试其他社区检测方法。其实你可以尝试所有在合理时间内运行的程序（这取决于你的图形大小），然后比较它们的结果。另外，因为你有一个加权图，你可以看看moduland method family，这在igraph中没有实现，但有很好的文档，你可以设置很复杂的设置。

编辑： OP的意见建议原始数据描述有向图。 fastgreedy算法无法考虑方向，如果在有向图上调用，则会出现错误。这就是为什么在我的例子中，我创建了一个无向igraph.Graph()对象。如果你想运行其他方法，其中一些可能能够应对向网络，首先需要创建一个有向图：

G = igraph.Graph.TupleList(L, directed = True, edge_attrs = ['weight']) 
G.is_directed() 
# returns True 

要fastgreedy运行，图形转换为无向。由于您有边的权重属性，因此需要指定在同一对顶点之间的相反方向的两条边折叠为一条无向边时，应该执行的操作。你可以做很多事情的权重，如取均值，较大或较小的一个，等等。例如，要使合并边缘的平均重量的原边：

uG = G.as_undirected(combine_edges = 'mean') 
fg = uG.community_fastgreedy(weights = 'weight') 

重要：请注意，在此操作中以及添加或删除顶点或边时，igraph会重新对顶点和边进行编制索引，因此如果您知道顶点编号x与您的原始编号y相对应，重新编索引之后将无效，您需要重新创建name2vid和vid2name字典。