6
いくつかのグラフがあると、ランダムに生成された可能性が高いと判断したいと思います。 Erdős-Rényiモデルとの比較はこの情報を得る良い方法だと言われましたが、どうやってそれをどうやって行うのかは分かりません。Erdős-Rényiモデルを使用してグラフがランダムであるかどうかを確認しますか？
アドバイスはありますか？
A
答えて
5
最も簡単な方法は、予想されるリンク数を、指定したグラフで観察したものと比較することです。少しスマートな方法は、次数分布を調べることです。 Erdős-Rényiグラフは二項分布を持つが、実世界ネットワークは一般にべき乗法である。
グラフを生成するために他の種類のモデルが使用されているかどうかを知っているかどうかをテストする方が簡単かもしれません。
0
ランダムに1つのグラフが生成されたかどうかを判断することはできません。生成アルゴリズムがランダムである場合は、エッジの分布のランダム性をチェックする必要があります。しかし、あなたはそのアルゴリズムによって生成された多くのインスタンスを必要とします。数学、暗号、情報理論におけるランダム性の概念をよりよく確認[rfc 1750]
Erdős-Rényiモデルでは、n個のノードを取り、可能なすべてのエッジが存在確率[p（p、p）]を持つということを基本的に示しています。したがって、pによって、予想されるエッジ数とこの予想からのずれを生成することができます。グラフの重要な比率がこの期待値の標準偏差内にある場合は、アルゴリズムが全くランダムではなく、予想されるエッジの数である少なくとも1つの特徴が明らかになっているとは限りません。
しかし、多くの状態（グラフ、中間グラフ生成ステップなど）を持たずに、あなたはそこで失われます。言って、私はあなたに番号を与えます：4.ランダムに生成されるかどうか？
2
www.statnet.orgのR（www.r-project.org）のERGMパッケージをご覧ください。観測されたネットワークがランダムプロセスによって生成されていることを100％確実に伝えることはできないかもしれませんが、ランダムまたは非ランダムなパートナー選択プロセスによって生成された可能性を評価することができます。 ERGMには、適合度を表すgofと呼ばれる機能があり、観測されたネットワークとシミュレートされたランダムネットワークを比較し、測地線距離分布、エッジワイズ共有パートナー分布、次数分布、トライアドセンサス分布などのネットワーク統計を調べます。これにより、ネットワークがランダムであるかどうかにかかわらず、情報に基づいた判断を下すことができます。