7

次の関数は、ランダムに生成された size の隣接行列を返しnxn、グラフを表します。

import random

def random_adjacency_matrix(n):   
    matrix = [[random.randint(0, 1) for i in range(n)] for j in range(n)]

    # No vertex connects to itself
    for i in range(n):
        matrix[i][i] = 0

    # If i is connected to j, j is connected to i
    for i in range(n):
        for j in range(n):
            matrix[j][i] = matrix[i][j]

    return matrix

これは非常にナイーブなソリューションであり、2 つの追加要件を満たしたいと考えています。

  1. マトリックスが表すグラフは完全に接続されている必要があります。つまり、いくつかのステップで他のノードから到達できないノードがあってはなりません。

  2. 各ノードには多数のエッジがあります。現在、それは完全にランダムであるため、ノードが持つエッジの数はかなり均一であり、nが大きい場合、すべてのグラフでエッジの平均数も大きくなる傾向があります。グラフのサイズに関係なく、ノードあたりのエッジの平均数をさらに変化させて、接続が非常に少ないグラフと多くのグラフがあるようにしたいと考えています。

編集: networkx パッケージを使用すると、これは私が望むもののようですが、上記のポイント 1 のみが満たされています:

import networkx, random
G = networkx.binomial_graph(50, random.random()) # 50 nodes, random probability of an edge
4

4 に答える 4

3

まず、networkx グラフ ライブラリをお勧めします。非常に使いやすく、優れたアルゴリズムのツールボックスが既に含まれています。たとえば、グラフの接続性を簡単にテストしたり、グラフ内の接続されたコンポーネントのセットを要求したりできます。

第二に、標準的な名前付き統計分布にはさまざまなものがあります。あなたが考えているものを見つけることができれば、それはあなたと助けを申し出ている人の両方に役立つでしょう. あなたが与えた大まかな説明から、べき乗分布（別名「ロングテール」分布、「スケールフリーネットワーク」も参照）を探しているように思えます。この種の分布は (たとえば) ソーシャル ネットワークでよく見られます。この場合、非常に高度に接続されたノード (つまり、人気のあるノード) は比較的少なく、接続性が非常に低いノードが非常に多くあります。少数の高度に接続されたものと疎に接続された多数のものとの間には、中間で一種の指数関数的減衰があります。これは、ランダムに生成されたソーシャル ネットワークについて説明している論文のようです。ソーシャル ネットワークのランダム グラフ モデル。

networkx と適切な統計分布が与えられれば、夢のようなグラフを作成できるはずです。プロジェクトの成功を祈り、コーディングをお楽しみください。

于 2012-05-11T17:17:05.117 に答える
2

必要なグラフのタイプを完全に指定するには、十分な情報が提供されていません。それにもかかわらず、グラフは通常、何らかの物理構造の抽象化であるため、ランダム グラフに対する一般的な要求は、スケールフリーのものです。これらのグラフは、次数分布が累乗則に漸近的に従うという性質を持っています。人口動態、Facebook の友人、引用ネットワーク、およびインターネット トラフィックはすべて、あるドメインに対してべき法則依存性を持っています。スケールフリー ネットワークを生成する標準的な方法は、Barabási–Albert 法です。以下に (ウィキペディアから) 再現されているのは、そのようなネットワークの作成のアニメーションです。任意の N に対して接続されることが保証され、一般化により接続を設定できます。

ここに画像の説明を入力

networkxこれらのランダム グラフを簡単に生成できます。

import networkx

node_number = 20
initial_nodes = 2
G = networkx.barabasi_albert_graph(node_number, initial_nodes)
于 2012-05-11T17:40:21.750 に答える
1

問題1：

まず、すべてのノードを接続するランダムなスパニングツリーを作成してから、他のエッジを追加します。

問題2：

(i,j)のすべてのリストを作成し、リストを1 ≤ i < j ≤ nシャッフルして、最初のk個のエッジを取得します。グラフにはn頂点とk±nエッジがあります。

于 2012-05-11T17:09:33.843 に答える
1

(1) これは簡単です。最初にツリーを作成し、接続が確保された後でのみ、エッジを追加し始めます。
これは、接続された頂点のセットを繰り返し増加させることにより、簡単に実行できます。
擬似コード:

source <- select random vertex
set <- {source}
while set != V:
   chose a random vertex v from set, and u from V\set
   add (v,u),(u,v) as an edge
   add u to set

(2) 正規分布を使用して、ノードあたりのエッジ数を選択し
ます。各ノードは異なるランダム変数を取得するため、ノードの数が異なります。

  • 物事は実生活では正規分布する傾向があるため、これは良いアプローチだと思います (中心極限定理により)。
  • 頂点ごとのエッジ数を決定するために使用される確率変数の平均と分散を変更することで、接続性を制御できます。
  • 他の分布を使用してノードあたりのエッジ数を選択することもできますが、正規分布が最も適していると思います。
于 2012-05-11T17:12:22.650 に答える