学位分布

グラフやネットワークの研究において、ネットワーク内のノードの次数とは、そのノードが他のノードと持つ接続の数であり、次数分布とは、ネットワーク全体におけるこれらの次数の確率分布のことである。

ネットワークにおけるノードの次数（接続性と誤って呼ばれることもある）とは、そのノードが他のノードと持つ接続（エッジ）の数のことです。ネットワークが有向ネットワーク、つまりエッジが1つのノードから別のノードへ一方向に向いている場合、ノードには2つの異なる次数、すなわち入次数（入ってくるエッジの数）と出次数（出ていくエッジの数）があります。

ネットワークの次数分布P ( k ) は、次数がkであるネットワーク内のノードの割合として定義されます。したがって、ネットワークに合計n個のノードがあり、そのうちn _{k 個}のノードが次数kである場合、次のようになります。

${\displaystyle P(k)={\frac {n_{k}}{n}}}$。

同じ情報は、累積次数分布、次数がkより小さいノードの割合、あるいは、 C を累積次数分布とみなした場合の、次数がk (1 - C )以上であるノードの割合である相補累積次数分布の形で提示されることもあります。つまり、 Cの補集合です。

次数分布は、インターネットやソーシャルネットワークなどの実際のネットワークと理論的なネットワークの両方を研究する上で非常に重要です。たとえば、最も単純なネットワークモデルである（エルデシュ・レニーモデル）ランダムグラフでは、 n個のノードのそれぞれが確率p（または 1 − p ）で独立して接続されている（または接続されていない）場合、次数kの二項分布を持ちます。

${\displaystyle P(k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},}$

（または、nが大きい極限ではポアソン分布、平均次数が${\displaystyle \langle k\rangle =p(n-1)}$（ は固定されていると仮定する）。しかし、現実世界のほとんどのネットワークは、これとは大きく異なる次数分布を持っています。ほとんどのネットワークは右に大きく偏っており、これはノードの大部分は次数が低く、少数の「ハブ」と呼ばれるノードは次数が高いことを意味します。インターネット、ワールドワイドウェブ、および一部のソーシャルネットワークなど、いくつかのネットワークは、次数分布がおおよそべき乗則に従うと主張されています。${\displaystyle P(k)\sim k^{-\gamma }}$ここでγは定数である。このようなネットワークはスケールフリーネットワークと呼ばれ、その構造的および動的な特性から特に注目を集めている。^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

過剰次数分布とは、エッジをたどって到達したノードについて、そのノードに接続されている他のエッジの数の確率分布のことです。^{[ 5 ]}言い換えれば、リンクをたどって到達したノードから出ているリンクの分布です。

ネットワークの次数分布が${\displaystyle P(k)}$1 つのノードを選択し (ランダムに選択してもそうでなくても)、その隣接ノードのいずれか (少なくとも 1 つの隣接ノードがあると仮定) に移動すると、そのノードが${\displaystyle k}$隣人は与えられません${\displaystyle P(k)}$その理由は、異種ネットワークでノードが選択されると、そのノードの既存の近隣ノードのいずれかをたどることでハブに到達する可能性が高くなるためです。このようなノードが次数を持つ真の確率は${\displaystyle k}$は${\displaystyle q(k)}$これはそのノードの過剰次数と呼ばれます。ノード間の相関が無視され、すべてのノードがネットワーク内の他のどのノードにも同じ確率で接続されていると仮定される構成モデルでは、過剰次数分布は次のように見つけることができます。^{[ 5 ]}

${\displaystyle q(k)={\frac {k+1}{\langle k\rangle }}P(k+1),}$

どこ${\displaystyle {\langle k\rangle }}$はモデルの平均次数（平均次数）です。このことから、任意のノードの隣接ノードの平均次数は、そのノードの平均次数よりも大きいことがわかります。ソーシャルネットワークでは、これは平均してあなたの友人はあなたよりも多くの友人を持っていることを意味します。これは「友情のパラドックス」として有名です。ネットワークの平均超過次数が1より大きい場合、ネットワークは巨大なコンポーネントを持つ可能性があることが示されます。

