Aritalab:Lecture/NetworkBiology/Degree Distribution

次数分布

次数 k が全頂点の中で占める割合 p(k) を次数分布といいます。確率分布なので総和は 1 です。

$\textstyle \sum_k p(k) = 1$

その平均値を、平均次数といい　<k> = Σ k p(k) と書きます。

隣接点の次数分布

隣接する頂点の次数を $p ( j | k )$ と書きましょう。ここで次数 k の頂点に隣接する頂点の次数が j です。

$p(j|k) = \frac{j p(j)}{\sum_k k p(k)} = \frac{j}{\langle k \rangle}p(j)$

別の言い方をすると、頂点をランダムに選んで次数が j である確率は p( j) ですが、辺をランダムに選んでその先に来る頂点の次数が j である確率が p ( j | k ) です。辺をたどった先の頂点はハブが来やすく、その来やすさは、頂点の次数に正比例します。（次数 j の頂点は相対的に j / <k> だけ、現れやすい。）

辺の先に来る頂点の次数平均を求めましょう。

$\sum_{j} j p(j|k) = \frac{1}{\langle k \rangle} \sum_{j} j^2 p(j) = \frac{\langle k^2 \rangle}{\langle k \rangle}$

この値は各所で用いますが、k から j をたどる辺 1 本ぶんを最初に引いておく場合もあります。このとき、値は $\textstyle \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}$ になります。

次数相関

隣接する頂点どうしの次数が似る度合いを次数相関といいます。 辺がランダムに張られる場合は次数相関は 0 になりますが、映画俳優の競演関係といったネットワークはハブどうしが隣接する、つまり正の相関を持つ (assortative) ことが知られています。 生態系のような生物学ネットワークでは負の相関を持つ (disassortative) と考えられます。

隣接点の平均次数は、次数分布や頂点の次数 k によらず一定値となります。

$\sum_{j\not=k} j p(j|k) = \frac{\langle k^2 \rangle - \langle k \rangle}{\langle k \rangle}$

全頂点の次数が同じ時 <k²> = <k>² となるので、隣接点の平均次数は <k> - 1 になります（たどってくる辺を除いた場合）。また次数の偏りが大きくハブが存在する場合、隣接点の平均次数は <k> を大きくうわまわります。（つまり隣にハブが来やすくなる。）次数がポアソン分布に従う場合、<k²> = <k>² + <k> が成り立ちます。ポアソン分布の場合は、たどる辺をちょ差し引くと、ちょうど隣接点も次数 <k> です。

計算法

次数相関 r をピアソンの相関係数に従って定義しましょう。M 本ある辺の両端点 u, v の次数をそれぞれ k_u, k_u とおきます。相関係数の分子は k_u, k_v の平均からの差分を計算します。 分母は k_u と k_v の標準偏差の積ですが、実際には分散を計算します。

$r = \frac{\sum_{(u,v)\in E}^M (k_u k_v - \langle k \rangle^2) }{M (\langle k^2 \rangle - \langle k \rangle^2) }$