yohm's blog

プログラミングや研究などについて

What Big Data tells: Sampling the Social Network by Communication Channel

“What big data tells: Sampling the social network by communication channel” という論文が出ました。 “What Big Data tells: Sampling the social network by communication channels”, J. Torok, Y. Murase, H.-H. Jo, J. Kertesz, K. Kaski, Phys.Rev.E 94. 052319(2016) arXiv ここではその論文の内容を紹介します。

ICTの発達によって人間関係のコミュニケーションのデータがこれまでにないほど大規模かつ定量的に調べられるようになり、人間関係のネットワーク(社会ネットワーク)の特徴が明らかになってきました。これまでにFacebookなどのSNSTwitter、携帯電話の通話記録、E-mailなどの様々な電子デバイスのデータに加えて、IoTを利用して個人の物理的な距離をトレースすることにより対面でのコミュニケーションを推定した研究もあります。

これらの情報によって人々がどのように社会的な関係を築くかということについて多くの知見が得られましたが、これらの研究はそれぞれあるコミュニケーション手段の一つ一つを個別に解析した事例がほとんどです。一方で人々は日常的に様々な手段(電話、メール、SNS、チャット、オフラインでの対面での会話)を組み合わせてコミュニケーションをとっています。これらのコミュニケーションの全記録を解析することができればよいのでしょうが、技術的な面だけではなくプライバシーというデリケートな問題も含んでいるため今後も非常に難しいでしょう。(そのような研究事例もありますが、ボランティアを対象としたものとなるのでどうしても小規模な解析に限定されます。)つまり、研究対象のデータとして得られるネットワークというのは、社会ネットワークを部分的にサンプリングしたものにならざるを得ないのです。

この論文で扱っているテーマは、データから得られた「サンプリングしたネットワーク」の特徴がどの程度「全社会ネットワーク」の特徴を再現するか、言い換えるとデータからどの程度全ネットワークの特性を推定できるか、という問題です。もしサンプリングしたネットワークと全ネットワークが顕著に異なる特性を示すのであれば、データから全ネットワークの特性についての情報を限定的にしか得ることができないということになります。既存のデータの解釈が大きく変わることになるため非常に重要な問題と言えます。

f:id:yohm:20170212223223p:plain

実はサンプリングによってネットワーク特性が変わっていることを示す自明な特性があります。それは次数分布(各ノードのリンク数の分布)です。様々なICTデータから社会ネットワークが推定されていますが、ほぼ全てのデータが単調減少な次数分布を示しています。つまり最も頻度の大きい次数は1ということになりますが、これが全ネットワークとは違う特性であることは明白です。実社会では大多数の人が複数の人(ダンバーの仮説によれば典型的には150人程度)と親交があり、一人としか親交がない人は極めて稀であるということには異論がないでしょう。つまり、全ネットワークは何かしらピークを持つ次数分布(以下では単峰型と呼びます)になっていると思われますが、サンプリングしたことによって次数分布が単調減少になっているのです。では他のネットワーク特性も同じようにサンプリングによって変化するでしょうか?

f:id:yohm:20170212223235p:plain

assortativity(隣接ノードの次数相関)を考えてみましょう。様々な社会ネットワークのデータはそれぞれ様々な背景があり独立に調べられているものの、そのどれもが普遍的に正の次数相関を示しています。つまり次数の高いノードは他の高い次数を持つノードと繋がっている確率が高く、反対に低い次数のノードの隣接ノードは低い次数を持つ傾向があります。社会ネットワークには同じ特徴(例えば同じ性別、年代、社会的地位)を持つ人どうしが互いに繋がる傾向があることがわかっており、そのような傾向はHomophilyと呼ばれています。次数の相関についてもHomophilyの一つであるとこれまで解釈されてきました。

しかし、我々はグラフのサンプリングの研究で以下のようなことを明らかにしました。

  1. 一般的にassortativityがサンプリング後ももとのネットワークのものが維持されるためにはランダムにノードやリンクを一定確率でサンプリングする必要がある。しかし、そのようにサンプリングを行うと単調減少な次数分布は得られず、ピークを持つ次数分布になってしまう。
  2. ピークを持つ次数分布から単調減少な次数分布を再現するサンプリングの方法を提案した。この方法では単調減少な次数分布と正の次数相関を再現するパラメータ領域がある。このパラメータ領域では、かならず次数分布が正のバイアスを受ける。つまり、必ずしも元のネットワークが正の次数相関を持っていなくても、サンプリング後に正の次数相関を持つ場合がある。

このモデルは高校生の数学でもわかるくらいシンプルなモデルですが、現実の人々の行動のことを考えてももっともらしいモデルです。別の記事で紹介したいと思います。

これは我々が観測可能なデータはサンプリングの影響を強く反映しており、データで正の次数相関が観測されたからといって、全社会ネットワークが正の次数相関を持つとは結論づけることができないということを意味します。データを正しく解釈するためには、どのようにネットワークがサンプリングされるか、言い換えると人々がどのようにコミュニケーション手段を選択しているか、という部分についての理解を深めていくことが重要であることを示唆しています。

