0

二部ネットワークを構成する以下の形式のデータがあります。

A1 - B1
A2 - B2
A2 - B1
A3 - B1
A4 - B2
A5 - B3
A6 - B3
A7 - B3
A7 - B3
A8 - B4
A9 - B3

私がやりたいことは、(理想的には python または C で) 何かを書くか、既存のライブラリを使用してデータ内の個々のコミュニティを識別することです。例えば

A1、A2、A3、A4 はすべて同じコミュニティの一部です。なぜなら、A5、A6、A7、A8、A9 はすべて B3 と B4 に接続されているのと同様に、B1、B2 に接続しているためです。

私の問題がどこにあるのかについて、ネットワークフローとグラフに関するさまざまな記事をたくさん読んで、少し混乱しています。これは幅優先検索の単なる形式ですか、それともこれを行うためのより効率的な手段はありますか?

ありがとう

4

5 に答える 5

3

Python とigraph ライブラリを使用すると、次のことができます。

import igraph
graph = igraph.Graph.Formula("A1-B1, A2-B2, A2-B1, A3-B1, A4-B2, A5-B3, A6-B3, A7-B3, A8-B4, A9-B3")
comms = graph.clusters()
for comm in comms:
    print ", ".join(graph.vs[comm]["name"])

簡単な説明:Graph.Formula上記のような文字列表現からグラフを作成しますが、igraph が提供する他の方法を使用してグラフを作成することもできます。を使用する利点は、頂点名を含む頂点属性がGraph.Formula自動的に作成されることです。ネットワークの接続されたコンポーネントを検索し、オブジェクトを返します。このオブジェクトをループで使用して、コンポーネントを反復処理できます。ループのコアでは、変数には常に現在のコミュニティ内のノードのインデックスが含まれます。を使用してコミュニティの頂点を選択し、それらの名前をリスト ( ) として要求してから、名前をカンマで結合します。namegraph.clusters()VertexClusteringforforcommgraph.vs[comm]graph.vs[comm]["name"]

于 2010-01-22T00:28:18.470 に答える
1

@Eliは、接続されたコンポーネントを見つけることをお勧めします。ラベル（この場合はとにかく）が「A」で始まることを知っているので、次のように行うことができます。

import networkx as nx
edges = """A1 - B1
A2 - B2
A2 - B1
A3 - B1
A4 - B2
A5 - B3
A6 - B3
A7 - B3
A7 - B3
A8 - B4
A9 - B3""".split('\n')
G = nx.parse_edgelist(edges,delimiter=' - ')
for component in nx.connected_components(G):
    print [n for n in component if n.startswith('A')]
于 2012-11-24T00:02:11.767 に答える
1

いいえ！NetworkX ライブラリには 2 部グラフ用の関数が 4 つしかないため、注意して使用してください。1 つは 2 部構成かどうかを確認するため、1 つはノードを色付けするため、1 つは重みのない単純な 2 部ネットワークを作成するため、もう 1 つは 2 部ネットワークの射影を作成するためのものです。最後の 1 つの関数を使用できます。

于 2011-05-02T22:08:09.677 に答える
1

Python を使用する場合は、NetworkXライブラリについてお読みください。グラフ用のモジュールとアルゴリズムの実装がたくさんあります。特に、Bipartiteモジュールが役立つ場合があります。「コミュニティ」の意味がわかりませんが、bipartite_colorそのモジュールの機能が役立つ場合があります。

于 2010-01-09T10:36:02.283 に答える
1

たぶん次のようなものです：

import collections

data = ( ("A1", "B1"), ("A2", "B2"), ("A2", "B1") )
out = collections.defaultdict(list)

for value, key in data:
  out[key].append(value)

print out
-> defaultdict(<type 'list'>, {'B1': ['A1', 'A2'], 'B2': ['A2']})

ただし、これは一方向にしか機能しません。もちろん、A をキーとして設定したものと B をキーとして設定したものの 2 つの辞書を作成することもできます。キーは不変（文字列、数値）であると想定しています。

于 2010-01-09T10:36:42.663 に答える