複雑ネットワーク

【ふくざつねっとわーく (complex network) 】

概要

現実世界で観察される，何らかの特徴的な性質を持つグラフのこと．もしくは一般にそのような性質を持つグラフのこと．インターネット， WWWのハイパーリンク構造，交友・知人関係，論文の引用関係，ニューラル・ネットワーク，たんぱく質の代謝反応など，グラフとして表現される現実の構造の多くは一見複雑な形状をしているが，自明でない特徴的な性質を持つ．このようなグラフ構造を総称して複雑ネットワークという．

詳説

　現実世界で観察される, 何らかの特徴的な性質を持つグラフのこと. もしくは一般にそのような性質を持つグラフのこと.

　インターネット, WWWのハイパーリンク構造, 交友・知人関係, 論文の引用関係, ニューラル・ネットワーク, たんぱく質の代謝反応など, グラフとして表現される現実の構造の多くは一見複雑な形状をしているが, 自明でない特徴的な性質を共通して持つことが近年分かってきた. そこで, 現実の大規模なグラフ構造の持つ特徴を調べ, その特徴が現れる原理を解明する研究が急速に進展している.

　なお, グラフにおいて点や辺に容量や長さなどの属性がある場合は特にネットワークと言うが, 複雑ネットワークの研究領域では, その区別は明確ではない. また, 特徴的な性質というものも明確に定まっているものではない.

　複雑ネットワークの特徴的な構造として知られる代表的なものとして, まずスケールフリー (scale-free) がある. スケールフリーとは, 次数が $k\,$ である確率 $p(k)\,$ , つまり次数分布がべき乗則を満たすこと（ $p(k)\propto k^{-\gamma }\,$ , ただし $\gamma \,$ は正の実数）を意味する.

　また, クラスタ係数に関しても特徴的な性質を持つことが多い. ここで, 次数 $k\,$ の点 $v\,$ のクラスタ係数は, 隣接点間の辺数を $k(k-1)/2\,$ (つまり隣接点間辺数の取りうる最大値) で割ったものとして定義され, すべての点にわたるクラスタ係数の平均がそのグラフのクラスタ係数と定義される. 現実の複雑ネットワークのクラスタ係数は, 点数に関わらず比較的大きい値を取ることが知られている.

　スモールワールド (small world) とは, 点数の多さに比較して平均点間距離が小さく, クラスタ係数が大きいことを指す. 単に平均点間距離が小さいことをスモールワールドということもある. この特徴を持つ現実の複雑ネットワークも多い.

　現実の複雑ネットワークが, スケールフリーをはじめ上記で挙げたような性質を持つ原因を解明するために, 様々なモデルが検討されてきた.

　複雑ネットワークの研究の興隆以前から知られていた, ErdösとRéyniのランダム・グラフは, 点集合の任意の二点間に確率的に辺を張ることでグラフを生成するモデルである. ただ, この次数分布はポアソン分布に従うため, スケールフリーではない. また, クラスタ係数は点数 $n\,$ の増加にしたがって $0\,$ に収束する. ただし, 平均点間距離は $O(\log n)\,$ であって小さいと言える.

　WattsとStrogatzは, 大きなクラスタ係数と小さい平均点間距離を同時に実現するスモールワールド・ネットワークのモデルを提案した. これは, 正方格子の辺集合の一部をランダムにつなぎかえるというものである. ただし, このモデルで生成されるグラフはスケールフリーではない.

　BarabásiとAlbertによるBAモデルは, 時間の経過とともに点も付け加えられていく「成長」(growth) と, 新しく加わった点は次数の高い既存の点と高い確率で辺で繋がれる「優先的選択」(preferential attachment) という２つの原理を基本としており, スケールフリーであるグラフ（ $p(k)\propto k^{-3}\,$ ）を生成する. また, 点数 $n\,$ の時, 直径は $O(\log n/\log \log n)\,$ であり, 平均点間距離は小さい. ただし, クラスタ係数は点数の増加にしたがって0に収束するため, 現実の複雑ネットワークとは違って小さい.

