2

我正在使用包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) 时间；也许邻接列表（作为 dicts in 的 dict 实现networkx）会更快。在那种情况下，有人知道networkx中的加权图和邻接表吗？

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

4

1 回答 1

4

我不确定为什么在将 numpy 矩阵转换为 Di-Graph 时这很慢。请在下面尝试这种方法，看看是否有帮助。

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
于 2013-06-24T16:01:22.537 回答