このようなネットワークのサンプリングという側面に着目した研究はこれまであまり注目を集めておらず、一般的にどのようなネットワークからどのような手法でサンプリングを行うとネットワーク特性がどう変化するのかといった問題の数理的な理解は不十分です。データの不完全性が問題になるケースは社会ネットワークだけではないため、今後、理論的な研究が進み、様々な複雑ネットワークの研究にも応用されることが期待されます。

Introduction of Weighted Social Network Model

これまで人間関係のネットワークの特徴がICTを使ったコミュニケーションのログを解析することによって明らかになってきました。例えば「弱い紐帯の仮説」という社会学で提唱されていた社会ネットワークについての仮説があります。この仮説ではネットワークのトポロジーとリンクの強さについての関係について、リンクが強いほどその両端のノード(人)は共通の友人を持つ頻度が高いということを述べています。もっとざっくりというと「密に結合したコミュニティの中ではリンクが強く、コミュニティ間をつなぐリンクは弱い」ということです。Onnelaらによって一国の全人口規模の携帯電話ユーザーの利用記録の解析をした研究によって、上記の関係が定量的に確認されています。

このような特徴をもつネットワークはどのような過程で形成されるのか?それを理解するための数理モデルについても研究が進んでいます。ここではKumpulaらが提唱した Weighted Social Network model (WSNモデル)というモデルを紹介します。Kumpula et al., Phys. Rev. Let. 99, 228701 (2007)

このモデルはノード数Nの重み付き無向グラフを考え、”Global Attachment(GA)”, “Local Attachment(LA)”, “Node Deletion(ND)” という3つのルールでネットワークを更新していくモデルです。

f:id:yohm:20170130210807p:plain

Global Attachment はあるノードが確率 \(p_r\) でランダムに選んだ別ノードにつながるというルールです。 例えば、たまたま同じ場所にいて知り合いになる、同じクラスになって知り合いになる、など既存の友人関係とは必ずしも関係のない人と出会う過程をモデル化しています。

一方、Local Attachment は友人に他の友人を紹介するという過程をモデル化しています。 ノード\(i\)が、隣接ノード\(j\)をリンクの重み \(w_{ij}\) に比例する確率で選び、さらにノード\(j\)の隣接ノード\(k\)を同様にリンクの重み\(w_{jk}\)に比例する確率で選びます。もし\(i\)と\(k\)の間にリンクが存在しなければ確率\(p_\Lambda\)でリンクを生成します。 この際に選択された \(i\), \(j\), \(k\)間の3本リンクは重みを \(\delta\) だけ増やします。友人同士で連絡を取り合うとリンクが強くなるということを表しています。

3つめのルールNode Deletionはノードを消すルールです。各タイムステップごとにノードをpdpdで削除し、新しいリンクの無いノードと入れ替えます。つまり選択されたノードの周りのリンクを全て削除することに相当します。もしこのルールが無いとリンクの数は永遠に増え続け最終的に完全グラフなるので、何かしらのリンクを削除するルールは必要不可欠になります。

このモデルでシミュレーションを行うと次の動画のようになります。 自発的にコミュニティ構造ができ、さらにそれらのコミュニティどうしは弱いリンクで繋がれるという現実で見られたパターンを再現します。

youtu.be

この動画を見るとどのようにしてコミュニティ構造が作られていくかがわかります。 まずノードはGlobal Attachmentによってランダムに別のノードに繋がれていき、コミュニティの「核」ができます。 Global Attachmentに繋がれたノードどうしはLocal Attachmentによってお互いをつなぐリンクを強化しつつ、友人を紹介することによって密につながりコミュニティを成長させていきます。 コミュニティは成長する過程でも、Global Attachmentによって弱いリンクがランダムに生成されますが、これがコミュニティ間をつなぐ弱い紐帯となります。 つまりLocal Attachmentというコミュニティを強固に形成する作用と、Global Attachmentというコミュニティどうしを散発的につなぐ作用の二つが重要な役割を果たしています。

このように2種類のリンク形成過程があるということは実データからも示唆されており(Kossinets et al., Science(2006))、それぞれFocal Closure、Cyclic Closureと呼ばれています。WSNモデルは、社会ネットワークでコミュニティの形成過程の本質をシンプルなモデルでうまく捉えているように思えます。個々のリンクの形成過程とネットワーク全体の構造の特徴の関係についての示唆に富むモデルと言えるでしょう。

またこの研究を起点としてテンポラルネットワーク(H.-H. Jo et al., PlosOne (2011))や多層ネットワークモデル(Y. Murase et al., Phys. Rev. E(2014))など様々な拡張も提案されています。

Modeling the Role of Relationship Fading and Breakup

“Modeling the role of relationship fading and breakup in social network formation” という社会ネットワークのモデル化についての論文を書きました。 この論文はPlosOneに掲載され、United Academics というサイトでも紹介されました。

