使用Igraph图形库确定介数中心性

Question

我是一个非常平庸的程序员，但我仍然希望使用igraph Python库来确定用户在给定论坛中的中心性对他以后对该论坛的贡献的影响。

我联系了另一个人，他使用NetworkX库做了类似的事情，但考虑到论坛当前的规模，计算准确的中心性指数几乎是不可能的 - 它需要太多时间。

这是他的代码：

import networkx as netx
import sys, csv

if len(sys.argv) is not 2:
   print 'Please specify an input graph.'
   sys.exit(1)

ingraph = sys.argv[1]
graph = netx.readwrite.gpickle.read_gpickle(ingraph)

num_nodes = len(graph.nodes())
print '%s nodes found in input graph.' % num_nodes
print 'Recording data in centrality.csv'

# Calculate all of the betweenness measures
betweenness = netx.algorithms.centrality.betweenness_centrality(graph)
print 'Betweenness computations complete.'
closeness = netx.algorithms.centrality.closeness_centrality(graph)
print 'Closeness computations complete.'

outcsv = csv.writer(open('centrality.csv', 'wb'))

for node in graph.nodes():
   outcsv.writerow([node, betweenness[node], closeness[node]])

print 'Complete!'

我尝试使用igraph库编写类似的代码（该库允许进行快速估算而不是精确计算），但我似乎无法将数据写入CSV文件。

我的代码：

import igraph
import sys, csv

from igraph import *

graph = Graph.Read_Pajek("C:\karate.net")

print igraph.summary(graph)

estimate = graph.betweenness(vertices=None, directed=True, cutoff=2)
print 'Betweenness computation complete.'

outcsv = csv.writer(open('estimate.csv', 'wb'))

for v in graph.vs():
   outcsv.writerow([v, estimate[vs]])

print 'Complete!'

我在igraph文档中找不到如何调用单个顶点（或节点，在NetworkX术语中）的方法，所以我一直收到错误消息。也许我还忘了其他事情；我可能太差了，无法注意到:P

我做错了什么？

- daniel_ev

---

我相信这就是在igraph中调用单个顶点的方法，@danihp！ - daniel_ev

vs 是图形对象的一个属性，它的行为类似于顶点列表，因此将其用作 estimate 的索引是不正确的（因为单独使用 vs 是未定义的变量）。您应该使用 v.index 代替 vs。 - Tamás

Answer 1

因为需要清晰易懂，最终证明以下方法是行之有效的：

import igraph
import sys, csv

from igraph import *
from itertools import izip

graph = Graph.Read_GML("C:\stack.gml")

print igraph.summary(graph)

my_id_to_igraph_id = dict((v, k) for k, v in enumerate(graph.vs["id"]))

estimate = graph.betweenness(directed=True, cutoff=16)
print 'Betweenness computation complete.'

print graph.vertex_attributes()

outcsv = csv.writer(open('estimate17.csv', 'wb'))

outcsv.writerows(izip(graph.vs["id"], estimate))

print 'Complete!'

- daniel_ev

---

嗨，丹尼尔，我注意到你在这个例子中选择了cutoff=16，我想知道在选择截断值时是否有什么经验法则？我有150万个顶点和1100万条边，你有什么建议可以选择截断值吗？ - Psyduck

Answer 2

正如您已经注意到的那样，使用图形对象的vs属性可以访问igraph中的单个定点。 vs的行为类似于列表，因此对其进行迭代将产生图形的顶点。每个顶点都由Vertex类的实例表示，顶点的索引由其index属性给出。 （请注意，igraph对顶点和边缘都使用连续的数字索引，因此需要index属性，而不能直接使用原始顶点名称）。

我假设您需要的是最初存储在输入文件中的顶点的名称。名称存储在name或id顶点属性中（取决于您的输入格式），因此您可能需要这个：

for v in graph.vs:
    outcsv.writerow([v["name"], estimate[v.index]])

请注意，顶点属性可以通过将顶点对象索引为字典来访问。另一种方法是直接将vs对象用作字典；这将为您提供一个包含所有顶点给定属性值的列表。例如：

from itertools import izip

for name, est in izip(graph.vs["name"], estimate):
    outcsv.writerow([name, est])

使用生成器表达式的更快版本：

outcsv.writerows(izip(graph.vs["name"], estimate))

- Tamás

---

你需要决定是否使用“import igraph”（在这种情况下，你必须使用“igraph.Graph.Read_Pajek”构建你的图形），或者使用“from igraph import *”（在这种情况下，你只需要“summary(graph)”）。此外，你不需要“import itertools”，只需要“from itertools import izip”。除此之外，对我来说看起来都很好。 - Tamás

那么，我理解完整的代码是这样的：（...） graph = Graph.Read_Pajek("C:\karate.net") print igraph.summary(graph) estimate = graph.betweenness(vertices=None, directed=True, cutoff=2) print 'Betweenness computation complete.' outcsv = csv.writer(open('estimate.csv', 'wb')) outcsv.writerows(izip(graph.vs["name"], estimate)) print 'Complete!' 抱歉，我无法在评论中换行。无论如何，@tamas，上述代码会导致outcsv.writerows(izip(graph(vs["name"], estimate))出现“KeyError: 'Attribute does not exist'”错误。有什么想法吗？ - daniel_ev

尝试使用"id"而不是"name"，或者使用print graph.vertex_attributes()列出顶点属性，以确定哪个属性包含您需要的顶点名称。 - Tamás

使用“id”而不是名称产生了相同的错误；打印graph.vertex_attributes()只返回了[]。如果我显得很愚蠢，我很抱歉——我还是比较新手的:P - daniel_ev

看起来你的图没有顶点属性，这种情况下你只能通过其数字索引来识别顶点。因此，只需使用outcsv.writerows(enumerate(estimate))即可。 - Tamás

考虑到你在igraph邮件列表上的进一步评论，@Tamas，我现在遇到了一个错误：“izip参数＃2必须支持迭代”。有什么想法吗？ - daniel_ev