Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

【ネットワークの統計解析】第3回 代表的なネットワークのモデルを俯瞰する (1)

R&D 新卒 データ分析 連載

f:id:kur0cky:20201023211747j:plain

こんにちは．Sansan DSOC 研究開発部の黒木裕鷹です． 10月にゼルダの伝説 Breath of the Wild を購入し毎日2~30分ほどプレイしているのですが，寄り道ばかりしてしまい，まったくクリアできる気配がありません笑

さて，この連載では，自分の勉強・復習も兼ねて，ネットワークデータにまつわる統計解析を気の向くままに紹介しています． 第1, 2回は，ネットワークデータの標本調査（サンプリング）を扱いましたが， 今回からはいよいよ数理モデルを取りあげていきます． とはいえ，一概にネットワークのモデルといってもその範囲や種類は膨大なものになります． そこで，今回の記事では手始めに，広くネットワークデータにまつわる現象とそれぞれの代表的な数理モデルを俯瞰し，全体感を掴むことにします． それでも長くなってしまうことが予想されるため，この記事では主に「複雑ネットワーク」というテーマを中心に絞り，ノードの分散表現や深層学習の利用については次回の記事に回したいと思います．それではやっていきます

ランダムネットワークと複雑ネットワーク

複雑ネットワーク

ネットワーク構造をもつデータは幅広い分野で観測することができます． たとえば，無数のwebサイトとハイパーリンクによって構成されるWWW (World Wide Web) ，FacebookやTwitterなどSNSの交友関係，交通網，研究者の共著ネットワーク，タンパク質の相互作用ネットワーク (Protein Protein Interaction; PPI) などです． しかし，これら現実の多くのネットワークが，「ランダムなネットワーク」ではうまく近似できず，かつ「ある共通の性質」を持っていることが知られています． その代表的なものが「スモールワールド性」と「スケールフリー性」です． これらの「性質」をもつネットワークはどのようにすれば作ることができるのか，ネットワーク生成モデルの研究が盛んに行われました．

次回以降の記事でまた触れるかと思いますが，それぞれの性質について簡単に紹介します． スモールワールド性とは，その名の通り世界は狭いことを表す性質で，「6次の隔たり」という言葉でも知られています． 世界中からどのように2人を選んでも，6人程度の知り合いを介してつながっている，という主張です． もう少し詳細には，ノード間の平均距離やネットワーク直径が，ネットワークの大きさ（ノードの数）に比べて圧倒的に小さい，ということを意味しています． 比較的大きいクラスター係数を併せ持つのも特徴です． スモールワールド・ネットワークを生成するモデルとしては，Watts-Strogatz (WS) モデル[15]が有名です．

一方でスケールフリー性とは，次数分布がべき則で近似できることを表します． つまり，あるノードが次数 kをもつ確率を p(k)としたとき，その確率が次式のようになるということです．

\displaystyle p(k)\propto k ^ {-\gamma}

ここで， \gammaはべき指数とよばれ，特に 2 \leq \gamma \leq 3のときを指してスケールフリーネットワークといわれることが多いです． というのも，この範囲では「平均次数が定まる一方で，次数の2次モーメントが発散する」という特殊な状態が起こるためです． このことが示しているのは，平均的なつながりの数は有限になるのに対し，極端に多くのつながりを有するノードが存在する，ということです． スケールフリー・ネットワークを生成するモデルとしては，Barabasi-Albert (BA) モデル[3]が有名です．

ランダムネットワーク

上記の性質やWSモデル，BAモデルなどについての統計的側面は十分に研究されてきました． その一方で，ランダムネットワークについても研究が進んでいます． 任意のノード間にエッジが張られる確率は一定であるとする Erdos-Renyi (ER) モデル[5]を皮切りに，任意の次数分布を与える一般化ランダムグラフモデル[11]，エッジの有無へのロジスティック回帰の適用を発端とした指数ランダムグラフモデル (exponential random graph model; ERGM) [8, 14]などが開発されてきました．

