Networkx 永远不会完成 200 万个节点的介数中心性计算
Networkx never finishes calculating Betweenness centrality for 2 mil nodes
我有一个简单的 Twitter 用户图，其中包含大约 200 万个节点和 500 万条边。我正在尝试使用 Centrality。但是，计算需要很长时间（一个多小时）。我不认为我的图表非常大，所以我猜我的代码可能有问题。
这是我的代码。
%matplotlib inline
import pymongo
import networkx as nx
import time
import itertools
from multiprocessing import Pool
from pymongo import MongoClient
from sweepy.get_config import get_config
config = get_config()
MONGO_URL = config.get('MONGO_URL')
MONGO_PORT = config.get('MONGO_PORT')
MONGO_USERNAME = config.get('MONGO_USERNAME')
MONGO_PASSWORD = config.get('MONGO_PASSWORD')
client = MongoClient(MONGO_URL, int(MONGO_PORT))
db = client.tweets
db.authenticate(MONGO_USERNAME, MONGO_PASSWORD)
users = db.users
graph = nx.DiGraph()
for user in users.find():
graph.add_node(user['id_str'])
for friend_id in user['friends_ids']:
if not friend_id in graph:
graph.add_node(friend_id)
graph.add_edge(user['id_str'], friend_id)
数据在MongoDB。这是数据示例。
{
"_id" : ObjectId("55e1e425dd232e5962bdfbdf"),
"id_str" : "246483486",
...
"friends_ids" : [
// a bunch of ids
]
}
我尝试使用中间中心性并行来加速，但它仍然非常慢。
https://networkx.github.io/documentation/latest/examples/advanced/parallel_betweenness.html
"""
Example of parallel implementation of betweenness centrality using the
multiprocessing module from Python Standard Library.
The function betweenness centrality accepts a bunch of nodes and computes
the contribution of those nodes to the betweenness centrality of the whole
network. Here we divide the network in chunks of nodes and we compute their
contribution to the betweenness centrality of the whole network.
"""
def chunks(l, n):
"""Divide a list of nodes `l` in `n` chunks"""
l_c = iter(l)
while 1:
x = tuple(itertools.islice(l_c, n))
if not x:
return
yield x
def _betmap(G_normalized_weight_sources_tuple):
"""Pool for multiprocess only accepts functions with one argument.
This function uses a tuple as its only argument. We use a named tuple for
python 3 compatibility, and then unpack it when we send it to
`betweenness_centrality_source`
"""
return nx.betweenness_centrality_source(*G_normalized_weight_sources_tuple)
def betweenness_centrality_parallel(G, processes=None):
"""Parallel betweenness centrality function"""
p = Pool(processes=processes)
node_divisor = len(p._pool)*4
node_chunks = list(chunks(G.nodes(), int(G.order()/node_divisor)))
num_chunks = len(node_chunks)
bt_sc = p.map(_betmap,
zip([G]*num_chunks,
[True]*num_chunks,
[None]*num_chunks,
node_chunks))
# Reduce the partial solutions
bt_c = bt_sc[0]
for bt in bt_sc[1:]:
for n in bt:
bt_c[n] += bt[n]
return bt_c
print("Computing betweenness centrality for:")
print(nx.info(graph))
start = time.time()
bt = betweenness_centrality_parallel(graph, 2)
print("\t\tTime: %.4F" % (time.time()-start))
print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0]))
从Mongodb到networkx的导入过程比较快，不到一分钟。
TL/DR：介数中心性的计算速度非常慢，因此您可能希望通过考虑 myk 节点的子集来使用近似度量，其中 myk 的数量要少得多比网络中的节点数多，但大到足以具有统计意义（NetworkX 对此有一个选项：betweenness_centrality(G, k=myk).
花了很长时间我一点也不惊讶。中介中心性是一个缓慢的计算。 networkx 使用的算法是 O(VE)，其中 V 是顶点数，E 是边数。在你的情况下 VE = 10^13。我预计导入图表需要 O(V+E) 时间，所以如果这花费的时间足够长以至于你可以看出它不是瞬时的，那么 O(VE) 会很痛苦。
如果具有 1% 的节点和 1% 的边（即 20,000 个节点和 50,000 条边）的简化网络需要时间 X，那么您所需的计算将花费 10000 倍。如果 X 是一秒，那么新的计算结果接近 3 小时，我认为这是非常乐观的（见下面我的测试）。因此，在您确定您的代码有问题之前，运行 它会在一些较小的网络上运行，并估计您的网络的 运行 时间应该是多少。
一个好的替代方法是使用近似度量。标准介数度量考虑每一对节点和它们之间的路径。 Networkx 提供了一种替代方法，它使用仅 k 个节点的随机样本，然后找到这些 k 个节点与网络中所有其他节点之间的最短路径。我认为这应该在 O(kE) 时间
内加速到 运行
所以你要用的是
betweenness_centrality(G, k=k)
如果您想限制结果的准确度，可以使用较小的 k 进行多次调用，确保它们相对接近，然后取平均结果。
这是我对 运行 时间的一些快速测试，随机图形为 (V,E)=(20,50)； (200,500);和 (2000,5000)
import time
for n in [20,200,2000]:
G=nx.fast_gnp_random_graph(n, 5./n)
current_time = time.time()
a=nx.betweenness_centrality(G)
print time.time()-current_time
>0.00247192382812
>0.133368968964
>15.5196769238
所以在我的电脑上处理一个只有你的 0.1% 大小的网络需要 15 秒。做一个和你一样大的网络大约需要 1500 万秒。那是 1.5*10^7 秒，略低于 pi*10^7 秒的一半。由于 pi*10^7 秒是一年中秒数的非常好的近似值，这将花费我的计算机大约 6 个月的时间。
因此您需要 运行 使用近似算法。
我有一个简单的 Twitter 用户图，其中包含大约 200 万个节点和 500 万条边。我正在尝试使用 Centrality。但是，计算需要很长时间（一个多小时）。我不认为我的图表非常大，所以我猜我的代码可能有问题。
这是我的代码。
%matplotlib inline
import pymongo
import networkx as nx
import time
import itertools
from multiprocessing import Pool
from pymongo import MongoClient
from sweepy.get_config import get_config
config = get_config()
MONGO_URL = config.get('MONGO_URL')
MONGO_PORT = config.get('MONGO_PORT')
MONGO_USERNAME = config.get('MONGO_USERNAME')
MONGO_PASSWORD = config.get('MONGO_PASSWORD')
client = MongoClient(MONGO_URL, int(MONGO_PORT))
db = client.tweets
db.authenticate(MONGO_USERNAME, MONGO_PASSWORD)
users = db.users
graph = nx.DiGraph()
for user in users.find():
graph.add_node(user['id_str'])
for friend_id in user['friends_ids']:
if not friend_id in graph:
graph.add_node(friend_id)
graph.add_edge(user['id_str'], friend_id)
数据在MongoDB。这是数据示例。
{
"_id" : ObjectId("55e1e425dd232e5962bdfbdf"),
"id_str" : "246483486",
...
"friends_ids" : [
// a bunch of ids
]
}
我尝试使用中间中心性并行来加速，但它仍然非常慢。 https://networkx.github.io/documentation/latest/examples/advanced/parallel_betweenness.html
"""
Example of parallel implementation of betweenness centrality using the
multiprocessing module from Python Standard Library.
The function betweenness centrality accepts a bunch of nodes and computes
the contribution of those nodes to the betweenness centrality of the whole
network. Here we divide the network in chunks of nodes and we compute their
contribution to the betweenness centrality of the whole network.
"""
def chunks(l, n):
"""Divide a list of nodes `l` in `n` chunks"""
l_c = iter(l)
while 1:
x = tuple(itertools.islice(l_c, n))
if not x:
return
yield x
def _betmap(G_normalized_weight_sources_tuple):
"""Pool for multiprocess only accepts functions with one argument.
This function uses a tuple as its only argument. We use a named tuple for
python 3 compatibility, and then unpack it when we send it to
`betweenness_centrality_source`
"""
return nx.betweenness_centrality_source(*G_normalized_weight_sources_tuple)
def betweenness_centrality_parallel(G, processes=None):
"""Parallel betweenness centrality function"""
p = Pool(processes=processes)
node_divisor = len(p._pool)*4
node_chunks = list(chunks(G.nodes(), int(G.order()/node_divisor)))
num_chunks = len(node_chunks)
bt_sc = p.map(_betmap,
zip([G]*num_chunks,
[True]*num_chunks,
[None]*num_chunks,
node_chunks))
# Reduce the partial solutions
bt_c = bt_sc[0]
for bt in bt_sc[1:]:
for n in bt:
bt_c[n] += bt[n]
return bt_c
print("Computing betweenness centrality for:")
print(nx.info(graph))
start = time.time()
bt = betweenness_centrality_parallel(graph, 2)
print("\t\tTime: %.4F" % (time.time()-start))
print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0]))
从Mongodb到networkx的导入过程比较快，不到一分钟。
TL/DR：介数中心性的计算速度非常慢，因此您可能希望通过考虑 myk 节点的子集来使用近似度量，其中 myk 的数量要少得多比网络中的节点数多，但大到足以具有统计意义（NetworkX 对此有一个选项：betweenness_centrality(G, k=myk).
花了很长时间我一点也不惊讶。中介中心性是一个缓慢的计算。 networkx 使用的算法是 O(VE)，其中 V 是顶点数，E 是边数。在你的情况下 VE = 10^13。我预计导入图表需要 O(V+E) 时间，所以如果这花费的时间足够长以至于你可以看出它不是瞬时的，那么 O(VE) 会很痛苦。
如果具有 1% 的节点和 1% 的边（即 20,000 个节点和 50,000 条边）的简化网络需要时间 X，那么您所需的计算将花费 10000 倍。如果 X 是一秒，那么新的计算结果接近 3 小时，我认为这是非常乐观的（见下面我的测试）。因此，在您确定您的代码有问题之前，运行 它会在一些较小的网络上运行，并估计您的网络的 运行 时间应该是多少。
一个好的替代方法是使用近似度量。标准介数度量考虑每一对节点和它们之间的路径。 Networkx 提供了一种替代方法，它使用仅 k 个节点的随机样本，然后找到这些 k 个节点与网络中所有其他节点之间的最短路径。我认为这应该在 O(kE) 时间
所以你要用的是
betweenness_centrality(G, k=k)
如果您想限制结果的准确度，可以使用较小的 k 进行多次调用，确保它们相对接近，然后取平均结果。
这是我对 运行 时间的一些快速测试，随机图形为 (V,E)=(20,50)； (200,500);和 (2000,5000)
import time
for n in [20,200,2000]:
G=nx.fast_gnp_random_graph(n, 5./n)
current_time = time.time()
a=nx.betweenness_centrality(G)
print time.time()-current_time
>0.00247192382812
>0.133368968964
>15.5196769238
所以在我的电脑上处理一个只有你的 0.1% 大小的网络需要 15 秒。做一个和你一样大的网络大约需要 1500 万秒。那是 1.5*10^7 秒，略低于 pi*10^7 秒的一半。由于 pi*10^7 秒是一年中秒数的非常好的近似值，这将花费我的计算机大约 6 个月的时间。
因此您需要 运行 使用近似算法。