7

スモールワールドプロパティ（べき乗則分布を示す）を持つランダムグラフを生成しようとしています。networkxパッケージを使い始めたところ、さまざまなランダムグラフ生成が提供されていることがわかりました。特定のノードの次数がガンマ分布に従うグラフを生成できるかどうか誰かに教えてもらえますか（Rまたはpythonのnetworkxパッケージを使用）？

4

4 に答える 4

7

構成モデルを使用する場合は、NetworkXで次のようなものが機能するはずです。

import random 
import networkx as nx
z=[int(random.gammavariate(alpha=9.0,beta=2.0)) for i in range(100)]
G=nx.configuration_model(z)

ガンマ分布のパラメーターによっては、シーケンスzの平均を調整する必要がある場合があります。また、zはグラフィカルである必要はありません（マルチグラフを取得します）が、偶数の合計が必要なため、いくつかのランダムシーケンスを試す（または1を追加する）必要があります...

configuration_modelのNetworkXドキュメントノートには、別の例、リファレンス、および並列エッジと自己ループを削除する方法が記載されています。

Notes
-----
As described by Newman [1]_.

A non-graphical degree sequence (not realizable by some simple
graph) is allowed since this function returns graphs with self
loops and parallel edges.  An exception is raised if the degree
sequence does not have an even sum.

This configuration model construction process can lead to
duplicate edges and loops.  You can remove the self-loops and
parallel edges (see below) which will likely result in a graph
that doesn't have the exact degree sequence specified.  This
"finite-size effect" decreases as the size of the graph increases.

References
----------
.. [1] M.E.J. Newman, "The structure and function
       of complex networks", SIAM REVIEW 45-2, pp 167-256, 2003.

Examples
--------
>>> from networkx.utils import powerlaw_sequence
>>> z=nx.create_degree_sequence(100,powerlaw_sequence)
>>> G=nx.configuration_model(z)

To remove parallel edges:

>>> G=nx.Graph(G)

To remove self loops:

>>> G.remove_edges_from(G.selfloop_edges())

これは、 http：//networkx.lanl.gov/examples/drawing/degree_histogram.htmlにあるものと同様の例で、接続されている最大のコンポーネントのグラフレイアウトを含む図面を作成します。

#!/usr/bin/env python
import random
import matplotlib.pyplot as plt
import networkx as nx

def seq(n):
    return [random.gammavariate(alpha=2.0,beta=1.0) for i in range(100)]    
z=nx.create_degree_sequence(100,seq)
nx.is_valid_degree_sequence(z)
G=nx.configuration_model(z)  # configuration model

degree_sequence=sorted(nx.degree(G).values(),reverse=True) # degree sequence
print "Degree sequence", degree_sequence
dmax=max(degree_sequence)

plt.hist(degree_sequence,bins=dmax)
plt.title("Degree histogram")
plt.ylabel("count")
plt.xlabel("degree")

# draw graph in inset 
plt.axes([0.45,0.45,0.45,0.45])
Gcc=nx.connected_component_subgraphs(G)[0]
pos=nx.spring_layout(Gcc)
plt.axis('off')
nx.draw_networkx_nodes(Gcc,pos,node_size=20)
nx.draw_networkx_edges(Gcc,pos,alpha=0.4)

plt.savefig("degree_histogram.png")
plt.show()
于 2010-12-01T21:32:11.280 に答える
2

私は少し前にベースPythonでこれを行いました...IIRC、私は次の方法を使用しました。メモリから、これは完全に正確ではないかもしれませんが、うまくいけば、それは何かの価値があります：

  1. グラフ内のノードの数Nと、密度（可能なエッジ上の既存のエッジ）Dを選択します。これは、エッジの数Eを意味します。
  2. ノードごとに、最初にランダムな正の数xを選択し、P（x）を見つけることによってその次数を割り当てます。ここで、PはPDFです。ノードの次数は（P（x）* E / 2）-1です。
  3. ランダムにノードを選択し、それを別のランダムノードに接続します。いずれかのノードが割り当てられた次数を実現した場合は、それ以降の選択から除外します。E回繰り返します。

一般に、これは連結グラフを作成しないことに注意してください。

于 2010-12-01T20:58:29.073 に答える
1

これは非常に遅いことを私は知っていますが、数学を使って、もう少し簡単ではありますが、同じことを行うことができます。

RandomGraph [DegreeGraphDistribution [{3、3、3、3、3、3、3、3}]、4]

これにより、4つのランダムグラフが生成され、各ノードには所定の次数があります。

于 2013-10-06T04:35:17.333 に答える
1

上記を含め、networkx入力としてdegree_distributionを受け取る4つのアルゴリズムを提供します。

  • configuration_model：@ericによる説明
  • expected_degree_graph：各ノードの予想される次数に基づく確率論的アプローチを使用します。正確な度数ではなく、概算値が得られます。
  • havel_hakimi_graph：これは最初に最高度のノードを接続しようとします
  • random_degree_sequence_graph：私が見る限り、これは@JonCが提案したものと似ています。trials適切な構成を見つける保証がないため、パラメーターがあります。

完全なリスト（有向グラフのアルゴリズムのいくつかのバージョンを含む）はここにあります。

私はまた、いくつかの論文を見つけました：

于 2017-07-25T17:24:32.157 に答える