人間社会は各個人が別の人とコミュニケーションをとりながら成り立っています。そのような人間の交友関係のネットワークは固定化されたものではなく、リンクやノードが新たに作られたり消されたりして形を変えながら存在しているようです。例えば、友人に誰か別の友人を紹介してもらったり、学校に誰かが転校してきたりしたときにはネットワークにあらたにリンクが作られるでしょう。

一方でネットワークは成長するばかりではなく、リンクの消滅も我々の周りにはよくみられます。例えば、仲のよいカップルが突然喧嘩別れすることもあるでしょうし、古くからの友達とだんだんと疎遠になっていって連絡をいつの間にかとらなくなることもあるでしょうし、転校や転職などで友人がいなくなることもあるかもしれません。このように様々な形で人間関係のリンクは切れることがあります。

これまで個々のリンク形成過程と全体のネットワーク構造の関係についてよく研究されて来ましたが、リンクの消滅がネットワーク全体に対して与える影響というのはあまり調べられて来ませんでした。この論文では「リンクの切れ方が社会ネットワーク全体の特性をどのように変えていくか」という問題について理論的に調べました。

具体的にいうとWeighted Social Networkモデルという社会ネットワークの特徴を再現するモデルをベースとして、”Link Deletion (LD)”, “Node Deletion (ND)”, “Link Aging (Aging)” という3種類のリンクの切れ方のモデルの性質を調べました。

LDは「カップルが突然喧嘩別れする」というような唐突にリンクが切れる状況をモデル化しており、具体的には各タイムステップごとに各リンクがある確率で切れる、というモデルです。 NDは例えば「誰かがいなくなる」というような状況に対応するモデルで、各ノードがある確率で取り除かれる、というモデルです。 Agingは「だんだん疎遠になっていく」という状況を記述しています。時間とともにリンクの重みが指数関数的に減衰し、閾値を下回ったところでリンクが切れるというモデルです。 この3つのリンクの切れ方は出来上がるネットワークにどのような差異を生み出すでしょうか?

実は研究を始めた当初は、適切に時間スケールさえ合わせればリンク断絶のモデルを変えても結果としてできあがるネットワークに大差はないだろうと考えていました。 もともとこのモデルではNDがリンク削除のメカニズムとして提唱していたのですが、共同研究者の一人がこのモデルが好きじゃないと言い出したのでしぶしぶAgingモデルを試したのがこの研究のきっかけになりました。Agingモデルにすると想像以上に顕著な差異が出てきて、しかも詳細に調べてみるとこの差異は社会ネットワークの特性とも深く関連していることがわかりました。

3つのモデルで出来上がるネットワークを可視化すると以下のようになります。

f:id:yohm:20170128184931p:plain

まず気づくのは、Agingモデルではノードが互いに強く結合した幾つかのグループに分割されます。このような密に結合したグループはネットワーク科学でコミュニティと呼ばれています。Agingモデルではコミュニティ内部は密につながっている一方で、コミュニティ間は非常に弱いリンクでまばらにつながっているだけです。例えて言えば外部とはあまり交流をしない村社会のような「閉じた」ネットワーク構造です。このような特徴はモジュラリティという指標で評価することができ、Agingで形成されるネットワークは非常にモジュラリティが高いネットッワークになります。

それとは対照的にNDやLDでは局所的にコミュニティ構造を持っていますがAgingほど極端ではなく、コミュニティ外部ともそれなりの頻度でリンクを作っており、より「開かれた」ネットワークを形成していると言えるでしょう。

Agingのネットワークのモジュラリティが高い理由は社会ネットワークの特徴と関係しています。 社会ネットワークにはリンクのトポロジーと重みの間に関係があることがわかっており、コミュニティ内部に重みが大きいリンクが多く存在し、それらのコミュニティは互いに弱いリンク(「弱い紐帯」)で繋がれているという特徴があることが知られています。 Agingはだんだんとリンクが弱くなるモデルなので、コミュニティ間をつなぐリンクが優先的に切られます。コミュニティ構造がAgingによってさらに強調される形となり、結果としてモジュラリティが非常に高い「閉じた」ネットワークが出来上がります。一方でLDやNDではコミュニティ外部のリンクだけを優先的に切るというメカニズムがないため、結果としてより「開かれた」ネットワークになりやすいのです。論文にはより詳細な話が書いてありますが話の本質はここに書いてある通りです。

では、どのモデルがより現実に近いのでしょうか? 我々は、シミュレーション結果に対して様々なネットワーク特性(次数分布、ノード強さ分布、コミュニティサイズ分布など)を現実の携帯電話の通話記録のネットワークと比較しました。 その結果、定性的な比較ではありますが、LDが最も現実を再現し、Agingの結果とは明らかに符合しないことがわかりました。

現実の社会ではLD、ND、Agingのように様々なリンクの切れ方が混在していると思われますが、その中でも主要な役割を果たしているのは、Link Deletionでモデル化されるようなリンクが突発的に切れるようなイベントなのかもしれません。 これまで社会におけるリンクの形成過程については実データからも研究が詳細に行われてきましたが、リンクの切れ方についての実データを利用した研究は比較的少ないようです。本研究で得られた示唆が更なるデータによって検証されることを期待したいと思います。