python - 提高 networkx 中的 python 性能

Question

我正在使用包 numpy 和网络在 python 中创建网络。这是我需要帮助的代码:

def create_rt_network(self):                                                                                                       
    """construct a retweet network from twitter db"""                                                                                                                                                                        
    con = mdb.connect(**proper-information**)                                                                                                                                                                                            
    cur = con.cursor(mdb.cursors.DictCursor)                                                                                       
    cur.execute("select COUNT(*) from users")                                                                                                                                                                                                                   
    N = cur.fetchone()['COUNT(*)']                                                                                                                                                                                                                                       
    mat = np.empty((N, N))                                                                                                                                                                                                                                  
    #read adjacency table and store data into mat                                                                                                                                                                                                                 
    cur.execute("select * from adjacency")                                                                                                                                                                               
    rows = cur.fetchall() 

    for row in rows:                                                                                                                                                             
        curRow = row['r']                                                                                                                                                                                                                                   
        curCol = row['c']                                                                                                                                                         
        weight = row['val']                                                                                                                                                                                                                                               
        mat[curRow][curCol] = weight                                                                                                                                                                                                                                                                                                                                                                          
    cur.close()                                                                                                                                                                                              
    con.close()      

    g = nx.from_numpy_matrix(mat, create_using=nx.DiGraph())                                                                                            
    return g 

事实:

1. 创建此图表大约需要一个小时
2. 表 adjacency 包含 212,000 行

由于我是 python 的新手，我不知道解释器执行了多少优化(如果有的话)。无论如何，我认为错误在于实际创建该行中的图形:

g = nx.from_numpy_matrix(mat, create_using=nx.DiGraph())

我相信这是因为:

1. 我在没有该行的情况下运行了代码，速度很快(最多 10 秒)
2. 我认为写 mat 是 O(nlgn)，因为我们有 n 行，从数据库读取(btree 搜索)是 O(lgn)，写 mat 是O(1).

我只是想到读取邻接矩阵需要 O(n^2) 时间；也许邻接列表(在 networkx 中实现为字典的字典)会更快。在那种情况下，有人知道 networkx 中的加权图和邻接表吗？

如果您想了解更多信息，请告诉我，非常感谢所有帮助!注意:对于 future :我怎么知道一个小时是否合理？

Answer 1

我不确定为什么将 numpy 矩阵转换为有向图时速度很慢。请尝试下面的这种方法，看看它是否有帮助。

def create_directed_graph(rows):
    g = nx.DiGraph()
    for row in rows:
        curRow = row['r']
        curCol = row['c']
        weight = row['val']
        g.add_edge(curRow,curCol,Weight=weight)
    return g