2

データマイニングで集めたデータから巨大なグラフを作成しました。

グラフ作成に「networkx」を使用しましたが、巨大なグラフを別のグラフに変更したいと考えています。

各ノードの加重エッジの合計は 1 です。

だから私は以下のように私のコードを書きます：

ng=nx.Graph()  
for n in g.nodes():  
    s=0.0  
    for nb in g.neighbors(n):  
         s=s+1.0/g[n][nb]['weight']  
    for nb in g.neighbors(n):  
        ng.add_edge(n,nb,weight=1.0/s/g[n][nb]['weight'])

以下のようなコードで結果を確認した後

for n in ng.neighbors('100002950636410'):
    print str(n) + ' : ' + str(ng[n]['100002950636410']['weight'])

近隣の合計は 1 ではなく、「重み」が 1 であるエッジがたくさんあります。

私は何か間違っていましたか？私の計算とコードは正しいと思いますが、問題がグラフのサイズである場合、どうすればよいですか?

4

1 に答える 1

3

あなたの問題の問題

あなたのソリューションは、あなたがやろうとしている方法で機能するとは思いません。最初に理由を説明し、次に別の解決策を提案します。

次のコードを検討してください。

import networkx as nx
import matplotlib.pyplot as plt
import random

# Set up a graph with random edges and weights

G = nx.barabasi_albert_graph(6, 2, seed= 3214562)
for u,v in G.edges_iter():
    G[u][v]['weight'] = int(random.random() * 10)

pos = nx.spring_layout(G)

nx.draw(G, pos)
nx.draw_networkx_edge_labels(G,pos)
plt.show()

次の図が生成されます。

ここに画像の説明を入力

ノード 1 を考えてみましょう。重みがそれぞれ 2 と 9 の 2 つのエッジがあります。重みをそれぞれ 2/11 と 9/11 に調整する必要があります。

次に、ノード 4 について考えます。これには、重みがそれぞれ 2/11 と 8 の 2 つのエッジがあります。最初の重みは前の計算で固定されているため、基本的に 2 番目の重みは 8/(8+2/11) になるように調整します。

これで、重みが調整および固定された 3 つのエッジができました。ノード 0、3、および 5 についてこれを繰り返します。プロセスの最後までに、ノード 2 の周囲のすべてのエッジが再調整および修正されますが、顕著な一致がない限り、それらの合計は 1 になりません。もちろん、より大きなグラフでは、この問題ははるかに速く発生します。

ソリューション

エッジ自体を再重み付けする代わりに、再重み付けされたエッジのディクショナリを含む新しいデータ属性を各ノードにアタッチすることを提案します。これは、デモンストレーションに関連するコードです。

for n in G.nodes_iter():
    total = sum([ attr['weight']
                  for u,v,attr in G.edges(n, data=True) ])
    total = float(total)
    weights = dict([(nb, G[n][nb]['weight']/total)
                    for nb in G.neighbors(n)])
    G[n]['adj_weights'] = weights

# Print out the adjusted weights

for n in G.nodes_iter():
    for nb,w in G[n]['adj_weights'].iteritems():
        w = int(w*1000)/1000.
        print '{} to {}: {}'.format(n, nb, w)

これにより、次が生成されます。

0 to 2: 0.272
0 to 3: 0.727
1 to 2: 0.818
1 to 4: 0.181
2 to 0: 0.081
2 to 1: 0.243
2 to 3: 0.243
2 to 4: 0.216
2 to 5: 0.216
3 to 0: 0.363
3 to 2: 0.409
3 to 5: 0.227
4 to 1: 0.2
4 to 2: 0.8
5 to 2: 0.615
5 to 3: 0.384

したがって、ノード 0 へのエッジの合計は 1 になります。たとえば、ノード 3 に接続されたエッジも同様です。ただし、エッジ (0,3) の重みは、ノード 0 から見た場合は 0.727、ノード 3 から見た場合は 0.363 です。

これでうまくいくことを願っています。

于 2013-06-04T17:15:32.850 に答える