Pythonの無向グラフでトライアド国勢調査を効率的に計算する方法

16
EmJ 2019-06-11 20:15.

私はtriad census自分のために次のように計算していますundirected network

import networkx as nx
G = nx.Graph()
G.add_edges_from(
    [('A', 'B'), ('A', 'C'), ('D', 'B'), ('E', 'C'), ('E', 'F'),
     ('B', 'H'), ('B', 'G'), ('B', 'F'), ('C', 'G')])

from itertools import combinations
#print(len(list(combinations(G.nodes, 3))))

triad_class = {}
for nodes in combinations(G.nodes, 3):
    n_edges = G.subgraph(nodes).number_of_edges()
    triad_class.setdefault(n_edges, []).append(nodes)
print(triad_class)

小規模なネットワークでは正常に機能します。ただし、現在、約4000〜8000ノードのより大きなネットワークがあります。1000ノードのネットワークで既存のコードを実行しようとすると、実行に数日かかります。これを行うためのより効率的な方法はありますか?

私の現在のネットワークはほとんどまばらです。つまり、ノード間の接続はごくわずかです。その場合、接続されていないノードを残して、最初に計算を実行し、後で接続されていないノードを出力に追加できますか?

また、すべての組み合わせを計算せずに、おおよその答えを得ることができてうれしいです。

トライアド国勢調査の例:

トライアド国勢調査では、トライアド(3ノード)を次の図に示す4つのカテゴリに分類しています。

たとえば、以下のネットワークについて考えてみます。

4つのクラスのトライアド国勢調査は次のとおりです。

{3: [('A', 'B', 'C')], 
2: [('A', 'B', 'D'), ('B', 'C', 'D'), ('B', 'D', 'E')], 
1: [('A', 'B', 'E'), ('A', 'B', 'F'), ('A', 'B', 'G'), ('A', 'C', 'D'), ('A', 'C', 'E'), ('A', 'C', 'F'), ('A', 'C', 'G'), ('A', 'D', 'E'), ('A', 'F', 'G'), ('B', 'C', 'E'), ('B', 'C', 'F'), ('B', 'C', 'G'), ('B', 'D', 'F'), ('B', 'D', 'G'), ('B', 'F', 'G'), ('C', 'D', 'E'), ('C', 'F', 'G'), ('D', 'E', 'F'), ('D', 'E', 'G'), ('D', 'F', 'G'), ('E', 'F', 'G')], 
0: [('A', 'D', 'F'), ('A', 'D', 'G'), ('A', 'E', 'F'), ('A', 'E', 'G'), ('B', 'E', 'F'), ('B', 'E', 'G'), ('C', 'D', 'F'), ('C', 'D', 'G'), ('C', 'E', 'F'), ('C', 'E', 'G')]}

必要に応じて詳細をお知らせします。

編集:

回答で提案されているようにmemory error行にコメントすることで、を解決することができ#print(len(list(combinations(G.nodes, 3))))ました。しかし、私のプログラムはまだ遅く、1000ノードのネットワークでも実行するのに数日かかります。私はPythonでこれを行うためのより効率的な方法を探しています。

私はnetworkx他のライブラリや言語を使用した回答に限定されず、喜んで受け入れます。

いつものように、必要に応じて詳細を提供させていただきます。

4 answers

5
Lomtrur 2019-06-14 23:18.

考え方は単純です。グラフを直接操作する代わりに、隣接行列を使用します。これがより効率的だと思いました、そして私は正しかったようです。

隣接行列では、1は、2つのノード間にエッジがあることを示します。たとえば、最初の行は、「AとB、およびCの間にリンクがあります」と読み取ることができます。

そこから私はあなたの4つのタイプを見て、次のことを見つけました。

  • タイプ3の場合、N1とN2、N1とN3の間、およびN2とN3の間にエッジが必要です。隣接行列では、各行(各行がノードとその接続を表し、これはN1)を調べて、接続されているノード(つまり、N2)を見つけることでこれを見つけることができます。次に、N2の行で、接続されているすべてのノード(これはN3)をチェックし、N1の行に正のエントリがあるノードを保持します。この例は「A、B、C」で、AはBに接続しています。BはCに接続しており、AもCに接続しています。

  • タイプ2の場合、タイプ3とほぼ同じように機能します。ただし、N1の行のN3列に0を見つけたい場合を除きます。この例は「A、B、D」です。AはBに接続し、BはD列に1を持っていますが、Aはそうではありません。

  • タイプ1の場合、N2の行を調べて、N1行とN2行の両方が0であるすべての列を見つけます。

  • 最後に、タイプ0の場合、エントリが0であるN1行のすべての列を調べてから、それらの行を確認し、0を持つすべての列も見つけます。

