次数分布

テンプレート:ネットワーク科学 次数分布（じすうぶんぷ、テンプレート:Lang-en-short）とは、グラフやネットワークの研究において、ネットワーク中のノードが持つ他のノードとの接続数である次数について、それらがネットワーク全体でどのような確率分布に従うかを表したものである。

定義

ネットワーク中のノードの次数（しばしば誤って連結度 (グラフ理論)と呼ばれる）とは、そのノードが他のノードとの間に持つ接続、すなわちテンプレート:仮リンクの数である。ネットワークが有向である場合、すなわち辺が一方のノードからもう一方のノードへ向きを持つ場合、ノードは2種類の異なる次数を持つ。すなわち、入ってくる辺の数である入次数と、出ていく辺の数である出次数である。

ネットワークの次数分布 P(k) は、ネットワーク中で次数 k を持つノードの割合として定義される。したがって、ネットワーク全体に n 個のノードがあり、そのうち n_k 個が次数 k を持つとすると、次のようになる。

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

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

観測された次数分布

次数分布は、インターネットや社会的ネットワークといった実在のネットワークと、理論的なネットワークの両方を研究する上で非常に重要である。例えば最も単純なネットワークモデルである（エルデシュ・レーニイモデルの）ランダムグラフでは、n 個の各ノードが確率 p（あるいは 1 − p）で独立に接続される（あるいはされない）ため、次数 k は二項分布に従う。

$P(k)=(\genfrac{}{}{0ex}{}{n-1}{k})p^k(1-p{)}^{n-1-k},$

（あるいは、平均次数 $⟨k⟩=p(n-1)$ を一定に保ったまま n を大きくする極限では、ポアソン分布になる。）しかし、現実世界のほとんどのネットワークの次数分布は、これとは大きく異なっている。その多くは強く右に歪んでおり、大多数のノードは低い次数しか持たない一方、「ハブ」と呼ばれるごく少数のノードが高い次数を持つ。インターネット、World Wide Web、および一部の社会的ネットワークなど、いくつかのネットワークは、次数分布がおおよそ冪乗則に従うと主張されてきた。

$P(k)\sim k^{-\gamma }$

ここで γ は定数である。このようなネットワークはテンプレート:仮リンクと呼ばれ、その構造的・動的な性質から特に注目を集めてきた。

過剰次数分布

過剰次数分布とは、ある辺をたどって到達したノードについて、そのノードに接続している他の辺の本数に関する確率分布である。言い換えれば、ある辺をたどって到達したノードから出ていくリンクの分布である。

あるネットワークが次数分布 $P(k)$ を持つとする。ある1つのノードを（無作為かどうかにかかわらず）選び、その隣接ノードの1つへ移動する（少なくとも1つの隣接ノードを持つと仮定する）とき、そのノードが $k$ 個の隣接ノードを持つ確率は、$P(k)$ では与えられない。これは、不均一なネットワークにおいてあるノードが選ばれた際、そのノードの既存の隣接ノードの1つをたどることで、ハブに到達する確率がより高くなるためである。このようなノードが次数 $k$ を持つ真の確率は $q(k)$ であり、これはそのノードの過剰次数と呼ばれる。ノード間の相関を無視し、すべてのノードがネットワーク中の他のあらゆるノードと同じ確率で接続していると仮定するテンプレート:仮リンクでは、過剰次数分布は次のように求められる。

$q(k)=\frac{k+1}{⟨k⟩}P(k+1),$

ここで $⟨k⟩$ はこのモデルの平均次数である。ここから、あるノードの隣接ノードの平均次数は、そのノード自身の平均次数よりも大きいことが導かれる。社会的ネットワークにおいては、これは「自分の友人は、平均して自分よりも多くの友人を持つ」ことを意味する。これはテンプレート:仮リンクとして知られている。平均過剰次数が1より大きい場合、そのネットワークはテンプレート:仮リンクを持ちうることが示せる。

$\sum _{k}kq(k)>1\Rightarrow ⟨k^2⟩/⟨k⟩-1>1\Rightarrow ⟨k^2⟩-2⟨k⟩>0$

なお、これら最後の2つの式はテンプレート:仮リンクについてのみ成り立つものであり、現実世界のネットワークの過剰次数分布を導出するには、次数相関も考慮に入れる必要がある。

母関数法

母関数は、ランダムなネットワークのさまざまな性質を計算するために利用できる。あるネットワークの次数分布と過剰次数分布をそれぞれ $P(k)$ および $q(k)$ とすると、次の2つの形式でべき級数を書くことができる。

$G_0(x)={\sum }_{k}P(k)x^k$ および $G_1(x)={\sum }_{k}q(k)x^k={\sum }_k\frac{k}{⟨k⟩}P(k)x^{k-1}$

$G_1(x)$ は $G_0(x)$ の導関数からも得ることができる。

$G_1(x)=\frac{G{\text{'}}_0(x)}{G{\text{'}}_0(1)}$

確率分布 $P(k)$ の母関数が分かっていれば、微分することで $P(k)$ の値を求めることができる。

$P(k)=\frac{1}{k!}\frac{{\mathrm{d}}^{k}G}{\mathrm{d}{x}^k}{|}_{x=0}$

