(57)【要約】【課題】  有向スケールフリーオブジェクト関係のモデルを生成するためのシステムおよび方法を提供する。【解決手段】  １つの態様では、乱数の系列が生成される。そして、これら個々の乱数が時間にわたって選択されて、入次数および出次数の系列に基づいて、有向スケールフリーオブジェクト関係をグラフとして生成する。【選択図】  図２
2004318884.tif 000002
【特許請求の範囲】
【請求項１】
有向スケールフリーオブジェクト関係をモデル化するために、プロセッサにより実行可能なコンピュータプログラム命令を備えたコンピュータ可読媒体であって、該コンピュータプログラム命令は、
乱数の系列を生成するための命令と、
時間にわたって前記乱数のうちの個々の乱数を連続的に選択して有向スケールフリーオブジェクト関係のモデルをグラフとして生成するための命令であって、グラフの発展が入次数および出次数の両方に依存している命令と
を備えたことを特徴とするコンピュータ可読媒体。
【請求項２】
前記グラフは、ノードと、該ノードのそれぞれの間の有向辺とを備えたウェブグラフであり、前記ノードはウェブページに対応し、前記有向辺はあるウェブページから別のウェブページへのハイパーリンクに対応していることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項３】
前記コンピュータプログラム命令は、前記乱数を連続的に使用して、設定可能なパラメータα、βおよびγに従って、
（Ａ）新しいオブジェクトと古いオブジェクトの間に辺を追加すること、
（Ｂ）２つの古いオブジェクトの間に辺を追加すること、または
（Ｃ）古いオブジェクトから新しいオブジェクトへの辺を追加すること
によって前記グラフを更新するための命令をさらに備えたことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項４】
前記コンピュータプログラム命令は、有向優先的選択の関数として前記グラフに新しい辺を追加するための命令をさらに備えたことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項５】
前記コンピュータプログラム命令は、入次数シフトおよび／または出次数シフトδinおよび／またはδoutの関数として前記グラフを生成するための命令をさらに備えたことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項６】
前記コンピュータプログラム命令は、設定可能なパラメータα、β、γ、δinおよびδoutのセットに基づく測定された環境特性の関数として前記グラフをモデル化するための命令をさらに備えたことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項７】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項８】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なり、パラメータα、β、γ、δinおよびδoutを有するジェネレータに対して、ｄinに等しい入次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数１】
2004318884.tif 000055
ここで
【数２】
2004318884.tif 000056
であり、ｄoutに等しい出次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数３】
2004318884.tif 000057
ここで
【数４】
2004318884.tif 000058
であることを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項９】
前記コンピュータプログラム命令は、確率分布
Ｐｒ（ｗ＝ｗj）∝（ｄin（ｗj）＋δin）
に従って選択されたランダムな古いオブジェクトｗへ新しいオブジェクトｖからの辺を追加することによって、前記グラフを更新するための（Ａ）に基づく命令をさらに備えたことを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項１０】
前記コンピュータプログラム命令は、前記グラフの第１の既存のオブジェクトｖから第２の既存のオブジェクトｗへの辺を追加することによって前記グラフを更新するための（Ｂ）に基づく命令をさらに備え、該オブジェクトｖおよびｗは、確率分布
Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）
に従って選択されることを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項１１】
前記コンピュータプログラム命令は、ランダムに選択された古いオブジェクトｗから新しいオブジェクトｖへの辺を追加することによって前記グラフを更新するための（Ｃ）に基づく命令をさらに備え、ｗは、確率分布
Ｐｒ（ｗ＝ｗi）∝ｄout（ｗi）＋δout
に従って選択されることを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項１２】
（Ａ）前記コンピュータプログラム命令は、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、新しいオブジェクトｖiから古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加する命令をさらに備えたことを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項１３】
（Ｂ）に基づく前記コンピュータプログラム命令は、
区間［０，ｔ＋ｎδout］を幅ｄout（ｖi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｖiを選択することと、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、古いオブジェクトｖiから古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加する命令をさらに備えたことを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項１４】
（Ｃ）に基づく前記コンピュータプログラム命令は、
区間［０，ｔ＋ｎδout］を幅ｄout（ｗi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｗiを選択することと
によって、古いオブジェクトｗiから新しいオブジェクトｖjへの辺Ｅ（ｉ，ｊ）を追加する命令をさらに備えたことを特徴とする請求項３に記載のコンピュータ可読媒体。
【請求項１５】
前記コンピュータプログラム命令は、
前記グラフの新しい頂点ｖに対して、指定された分布ＤinおよびＤoutから２つの乱数λ（ｖ）およびμ（ｖ）を独立に生成するための命令と、
前記乱数を利用して、
（Ａ）Ｐｒ（ｗ＝ｗj）∝λ（ｗj）（ｄin（ｗj）＋δin）となるように、λ（ｗ）（ｄin＋δin）に従って既存の頂点ｗを選択すること、
（Ｂ）Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝μ（ｖi）λ（ｗj）（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）となるように、μ（ｖ）（ｄout＋δout）に従って既存の頂点ｖ、およびλ（ｗ）（ｄin＋δin）に従って第２の既存の頂点ｗを選択すること、または
（Ｃ）Ｐｒ（ｗ＝ｗi）∝μ（ｗi）（ｄout（ｗi）＋δout）となるように、μ（ｗ）（ｄout＋δout）に従って既存の頂点ｗを選択すること、
のように前記グラフの頂点を更新するための命令と
をさらに備えたことを特徴とする請求項１に記載のコンピュータ可読媒体。
【請求項１６】
有向スケールフリーオブジェクト関係のモデルを生成する方法であって、
乱数の系列を生成することと、
時間にわたって前記乱数のうちの個々の乱数を連続的に選択して有向スケールフリーオブジェクト関係のモデルをグラフとして生成することであって、該グラフの発展が入次数および出次数の両方に依存していることと
を備えることを特徴とする方法。
【請求項１７】
前記グラフは、ノードと、該ノードのそれぞれの間の有向辺とを備えたウェブグラフであり、前記ノードはウェブページに対応し、前記有向辺はあるウェブページから別のウェブページへのハイパーリンクに対応していることを特徴とする請求項１６に記載の方法。
【請求項１８】
前記方法は、前記乱数を連続的に使用して、設定可能なパラメータα、βおよびγに従って、
（Ａ）新しいオブジェクトと古いオブジェクトの間に辺を追加すること、
（Ｂ）２つの古いオブジェクトの間に辺を追加すること、または
（Ｃ）古いオブジェクトから新しいオブジェクトへの辺を追加すること
によって前記グラフを更新することをさらに備えることを特徴とする請求項１６に記載の方法。
【請求項１９】
前記方法は、有向優先的選択の関数として前記グラフに新しい辺を追加することをさらに備えることを特徴とする請求項１６に記載の方法。
【請求項２０】
前記方法は、入次数シフトおよび／または出次数シフトδinおよび／またはδoutの関数として前記グラフを生成することをさらに備えることを特徴とする請求項１６に記載の方法。
【請求項２１】
前記方法は、設定可能なパラメータα、β、γ、δinおよびδoutのセットに基づく測定された環境特性の関数として前記グラフをモデル化することをさらに備えることを特徴とする請求項１６に記載の方法。
【請求項２２】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なることを特徴とする請求項１６に記載の方法。
【請求項２３】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なり、パラメータα、β、γ、δinおよびδoutを有するジェネレータに対して、ｄinに等しい入次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数５】
2004318884.tif 000059
ここで
【数６】
2004318884.tif 000060
であり、ｄoutに等しい出次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数７】
2004318884.tif 000061
ここで
【数８】
2004318884.tif 000062
であることを特徴とする請求項１６に記載の方法。
【請求項２４】
（Ａ）は、確率分布
Ｐｒ（ｗ＝ｗj）∝（ｄin（ｗj）＋δin）
に従って選択されたランダムな古いオブジェクトｗへ新しいオブジェクトｖからの辺を追加することによって、前記グラフを更新することをさらに備えることを特徴とする請求項１８に記載の方法。
【請求項２５】
（Ｂ）は、前記グラフの第１の既存のオブジェクトｖから第２の既存のオブジェクトｗへの辺を追加することによって前記グラフを更新することをさらに備え、該オブジェクトｖおよびｗは、確率分布
Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）
に従って選択されることを特徴とする請求項１８に記載の方法。
【請求項２６】
（Ｃ）は、ランダムに選択された古いオブジェクトｗから新しいオブジェクトｖへの辺を追加することによって前記グラフを更新することをさらに備え、ｗは、確率分布
Ｐｒ（ｗ＝ｗi）∝ｄout（ｗi）＋δout
に従って選択されることを特徴とする請求項１８に記載の方法。
【請求項２７】
（Ａ）は、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、新しいオブジェクトｖiから古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加することをさらに備えることを特徴とする請求項２４に記載の方法。
【請求項２８】
（Ｂ）は、
区間［０，ｔ＋ｎδout］を幅ｄout（ｖi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｖiを選択することと、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、古いオブジェクトｖiから第２の古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加することをさらに備えることを特徴とする請求項２５に記載の方法。
【請求項２９】
（Ｃ）は、
区間［０，ｔ＋ｎδout］を幅ｄout（ｗi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｗiを選択することと
によって、古いオブジェクトｗiから新しいオブジェクトｖjへの辺Ｅ（ｉ，ｊ）を追加することをさらに備えることを特徴とする請求項２６に記載の方法。
【請求項３０】
前記方法は、
前記グラフの新しい頂点ｖに対して、指定された分布ＤinおよびＤoutから２つの乱数λ（ｖ）およびμ（ｖ）を独立に生成することと、
前記乱数を利用して、
（Ａ）Ｐｒ（ｗ＝ｗj）∝λ（ｗj）（ｄin（ｗj）＋δin）となるように、λ（ｗ）（ｄin＋δin）に従って既存の頂点ｗを選択すること、
（Ｂ）Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝μ（ｖi）λ（ｗj）（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）となるように、μ（ｖ）（ｄout＋δout）に従って既存の頂点ｖ、およびλ（ｗ）（ｄin＋δin）に従って第２の既存の頂点ｗを選択すること、または
（Ｃ）Ｐｒ（ｗ＝ｗi）∝μ（ｗi）（ｄout（ｗi）＋δout）となるように、μ（ｗ）（ｄout＋δout）に従って既存の頂点ｗを選択すること
のように前記グラフの頂点を更新すること
をさらに備えることを特徴とする請求項１６に記載の方法。
【請求項３１】
有向スケールフリーオブジェクト関係のモデルを生成するためのコンピューティングデバイスであって、
プロセッサと、
前記プロセッサに結合したメモリであって、
乱数の系列を生成することと、
時間にわたって前記乱数のうちの個々の乱数を連続的に選択して有向スケールフリーオブジェクト関係のモデルをグラフとして生成することであって、該グラフの発展が入次数および出次数の両方に依存していることと
のために、前記プロセッサにより実行可能なコンピュータプログラム命令を備えたメモリと、
を備えたことを特徴とするコンピューティングデバイス。
【請求項３２】
前記グラフは、ノードと、該ノードのそれぞれの間の有向辺とを備えたウェブグラフであり、前記ノードはウェブページに対応し、前記有向辺はあるウェブページから別のウェブページへのハイパーリンクに対応していることを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３３】
前記コンピュータプログラム命令は、前記乱数を連続的に使用して、設定可能なパラメータα、βおよびγに従って、
（Ａ）新しいオブジェクトと古いオブジェクトとの間に辺を追加すること、
（Ｂ）２つの古いオブジェクトの間に辺を追加すること、または
（Ｃ）古いオブジェクトから新しいオブジェクトへの辺を追加すること
によって前記グラフを更新するための命令をさらに備えたことを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３４】
前記コンピュータプログラム命令は、有向優先的選択の関数として前記グラフに新しい辺を追加するための命令をさらに備えたことを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３５】
前記コンピュータプログラム命令は、入次数シフトおよび／または出次数シフトδinおよび／またはδoutの関数として前記グラフを生成するための命令をさらに備えたことを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３６】
前記コンピュータプログラム命令は、設定可能なパラメータα、β、γ、δinおよびδoutのセットに基づく測定された環境特性の関数として前記グラフをモデル化するための命令をさらに備えたことを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３７】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なることを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３８】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なり、パラメータα、β、γ、δinおよびδoutを有するジェネレータに対して、ｄinに等しい入次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数９】
2004318884.tif 000063
ここで
【数１０】
2004318884.tif 000064
であり、ｄoutに等しい出次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数１１】
2004318884.tif 000065
ここで
【数１２】
2004318884.tif 000066
であることを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項３９】
前記コンピュータプログラム命令は、確率分布
Ｐｒ（ｗ＝ｗj）∝（ｄin（ｗj）＋δin）
に従って選択されたランダムな古いオブジェクトｗへ新しいオブジェクトｖからの辺を追加することによって、前記グラフを更新するための（Ａ）に基づく命令をさらに備えたことを特徴とする請求項３３に記載のコンピューティングデバイス。
【請求項４０】
前記コンピュータプログラム命令は、前記グラフの第１の既存のオブジェクトｖから第２の既存のオブジェクトｗへの辺を追加することによって前記グラフを更新するための（Ｂ）に基づく命令をさらに備え、該オブジェクトｖおよびｗは、確率分布
Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）
に従って選択されることを特徴とする請求項３３に記載のコンピューティングデバイス。
【請求項４１】
前記コンピュータプログラム命令は、ランダムに選択された古いオブジェクトｗから新しいオブジェクトｖへの辺を追加することによって前記グラフを更新するための（Ｃ）に基づく命令をさらに備え、ｗは、確率分布
Ｐｒ（ｗ＝ｗi）∝ｄout（ｗi）＋δout
に従って選択されることを特徴とする請求項３３に記載のコンピューティングデバイス。
【請求項４２】
（Ａ）に基づく前記コンピュータプログラム命令は、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、新しいオブジェクトｖiから古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加するための命令をさらに備えたことを特徴とする請求項３３または３９に記載のコンピューティングデバイス。
【請求項４３】
（Ｂ）に基づく前記コンピュータプログラム命令は、
区間［０，ｔ＋ｎδout］を幅ｄout（ｖi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｖiを選択することと、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、古いオブジェクトｖiから第２の古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加するための命令をさらに備えたことを特徴とする請求項３３または４０に記載のコンピューティングデバイス。
【請求項４４】
（Ｃ）に基づく前記コンピュータプログラム命令は、
区間［０，ｔ＋ｎδout］を幅ｄout（ｗi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｗiを選択することと
によって、古いオブジェクトｗiから新しいオブジェクトｖjへの辺Ｅ（ｉ，ｊ）を追加するための命令をさらに備えたことを特徴とする請求項３３または４１に記載のコンピューティングデバイス。
【請求項４５】
前記コンピュータプログラム命令は、
前記グラフの新しい頂点ｖに対して、指定された分布ＤinおよびＤoutから２つの乱数λ（ｖ）およびμ（ｖ）を独立に生成するための命令と、
前記乱数を利用して、
（Ａ）Ｐｒ（ｗ＝ｗj）∝λ（ｗj）（ｄin（ｗj）＋δin）となるように、λ（ｗ）（ｄin＋δin）に従って既存の頂点ｗを選択すること、
（Ｂ）Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝μ（ｖi）λ（ｗj）（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）となるように、μ（ｖ）（ｄout＋δout）に従って既存の頂点ｖ、およびλ（ｗ）（ｄin＋δin）に従って第２の既存の頂点ｗを選択すること、または
（Ｃ）Ｐｒ（ｗ＝ｗi）∝μ（ｗi）（ｄout（ｗi）＋δout）となるように、μ（ｗ）（ｄout＋δout）に従って既存の頂点ｗを選択すること、
のように前記グラフの頂点を更新するための命令と
をさらに備えたことを特徴とする請求項３１に記載のコンピューティングデバイス。
【請求項４６】
有向スケールフリーオブジェクト関係のモデルを生成するためのコンピューティングデバイスであって、
乱数の系列を生成するための手段と、
時間にわたって前記乱数のうちの個々の乱数を連続的に選択して有向スケールフリーオブジェクト関係のモデルをグラフとして生成するための手段であって、該グラフの発展が入次数および出次数の両方に依存している手段と
を備えたことを特徴とするコンピューティングデバイス。
【請求項４７】
前記グラフは、ノードと、該ノードのそれぞれの間の有向辺とを備えたウェブグラフであり、前記ノードはウェブページに対応し、前記有向辺はあるウェブページから別のウェブページへのハイパーリンクに対応していることを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項４８】
前記乱数を連続的に使用して、設定可能なパラメータα、βおよびγに従って、
（Ａ）新しいオブジェクトと古いオブジェクトとの間に辺を追加すること、
（Ｂ）２つの古いオブジェクトの間に辺を追加すること、または
（Ｃ）古いオブジェクトから新しいオブジェクトへの辺を追加すること
によって前記グラフを更新するための手段をさらに備えたことを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項４９】
有向優先的選択の関数として前記グラフに新しい辺を追加するための手段をさらに備えたことを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項５０】
入次数シフトおよび／または出次数シフトδinおよび／またはδoutの関数として前記グラフを生成するための手段をさらに備えたことを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項５１】
設定可能なパラメータα、β、γ、δinおよびδoutのセットに基づく測定された環境特性の関数として前記グラフをモデル化するための手段をさらに備えたことを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項５２】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なることを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項５３】
前記グラフによって表されたオブジェクトに関連する入次数べき乗則は、該オブジェクトに関連する出次数べき乗則と異なり、パラメータα、β、γ、δinおよびδoutを有するジェネレータに対して、ｄinに等しい入次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数１３】
2004318884.tif 000067
ここで
【数１４】
2004318884.tif 000068
であり、ｄoutに等しい出次数を持つ頂点の割合が漸近的に以下のようにスケールし、
【数１５】
2004318884.tif 000069
ここで
【数１６】
2004318884.tif 000070
であることを特徴とする請求項４６に記載のコンピューティングデバイス。
【請求項５４】
確率分布
Ｐｒ（ｗ＝ｗj）∝（ｄin（ｗj）＋δin）
に従って選択されたランダムな古いオブジェクトｗへ新しいオブジェクトｖからの辺を追加することによって、前記グラフを更新するための（Ａ）に基づく手段をさらに備えたことを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項５５】
前記グラフの第１の既存のオブジェクトｖから第２の既存のオブジェクトｗへの辺を追加することによって前記グラフを更新するための（Ｂ）に基づく手段をさらに備え、該オブジェクトｖおよびｗは、確率分布
Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）
に従って選択されることを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項５６】
ランダムに選択された古いオブジェクトｗから新しいオブジェクトｖへの辺を追加することによって前記グラフを更新するための（Ｃ）に基づく手段をさらに備え、ｗは、確率分布
Ｐｒ（ｗ＝ｗi）∝ｄout（ｗi）＋δout
に従って選択されることを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項５７】
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、新しいオブジェクトｖiから古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加するための（Ａ）に基づく手段をさらに備えたことを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項５８】
区間［０，ｔ＋ｎδout］を幅ｄout（ｖi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｖiを選択することと、
区間［０，ｔ＋ｎδin］を幅ｄin（ｗj）＋δinのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδin］から均等に乱数ｒinを選択することと、
前記乱数ｒinがｊ番目のスロットに入る場合に古いオブジェクトｗjを選択することと
によって、古いオブジェクトｖiから第２の古いオブジェクトｗjへの辺Ｅ（ｉ，ｊ）を追加するための（Ｂ）に基づく手段をさらに備えたことを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項５９】
区間［０，ｔ＋ｎδout］を幅ｄout（ｗi）＋δoutのｎ個のスロットに分割することと、
前記区間［０，ｔ＋ｎδout］から均等に乱数ｒoutを選択することと、
前記乱数ｒoutがｉ番目のスロットに入る場合に古いオブジェクトｗiを選択することと
によって、古いオブジェクトｗiから新しいオブジェクトｖjへの辺Ｅ（ｉ，ｊ）を追加するための（Ｃ）に基づく手段をさらに備えたことを特徴とする請求項４８に記載のコンピューティングデバイス。
【請求項６０】
前記グラフの新しい頂点ｖに対して、指定された分布ＤinおよびＤoutから２つの乱数λ（ｖ）およびμ（ｖ）を独立に生成するための手段と、
前記乱数を利用して、
（Ａ）Ｐｒ（ｗ＝ｗj）∝λ（ｗj）（ｄin（ｗj）＋δin）となるように、λ（ｗ）（ｄin＋δin）に従って既存の頂点ｗを選択することと、
（Ｂ）Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝μ（ｖi）λ（ｗj）（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）となるように、μ（ｖ）（ｄout＋δout）に従って既存の頂点ｖ、およびλ（ｗ）（ｄin＋δin）に従って第２の既存の頂点ｗを選択すること、または
（Ｃ）Ｐｒ（ｗ＝ｗi）∝μ（ｗi）（ｄout（ｗi）＋δout）となるように、μ（ｗ）（ｄout＋δout）に従って既存の頂点ｗを選択することと
のように前記グラフの頂点を更新するための手段と
をさらに備えたことを特徴とする請求項４６に記載のコンピューティングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、有向スケールフリーオブジェクト関係（ｄｉｒｅｃｔｅｄ  ｓｃａｌｅ  ｆｒｅｅ  ｏｂｊｅｃｔ  ｒｅｌａｔｉｏｎｓｈｉｐｓ）の成長および分布のモデルを生成することに関する。
【背景技術】
【０００２】
ランダムグラフの分布を生成するための多くの新しいプロセスが導入され、解析されている。これらは、「ウェブグラフ」のような多くの大規模な実世界のグラフにおいて観測観察されるある種の共通の特徴に触発されたものである。ウェブグラフの頂点（ｖｅｒｔｅｘ）は、ウェブページであり、２つのウェブページ間のハイパーリンクごとに有向辺（ｄｉｒｅｃｔｅｄ  ｅｄｇｅ）がある。概観を知るために、調査論文である非特許文献２および１５を参照されたい。モデル化されるその他のグラフには、「インターネットグラフ」（非特許文献１８）、映画俳優（非特許文献２８）および科学的コラボレーショングラフ（非特許文献２５）、セルラネットワーク（非特許文献２１）等がある。
【０００３】
他のネットワークとの関連でStrogatzとWatts（非特許文献２８）によって最初に検討された対数径（ｌｏｇａｒｉｔｈｍｉｃ  ｄｉａｍｅｔｅｒ）の「スモールワールド現象」に加えて、主な観測の１つは、これらの大規模な実世界グラフの多くは、頂点次数の分布が古典的なランダムグラフモデルＧ（ｎ，ｐ）およびＧ（ｎ，Ｍ）（非特許文献１６、１７、１９、および９も参照）のポアソン分布ではなく、べき乗則に従う点で「スケールフリー」（非特許文献５、７、２４を参照）であることである。ワールドワイドウェブ（ＷＷＷ）に見られるように動的に発展するオブジェクト関係を示す実世界の事象、現象、およびシステムについての、小径（ｓｍａｌｌ  ｄｉａｍｅｔｅｒ）およびクラスタリングなどのこのようなスケールフリー性や、他の特徴をモデル化しようと試みる多くの新しいグラフジェネレータが提案されている。残念ながら、このような既存のジェネレータは、完全に無向性であるか、良くても半方向性、あるいは一方向性（すなわち、入次数または出次数のどちらかを扱うが、両方を同時に扱っていない）のモデルを生成し、そして／または静的にあらかじめ決められた次数分布を有している。
【０００４】
【非特許文献１】W.  Aiello,  F.  Chung  and  L.  Lu,  A  random  graph  model  for  power  law  graphs,  Experiment.  Math.  10  (2001),  53-66.
【非特許文献２】R.  Albert  and  A.L.  Barabasi,  Statistical  mechanics  of  complex  networks,  arXiv:cond-mat/0106096  2001)
【非特許文献３】R.  Albert,  H.  Jeong  and  A.L.  Barabasi,  Diameter  of  the  world-wide  web,  Nature  401  (1999),  130-131.
【非特許文献４】K.  Azuma,  Weighted  sums  of  certain  dependent  variables,  Tohoku  Math.  J.  3  (1967),  357-367.
【非特許文献５】A.-L.  Barabasi  and  R.  Albert,  Emergence  of  scaling  in  random  networks,  Science  286  (1999),  509-512.
【非特許文献６】A.-L.  Barabasi,  R.  Albert  and  H.  Jeong,  Mean-field  theory  for  scale-free  random  networks,  Physica  A  272  (1999),  173-187.
【非特許文献７】A.-L.  Barabasi,  R.  Albert  and  H.  Jeong,  Scale-free  characteristics  of  random  networks:  the  topology  of  world-wide  web,  Physica  A  281  (2000),  69-77.
【非特許文献８】G.  Bianconi  and  A.-L.  Barabasi,  Competition  and  multiscaling  in  evolving  networks,  cond-mat/0011029.
【非特許文献９】B.  Bollobas,  Random  Graphs,  Second  Edition,  Cambridge  studies  in  advanced  mathematics,  vol.  73,  Cambridge  University  Press,  Cambridge,  2001,  xvi  +  498  pp.
【非特許文献１０】B.  Bollobas,  Martingales,  isoperimetric  inequalities  and  random  graphs.    In  Combinatorics  (Eger,  1987),  113-139,  Colloq.  Math.  Soc.  Janos  Bolyai,  52,  North-Holland,  Amsterdam  1988.
【非特許文献１１】B.  Bollobas  and  O.M.  Riordan,  The  diameter  of  a  scale-free  random  graph,  submitted  for  publication.
【非特許文献１２】B.  Bollobas,  O.M.  Riordan,  J.  Spencer,  and  G.  Tusnady,  The  degree  sequence  of  a  scale-free  random  graph  process,  Random  Structures  and  Algorithms  18  (2001),  279-290.
【非特許文献１３】A.  Broder,  R.  Kumar,  F.  Maghoul,  P.  Raghavan,  S.  Rajagopalan,  R.  Stata,  A.  Tomkins  and  J.  Wiener,  Graph  structure  in  the  web,  Proc  9th  WWW  Conf.  309-320  (2000).
【非特許文献１４】C.  Cooper  and  A.  Frieze,  A  general  model  of  web  graphs,  preprint.
【非特許文献１５】S.N.  Dorogovtsev  and  J.F.F.  Mendes,  Evolution  of  random  networks,  preprint.
【非特許文献１６】P.  Erdos  and  A.  Renyi,  On  random  graphs.  I,  Publ.  Math.  Debrecen  6  (1959),  290-297.
【非特許文献１７】P.  Erdos  and  A.  Renyi,  On  the  evolution  of  random  graphs,  Magyar  Tud.  Akad.  Mat.  Kutato  Int.  Kozl.  5  (1960),  17-61.
【非特許文献１８】M.  Faloutsos,  P.  Faloutsos  and  C.  Faloutsos,  On  power-law  relationships  of  the  internet  topology,  SIGCOMM  1999,  Comput.  Commun.  Rev.  29  (1999),  251.
【非特許文献１９】E.N.  Gilbert,  Random  graphs,  Ann.  Math.  Statist.  30  (1959),  1141-1144.
【非特許文献２０】W.  Hoeffding,  Probability  inequalities  for  sums  of  bounded  random  variables,  J.  Amer.  Statist.  Assoc.  58  (1963),  13-30.
【非特許文献２１】H.  Jeong,  B.  Tombor,  R.  Albert,  Z.N.  Oltvai  and  A.-L.  Barabasi,  The  large-scale  organization  of  metabolic  networks,  Nature  407  (2000),  651-654.
【非特許文献２２】J.  Kleinberg,  R.  Kumar,  P.  Raghavan,  S.  Rajagopalan  and  A.  Tomkins,  The  web  as  a  graph:  measurements,  models,  and  methods,  COCOON  1999.
【非特許文献２３】R.  Kumar,  P.  Raghavan,  S.  Rajagopalan  and  A.  Tomkins,  Extracting  large  scale  knowledge  bases  from  the  web,  VLDB  1999.
【非特許文献２４】R.  Kumar,  P.  Raghavan,  S.  Rajagopalan,  D.  Sivakumar,  A.  Tomkins  and  E.  Upfal,  Stochastic  models  for  the  web  graph,  FOCS  2000.
【非特許文献２５】M.E.J.  Newman,  The  structure  of  scientific  collaboration  networks,  Proc.  Natl.  Acad.  Sci  USA  98  (2001),  404-409.
【非特許文献２６】M.E.J.  Newman,  S.H.  Strogatz  and  D.J.  Watts,  Random  graphs  with  arbitrary degree  distributions  and  their  applications,  Phys.  Rev.  E  64,  026118  (2001).
【非特許文献２７】D.  Osthus  and  G.  Buckley,  Popularity  based  random  graph  models  leading  to  a  scale-free  degree  distribution,  preprint.
【非特許文献２８】D.J.  Watts  and  S.H.  Strogatz,  Collective  dynamics  of  'small-world'  networks.  Nature  393  (1998),  440-442.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
このことに照らして、グラフを生成するための既存の技法は、オブジェクトに出たり入ったりする両方のリンクに応じた形で発展する有向オブジェクト関係（すなわち、あるオブジェクトから別のオブジェクトへのリンク）を有する動的に生成されたスケールフリーグラフの現実的な取り扱いを提供していない。この結果、従来の生成技法では、自然界、および／またはＷＷＷのような他の動的環境に存在することのあるスケールフリーな有向オブジェクト関係について、具体的、または完全にモデル化されたシミュレーションを正しく表していない。
【０００６】
これらの制限を考慮すると、関係（例えばネットワークトポロジー）の有向スケールフリーグラフまたは動的コミュニティのモデルを生成するためのシステムおよび方法が強く望まれる。このようなジェネレータは、例えば、有向インターネットルーティングプロトコルをテストするサンプルの有向ネットワークトポロジーを生成したり、サーチアルゴリズムをテストするサンプルウェブグラフを生成したりするために使用することができる。
【課題を解決するための手段】
【０００７】
有向スケールフリーオブジェクト関係のモデルを生成するためのシステムおよび方法が記載されている。１つの態様では、乱数の系列を生成する。そして、これら個々の乱数を時間にわたって選択して、入次数（ｉｎ−ｄｅｇｒｅｅ）および出次数（ｏｕｔ−ｄｅｇｒｅｅ）の系列に基づいて、有向スケールフリーオブジェクト関係をグラフとして生成する。
【発明を実施するための最良の形態】
【０００８】
以下の詳細な説明は、付随する図面を参照してなされる。図では、コンポーネントの参照番号の左端の数字はそのコンポーネントが最初に現れる特定の図を表している。
【０００９】
（概要）
以下のシステムおよび方法は、オブジェクト関係の有向スケールフリーモデリングを生成する。これは、入次数および出次数の両方（双方向）の同時処理を通じて達成されて、べき乗則の次数分布を有するグラフを生成するための非常に自然なモデルを提供する。モデル化されるエンティティまたは抽象化の特性に応じて、べき乗則は入次数と出次数とで異なることがある。このようなモデリングは、例えば、自然界、および技術コミュニティ（例えば、ＷＷＷ上のウェブページ間の有向ハイパーリンク、ＡＳインターネット上の自律的なシステム間のコネクション、インターネット上のルータ間のコネクション等）において観測されているべき乗則と一致している。
【００１０】
（例示的なオペレーティング環境）
図面を見ると、同様の参照番号は同様の要素を指しており、本発明は、好適なコンピューティング環境において実施されるものとして示される。必須ではないが、本発明は、パーソナルコンピュータにより実行されるプログラムモジュール等のコンピュータ実行可能命令との一般的関連で記述されている。プログラムモジュールは、一般に、特定のタスクを実行したり、特定の抽象データ型を実装したりするルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含む。
【００１１】
図１は、有向スケールフリーネットワークトポロジーを生成するための後述のシステム、装置および方法を実施することができる好適なコンピューティング環境１２０の一例を示している。例示的なコンピューティング環境１２０は、好適なコンピューティング環境の単なる一例に過ぎず、本明細書に記載のシステムおよび方法の使用または機能の範囲についていかなる限定を示唆するものではない。また、コンピューティング環境１２０は、コンピューティング環境１２０に示されたいかなるコンポーネントまたはその組合せに関していかなる依存性または要件を有するものとも解釈されてはならない。
【００１２】
本明細書に記載の方法およびシステムは、多くの他の汎用または専用のコンピューティングシステムの環境または構成とともに動作する。適していると思われる周知のコンピューティングシステム、環境、および／または構成の例には、ハンドヘルドデバイス、対称型マルチプロセッサ（ＳＭＰ）システム、マイクロプロセッサベース、またはプログラム可能な民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、ポータブル通信デバイス等があるが、これらには限定されない。本発明は、通信ネットワークを通じてリンクされるリモート処理デバイスによりタスクが実行される分散コンピューティング環境で実施されてもよい。分散コンピューティング環境では、プログラムモジュールはローカルおよびリモートの両方のメモリ記憶デバイスに配置されることがある。
【００１３】
図１に示すように、コンピューティング環境１２０は、コンピュータ１３０の形態の汎用コンピューティングデバイスを含む。コンピュータ１３０は、１つまたは複数のプロセッサ１３２、システムメモリ１３４、およびシステムメモリ１３４を含む種々のシステムコンポーネントをプロセッサ１３２に結合するバス１３６を含む。バス１３６は、さまざまなバスアーキテクチャのいずれかを使用するメモリバスまたはメモリコントローラ、周辺バス、アクセラレーテッドグラフィクスポート、およびプロセッサバスまたはローカルバスを含む、いくつかのタイプのバス構造のいずれかの１つまたは複数を表す。限定ではなく、例として、このようなアーキテクチャには、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、およびＭｅｚｚａｎｉｎｅバスとしても知られているＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔｓ）バスがある。
【００１４】
コンピュータ１３０は通常、さまざまなコンピュータ可読媒体を含む。このような媒体は、コンピュータ１３０によりアクセス可能な任意の利用可能な媒体であってよく、揮発性および不揮発性媒体、リムーバブルおよび非リムーバブル媒体の両方が含まれる。図１において、システムメモリ１３４は、ランダムアクセスメモリ（ＲＡＭ）１４０のような揮発性メモリ、および／または読み出し専用メモリ（ＲＯＭ）１３８のような不揮発性メモリの形態のコンピュータ可読媒体を含む。起動中などにコンピュータ１３０内の要素間で情報を転送するのに役立つ基本ルーチンが入っている基本入出力システム（ＢＩＯＳ）１４２はＲＯＭに格納される。ＲＡＭは通常、プロセッサ１３２によって直接アクセス可能、および／またはプロセッサ１３２が現在操作されているデータおよび／またはプログラムモジュールを収容する。
【００１５】
コンピュータ１３０はさらに、他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータ記憶媒体を含んでもよい。例えば、図１は、非リムーバブルの不揮発性磁気媒体（図示しないが、通常、「ハードドライブ」と呼ばれる）との読み書きを行うハードディスクドライブ１４４、リムーバブルの不揮発性磁気ディスク１４８（例えば「フロッピー（登録商標）ディスク」）との読み書きを行う磁気ディスクドライブ１４６、そしてＣＤ−ＲＯＭ／Ｒ／ＲＷ、ＤＶＤ−ＲＯＭ／Ｒ／ＲＷ／＋Ｒ／ＲＡＭ等の光媒体のようなリムーバブルの不揮発性光ディスク１５２との読み書きを行う光ディスクドライブ１５０を示している。ハードディスクドライブ１４４、磁気ディスクドライブ１４６および光ディスクドライブ１５０はそれぞれ、１つまたは複数のインタフェース１５４によってバス１３６に接続される。
【００１６】
これらのドライブおよび関連するコンピュータ可読媒体は、コンピュータ１３０のためのコンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性ストレージを提供する。本明細書に記載の例示的環境は、ハードディスク、リムーバブル磁気ディスク１４８およびリムーバブル光ディスク１５２を使用するが、当業者には理解されるように、磁気カセット、フラッシュメモリカード、ディジタルビデオディスク、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）等のような、コンピュータによってアクセス可能なデータを格納することができる他のタイプのコンピュータ可読媒体もまた、例示的なオペレーティング環境で使用することができる。
【００１７】
ハードディスク、磁気ディスク１４８、光ディスク１５２、ＲＯＭ１３８、またはＲＡＭ１４０には、例えば、ランタイム環境を提供するオペレーティングシステム（ＯＳ）１５８、１つまたは複数のアプリケーションプログラム１６０、他のプログラムモジュール１６２、およびプログラムデータ１６４等の、いくつものプログラムモジュールを格納することができる。
【００１８】
ユーザは、キーボード１６６およびポインティングデバイス１６８（例えば「マウス」）のような入力デバイスを通じてコンピュータ１３０にコマンドおよび情報を提供することができる。他の入力デバイス（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星アンテナ、シリアルポート、スキャナ、カメラ等を含むことがある。これらおよび他の入力デバイスは、バス１３６に結合されているユーザ入力インタフェース１７０を通じて処理ユニット１３２に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）のような他のインタフェースおよびバス構造により接続されてもよい。
【００１９】
モニタ１７２または他のタイプの表示デバイスもまた、ビデオアダプタ１７４のようなインタフェースを通じてバス１３６に接続される。モニタ１７２に加えて、パーソナルコンピュータは通常、スピーカおよびプリンタのような他の周辺出力デバイス（図示せず）を含み、これらは出力周辺インタフェース１７６を通じて接続することができる。
【００２０】
コンピュータ１３０は、リモートコンピュータ１７８のような１つまたは複数のリモートコンピュータへの論理コネクションを用いてネットワーク環境で動作することがある。リモートコンピュータ１７８は、コンピュータ１３０に関して本明細書に記載した要素および特徴の多くまたはすべてを含むことができる。図１に示した論理コネクションは、ローカルエリアネットワーク（ＬＡＮ）１８０および一般的な広域ネットワーク（ＷＡＮ）１８２である。このようなネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネットおよびインターネットで一般的である。
【００２１】
ＬＡＮネットワーキング環境で使用される場合、コンピュータ１３０はネットワークインタフェースまたはアダプタ１８４を通じてＬＡＮ１８０に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータは通常、ＷＡＮ１８２を介して通信を確立するためのモデム１８６等の手段を含む。モデム１８６は、内蔵でも外付けでもよいが、ユーザ入力インタフェース１７０等の適当なメカニズムを介してシステムバス１３６に接続することができる。
【００２２】
図１には、インターネット経由のＷＡＮの特定の実施例が示されている。ここで、コンピュータ１３０はモデム１８６を使用して、インターネット１８８経由で少なくとも１つのリモートコンピュータ１７８との通信を確立する。
【００２３】
ネットワーク環境では、コンピュータ１３０に関して図示されているプログラムモジュールまたはその部分は、リモートメモリ記憶デバイスに格納されてもよい。このように例えば、図１に示すように、リモートアプリケーションプログラム１９０はリモートコンピュータ１７８のメモリデバイス上に存在することもある。理解されるように、図示し説明したネットワークコネクションは例示であり、コンピュータ間に通信リンクを確立する他の手段を使用してもよい。
【００２４】
図２は、アプリケーションプログラム１６０およびプログラムデータ１６４を含む、図１のシステムメモリ１３４のさらなる例示的な態様を示すブロック図である。アプリケーションプログラム１６０は、例えば、有向スケールフリーグラフ２０４（以下、多くの場合「グラフ」という）を生成するための有向スケールフリーオブジェクト関係ネットワーク生成モジュール２０２を含む。各グラフ２０４は、時間ｔにわたり実行される離散的な繰り返し動作中にネットワーク生成モジュール２０２によってグラフに追加された頂点およびそれぞれの頂点間の辺を表している。グラフ２０４を生成するために使用されるアルゴリズムのさらに詳細な態様に進む前に、グラフ２０４の例示的な構造および要素について、グラフ２０４（ａ）を参照して説明する。
【００２５】
グラフ２０４（ａ）は行列として表現されている。行列のそれぞれの横の行ｉおよび縦の列ｊは、それぞれの頂点、またはノード（すなわち、Ｎｏｄｅ1〜ＮｏｄｅN）に対応する。このように、ｉ＝１...Ｎ、およびｊ＝１...Ｎである。（以下、多くの場合ノードという用語は頂点という用語と互換的に用いる）。ある数のノードから、より多くのノードへグラフ２０４（ａ）を成長させるため、ネットワーク生成モジュール２０２がノードをグラフ２０４（ａ）に追加する。これは、新しいノードを表す行および列がグラフ２０４（ａ）に追加されることを意味する。グラフ２０４（ａ）の（ｉ，ｊ）要素Ｅ（ｉ，ｊ）は、ノードｉからノードｊへの有向辺またはコネクションの数を表す。これは、例えば、ウェブページｉからウェブページｊへのハイパーリンクの数、あるいはエンティティｉからエンティティｊへのＥ（ｉ，ｊ）個のオブジェクトまたは特性の有向移動（例えば、商人と買い手の間の金銭や商品の移動）等をモデル化する。
【００２６】
表現２０４（ａ）においては、辺の向きが行ノードから列ノードへと評価される規約を適用している。
【００２７】
次に、図３のネットワーク３００を考慮して、グラフ２０４（ａ）の辺Ｅ（ｉ，ｊ）の値について説明する。図３は、有向オブジェクト関係の例示的なネットワーク３００を示している。この例示的ネットワークにおいて、オブジェクト３０２−１、３０２−２、および３０２−３は、別のオブジェクトとの間に少なくとも１つの辺３０４（すなわち、１つまたは複数の辺３０４−１〜３０４−Ｎ）を有する。例えば、オブジェクト３０２−１（図３）はループしている辺３０４−１を示している。これは、このオブジェクトがそれ自体との関係を有する（例えば、それ自体の内部のポイントに対するハイパーリンクを有するウェブページ）ことを示す。
【００２８】
図２を参照すると、このようなループしている辺は、グラフ２０４（ａ）において、行Ｎｏｄｅ1と列Ｎｏｄｅ1の交点に対応する辺の値にも表現されている（すなわち、Ｅ（１，１）＝１）。これは、Ｎｏｄｅ1がそれ自体と単一の関係を有することを示している。このタイプの辺を「ループ」という。
【００２９】
この実施例では、モジュール２０２は、グラフ２０４に（自己）ループを生成することができる。しかし、生成モジュール２０２は、ループを生成しないように構成して自己ループのないシステムをモデル化することができる。
【００３０】
図２の有向スケールフリーグラフ２０４（ａ）を用いて図３の辺３０４を表す別の例として、図３のオブジェクト３０２−１がノード３０２−２に対する３本の辺３０４−２〜３０４−４を有することに注目する。特に、行Ｎｏｄｅ1の列Ｎｏｄｅ2との交点（すなわちＥ（１，２））は３という値を示しており、これは、図３のオブジェクト３０２−１とオブジェクト３０２−２の間の関係を表している。このタイプの辺を「多重辺」といい、一般に、特定のオブジェクトＮｏｄｅiから別のオブジェクトＮｏｄｅjへの２つ以上の辺を指す。この実施例では、モジュール２０２は、グラフ２０４に多重辺を生成することができる。しかし、別の実施例では、生成モジュール２０２は、多重辺を生成しないように構成して単一辺のみがあるシステムをモデル化することができる。
【００３１】
図３のネットワーク３００、および図２のグラフ２０４（ａ）はそれぞれ３個のみのノード／オブジェクトを表現／マップしているが、理解され得るように、例示的なネットワーク３００およびグラフ２０４（ａ）によって表現／マップされるオブジェクトの複雑さおよび個数は例示であり、いかなる複雑さのいかなる個数のオブジェクトを表現／マップすることができる。
【００３２】
次に、有向スケールフリーオブジェクト関係を生成する生成モジュール２０２によって使用されるアルゴリズムについてさらに詳細に説明する。
【００３３】
（有向スケールフリーオブジェクト関係の生成）
図２を参照すると、生成モジュール２０２は、グラフ２０４の生成中にランダムおよび確率の側面を導入して、例えば技術的（例、ウェブ）、文化的、自然等の環境でしばしば観測される、動的に作成されるオブジェクト（例、ウェブページ等）およびそれらの間の関係（例、ハイパーリンク等）をシミュレートする。このようなランダムの側面は、生成モジュール２０２が、乱数生成モジュール（ＲＮＧ）２０８に対して、時間ｔにわたり反復的にそれぞれの乱数２０６を要求することを通じて得られる。ＲＮＧ２０８は、独立したモジュールとすることができ、またはＯＳ１５８（図１）のようなコンピュータプログラムモジュールによって提供されるサービスとすることもできる。
【００３４】
乱数２０６は、０と１の間にあることが要求される場合がある。これらの乱数２０６のそれぞれについて、ネットワーク生成モジュール２０２は、乱数２０６を用いて、その乱数が、０とαの間、αとα＋βの間、α＋βとα＋β＋γの間のいずれにあるかに応じて、それぞれ（Ａ）、（Ｂ）および（Ｃ）とラベル付けされる３つの可能性のうちの１つを決める。パラメータα、βおよびγは、足し合わせると１に等しい（すなわちα＋β＋γ＝１）非負の実数である。これらのパラメータは、設定データ２１０のそれぞれの部分として格納される。パラメータα、βおよびγは、さまざまな方法で選択／決定することができる。例えば、システム管理者によって手動で事前設定されるか、あるいは環境測定値を考慮してプログラム的に設定される等である。これにより、モデル生成プロセスをカスタマイズする自由度が著しく高まって、種々のタイプの測定環境の構造的関係およびオブジェクト関係をシミュレートすることができる。
【００３５】
生成モジュール２０２が乱数２０６を範囲［０，α］にマップする場合、生成モジュール２０２は、頂点を追加し、その新しい頂点から既存の（古い）頂点への辺を追加することによって、グラフ２０４を拡張する。生成モジュール２０２が乱数２０６を範囲［α，α＋β］にマップする場合、生成モジュール２０２は、２つの古い頂点を連結することによってグラフ２０４を拡張する（すなわち、頂点は追加されず、Ｅ（ｉ，ｊ）値の１つが１だけ増加する）。生成モジュール２０２が乱数２０６を範囲［α＋β，α＋β＋γ］にマップする場合、生成モジュール２０２は、古い頂点を新しく生成した頂点に連結することによってグラフ２０４を拡張する。さらに、グラフ生成中、モジュール２０２は、設定可能な定数δinおよび／またはδoutを適用して、入次数シフトおよび出次数シフトをグラフに導入する。
【００３６】
次数シフトδinまたはδoutは、頂点の入次数または出次数にそれぞれ加算される非負のパラメータである。次数シフトは、ランダム頂点を選択するために使用される他の規則を適用する前に加算される。
【００３７】
上記をふまえて、Ｇ0を、ある決まった初期有向グラフ２０４、例えば、辺のない（すなわちＥ（１，１）＝０）単一の頂点（すなわちＮｏｄｅ1）とし、ｔ0を、Ｇ0の辺の数とする。生成モジュール２０２は、繰り返しごとに常に１本の辺を追加し、Ｇ（ｔ0）＝Ｇ0に設定し、そのため時刻ｔでは、グラフＧ（ｔ）はちょうどｔ本の辺と、ランダムな数ｎ（ｔ）個の頂点を有する。説明のために、辺および頂点の数、ならびに他の中間パラメータおよび計算値を、「他のデータ」２１２のそれぞれの部分によって表す。
【００３８】
生成モジュール２０２の動作において、ｄout＋δoutに従ってＧ（ｔ）の頂点ｖを選択することは、Ｐｒ（ｖ＝ｖi）がｄout（ｖi）＋δoutに比例するように、すなわちＰｒ（ｖ＝ｖi）＝（ｄout（ｖi）＋δout）／（ｔ＋δoutｎ（ｔ））となるようにｖを選択することを意味する。ｄin＋δinに従ってｖを選択するとは、Ｐｒ（ｖ＝ｖj）＝（ｄin（ｖj）＋δin）／（ｔ＋δinｎ（ｔ））となるようにｖを選択することを意味する。ここで、ｄout（ｖi）およびｄin（ｖj）はそれぞれ、グラフＧ（ｔ）で測定されるｖiの出次数およびｖjの入次数である。
【００３９】
ｔ≧ｔ0の場合、生成モジュール２０２は、次の規則に従ってＧ（ｔ）からＧ（ｔ＋１）を形成する：
（Ａ）  確率α（設定データ値２１０を参照）で、新しい頂点ｖを、ｖから既存の頂点ｗへの辺とともに追加する。ここでｗは、Ｐｒ（ｗ＝ｗj）∝（ｄin（ｗj）＋δin）となるように、ｄin＋δinに従って選択される。（例えば、ウェブグラフにおいて、頂点ｖから頂点ｗへのハイパーリンクを表す１本の辺を追加する）。このアルゴリズムへの入力はｎ＝ｎ（ｔ）個の頂点およびｔ本の辺であり、出力はｎ（ｔ＋１）＝ｎ（ｔ）＋１個の頂点およびｔ＋１本の辺である。新しい頂点ｖ＝Ｎｏｄｅn+1を追加した後、その新しい頂点ｖからの辺を受け入れることになる特定の既存の頂点ｗは次のように決定される：
Ｅ（ｉ，ｊ）＝Ｅij＝頂点ｉから頂点ｊへの辺の数。
【００４０】
【数１】
2004318884.tif 000003
【００４１】
この時点で、生成モジュール２０２は、０と、Ｇ（ｔ）におけるすべての数ｄin（ｊ）＋δinの和
【００４２】
【数２】
2004318884.tif 000004
【００４３】
との間のさらなる乱数２０６を要求する。０からｔ＋ｎδinまでの範囲は、長さｄin（ｊ）＋δin，ｊ＝１，...，ｎのｎ個のスロットに分割される。乱数２０６は特定のスロットｊに入ることになる。この時点で、生成モジュール２０２はＥ（ｎ＋１，ｊ）＝１に設定する。
【００４４】
（Ｂ）  確率β（設定データ値２１０を参照）で、既存の頂点ｖから既存の頂点ｗへの辺を追加する。ここでｖおよびｗは、Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）となるように、独立に、ｄout＋δoutに従ってｖ、そしてｄin＋δinに従ってｗが選択される。このアルゴリズムへの入力はｎ＝ｎ（ｔ）個の頂点およびｔ本の辺であり、出力はｎ（ｔ＋１）＝ｎ（ｔ）個の頂点およびｔ＋１本の辺である。生成モジュール２０２は、次のような乱数２０６（ｒout）を生成することによって、頂点ｗに対して辺を追加することになる特定の既存の頂点ｖを選択する：
ｒout∈［０，ｔ＋ｎδout］
この範囲は、ｉ番目のスロットが長さｄout（ｉ）＋δoutを有するスロットに分割される。乱数２０６は特定のスロットｉに入り、頂点ｖはＮｏｄｅiになることになる。生成モジュール２０２は、次のような乱数２０６（ｒin）を生成することによって、辺を受け入れることになる頂点ｗを決定する：
ｒin∈［０，ｔ＋ｎδin］
この範囲は、ｊ番目のスロットが長さｄin（ｊ）＋δinを有するスロットに分割される。乱数２０６は特定のスロットｊに入り、頂点ｗはＮｏｄｅjになることになる。この時点で、生成モジュール２０２はＥ（ｉ，ｊ）を１だけインクリメントする。
【００４５】
（Ｃ）  確率γ（設定データ値２１０を参照、これはγ＝１−α−βとして計算できる）で、新しい頂点ｖと、既存の頂点ｗからｖへの辺とを追加する。ここでｗは、Ｐｒ（ｗ＝ｗi）∝（ｄout（ｗi）＋δout）となるように、ｄout＋δoutに従って選択される。このアルゴリズムへの入力はｎ＝ｎ（ｔ）個の頂点およびｔ本の辺であり、出力はｎ（ｔ＋１）＝ｎ（ｔ）＋１個の頂点およびｔ＋１本の辺である。新しい頂点ｖ＝Ｎｏｄｅn+1を追加すると、その新しい頂点ｖに対して辺を追加することになる特定の既存の頂点ｗは次のように決定される：
乱数（ｒout）２０６を下記に従って生成する。
ｒout∈［０，ｔ＋ｎδout］
【００４６】
この範囲は、ｊ番目のスロットが長さｄout（ｉ）＋δoutを有するようなスロットに分割される。乱数２０６は特定のスロットｉに入り、頂点ｗはＮｏｄｅiになることになる。したがって、生成モジュール２０２はＥ（ｉ，ｎ＋１）＝１に設定する。
【００４７】
生成モジュール２０２はパラメータに関するさらなる仮定をしないが、パラメータのある特定の設定が回避される場合に限り、結果として得られるグラフの挙動は非自明となる。特に、自明性を除外するために、以下のパラメータ値を回避することができる：
・α＋γ＝０（⇔グラフが成長しない）
・δin＋δout＝０（⇔Ｇ0に属さないすべての頂点でｄin＝０またはｄout＝０）
・αδin＋γ＝０（⇔Ｇ0に属さないすべての頂点でｄin＝０）
・γ＝１（⇔Ｇ0に属さないすべての頂点でｄin＝１）
・γδout＋α＝０（⇔Ｇ0に属さないすべての頂点でｄout＝０）
・α＝１（⇔Ｇ0に属さないすべての頂点でｄout＝１）
【００４８】
１つの実施例において、グラフ２０４がウェブグラフを表す場合、δoutは０に設定される。その動機は、規則（Ｃ）の下で追加された頂点が、純粋にコンテンツを提供するウェブページに対応することである。このようなページは変化せず、出リンクなしで生じ、出リンクなしのままとどまる。この実施例では、規則（Ａ）の下で生成／追加される頂点は通常のページに対応し、そのページへは後でリンクが追加される可能性がある。数学的には、δout＝０に加えてδin＝０ととることが自然に思われるかもしれないが、そうすると、Ｇ0に属さないあらゆるページが入リンクを有しないか出リンクを有しないかのいずれかであるようなモデル、すなわち自明なモデルとなってしまう。
【００４９】
非ゼロ値のδinは、ページが、何か（例えばサーチエンジン）がそれをポイントするまでウェブの一部とみなされないと主張することに対応する。これにより、生成モジュール２０２は、グラフの残りの部分とは独立／別個にサーチエンジンからの辺を考慮することができる。というのは、それらの辺は通常、他のタイプの辺とは異なる性質の辺であるとみなされる（例えばサーチアルゴリズムを実装する目的で）からである。同じ理由により、δinは整数である必要はない。パラメータδoutを含めるのは、辺の方向を逆転すること（αとγ、およびδinとδoutの入れ換え）に関して対称性をモデルに与え、そしてウェブグラフの場合以外のコンテクストにもモデルを適応させるためである。
【００５０】
１つの実施例において、β＝γ＝δout＝０およびα＝δin＝１とし、生成モジュール２０２は、Barabasi-Albertモデル（非特許文献５）のｍ＝１の特別な場合の正確なバージョンを含む。ここでｍは、それぞれの新しい頂点に追加される新しい辺の数を表す。新しい頂点毎にｍ本の辺を追加するか、または（非特許文献１４にあるように）新しい頂点毎にある特定の分布のランダムな本数の新しい辺を追加することによって、ここまで説明したものよりも一般的なモデルを、さらなるパラメータを用いて生成することができる。本明細書の記載を実施するにあたって、Barabasi-Albertパラメータｍ、すなわち全体の平均次数を変化させることの主要な効果は、βを変化させることによって達成される。
【００５１】
ここまで説明したものよりも一般的なモデルを、同じくさらなるパラメータを用いて生成して、異なる頂点が異なる適応度を有するシステムを記述することができる。例えば、一部のウェブページは他のウェブページより適応度が高い、すなわち魅力的であるとみなすことができ、たとえそれらの次数が適応度の低いウェブページの次数ほど高くなくても、単位時間当たりに、より多くのコネクションを得ることがある。これをモデル化するため、生成モジュール２０２が新しい頂点ｖを作成するたびに、乱数ジェネレータ２０８が独立に２つの乱数λ（ｖ）およびμ（ｖ）を、それぞれある指定された分布ＤinおよびＤoutから、互いに独立して、そしてすべての先行する選択と独立して生成する。すると、先のステップ（Ａ）、（Ｂ）および（Ｃ）はつぎのように修正される。ステップ（Ａ）では、Ｐｒ（ｗ＝ｗj）∝λ（ｗj）（ｄin（ｗj）＋δin）となるように、既存の頂点ｗがλ（ｗ）（ｄin＋δin）に従って選択される。ステップ（Ｂ）では、Ｐｒ（ｖ＝ｖi，ｗ＝ｗj）∝μ（ｖi）λ（ｗj）（ｄout（ｖi）＋δout）（ｄin（ｗj）＋δin）となるように、既存の頂点ｖがμ（ｖ）（ｄout＋δout）に従って選択され、既存の頂点ｗがλ（ｗ）（ｄin＋δin）に従って選択される。ステップ（Ｃ）では、Ｐｒ（ｗ＝ｗi）∝μ（ｗi）（ｄout（ｗi）＋δout）となるように、既存の頂点ｗがμ（ｗ）（ｄout＋δout）に従って選択される。
【００５２】
（例示的な手続き）
図４は、有向スケールフリーオブジェクト関係を生成するための例示的な手続き４００を示している。説明のために、これらの手続き上の動作は、図１および図２のプログラムモジュールおよびデータ機能を参照して説明される。ブロック４０２で、生成モジュール２０２は、数値確率α、β、γ、および設定可能な入次数および出次数のシフト定数δinおよびδoutを設定する。ブロック４０４で、生成モジュール２０２は、乱数２０６を生成して、時間にわたって連続するステップ（Ａ）、（Ｂ）または（Ｃ）を選択して、有向スケールフリーオブジェクト関係をグラフとして生成する。有向辺がそこに／そこから追加される頂点のさらなるランダム選択は、優先的選択（ｐｒｅｆｅｒｅｎｔｉａｌ  ａｔｔａｃｈｍｅｎｔ）、すなわち、先の（Ａ）、（Ｂ）および（Ｃ）に記載したような入次数および出次数による選択を使用する。
【００５３】
（まとめ）
記載したシステムおよび方法は、有向スケールフリーオブジェクト関係を生成する。本システムおよび方法は、構造上の特徴および方法上の動作に固有の言葉で説明したが、添付の特許請求の範囲に記載した主題は、説明した特定の特徴および動作に必ずしも限定されない。むしろ、特定の特徴および動作は、特許請求の範囲の主題を実施する例示的な形態として開示されている。例えば、記載したシステム１００および方法４００は、ウェブまたはその一部の有向スケールフリーモデル（ウェブグラフ）の生成に適用可能であるほかに、多くの他の自然に発生している（人工、その他の）物理的および抽象的なオブジェクト関係のカスタマイズされたモデルを生成するために使用することもできる。
【００５４】
（付録Ａ）
べき乗則を求めるため、和が１になる定数α，β，γ≧０と、δin，δout≧０を固定し、
【００５５】
【数３】
2004318884.tif 000005
【００５６】
とおく。また、正の整数ｔ0と、ｔ0本の辺を有する初期グラフＧ（ｔ0）を固定する。入次数ｉを持つＧ（ｔ）の頂点の数をｘi（ｔ）、出次数ｉを持つ数をｙi（ｔ）とする。
【００５７】
なお、αδin＋γ＝０（Ｇ0に属さないすべての頂点が入次数０となる）の場合、またはγ＝１（Ｇ0に属さないすべての頂点が入次数１となる）の場合、入次数の分布が自明となるが、γδout＋α＝０またはα＝１の場合には出次数の分布が自明となる。したがって、次の定理ではこれらの場合を除外する。
【００５８】
定理１
ｉ≧０を固定する。ｘi（ｔ）＝ｐiｔ＋ｏ（ｔ）およびｙi（ｔ）＝ｑiｔ＋ｏ（ｔ）が確率１で成り立つような定数ｐiおよびｑiが存在する。さらに、αδin＋γ＞０かつγ＜１ならば、ｉ→∞のとき
【００５９】
【数４】
2004318884.tif 000006
【００６０】
である。ここでＸIN＝１＋１／ｃ1、ＣINは正の定数である。γδout＋α＞０かつα＜１ならば、ｉ→∞のとき
【００６１】
【数５】
2004318884.tif 000007
【００６２】
である。ここでＸOUT＝１＋１／ｃ2、ＣOUTは正の定数である。
【００６３】
上記の記述において、ｏ（ｔ）という記号は、ｉを固定してｔ→∞を指し、ａ（ｉ）〜ｂ（ｉ）は、ｉ→∞のときａ（ｉ）／ｂ（ｉ）→１を意味する。
【００６４】
証明  
初期グラフがｎ0個の頂点を有する場合、ｎ（ｔ）は、ｎ0に、平均（α＋γ）（ｔ−ｔ0）の二項分布を加えたものに等しいことに注意する。Chernoff境界から、十分に大きいすべてのｔに対して次式を得るようなある正の定数ｃが存在する。
【００６５】
【数６】
2004318884.tif 000008
【００６６】
特に、上記の確率はｔ→∞のときｏ（ｔ-1）である。
【００６７】
各ｉに対してグラフＧ（ｔ）内の入次数ｉの頂点の数を与えるベクトル（ｘ0（ｔ），ｘ1（ｔ），...）は、ｔが１だけ増えるに従ってどう変化するかを考える。Ｇ（ｔ）を所与とする。すると、確率αで、入次数０の新しい頂点が次のステップで作成され、確率γで、入次数１の新しい頂点が作成される。より具体的には、確率α＋βで、古い頂点の入次数が増加する。Ｇ（ｔ）からＧ（ｔ＋１）に進む際に、優先的選択規則から、動作（Ａ）または（Ｂ）を実行すると仮定すれば、入次数ｉの特定の頂点がその入次数を増加する確率はちょうど（ｉ＋δin）／（ｔ＋δinｎ（ｔ））である。（Ａ）または（Ｂ）を行う機会はα＋βであり、Ｇ（ｔ）は入次数ｉの頂点をちょうどｘi（ｔ）個有するので、これらのいずれかがＧ（ｔ＋１）内の入次数ｉ＋１の頂点となる機会はちょうど
【００６８】
【数７】
2004318884.tif 000009
【００６９】
となり、そのためこの確率で、入次数ｉの頂点の数が１だけ減少する。しかし、確率
【００７０】
【数８】
2004318884.tif 000010
【００７１】
で、Ｇ（ｔ）内の入次数ｉ−１の頂点がＧ（ｔ）内の入次数ｉの頂点となり、入次数ｉの頂点の数が１だけ増加する。これらの効果をまとめると、
【００７２】
【数９】
2004318884.tif 000011
【００７３】
となる。ここで、ｘ-1（ｔ）＝０とし、また、定義関数を１Aとし、これは、事象Ａが成り立つ場合に１であり、それ以外の場合に０となる。
【００７４】
ｉを固定する。（２）の両辺の期待値をとりたい。唯一の問題は、右辺第２項のｎ（ｔ）である。このため、（１）の非常に弱い形から、確率１−ｏ（ｔ-1）で｜ｎ（ｔ）−（α＋γ）ｔ｜＝ｏ（ｔ3/5）が得られることに注意する。そこで、ｎ（ｔ）がいかなる値をとっても、各ｊに対して
【００７５】
【数１０】
2004318884.tif 000012
【００７６】
が得られるので、
【００７７】
【数１１】
2004318884.tif 000013
【００７８】
であり、（２）の両辺の期待値をとると、
【００７９】
【数１２】
2004318884.tif 000014
【００８０】
となる。「正規化された期待値」Ｅｘi（ｔ）／ｔを
【００８１】
【数１３】
2004318884.tif 000015
【００８２】
と書くことにする。ｃ1＝（α＋β）／（１＋δin（α＋γ））を想起すると次式を得る。
【００８３】
【数１４】
2004318884.tif 000016
【００８４】
ここで、ｐ-1＝０とし、ｉ≧０に対してｐiを次式で定義する。
【００８５】
【数１５】
2004318884.tif 000017
【００８６】
まず、各ｉに対して、ｔ→∞のとき、
【００８７】
【数１６】
2004318884.tif 000018
【００８８】
が得られることを示す。その後、ｘi（ｔ）がその平均の周りに集中していることを示して、最後にｐiが記述したべき乗則に従うことを示す。（５）を調べるため、
【００８９】
【数１７】
2004318884.tif 000019
【００９０】
とおく。次に（４）を（３）から差し引くと、
【００９１】
【数１８】
2004318884.tif 000020
【００９２】
となり、次のように書き直すことができる。
【００９３】
【数１９】
2004318884.tif 000021
【００９４】
ここでΔi（ｔ）＝ｃ1（ｉ−１＋δin）εi-1（ｔ）／（ｔ＋１）＋ｏ（ｔ-7/5）である。
【００９５】
（５）を証明するためには、各ｉに対してεi（ｔ）＝ｏ（ｔ-2/5）であることを厳密に示さなければならない。これをｉに関する帰納法により行う。ｉ≧０およびεi-1（ｔ）＝ｏ（ｔ-2/5）と仮定する。ε-1（ｔ）＝０であることに注意して帰納法が開始される。すると、Δi（ｔ）＝ｏ（ｔ-7/5）であり、（６）から（例えばこの式をΔi（ｔ）に間してεi（ｔ）について明示的に解くことにより）εi（ｔ）＝ｏ（ｔ-2/5）となることを検証することができる。これにより（５）の証明が完了する。
【００９６】
次に、定理の記述にあるように、確率１で、
ｘi（ｔ）／ｔ→ｐi    （７）
が得られることを示す。これを行うためには、通常通り、Azuma-Hoeffding不等式（非特許文献４、２０および１０も参照）を用いて、ｘi（ｔ）がその期待値の周りに集中することを示す。これは、次の形で記述することができる：Ｘがｎ個の選択の系列によって決まる確率変数であり、１つの選択がＸの値を最大でもθだけ変化させる場合、
【００９７】
【数２０】
2004318884.tif 000022
【００９８】
である。これを適用するため、まず、各時間ステップごとに、操作（Ａ）、（Ｂ）または（Ｃ）のいずれを行うべきかを選択する。Ａを、このような選択の１つの（無限）系列に対応している事象とする。ほとんどすべてのＡ（技術的な意味で確率１）に対して、（５）を証明した論法が実際には次式を与えることに注意する。
【００９９】
Ｅ（ｘi（ｔ）｜Ａ）＝ｐiｔ＋ｏ（ｔ）    （９）
【０１００】
Ａを所与として、Ｇ（ｔ）を求めるには、各ステップにおいて、どの１つの古い頂点（（Ａ）または（Ｃ）の場合）、またはどの複数の古い頂点（（Ｂ）の場合）が関与するかを選択することが残っている。選択すべき古い頂点は多くても２ｔ個である。これらの選択の１つを例えばｖからｖ'に変えることは、最終グラフにおけるｖおよびｖ’の次数にしか影響しない。（後の段階で比例的選択を保存するため、ｖとｖ′の間で後の辺を適当に再分配しなければならないが、他の頂点は影響されない。）したがって、ｘi（ｔ）は多くても２だけ変化し、（８）を適用すると、次式を得る。
【０１０１】
【数２１】
2004318884.tif 000023
【０１０２】
（９）と合わせて、これは（７）が確率１で成り立つことを意味し、定理の前半を証明している。（なお、もう少し慎重に考慮すれば、おそらく（７）をｘi（ｔ）＝ｐiｔ＋Ｏ（ｔ1/2ｌｏｇｔ）で置き換えることができることに留意されたい。確かに我々の論法は（５）においてこの形の誤差境界を与える。上記の弱い境界は、式を簡単にするために、（１）におけるｔ1/2ｌｏｇｔをｏ（ｔ3/5）で置き換えた結果として得られた。しかし、このような厳格な誤差境界を目指す場合、（９）に至る技術的詳細は複雑になる可能性がある。）
【０１０３】
次に、（４）で定義された量ｐiの挙動を求める。
【０１０４】
γ＜１と仮定すると、α＋β＞０であることからｃ1＞０であるので、（４）を次のように書き直すことができる。
【０１０５】
【数２２】
2004318884.tif 000024
【０１０６】
これは
【０１０７】
【数２３】
2004318884.tif 000025
【０１０８】
および、ｉ≧１に対して
【０１０９】
【数２４】
2004318884.tif 000026
【０１１０】
を与える。ここで、実数ｘおよび整数ｎの場合、ｘ（ｘ−１）・・・（ｘ−ｎ＋１）に対して（ｘ）nと書く。また、ｘが整数でない場合であってもΓ（ｘ＋１）に対してｘ！を用いる。得られた公式が確かに解を与えることを確かめるのは容易である。
【０１１１】
【数２５】
2004318884.tif 000027
【０１１２】
であることを確かめることができる。大きい時刻ｔにおいて（α＋γ＋ｏ（１））ｔ個の頂点がある。
【０１１３】
（１０）から、定理の記述の通り、ｉ→∞のとき、
【０１１４】
【数２６】
2004318884.tif 000028
【０１１５】
であり、ここで
ｘIN＝（δin＋ｃ1-1）−（−１＋δin）＝１＋１／ｃ1
である。
【０１１６】
出次数については、αおよびγと、δinおよびδoutの役割を入れ換えた後は、計算は全く同じである。この入れ換えの下で、ｃ1はｃ2になるので、出次数に対するべき乗則の指数は、主張通りｘOUT＝１＋１／ｃ2となる。
【０１１７】
次に、入次数および出次数を同時に考慮して、より詳細な結果に進む。ｎij（ｔ）を、入次数ｉおよび出次数ｊを持つＧ（ｔ）の頂点の数とする。
【０１１８】
定理２
定理１の条件が成り立ち、α，γ＜１、およびαδin＋γδout＞０と仮定する。ｉ，ｊ≧０を固定する。すると、ｎij（ｔ）＝ｆijｔ＋ｏ（ｔ）が確率１で成り立つような定数ｆijが存在する。さらに、ｊ≧１を固定しｉ→∞のとき、
【０１１９】
【数２７】
2004318884.tif 000029
【０１２０】
であり、ｉ≧１を固定しｊ→∞のとき、
【０１２１】
【数２８】
2004318884.tif 000030
【０１２２】
である。ここでＣjおよびＤiは正の定数であり、
【０１２３】
【数２９】
2004318884.tif 000031
【０１２４】
および
【０１２５】
【数３０】
2004318884.tif 000032
【０１２６】
である。
【０１２７】
定理２は、ｉおよびｊの一方を固定して他方が無限大になるときのｆijの極限的挙動について記述しているが、ｉおよびｊが何からの形でともに無限大になるときの挙動については何も記述していないことに注意する。
【０１２８】
定理２の証明は、定理１の場合と同じ筋道を辿るが、計算がかなり多くなるので、付録Ｂに与える。主な相違点は、（１０）の代わりに解がはるかに複雑になる２次元の再帰的関係（１３）が得られることである。
【０１２９】
定理１および定理２のウェブグラフへの応用について議論する前に、（ウェブグラフをモデル化する場合に仮定するように）δout＝０の場合、出次数０で生じる頂点は常に出次数０であることに注意する。このような頂点はγ＞０の場合に限り存在する。したがって、γδout＞０はまさに、出次数０で生じた非ゼロ出次数を持つ頂点をグラフが含むための必要とさる条件である。このような頂点が存在する場合、それらは、ｊ＞０を固定しｉ→∞とした場合のｆijの挙動を支配することが分かる。同様の注釈が、入次数と出次数を入れ換えて、αδinに当てはまる。αδin＝γδout＝０の場合、Ｇ0に属さないあらゆる頂点は入次数または出次数のいずれかが０となる。
【０１３０】
なお、完全を期して、γδout＞０ならば、ｊ＝０の場合でも（１１）が成り立つことに注意する。γ＝０の場合、すべてのｉについてｆi0＝０である。γ＞０であるがδout＝０である場合には、出次数０を持つ頂点（タイプ（Ｃ）のステップで生じたもの）のうちでの入次数の発展は、非ゼロの出次数を合わせたすべての頂点のうちでのものと同じである。したがって、定理１から、この場合、
【０１３１】
【数３１】
2004318884.tif 000033
【０１３２】
が成り立つ。
【０１３３】
特定の値
興味のある問題として、（あるとすれば）どのパラメータに対して、本モデルが、ある種の実世界のグラフ、特にウェブグラフについて観測されたべき乗則を再現するかということがある。
【０１３４】
このセクションではδout＝０とする。というのは、これは、コンテンツのみのページが存在するウェブグラフをモデル化するからである。また、α＞０と仮定する。そうでなければ、非ゼロ出次数を持つ頂点（初期頂点）が有限個しか存在しなくなるからである。前と同様、ｃ1＝（α＋β）／（１＋δin（α＋γ））とし、今度はｃ2＝１−αであることに注意する。上記で示したように、べき乗則の指数は、入次数全体（または出次数を０に固定した場合の入次数）に対して
ＸIN＝１＋１／ｃ1
であり、出次数全体に対して
ＸOUT＝１＋１／ｃ2
であり、δin＞０の場合、指数は、固定した出次数ｊ≧１を持つ頂点のうちの入次数に対して、
Ｘ’IN＝１＋１／ｃ1＋ｃ2／ｃ1
であり、固定した入次数ｉ≧０を持つ頂点のうちの出次数に対して、
Ｘ’OUT＝１＋１／ｃ2＋δinｃ1／ｃ2
である。
【０１３５】
ウェブグラフの場合、最初の２つの指数の最近の測定値（非特許文献１３）はＸIN＝２．１およびＸOUT＝２．７である。（非特許文献３および２３における以前の測定値は、ＸINに対して同じ値を与えていたが、ＸOUTについてはより小さい値であった。）我々のモデルは、ｃ2＝．５９、したがってα＝．４１、およびｃ1＝１／１．１の場合に限りこれらの指数を与えるので、
【０１３６】
【数３２】
2004318884.tif 000034
【０１３７】
となる。この式は解の範囲を与える。端点はδin＝０、β＝．４９、γ＝．１、およびδin＝．２４、β＝．５９、γ＝０である。
【０１３８】
モデルのテストとして、指数Ｘ'INおよびＸ'OUTを測定することができるであろう（これらはもちろん実際には、固定した出次数／入次数が変わると変化する可能性がある）。Ｘ'INに対して２．７５、Ｘ'OUTに対して区間［２．７，３．０６］内の任意値が得られる。
【０１３９】
（付録Ｂ）
この付録では、定理２の証明を与える。定理１の証明と同様の論法で、各ｉおよびｊに対して、ｎij（ｔ）／ｔ→ｆijが得られることが分かる。ここでｆijは次式を満たす。
【０１４０】
【数３３】
2004318884.tif 000035
【０１４１】
言うまでもなく、ｉまたはｊが−１の場合にはｆijを０とする。頂点はそれ自体へのループを持つことがあり、その場合、１ステップでその入次数および出次数の両方が増加することに注意する。これはＥ（ｎij（ｔ））に対する式を複雑にするが、固定のｉおよびｊの場合、この期待値に関する効果はｏ（ｔ）であることが簡単に分かる。したがって（１３）は厳密に成り立つ。
【０１４２】
まず、ｊを固定してｉ→∞とした場合のｆijの展開を求める。
【０１４３】
再帰的関係（１３）は、係数ｆijの２次元配列に関する線形作用素Ｌについて次の形を有する。
【０１４４】
Ｌ（ｆ）＝α１｛i=0,j=1｝＋γ１｛i=1,j=0｝
Ｌの形から明らかに、この方程式には一意の解が存在する。線形性により、次のように書くことができる。
【０１４５】
ｆij＝ｇij＋ｈij
ここで
Ｌ（ｇ）＝α１｛i=0,j=1｝            （14）
および
Ｌ（ｈ）＝γ１｛i=1,j=0｝            （15）
である。
【０１４６】
最初にｇを考える。α，γ＜１から、ｃ1，ｃ2＞０であるので、
【０１４７】
【数３４】
2004318884.tif 000036
【０１４８】
とおき、（１４）をｃ1で割ると、次式を得る。
【０１４９】
【数３５】
2004318884.tif 000037
【０１５０】
（１６）を用いると、αδin＝０の場合にすべてのｉ＞０についてｇij＝０であることを示すのは困難ではない。したがって、さしあたりαδin＞０と仮定する。
【０１５１】
境界条件から、すべてのｉ＝０についてｇi0＝０が得られることに注意する。したがって、ｊ＝１の場合、（１６）の右辺第２項は消え、（代数の詳細を省略して）次のようになる。
【０１５２】
【数３６】
2004318884.tif 000038
【０１５３】
ここで
【０１５４】
【数３７】
2004318884.tif 000039
【０１５５】
は正の定数である。（ここでαδin＞０を用いた。）
【０１５６】
ｊ≧２の場合、（１６）の最後の項は常に０である。繰り返し法によりｇijについて解くと次式を得る。
【０１５７】
【数３８】
2004318884.tif 000040
【０１５８】
ある定数Ａjrについて
【０１５９】
【数３９】
2004318884.tif 000041
【０１６０】
がすべての１≦ｊ≦ｊ0およびすべてのｉ≧０に対して成り立つと仮定する。なお、ｊ0＝１についてＡ11＝ａですでにこれを示していることに注意されたい。ｊ＝ｊ0＋１とする。すると、（１７）および（１８）を用いると次式が得られる。
【０１６１】
【数４０】
2004318884.tif 000042
【０１６２】
さて、０＜ｙ＜ｘであり、ｓが０≦ｓ≦ｉ＋１となる整数であれば、次式を確かめることは容易である。
【０１６３】
【数４１】
2004318884.tif 000043
【０１６４】
（例えば、ｓに関して両辺は０であるｓ＝ｉ＋１から出発する下向き帰納法を用いることができ）（１９）と、（２０）のｓ＝０の場合とを組み合わせると次式が得られる
【０１６５】
【数４２】
2004318884.tif 000044
【０１６６】
異なるｒの値について１／（ｉ＋ｂr）！の係数を集め、ｂj−ｂr＝（ｊ−ｒ）ｃ2／ｃ1に注意すると、１≦ｒ≦ｊ−１に対して
【０１６７】
【数４３】
2004318884.tif 000045
【０１６８】
であり、
【０１６９】
【数４４】
2004318884.tif 000046
【０１７０】
であると仮定すれば、（１８）がｊ＝ｊ0＋１に対して成り立つことが分かる。実際に、Ａjrを計算せずに、興味のある（ｆではなくｇに対する）べき乗則が得られる。Ａ11＞０であるため、あらゆるｊ≧１に対してＡj1＞０であることさえ観測すれば、ｒ＝１の項が（１８）を支配する。したがって、任意の固定のｊ＞０に対して次式を得る。
【０１７１】
【数４５】
2004318884.tif 000047
【０１７２】
べき乗則のためにＡjrを必要としないと述べたが、その計算は容易なので、完全を期してその計算についても含める。あまり面白くない導出は省略すると、上記と同じ定数ａに対して次式となることを主張する。
【０１７３】
【数４６】
2004318884.tif 000048
【０１７４】
これは、上記の関係を用いてｊに関する帰納法により容易に確かめられる。
【０１７５】
次にｈを考える。これについても計算は同様である。（１５）から次式を得る。
【０１７６】
【数４７】
2004318884.tif 000049
【０１７７】
再び代数をほとんど省略するが、ｊ＝０に対してｈ00＝０が得られる一方、すべてのｉ≧１に対して
【０１７８】
【数４８】
2004318884.tif 000050
【０１７９】
が得られる。
【０１８０】
γδout＝０ならば、すべてのｊ＞０に対してｈij＝０であるので、以下γδout＞０と仮定する。今度は、境界条件はすべてのｊに対してｈ0j＝０を意味する。したがって、ｊ≧１について（２２）から次式を得る。
【０１８１】
【数４９】
2004318884.tif 000051
【０１８２】
（（１７）との唯一の相違点は、和がｋ＝１から始まることである。）前と同様の論法により、（２０）のｓ＝１の場合を用いると、ｉ≧１およびｊ≧０に対して次式が得られる。
【０１８３】
【数５０】
2004318884.tif 000052
【０１８４】
ここで
【０１８５】
【数５１】
2004318884.tif 000053
【０１８６】
である。（これは、δout＞０と仮定しているので理に適っている。）ここではｒ＝０の項が支配的であり、各ｊ≧０に対してｉ→∞のとき、ある正定数Ｃ''jに対して次式が得られることが分かる。
【０１８７】
【数５２】
2004318884.tif 000054
【０１８８】
ここでｆ＝ｇ＋ｈに戻り、固定のｊ≧１と、ｉ→∞とを考慮すると、γδout＞０の場合にはｈからの寄与が支配的となり、γδout＝０の場合、この寄与は０となることが分かる。よって、（２１）と（２３）を組み合わせると（１１）が証明される。
【０１８９】
定理２の後半、すなわち（１２）の証明は、入次数と出次数、αおよびγと、δinおよびδoutを入れ換えることにより得られる。
【図面の簡単な説明】
【０１９０】
【図１】有向スケールフリーオブジェクト関係のモデルを生成するためのシステムおよび方法を実施することができる例示的なコンピューティング環境のブロック図である。
【図２】有向スケールフリーオブジェクト関係のモデルを生成するためのアプリケーションプログラムおよびプログラムデータを含む、図１のシステムメモリのさらなる例示的な態様を示すブロック図である。
【図３】有向オブジェクト関係の例示的なネットワークを示す。
【図４】有向スケールフリーオブジェクト関係のモデルを生成する例示的な手続きを示す。
【符号の説明】
【０１９１】
１２０  コンピューティング環境
１３０  コンピュータ
１３２  プロセッサ
１３４  システムメモリ
１３６  バス
１３８  読み出し専用メモリ（ＲＯＭ）
１４０  ランダムアクセスメモリ（ＲＡＭ）
１４２  基本入出力システム（ＢＩＯＳ）
１４４  ハードディスクドライブ
１４６  磁気ディスクドライブ
１４８  リムーバブル不揮発性磁気ディスク
１５０  光ディスクドライブ
１５２  リムーバブル不揮発性光ディスク
１５４  インタフェース
１５８  オペレーティングシステム（ＯＳ）
１６０  アプリケーションプログラム
１６２  他のプログラムモジュール
１６４  プログラムデータ
１６６  キーボード
１６８  ポインティングデバイス
１７０  ユーザ入力インタフェース
１７２  モニタ
１７４  ビデオアダプタ
１７６  出力周辺インタフェース
１７８  リモートコンピュータ
１８０  ローカルエリアネットワーク（ＬＡＮ）
１８２  広域ネットワーク（ＷＡＮ）
１８４  ネットワークインタフェース
１８６  モデム
１８８  インターネット
１９０  リモートアプリケーションプログラム
２０２  有向スケールフリーオブジェクト関係ネットワーク生成モジュール
２０４  有向スケールフリーグラフ
２０６  乱数
２０８  乱数生成モジュール（ＲＮＧ）
２１０  設定データ
２１２  他のデータ
３００  ネットワーク
３０２  オブジェクト
３０４  辺
【図１】
2004318884.tif 000071
【図２】
2004318884.tif 000072
【図３】
2004318884.tif 000073
【図４】
2004318884.tif 000074
【外国語明細書】
2004318884000001.pdf