2

パッケージとネットワークを使用して、Pythonでネットワークを作成していますnumpy。助けが必要なコードは次のとおりです。

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. このグラフの作成には約 1 時間かかります
  2. テーブルadjacencyは 212,000 行を保持します

私はPythonが初めてなので、インタープリターが実行する最適化(もしあれば)の量は知りません。とにかく、エラーは実際に行にグラフを作成することにあると思います:

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

私はこれを信じています:

  1. その行なしでコードを実行しましたが、高速でした (最大 10 秒)。
  2. n 行あるので、書き込みmatは O(nlgn)、データベースからの読み取り (btree 検索) は O(lgn)、書き込みmatは O(1) だと思います。

隣接行列の読み取りには O(n^2) 時間がかかると思いました。おそらく、隣接リスト (これは dict の dict として実装されていますnetworkx) の方が高速です。その場合、networkx の加重グラフと隣接リストについて知っている人はいますか?

さらに詳しい情報が必要な場合はお知らせください。すべての助けをいただければ幸いです。 注:将来のために: 1 時間が妥当かどうかはどうすればわかりますか?

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 に答える