${\displaystyle \sum _{k}kq(k)>1\Rightarrow {\langle k^{2}\rangle }/{\langle k\rangle }-1>1\Rightarrow {\langle k^{2}\rangle }-2{\langle k\rangle }>0}$

最後の 2 つの式は構成モデルのみに関するものであり、実際のネットワークの過剰次数分布を導出するには、次数相関も考慮に入れる必要があることに注意してください。 ^{[ 5 ]}

生成関数は、ランダムネットワークのさまざまな特性を計算するために使用できます。あるネットワークの次数分布と超過次数分布が与えられた場合、${\displaystyle P(k)}$そして${\displaystyle q(k)}$それぞれ、2つのべき級数を次の形式で表すことができる。

${\displaystyle G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}}$そして${\displaystyle G_{1}(x)=\textstyle \sum _{k}\displaystyle q(k)x^{k}=\textstyle \sum _{k}\displaystyle {\frac {k}{\langle k\rangle }}P(k)x^{k-1}}$

${\displaystyle G_{1}(x)}$の誘導体からも得られる${\displaystyle G_{0}(x)}$:

${\displaystyle G_{1}(x)={\frac {G'_{0}(x)}{G'_{0}(1)}}}$

確率分布の生成関数がわかっている場合${\displaystyle P(k)}$そうすれば、${\displaystyle P(k)}$区別することによって：

${\displaystyle P(k)={\frac {1}{k!}}{\operatorname {d} ^{k}\!G \over \operatorname {d} \!x^{k}}{\biggl \vert }_{x=0}}$

モーメントなどのいくつかの特性は、簡単に計算できます。${\displaystyle G_{0}(x)}$およびその派生物：

