igraph 无效的顶点 ID

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：无法添加边，无效的顶点 ID

我发现了这个：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(weights=weight) 对吗？

我还有另一个问题；当我尝试通过以下方式添加更多集群时：

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，将图转换为无向图。由于您有边的权重属性，因此您需要指定当同一对顶点之间的 2 条相反方向的边折叠到一个无向边时 igraph 应该做什么。你可以用权重做很多事情，比如取平均值、较大的或较小的等。例如，要使组合边具有原始边的平均权重：

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

重要提示：请注意，在此操作中，以及添加或删除顶点或边时，igraph 会重新索引顶点和边，因此如果您知道顶点 ID x 对应于您的原始 ID y，重新索引后这将不再有效，您需要重新创建 name2vid 和 vid2name 词典。

igraph 无效的顶点 ID

igraph invalid vertex Id

cluster-analysis

hierarchical-clustering

igraph

python-2.7