　「成長」と「優先的選択」に基づいたバリエーションとして, 次数の小さい点が選択的に非活性化して新しい点からの辺を受け取れなくなる頂点非活性化モデルなどがある. モデルにはランダム性が組み込まれていることが多いが, 決定的な規則によって点や辺を追加する階層的モデルというものもある.

　「成長」と「優先的選択」とは異なる原理に基づくモデルとして閾値モデルというものがある. これは, 各点には重みが確率的に与えられており, 点 $i\,$ と $j\,$ の間には, $i\,$ と $j\,$ の重みの和や積 (一般的には二点の重みの関数) に基づいて確定的もしくは確率的に辺が張られるというものである. 点の重みが従う確率分布が指数分布に従う場合などに, スケールフリーであるグラフを生成することが分かっている. また平均点間距離は小さい. クラスタ係数は, 点数が増加しても有限な値に留まるため, 大きいと言える. 点間距離の効果も考慮した空間閾値モデルへの拡張もある.

　これらのように, 現実の複雑ネットワークの持つ性質を再現する様々なモデルが提案されているが, 利用する際には, 対象とする分野に応じて適切なモデルを選ぶことが必要である.

　複雑ネットワークの性質の解明が進むにしたがって, それらの性質を持つグラフ上での相互作用やアルゴリズムに関する研究も進みつつある.

　例えば, コンピュータウィルスの拡散過程の研究がある. 伝染病の拡散の研究は古くから行われており, SISモデルなどの確率過程のモデルがあったが, それらはグラフ構造を仮定していない. しかし, コンピュータウィルスの拡散はグラフ構造に強く依存するため, グラフ上のSISモデルであるコンタクト・プロセスをはじめ, 様々なモデルが研究されている. これらは基本的に, 各点が健康・病気・回復・ウィルス潜伏などの状態の一つを取り, 異なる状態の点が隣接すると, それぞれの点の状態が確率的に他の状態に遷移するというものである. BAモデルによって生成されたグラフでは, 感染のしやすさを表す感染確率が小さくても感染が広がりやすいことが知られている.

　Webコミュニティ探索に関する研究も進展しつつある. これは, Webのハイパーリンク構造によるネットワーク (Webグラフ) 内にコミュニティを見出すことである. コミュニティの定義は様々であるが, 相互に密接にリンクを張っているページの集合, 言い換えればWebグラフ内の密な部分グラフという捉え方や, あるページ集合とそれらへリンクを張る (関心を同じくする) ページ集合のなす二部グラフという捉え方が一般的である. このようなコミュニティを発見することによって, 検索エンジンのカバー率の向上や, ディレクトリ検索型検索サイトのカテゴリの自動生成などに応用できる.

　Kleinbergによって提案された, オーソリティとハブからなる二部グラフをコミュニティと考えるものは有名である. これは, 関連するページへ多くのリンクを持つページ (ハブ) は情報の連結点として重要であり, また多くのハブページからリンクされているページ (オーソリティ) は, そのトピックについて重要な情報を持つといういう考え方をベースとしている. Webグラフ構造から各ページのオーソリティとしての価値とハブとしての価値の高いものを選び出すことによってコミュニティを抽出する.

　検索サイトのGoogleで採用されている, 検索結果の重要度を測るページランクという概念は, Webグラフ上のランダムウォークと密接に関係している. 点 $p\,$ のランクを $r(p)\,$ , 次数を $d(p)\,$ とした時, $\textstyle r(p)={\sum }_{s\in }\{\ p\,$ を終点とする有向辺の始点集合 $S\}\ r(s)/d(s)\,$ を満たすものとして, 各点のランクが定義される（ただし, すべての点のランクの和が1であるように正規化される）. あるページのランクは, そこへリンクを張るページが多いほど, そしてリンク元のランクが高いほど高くなる. ただし, リンク元のページから外部へのリンクが多いと, それからの寄与は小さくなる. ページランクは, 有向グラフの遷移確率行列に基づくマルコフ過程にしたがうランダムウォークにおいて, 定常状態における各点での滞在確率に等しい.