• ${\displaystyle {\langle k\rangle }=G'_{0}(1)}$
• ${\displaystyle {\langle k^{2}\rangle }=G''_{0}(1)+G'_{0}(1)}$

そして一般的には：^{[ 5 ]}

• ${\displaystyle {\langle k^{m}\rangle }={\Biggl [}{{\bigg (}\operatorname {x} {\operatorname {d} \! \over \operatorname {dx} \!}{\biggl )}^{m}}G_{0}(x){\Biggl ]}_{x=1}}$

ポアソン分布に従うランダムネットワーク、例えばERグラフの場合、${\displaystyle G_{1}(x)=G_{0}(x)}$そのため、この種のランダムネットワークの理論は特に単純です。1番目と2番目に近い近傍の確率分布は、以下の関数によって生成されます。${\displaystyle G_{0}(x)}$そして${\displaystyle G_{0}(G_{1}(x))}$拡張すると、${\displaystyle m}$- 番目の近隣は以下によって生成されます:

${\displaystyle G_{0}{\bigl (}G_{1}(...G_{1}(x)...){\bigr )}}$、 と${\displaystyle m-1}$関数の反復${\displaystyle G_{1}}$それ自体に作用する。^{[ 6 ]}

1番目の隣人の平均数、${\displaystyle c_{1}}$、 は${\displaystyle {\langle k\rangle }={dG_{0}(x) \over dx}|_{x=1}}$そして、2番目の隣人の平均数は次のとおりです。${\displaystyle c_{2}={\biggl [}{d \over dx}G_{0}{\big (}G_{1}(x){\big )}{\biggl ]}_{x=1}=G_{1}'(1)G'_{0}{\big (}G_{1}(1){\big )}=G_{1}'(1)G'_{0}(1)=G''_{0}(1)}$

有向ネットワークでは、各ノードは入次数を持つ${\displaystyle k_{in}}$そして、いくつかの出次数${\displaystyle k_{out}}$これらはそれぞれ、そのノードに出入りするリンクの数です。${\displaystyle P(k_{in},k_{out})}$ランダムに選択されたノードの入次数が${\displaystyle k_{in}}$およびアウトディグリー${\displaystyle k_{out}}$すると、この同時確率分布に割り当てられた生成関数は、2つの値で記述できます。${\displaystyle x}$そして${\displaystyle y}$として：

${\displaystyle {\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}.}$

有向ネットワークではすべてのリンクが何らかのノードから出て別のノードに入るため、ノードに入るリンクの平均数はゼロになります。したがって、

${\displaystyle \langle {k_{in}-k_{out}}\rangle =\sum _{k_{in},k_{out}}\displaystyle (k_{in}-k_{out})P({k_{in},k_{out}})=0}$、

つまり、生成関数は以下を満たさなければならない。

${\displaystyle {\partial {\mathcal {G}} \over \partial x}\vert _{x,y=1}={\partial {\mathcal {G}} \over \partial y}\vert _{x,y=1}=c,}$

どこ${\displaystyle c}$は、ネットワーク内のノードの平均次数（入次数と出次数の両方）です。${\displaystyle \langle {k_{in}}\rangle =\langle {k_{out}}\rangle =c.}$

関数を使用する${\displaystyle {\mathcal {G}}(x,y)}$以前と同様に、入次数/出次数分布と入次数/出次数超過分布の生成関数を再び見つけることができます。${\displaystyle G_{0}^{in}(x)}$は、ランダムに選択されたノードに到着するリンクの数を生成する関数として定義でき、${\displaystyle G_{1}^{in}(x)}$は、ランダムに選択されたリンクをたどって到達したノードに到着するリンクの数として定義できます。生成関数も定義できます。${\displaystyle G_{0}^{out}(y)}$そして${\displaystyle G_{1}^{out}(y)}$そのようなノードから出る数については、次のようになります。^{[ 6 ]}

• ${\displaystyle G_{0}^{in}(x)={\mathcal {G}}(x,1)}$
• ${\displaystyle G_{1}^{in}(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}}$
• ${\displaystyle G_{0}^{out}(y)={\mathcal {G}}(1,y)}$
• ${\displaystyle G_{1}^{out}(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}}$

ここでは、1 番目の近傍の平均数、${\displaystyle c}$または以前に紹介したように${\displaystyle c_{1}}$、 は${\displaystyle {\partial {\mathcal {G}} \over \partial x}{\biggl \vert }_{x,y=1}={\partial {\mathcal {G}} \over \partial y}{\biggl \vert }_{x,y=1}}$また、ランダムに選択されたノードから到達可能な2番目の隣接ノードの平均数は、次式で与えられる。${\displaystyle c_{2}=G_{1}'(1)G'_{0}(1)={\partial ^{2}{\mathcal {G}} \over \partial x\partial y}{\biggl \vert }_{x,y=1}}$これらは、ランダムなノードに到達できる第 1 番目と第 2 番目の近傍の数でもあります。これらの方程式は明らかに対称であるため、${\displaystyle x}$そして${\displaystyle y}$[ ^{6 ]​}

符号付きネットワークでは、各ノードは正の次数を持つ。${\displaystyle k_{+}}$そして負の度合い${\displaystyle k_{-}}$これらはそれぞれ、そのノードに接続されているリンクの正の数と負の数です。${\displaystyle P(k_{+})}$そして${\displaystyle P(k_{-})}$符号付きネットワークの負の次数分布と正の次数分布を表す。^{[ 7 ] [ 8 ]}

• グラフ理論
• 複雑なネットワーク
• スケールフリーネットワーク
• ランダムグラフ
• 構造的遮断

• Albert, R.; Barabasi, A.-L. (2002). "複雑ネットワークの統計力学". Reviews of Modern Physics . 74 (1): 47–97 . arXiv : cond-mat/0106096 . Bibcode : 2002RvMP...74...47A . doi : 10.1103/RevModPhys.74.47 . S2CID 60545 . 
• Dorogovtsev, S.; Mendes, JFF (2002). "ネットワークの進化". Advances in Physics . 51 (4): 1079–1187 . arXiv : cond-mat/0106144 . Bibcode : 2002AdPhy..51.1079D . doi : 10.1080 /00018730110112519 . S2CID 429546 . 
• Newman, MEJ (2003). "複雑ネットワークの構造と機能". SIAM Review . 45 (2): 167–256 . arXiv : cond-mat/0303516 . Bibcode : 2003SIAMR..45..167N . doi : 10.1137/S003614450342480 . S2CID 221278130 .