これらランダムネットワークの応用には様々なものがあります． たとえば，ノード間のつながりをシャッフルすることにより，一般化ランダムネットワークを帰無仮説としたモンテカルロ検定を行うことができます． つまり，あるネットワーク特徴について，観測ネットワークが一般化ランダムネットワークではないかどうかの検定をシミュレーションで行えるということです． また，指数ランダムグラフモデルは，エッジを張りやすい人気者とそうでない人がいることを考慮したり，スター構造を導入することによって後述する homophily の寄与を考慮することができます．

ERモデルによるランダムネットワーク，WSモデルによるスモールワールドネットワーク，BAモデルによるスケールフリーネットワークの例を次に示しました． ノードの数や密度は同じにしていますが，クラスター係数やハブの存在などで違いがあることが分かると思います．

f:id:kur0cky:20201204115359p:plain
図：密度の同じランダムネットワーク（左），スモールワールドネットワーク（中央），スケールフリーネットワーク（右）

ランダムネットワークについては次回以降の記事で詳しく扱うつもりでいますが， 複雑ネットワークの良い和書としては，たとえば[1]や[2]があります．

その他の現象とモデリング

コミュニティ抽出

一部のノード集合が，その他のノード集合に比べてより密な状態を形成している状態は，現実のネットワークでも多く観測されます． たとえば，あるゲームのファンたちが，SNS上でより密にフォローし合っているような状態です． このような構造をコミュニティ (community) もしくはクラスタ (cluster) といい，所与のグラフからコミュニティ構造を特定するタスクをコミュニティ抽出 (community detection) といいます． グラフ分割やグラフクラスタリングとよばれることもあります．

さて，コミュニティを明確に定義することは難しいですが，どのようなグルーピングがより「コミュニティっぽいものを抽出できている」と考えられるでしょうか． 同じグループ内のノードは密に結びついている一方で，異なるグループのノード間は疎に結びついているとき，そのグループは一つのコミュニティっぽい，と誰もが考えるのではないでしょうか． このような考えに基づいた，modularity という指標がコミュニティ抽出ではよく用いられ，多くのアルゴリズムが modularity を最大化するように分割を探索します． modularity は，「グループ内のノードがつながるエッジの割合」から「リンクがランダムに配置された場合の期待値」を引いた値として定義されます． また，エッジを削除していくことによりネットワークを分割していくトップダウン的な手法と，ノードをまとめることでクラスタにしていくボトムアップ的な手法に大別されます．

確率的ブロックモデル (stochastic block model; SBM)[9] とよばれる確率モデルも，コミュニティ抽出のタスクに利用されることがあります． SBMでは，ノード集合が複数のグループに分かれていること，あるノード間にエッジが張られる確率はそれぞれノードがどのグループに属しているかのみに依存すること，を仮定したモデルです． つまり，それぞれのグループ内ではランダムグラフであり，2つのグループ間はランダムな2部グラフになっている，ということです． よって，グループ内 / 間でエッジが張られる確率は対称行列で表すことができます． それぞれのノードがどのグループに属しているかは未知ですが，EMアルゴリズムなどを用いれば推定することができます． SBMによって生成されたネットワークの例を次に示しました． ブロック数は3つに設定してあり，図からも3つのコミュニティがありそうなことが見て取れます．

f:id:kur0cky:20201204115349p:plain
図：確率的ブロックモデルによる生成ネットワークの例

また，上記のコミュニティ抽出に比べると少しマイナーですが，ネットワークのトポロジに着目した，拡散過程に基づくようなコミュニティの定義なんかもあったりします[13]．

コミュニティ抽出についてより詳しく知りたい方などは，たとえば[6]などを読むと良いでしょう．

同類度

現実のネットワークでは往々にして，あるノードの次数と近傍ノードの次数が無相関にはなりません． たとえば，WWW では0.82に，PPI では-0.10になるそうです[1]． このような次数の相関を次数相関 (degree assortativity) というのですが，次数以外の特性に関しても近傍との同類度 (assrotativity) を考えることができます． たとえば友人関係は，年齢，国籍，言語，所得，居住地域など，一定の特性に基づいた関係を築くといわれています． ほかにも，引用ネットワークにおける論文は，同じ分野の論文を引用する傾向があるでしょう． assortative なノードを近傍に選ぶ傾向のことを，homophily といいます． 前述した指数ランダムグラフモデル (ERGM) は homophily の寄与を考慮することができ，多様な分野で利用されています． ある交友ネットワークがあったとき，そこではどの程度「友達の友達もまた友達になりやすかったか」を推定できたりするわけです． homophily と ERGM については，DSOC研究員の前嶋による記事が分かりやすいです． また，次数相関のあるネットワークを生成する数理モデルも研究されていたりします[4, 10]．