このコードはあなたのために働くはずです。1000ノードの場合(i7-8565U CPUを搭載したマシンで)約7分かかりましたが、それでも比較的低速ですが、現在ソリューションを実行するのにかかる数日とはかけ離れています。結果を確認できるように、写真の例を含めました。ちなみに、コードは以下に示す例とは異なるグラフを生成します。コードのグラフの例と隣接行列はどちらも、含めた画像を参照しています。

1000ノードの例では、networkx.generators.random_graphs.fast_gnp_random_graphを使用しています。1000はノードの数、0.1はエッジ作成の確率、シードは一貫性のためだけのものです。グラフがまばらであるとおっしゃっていたので、エッジが作成される確率を設定しました。

networkx.linalg.graphmatrix.adjacency_matrix: "純粋なPython隣接行列表現が必要な場合は、networkx.convert.to_dict_of_dictsを試してください。これにより、スパース行列としてアドレス指定できる辞書形式が返されます。"

ディクショナリ構造にはM、最大でMディクショナリがネストされたディクショナリ(=行)があります。ネストされた辞書は空であるため、それらの中にキーが存在するかどうかを確認することは、上記のように1または0を確認することと同じであることに注意してください。

import time

import networkx as nx


def triads(m):
    out = {0: set(), 1: set(), 2: set(), 3: set()}
    nodes = list(m.keys())
    for i, (n1, row) in enumerate(m.items()):
        print(f"--> Row {i + 1} of {len(m.items())} <--")
        # get all the connected nodes = existing keys
        for n2 in row.keys():
            # iterate over row of connected node
            for n3 in m[n2]:
                # n1 exists in this row, all 3 nodes are connected to each other = type 3
                if n3 in row:
                    if len({n1, n2, n3}) == 3:
                        t = tuple(sorted((n1, n2, n3)))
                        out[3].add(t)
                # n2 is connected to n1 and n3 but not n1 to n3 = type 2
                else:
                    if len({n1, n2, n3}) == 3:
                        t = tuple(sorted((n1, n2, n3)))
                        out[2].add(t)
            # n1 and n2 are connected, get all nodes not connected to either = type 1
            for n3 in nodes:
                if n3 not in row and n3 not in m[n2]:
                    if len({n1, n2, n3}) == 3:
                        t = tuple(sorted((n1, n2, n3)))
                        out[1].add(t)
        for j, n2 in enumerate(nodes):
            if n2 not in row:
                # n2 not connected to n1
                for n3 in nodes[j+1:]:
                    if n3 not in row and n3 not in m[n2]:
                        # n3 is not connected to n1 or n2 = type 0
                        if len({n1, n2, n3}) == 3:
                            t = tuple(sorted((n1, n2, n3)))
                            out[0].add(t)
    return out


if __name__ == "__main__":
    g = nx.Graph()
    g.add_edges_from(
        [("E", "D"), ("G", "F"), ("D", "B"), ("B", "A"), ("B", "C"), ("A", "C")]
    )
    _m = nx.convert.to_dict_of_dicts(g)
    _out = triads(_m)
    print(_out)

    start = time.time()
    g = nx.generators.fast_gnp_random_graph(1000, 0.1, seed=42)
    _m = nx.convert.to_dict_of_dicts(g)
    _out = triads(_m)
    end = time.time() - start
    print(end)
5
kutschkem 2019-06-14 21:05.

数字を確認しましょう。ましょnは頂点の数であり、eはエッジの数。

0つのトライアドはO(n ^ 3)にあります

1つのトライアドはO(e * n)にあります

2 + 3のトライアドはO(e)にあります

2 + 3トライアドを取得するには:

For every node a:
   For every neighbor of a b:
      For every neighbor of b c:
        if a and c are connected, [a b c] is a 3 triad
        else [a b c] is a 2 triad
   remove a from list of nodes (to avoid duplicate triads)

次のステップは、目標が何であるかによって異なります。1と0のトライアドの数だけが必要な場合は、これで十分です。

説明:

