日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-A-9

複雑ネットワークの最小全域木の次数に関する性質について
05001451
01309090

1.

法政大学
法政大学

*鈴木一優
千葉英史

はじめに

複雑ネットワークとは，例えば，多くのノード数を持ち，次数や密度などの構造が均一ではないネットワークなど，複雑なネットワークの総称である．複雑ネットワークは，現実世界のネットワークを扱う研究領域として注目を浴びている．現実世界では，外的要因によって，ネットワークの一部が機能不全に陥ることがある．このとき，パーコレーション理論を用いることにより，ネットワークの機能不全に対する問題が解析されている．
文献 [1] では，パーコレーション現象を，最小全域木アルゴリズムを用いて説明できることが示された．また，文献 [2]，[3] で，計算実験を通して，重みが構造依存のスケールフリーネットワークに対する最小全域木の性質が調べられた．その結果，得られた最小全域木もスケールフリー性を持つことが示された．さらに，元の複雑ネットワークと得られた最小全域木の次数が，強い正の相関関係を持つことも示された．
実際のネットワークでは，重みが構造に依存していない場合がある．そこで，本研究では，計算実験を通して，重みがランダムに付された複雑ネットワークに対する最小全域木の性質を調査する．最小全域木の計算においては，複数のアルゴリズムを試み，次数分布と次数に関する相関係数について考察する．

SUZUKI Kazuhiro
CHIBA Eishiに従う．ランダムグラフは，確率的に構成されるモデルで，他の複雑ネットワークモデルとの比較対象として用いられる．

次数の相関関係

3.

元のネットワークとその最小全域木の次数の関係性について散布図を用いて調べる．このとき，• ki ： 元のネットワークの i 番目のノードの次数• kmsti ： 最小全域木の i 番目のノードの次数• ⟨k⟩ ： 元のネットワークの次数の平均• ⟨kmst ⟩ ： 最小全域木の次数の平均• ⟨k 2 ⟩ ： 元のネットワークの次数の 2 乗の平均
2 ⟩ ： 最小全域木の次数の 2 乗の平均
• ⟨kmst• ⟨kkmst ⟩ ： ki × kmsti の平均とすると，次数の Pearson 相関係数 r は，⟨kkmst ⟩ − ⟨k⟩⟨kmst ⟩r=√( 2)(⟨k 2 ⟩ − ⟨k⟩2 ) ⟨kmst⟩ − ⟨kmst ⟩2となる．ただし，−1 ≤ r ≤ 1 である [2]．

4.
4.1.

計算実験
計算実験の設定全てのネットワークモデルに対して，ノード数
N = 100, 000 とした．また，文献 [2]，[3] では，エッジの重みがネットワークの構造に基づいて決められた．しかし，現実世界のネットワークでは，重み2. 実験対象のネットワークモデルをネットワーク構造と無関係な値に設定する方が本研究の計算実験では，複雑ネットワークであ適切であることがしばしば見られる．そこで，本研
る WS モデル，BA モデル，および比較対象とし究では重みは一様乱数に従うとして，擬似乱数生成てのランダムグラフを用いる．WS モデルは，平均ノード間距離がノード数に比べて非常に小さく， 器 PCG64 から得られた値を重みとした．また，最小全域木を求める際に，Kruskal，Prim，Boruvka
ネットワーク内の密度が高いといった性質を持つのアルゴリズムを使った．
ネットワークモデルである．BA モデルは，スケールフリー性を持つネットワークモデルである．す4.2. 実験結果
なわち，次数分布 P (k) は，BA モデルに対して最小全域木を求め，その次P (k) ∝ k −γ ,(2 ≤ γ ≤ 3)

数の相補累積分布 F を図 1 に示す．また，得られた最小全域木の次数分布 P (kmst ) について，以下の性質が得られた:

そのため，得られた最小全域木はスケールフリー性をもつことが分かる．また，元の BA モデルの次数分布 P (k) について，以下の性質が得られた:

F−3.185
P (kmst ) ∝ kmst.

P (k) ∝ k −3.226 .
各ノード i に対する次数 (ki , kmsti ) を図 2 に示す．図 2 から相関係数 r = 0.949 である．r が 1 に近いほど，元のネットワークにおいて次数が高いノードは，最小全域木においてもそのノードの次数が高くなり; 元のネットワークにおいて次数が低いノードは，最小全域木においてもそのノードの次数が低くなる傾向がある．
ランダムグラフと WS モデルにおいても，同様の計算実験を行った．最小全域木の次数分布の指数 γ について，ランダムグラフの場合，γ = 2.796;
WS モデルの場合，γ = 2.670 と推定された．しかし，得られた最小全域木の相補累積分布が，推定値 γ を用いた相補累積分布上に位置しなかった．
そのため，ランダムグラフと WS モデルの最小全域木にスケールフリー性がないと結論付けられる．
次に，次数の相関係数について，ランダムグラフの場合，0.178; WS モデルの場合，0.314 となった．
これらの結果は，元のネットワークにおけるノードの次数と最小全域木におけるノードの次数との間には，BA モデルのような著しい関係が見られないことを意味する．
実験全体を通して，最小全域木アルゴリズムの違いによる計算結果の相違は見られなかった．

5.

おわりに

図 1: 次数の相補累積分布．

図 2: BA モデルとその最小全域木の次数に関する散布図．
査することが考えられる．また，本研究ではエッジの重みをランダムと仮定したが，現実世界のネットワークを反映する適切な重みを考慮して，その全域木の性質を調べることに興味がある．

参考文献[1] A.-L. Barabási, “Invasion percolation andglobal optimization”, Physical Review Letters, vol. 76, no. 20, pp. 3750–3753, 1996.

本研究では，計算実験を通して，重みがランダ[2] D.-H. Kim, S.-W. Son, Y.-Y. Ahn, P.-J. Kim,
ムに付されたランダムグラフ，WS モデル，BA モ
Y.-H. Eom, and H. Jeong, “Underlying scaleデルに対する最小全域木のスケールフリー性につ
free trees in complex networks”, Progress of
いて調べた．その結果，BA モデルに対する最小Theoretical Physics Supplement, no. 157, pp.
全域木のみスケールフリー性を示した．また，BA213–220, 2005.
モデルに対する最小全域木の次数は，元の BA モ
[3] P.J. Macdonald, E. Almaas, A.-L. Barabási,
デルの次数と強い相関関係を持つことを確認した．
“Minimum spanning trees of weighted scale今後の課題として，複雑ネットワークに対するfree networks”, Europhysics Letters, vol. 72,
最小全域木以外の全域木の次数に関する性質を調
no. 2, pp. 308–314, 2005.