ネットワーク上の確率過程

感染現象や情報拡散は，ネットワーク上の確率過程としてモデリングすることができます． たとえば Twitter では，フォロワーがツイートを見るだけでなくリツイートをすることによって，さらにそのフォロワーの目にも触れることになります． このとき，あるフォロワーがリツイートを行うかどうかを確率変数とみなすと，この拡散過程の統計的な性質を議論することができるわけです． 感染症のモデリングも同様に考えることができます． 感染からの回復後に免疫が獲得できる場合のモデルとしてSIRモデルが，インフルエンザなど免疫を得にくいものに対してはSISモデルなどがよく知られています． また，感染後の死亡も考慮したSIRDモデルなどの様々な拡張もあります．

もっとも単純な確率過程としてはランダムウォークが知られていますが，ネットワーク上をランダムウォークするような確率過程も考えることができます． 近傍ノードを無作為に選択し移動するような確率過程です． ネットワーク上のランダムウォークの有名な応用例に，pagerank があります． pagerank は Google の検索アルゴリズムで使われていたことで有名ですが，実はランダムウォークの定常分布として定義されます． 有向ネットワークの場合は，入次数が0であるノードの定常確率が0になってしまいうまくいきませんが，一定確率でランダムなノードにワープする，という工夫をすることで解決することができます．

近年着目されているノードの分散表現でも，ネットワーク上の確率過程によって系列データを作り出し，word2vec を適用するようなものが多数存在します[7, 12]．

おわりに

連載第3回の本記事では，モデルの具体的な紹介と説明に入っていく前に，ネットワークの解析でよく扱われる現象とそれらに対する代表的なモデルを俯瞰しました． 今回扱った内容は特に複雑ネットワーク中心として，1980から2000年代の話題を扱っていましたが，次回は深層学習にまつわるものを俯瞰したいと思います． 紹介できた内容はほんの一部ですし，そもそも私が知っている範囲もものすごく狭いのですが，少しでもネットワーク分析の全体像をうかがい知る助けとなれば幸いです．

さいごに，寒くなってきましたが，クリスマスも近づき街が浮き足立ってきたような感じがして楽しいですね．予定はないです． それではまた

参考文献

  1. Barabási, A. L. (2016). Network science. Cambridge university press. （アルバート・ラズロ・バラバシ. 池田裕一・井上 寛康・谷澤俊弘・京都大学ネットワーク社会研究会 (訳). (2019) ネットワーク科学: ひと・もの・ことの関係性をデータから解き明かす新しいアプローチ. 共立出版. ）
  2. 増田直紀, & 今野紀雄. (2010). 複雑ネットワーク: 基礎から応用まで. 近代科学社.
  3. Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. science, 286(5439), 509-512.
  4. Berg, J., & Lässig, M. (2002). Correlated random networks. Physical review letters, 89(22), 228701.
  5. Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1), 17-60.
  6. Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics reports, 659, 1-44.
  7. Grover, A., & Leskovec, J. (2016). node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 855-864.
  8. Holland, P. W., & Leinhardt, S. (1981). An exponential family of probability distributions for directed graphs. Journal of the american Statistical association, 76(373), 33-50.
  9. Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social networks, 5(2), 109-137.
  10. Newman, M. E. (2003). Mixing patterns in networks. Physical review E, 67(2), 026126.
  11. Newman, M. E., Strogatz, S. H., & Watts, D. J. (2001). Random graphs with arbitrary degree distributions and their applications. Physical review E, 64(2), 026118.
  12. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 701-710.
  13. Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118-1123.
  14. Wasserman, S., & Pattison, P. (1996). Logit models and logistic regressions for social networks: I. An introduction to Markov graphs andp. Psychometrika, 61(3), 401-425.
  15. Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’networks. nature, 393(6684), 440-442.

© Sansan, Inc.