1つのトライアドはすべて接続されたノード+1つの接続されていないノードであるため、接続されたノードの数+ 1つの他のノードを計算して数を取得し、他のノードが接続されている場合(2つおよび3つのトライアド)を減算します。

0トライアドは、ノードのすべての組み合わせから他のトライアドを差し引いたものです。

実際にトライアドをリストする必要がある場合、何をしても、0個のトライアドをリストすることはO(n ^ 3)にあり、グラフが大きくなるとあなたを殺してしまうため、ほとんど運が悪いです。

2 + 3トライアドの上記のアルゴリズムはO(e * max(#neighbors))にあり、他の部分はノードとエッジをカウントするためにO(e + n)にあります。0トライアドを明示的にリストする必要があるO(n ^ 3)よりもはるかに優れています。1つのトライアドのリストは、O(e * n)でも実行できます。

2
vurmux 2019-06-12 00:03.
  1. すべての組み合わせをリストに変換しようとすると、プログラムがクラッシュする可能性がありますprint(len(list(combinations(G.nodes, 3))))combinations少量のメモリを消費するイテレータを返すため、絶対に実行しないでください。ただし、リストはギガバイトのメモリを簡単に消費する可能性があります。

  2. グラフがまばらな場合は、連結成分でトライアドを見つける方が合理的です。nx.connected_components(G)

  3. Networkxにはトライアドサブモジュールがありますが、それはあなたに合わないようです。networkx.algorithms.triadsコードを変更して、カウントではなくトライアドを返すようにしました。あなたはここでそれを見つけることができます。DiGraphsを使用していることに注意してください。無向グラフで使用する場合は、最初に有向グラフに変換する必要があります。

2
Jainil Patel 2019-06-15 01:59.
import networkx as nx
from time import sleep
from itertools import combinations


G = nx.Graph()
arr=[]
for i in range(1000):
    arr.append(str(i))

for i,j in combinations(arr, 2):
    G.add_edges_from([(i,j)])

#print(len(list(combinations(G.nodes, 3))))
triad_class = [[],[],[],[]]

for nodes in combinations(G.subgraph(arr).nodes, 3):
            n_edges = G.subgraph(nodes).number_of_edges()
            triad_class[n_edges].append(nodes)


print(triad_class)

辞書は指数関数的に大きくなり、時間がかかるため、リストを使用すると辞書よりも挿入が速くなると思います。

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

2017年の最も人気のある投稿

2017年の最も人気のある投稿

ここLifehackerでは大きな年でした。一緒に、私たちはミツバチを救おうとし、ハッキングされ、太陽をじっと見つめ、グロスチェーンレストランの食べ物を食べ、核爆弾から身を隠しました。

ラストコール:素晴らしき人生だ、コーシャワイン、そしてジュリアチャイルドはユールログを作るのが苦手

ラストコール:素晴らしき人生だ、コーシャワイン、そしてジュリアチャイルドはユールログを作るのが苦手

写真:ゲッティイメージズ経由のハーバート・ドーフマン/コービスさて、昨日、幼い子供たちにマジシャンズを見させて銃を飛び越えていたようです。知っておくと良い!昨夜、娘と私はシカゴの素晴らしいビンテージシアターであるミュージックボックスで映画を見に行きました。年齢に関係なく、誰も問題を抱えてはいけません。それは素晴らしい人生です。

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

Tomorrow's Kitchen シリコンストレッチ蓋 12個パック | $14 | アマゾン | プロモーション コード 20OFFKINJALids は基本的にキッチンの靴下です。常に迷子になり、二度と閉じられない孤立したコンテナーが残ります。しかし、蓋が伸びて、残った容器、鍋、フライパン、さらには大きなスライスされた果物のすべてに適合するとしたらどうでしょうか? その非常に特殊な蓋を失うことを二度と心配する必要はありません。

あなたの最高のワシントン DC ハックを教えてください

あなたの最高のワシントン DC ハックを教えてください

このコラムでは、ロサンゼルスやラスベガスなど、いくつかの産業都市をハッキングしました。今こそ、軍産複合都市の時代です。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Precios accesibles, nuestro aprendizaje desde la perspectiva iOS

Cómo mejoramos la accesibilidad de nuestro componente de precio, y cómo nos marcó el camino hacia nuevos saberes para nuestro sistema de diseño. Por Ana Calderon y Laura Sarmiento Leer esta historia en inglés.

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

Language