モーメントなどの性質は、$G_0(x)$ とその導関数から簡単に計算できる。

• $⟨k⟩=G{\text{'}}_0(1)$
• $⟨k^2⟩=G^{\prime }{\text{'}}_0(1)+G{\text{'}}_0(1)$

そして一般には次のようになる。

• $⟨k^m⟩=[(\mathrm{x}\frac{\mathrm{d}}{\mathrm{dx}}{)}^m{G}_0(x){]}_{x=1}$

ER グラフのようなポアソン分布に従うランダムネットワークでは $G_1(x)=G_0(x)$ となり、これがこの種のランダムネットワーク理論が特に単純である理由である。第1近傍および第2近傍に関する確率分布は、それぞれ関数 $G_0(x)$ と $G_0(G_1(x))$ によって生成される。これを拡張すると、第 $m$ 近傍の分布は次のように生成される。

$G_0(G_1(\mathrm{...}{G}_1(x)\mathrm{...}))$

ここで、関数 $G_1$ はそれ自身に対して $m-1$ 回反復して作用する。

第1近傍の平均数 $c_1$ は $⟨k⟩=\frac{d{G}_0(x)}{dx}{|}_{x=1}$ であり、第2近傍の平均数は次のようになる。$c_2=\left[\frac{d}{dx}{G}_0\right(G_1(x)){]}_{x=1}={G_1}^{\prime }(1)G{\text{'}}_0(G_1(1))={G_1}^{\prime }(1)G{\text{'}}_0(1)=G^{\prime }{\text{'}}_0(1)$

有向ネットワークにおける次数分布

ウィキペディアのハイパーリンクグラフにおける入次数・出次数分布（対数スケール）

有向ネットワークでは、各ノードはそれぞれそのノードに出入りするリンクの本数である、いくつかの入次数 $k_{in}$ といくつかの出次数 $k_{out}$ を持つ。無作為に選んだノードが入次数 $k_{in}$ と出次数 $k_{out}$ を持つ確率を $P(k_{in},k_{out})$ とすると、この同時分布に対応する母関数は、2つの変数 $x$ と $y$ を用いて次のように書くことができる。

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

有向ネットワークにおけるすべてのリンクは、必ずいずれかのノードから出て別のノードへ入るため、あるノードに入ってくるリンクの正味の平均数はゼロになる。したがって、

$⟨k_{in}-k_{out}⟩=\sum _{k_{in},k_{out}}(k_{in}-k_{out})P(k_{in},k_{out})=0$

となり、これは母関数が次を満たさなければならないことを意味する。

$\frac{\partial 𝒢}{\partial x}{|}_{x,y=1}=\frac{\partial 𝒢}{\partial y}{|}_{x,y=1}=c,$

ここで $c$ はネットワーク中のノードの平均次数（入次数・出次数の双方について）であり、$⟨k_{in}⟩=⟨k_{out}⟩=c$ である。

関数 $𝒢(x,y)$ を用いることで、これまでと同様に、入次数・出次数分布および入過剰次数・出過剰次数分布に対する母関数を改めて求めることができる。$G_0^{in}(x)$ は、無作為に選んだノードに到着するリンクの本数に対する母関数として定義でき、$G_1^{in}(x)$ は、無作為に選んだリンクをたどって到達したノードに到着するリンクの本数として定義できる。同様に、そのようなノードから出ていくリンクの本数に対する母関数として $G_0^{out}(y)$ と $G_1^{out}(y)$ を定義することもできる。

• $G_0^{in}(x)=𝒢(x,1)$
• $G_1^{in}(x)=\frac{1}{c}\frac{\partial 𝒢}{\partial x}{|}_{y=1}$
• $G_0^{out}(y)=𝒢(1,y)$
• $G_1^{out}(y)=\frac{1}{c}\frac{\partial 𝒢}{\partial y}{|}_{x=1}$

ここで、第1近傍の平均数 $c$（先に $c_1$ として導入したもの）は $\frac{\partial 𝒢}{\partial x}{|}_{x,y=1}=\frac{\partial 𝒢}{\partial y}{|}_{x,y=1}$ であり、無作為に選んだノードから到達可能な第2近傍の平均数は次で与えられる。$c_2={G_1}^{\prime }(1)G{\text{'}}_0(1)=\frac{{\partial }^2𝒢}{\partial x\partial y}{|}_{x,y=1}$。これらの式は $x$ と $y$ について明らかに対称であるため、これらは同時に、ある無作為なノードへ到達しうる第1近傍・第2近傍の数でもある。

符号付きネットワークにおける次数分布

符号付きネットワークでは、各ノードはそれぞれ正次数 $k_{+}$ と負次数 $k_{-}$ を持ち、これらはそのノードに接続する正のリンクの数と負のリンクの数をそれぞれ表す。したがって $P(k_{+})$ と $P(k_{-})$ は、符号付きネットワークの正次数分布と負次数分布をそれぞれ表す。

関連項目

• グラフ理論
• 複雑ネットワーク
• テンプレート:仮リンク
• ランダムグラフ
• テンプレート:仮リンク

参考文献

• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite journal