10

複雑なネットワークを扱っています。特定のグラフで 3 つのノード (または三角形) のサイクルを形成するノードのグループを見つけたいと考えています。私のグラフには約 100 万個のエッジが含まれているため、単純な反復ソリューション (複数の「for」ループ) を使用するのはあまり効率的ではありません。

プログラミングに python を使用しています。これらの問題を処理するための組み込みモジュールがある場合は、お知らせください。

グラフ内の三角形を見つけるために使用できるアルゴリズムを誰かが知っている場合は、親切に返信してください。

4

11 に答える 11

5

ミリオン エッジは非常に小さいです。何千回も実行しない限り、単純な実装を使用してください。

一連の隣接ノードを指す node_ids の辞書があり、グラフが有向であると仮定します。

例えば：

nodes = {}
nodes[0] = 1,2
nodes[1] = tuple() # empty tuple
nodes[2] = 1

私の解決策：

def generate_triangles(nodes):
    """Generate triangles. Weed out duplicates."""
    visited_ids = set() # remember the nodes that we have tested already
    for node_a_id in nodes:
        for node_b_id in nodes[node_a_id]:
            if nod_b_id == node_a_id:
                raise ValueError # nodes shouldn't point to themselves
            if node_b_id in visited_ids:
                continue # we should have already found b->a->??->b
            for node_c_id in nodes[node_b_id]:
                if node_c_id in visited_ids:
                    continue # we should have already found c->a->b->c
                if node_a_id in nodes[node_c_id]:
                    yield(node_a_id, node_b_id, node_c_id)
        visited_ids.add(node_a_id) # don't search a - we already have all those cycles

パフォーマンスの確認:

from random import randint
n = 1000000
node_list = range(n)
nodes = {}
for node_id in node_list:
    node = tuple()
    for i in range(randint(0,10)): # add up to 10 neighbors
        try:
            neighbor_id = node_list[node_id+randint(-5,5)] # pick a nearby node
        except:
            continue 
        if not neighbor_id in node:
            node = node + (neighbor_id,)
    nodes[node_id] = node

cycles = list(generate_triangles(nodes))
print len(cycles)

試してみると、サイクルをカウントするよりもランダム グラフを作成する方が時間がかかりました。

ただし、テストすることをお勧めします ;) それが正しいことを保証するものではありません。

また、大きな Python グラフ ライブラリである networkx を調べることもできます。

于 2009-11-10T08:24:53.163 に答える
3

とても簡単で明確な方法は、Networkx を使用することです。

Networkx を使用すると、 nx.cycle_basis(G)によって無向グラフのループを取得し、3 つのノードを持つループを選択できます。

cycls_3 = [c for c in nx.cycle_basis(G) if len(c)==3]

または、 find_cliques(G)ですべてのクリークを見つけてから、必要なクリークを選択することもできます (3 つのノードで)。クリークは、すべてのノードが相互に接続されているグラフのセクションであり、3 つのノードを持つサイクル/ループで発生します。

于 2015-09-08T00:55:47.180 に答える
2

耳障りに聞こえたくないのですが、Google で検索してみましたか? 最初のリンクは、それを行うための非常に簡単なアルゴリズムです: http://www.mail-archive.com/algogeeks@googlegroups.com/msg05642.html

そして、ACM に関する次の記事があります (アクセスできる場合があります): http://portal.acm.org/citation.cfm?id=244866 (アクセスできない場合は、それを書いた女性に尋ねれば、コピーを手に入れることができます.)

また、クリーク分解に基づく三角形列挙法も想像できますが、どこかに記載されていたかどうかはわかりません。

于 2009-11-10T06:06:26.370 に答える
1

効率的ではありませんが、解決策を実装したい場合があるため、ループを使用してください。どれくらいの時間がかかるかを把握できるように、テストを作成します。

次に、新しいアプローチを試すときにできることは 2 つあります。1) 答えが同じであることを確認します。2) 改善点を確認します。

何かを見逃すような高速なアルゴリズムを持つことは、遅いアルゴリズムを持つことよりも悪いことになるでしょう。

スロー テストが完了したら、これを並行して実行できるかどうかを確認し、パフォーマンスの向上を確認できます。

次に、頂点が 3 つ未満のすべてのノードをマークできるかどうかを確認できます。

理想的には、最初に 100 程度に縮小して描画し、何が起こっているかをグラフィカルに確認できるようにすることをお勧めします。

アルゴリズムを見ると、脳はそれほど明白ではないパターンを認識することがあります。

于 2009-11-10T05:45:23.090 に答える
0

「三角形」の「すべて」を見つける必要がありますか? それとも、特定のノードが三角形の一部であるかどうかをテストするだけでよいでしょうか?

テストは簡単です。ノード A が与えられた場合、直接接続されている 2 つのノード B と C が接続されているかどうかを調べます。

すべての三角形、具体的には、各ノードが他の 2 つのノードに結合されている 3 つのノードのすべてのグループを見つける必要がある場合は、非常に長時間実行される「for each」ループですべての可能なグループをチェックする必要があります。

唯一の最適化は、同じ「グループ」を 2 回チェックしないようにすることです。たとえば、B と C が A のグループに属していないことを既にテストしている場合は、A と C がグループに属しているかどうかをチェックしないでください。 Bと。

于 2009-11-10T06:03:52.787 に答える