Analysis of a large-scale weighted network of one-to-one human communication

Jukka-Pekka Onnela 1,2
Jari Sramaki 1
Jorkki Hyvonen 1
Gabor Szabo 3,4
M. Argollo de Menezes 3
Kimmo kaski 1
Albert-Laszlo Barabasi 3,4
Janos Kertesz 1,5

1 Laboratoryof Computational Engineering, Helsinki Universityof Technology, Finland
2 ClarendonLaboratory, PhysicsDepartment, OxfordUniversity, Oxford, U.K
3 Departmentof PhysicsandCenterforComplexNetworksResearch, University of NotreDame, IN, USA
4 CenterforCancerSystemsBiology, DanaFarberCancerInstitute, Harvard University, Boston, MA, USA
5 Departmentof Theoretical Physics, BudapestUniversityof Technologyand Economics, Budapest, Hungary

2007 New J. Phys.

PDFファイルへのリンク

概要

社会ネットワークの解析の手法を実際に行った実験をもとに丁寧に説明している論文。
社会ネットワーク解析のレシピのようなもの。
十分に信頼できる規模・データでのweak ties hypothesisの証明に成功している。
edge-clustering coefficientとよく似たoverlapというパラメーターの利便性を主張している。
以下の構成からなる。

Introduction & Data
Basic network characteristics
Advanced network characteristics
Single link properties
Percolation studies
Discussion

Introduction Data

本論文では携帯電話の通信記録、７００万以上のノード、１８週間のデータをもとに解析。
電話の部分だけを考慮。（メールやその他は含まない）。
オペレーターはフィルタリングする。
エッジの定義に、
一方的な電話も含めると・・・７２０万ノード、２２６０万リンクからなるネットワークに。
お互いに掛け合った場合だけにすると・・・４６０万ノード、７００万リンク。
エッジの重みの付け方を２通り定義する。
一つはその２者間での総通話時間。
もう一つはその２者間でのそう通信回数。

Basic network characteristics

視覚的に解析（スノーボール法）
次数分布による分析
リンクの重み・ノードの強さの分布による分析
neighborとの関係の分析
クラスタリング係数を用いた分析
次数と重みと強さの関係

視覚的に解析（スノーボール法）

スノーボール法*1を用いてデータをサンプリングし、２次元で視覚化し、考察している。（たいした考察していない。）
スノーボール法では起点となるノードからの距離が一番遠いノードが抽出されたノードの集合の大部分を占めることを、実験のデータからグラフ・図を用いて示し、スノーボール法による視覚的解析の限界を説明している。

次数分布による分析

次数分布のグラフを作り、分析している。
一方向の電話も含めたグラフだと最大で34635の次数を持つノードが現れるなどして、社会ネットワークのモデルとしては不適切だと判断し、お互いに掛け合った場合のみをリンクとして定義する。
また、分析の対象として、LCC（largest connected components、繋がり合った最大の塊）とネットワーク全体とを比べ、ほとんど差がないので今後はLCCを扱うこととする。これにより、扱うノード数は全体の８４％の３９０万ノードになる。
グラフはべき乗則（power low）*2に従っている（つまりべき分布 *3）。少数の人がたくさんの人と繋がっているということがわかる。

リンクの重み・ノードの強さの分布による分析

リンクの重みの定義はその２者間での総通話時間と総通話回数。ノードの強さの定義はその人の総通話
時間と総通話回数。
リンクの重みの分布とノードの強さの分布を示し、その形が質量保存則がポイントとなるネットワーク（the number of passengers carried by the airline transportation network*4、the reaction fluxes in metabolic networks*5、packet transfer on the Internet*6）によく見られる形であると述べている。質量とは、旅行者だったり、分子だったり、データパケットのことである。
しかし、社会ネットワークおいて質量にあたるものは特にないのでその点については研究の余地がある。
またリンクの重みの付け方２通りで分布が似ていたのでランダムに5000リンクを抽出して相関を見たところ正の相関があることがわかった。

neighborとの関係の分析

伝統的なdegree-degree correlationをグラフにし、このネットワークがassortative mixing*7であることを述べている。
degree-degree correlationと同じ発想で、strength-strength correlation的なことも調べている。こちらについては、ほとんどの場合で相関は見られなかった。（相関が見られたのは全体の4.4％、理由はstrengthの定義によるものと考えられる）

クラスタリング係数を用いた分析

経験上、ネットワークにおいては高いクラスタリング係数が観測されることが多い。
クラスタリング係数*8と次数のグラフ（clustering spectrum）を示し、クラスタリング係数と次数の比例係数が-1でであり、これまでもネットワークでよく見られたものなので他のネットワークと区別するのに役に立たないと述べている。

次数と重みと強さの関係の分析

ノードの次数強さの関係をグラフにし、強さが次数に比例せず、次数の0.9乗・0.8乗に比例していることから、たくさんの人と話す人は一人の人と話す回数・時間がわずかに少ない・短いことを示している。
２つのノードの次数の積と強さの積の関係をグラフにし、強さの積が次数の積に比例せず、次数の積の0.4乗・0.7乗に比例していることからも、たくさんの人と話す人は一人一人の人と話す回数・時間がわずかに少ない・短いことを示している。
２つのノードの次数の積とその間のリンクの重さの関係をグラフにし、ほとんど相関がないことを示している。リンクの多い２人のリンクが重い訳ではない＝友達が多い人同士が仲良しという訳ではないということがわかる。つまり今回のグラフに関してはwaighted-assortativeではない。
２つのノードの次数の積とその間のリンクの重さの関係をグラフにし、リンクの重さが隣接ノードの強さの相乗平均に比例することを示している。電話をたくさん使う人同士はたくさん電話で話すということ。

Advanced network characteristics

ノードの強さと、triangleのintensity、coherenceとの関係
重み付きクラスタリング係数の利用*9
ランダムネットワークとの比較

ノードの強さと、triangleのintensity、coherenceとの関係

subgraph intensity*10とsubgraph coherence *11をsubgraphのプロパティとして導入している。
intensityはsubgraph内のすべてのリンクの重みの相乗平均で、subgraph内のリンクの強さを表す。
coherenceはsubgraph内のすべての重みの相加平均と相乗平均の比で、subgraph内でのリンクの均一性を表す。値は０〜１をとる。
この論文ではsubgraphとしてほとんどtriangleに注目した分析のみを行っている。
ノードの強さと、その強さのあるノードを含むtriangleのintensityの平均を同じ強さのノードで平均したものとの関係をグラフにし、強いノードほどtriangleのintensityが高いことを示している。
どうようにノードの強さと、その強さのあるノードを含むtriangleのcoherenceの平均を同じ強さのノードで平均したものとの関係をグラフにし、intensityのときとは明らかに違い、ノードが強すぎもせず弱すぎもしない中間くらいのときにcoherenceの値が高いことを示している。

重み付きクラスタリング係数の利用

ノードのプロパティとして重み付きクラスタリング係数*12を導入している。
ノードの強さと重み付きクラスタリング係数の関係をグラフに表し、強いノードほど重み付きクラスタリング係数が大きいことを示している。

ランダムネットワークとの比較

ランダムネットワークで存在が期待されるクリーク*13の数に比べて実験のネットワークでは圧倒的にクリークの数が多かったことを表を使って示している。
またランダムネットワークでのintensity・coherenceと実験のネットワークのintensity・coherenceをグラフにして比較し、どちらの値もsubgraphのノードの数が増えるほど実験のネットワークの方が圧倒的に高い値となる傾向があることを示している。intensityの結果とcoherenceの結果をまとめて考えると、クリークの中のリンクはどれも重く、均一な値を持っていると言えると述べている。

Single link properties

オーバーラップ（overlap）
媒介中心性（betweenness centrality）
オーバーラップと媒介中心性の関係

ここからはweak tie hypothesisと関連付けるためリンクの重さを強さ（strength）と言い換えることがある。

オーバーラップ（overlap）

リンクのプロパティとしてオーバーラップ*14を導入している。
よく似ているRadicchiらが考案したedge-clustering coefficientよりもより利用価値があることを主張している。
リンクの強さとオーバーラップの関係をグラフに表し、ほとんど（約９５％）のリンクに関してはリンクが強い程オーバーラップが大きいことを示している。このことでグラノヴェターのweak tie hypothesis（弱い紐帯（ちゅうたい）の仮説）*15が信頼できる十分な規模の社会ネットワークで実験的に証明されたと主張している。

媒介中心性（betweenness centrality）

リンクのプロパティとして媒介中心性（betweenness centrality）*16を導入している。
最短パス検出の計算量はかなり大きいので、この実験では全体のグラフの一部（１０万ノード）を始点として、すべてのノード（３９０万ノード）への最短パスを計算することにしている。
betweenness centralityもべき分布になっている。

オーバーラップと媒介中心性の関係

オーバーラップと媒介中心性の関係をグラフに表し、オーバーラップが小さいほど媒介中心性が大きいことを示している。
リンクの強さとbetweenness centralityの関係を示していないにもかかわらず、弱いリンクほどオーバーラップが小さくbetweenness centralityが大きく、強いリンクほどオーバーラップが大きくbetweenness centralityが小さい、と結論付けている。

Percolation studies

パーコレーション理論*17に基づいた分析を行っている。
具体的には一つずつリンクを消していったときにいろいろな観測量の変化を調べるのだが、この実験ではリンクをランダムに消していくのではなく、重さ、オーバーラップ、betweenness centralityを基準として、それぞれその値が高い方、低い方から計６通りの消し方で調べている。
観測量は、最も大きなリンクで繋がりあったノードの集合のノードの数、susceptibility（相転移のポイントがわかる）、平均最短パス長、平均クラスタリング係数、の４つとしている。
２４のグラフについてそのほとんどに言及しているが、ポイントはオーラップを基準にしたときとbetweenness centraliltyを基準にしたときで観測量の振る舞いが良く似ているということ。このことから社会ネットワークのコミュニティを発見するのにオーバーラップを用いると良いのではないかと述べている。betweenness centralityがよく使われるのだが、計算量はO(N^2lnN)と大きく、それに比べてオーバーラップの計算量はO(N)ですむからである。

Discussion

この実験、論文のまとめ。

*1:まずノードを一つ決め、そこから一定のパス以内で到達できるノードを抽出する手法。今回はパスの長さは５を持ちいている

*2:ある観測量がパラメータのべき乗に比例すること。

*3:べき乗則に従う分布の名前。正規分布に比べて裾の部分が厚い（fat tail）

*4:V. Colizza, A. Barrat, and M. Barth ́elemy, and A. Vespignani. The role of airline transportation network in the prediction and predictability of global epidemics. Proc. Natl. Acad. Sci USA, 103:2015–2020, 2006.

*5:K.-I. Goh, , B. Kahng, and D. Kim. Universal behavior of load distribution in scale-free networks. Phys. Rev. Lett., 87:278701, 2001.

*6:E. Almaas, B. Kov ́acs B, T. Vicsek, Z. N. Oltvai, and A.-L. Barab ́asi. Global organization of metabolic fluxed in the bacterium escherichia coli. Nature, 427:839–843, 2004.

*7:次数の多いノードが次数の多いノードと隣接していることが多い状態。（次数が大きいほど隣接ノードの次数の平均が大きい）

*8:ノードのプロパティ。ノードとそのノードの隣接ノード２つでtriangleを形成している確率

*9:intencity,coherence,weighted clustering coefficient（クラスタリング係数）はJ.-P. Onnela, J. Saram ̈aki, J. Kert ́esz, and K. Kaski. Intensity and coherence of motifs in weighted complex networks. Phys. Rev. E, 71:065103, 2005.で定義されている。

*10:intensityの定義　 $i(g) = (\prod\limit_{(ij)\in l_g} w_{ij})^{1/|l_g|}$

*11:coherenceの定義　 $q(g) = i(g)|l_g|/{\sum\limit_{(ij)\in l_g} w_{ij}$

*12:クラスタリング係数×triangleの平均intensity

*13:内包するすべてのノード間にリンクがあるようなsubgraphのこと

*14:リンクに隣接するノードそれぞれの友達が共通の友達である確率

*15:弱い紐帯からの方が情報を多く得られるといったような内容

*16:任意のノードとノードをつなぐパスを短くすることにそのリンクがどれだけ貢献しているかを表す値。定義は　　 $b_{ij} = \sum_{v\in {V_s}} \sum_{w\in {V/\{ v \} }} \sigma_{vw}(e)/\sigma_{vw}$ 　　vはすべてのノード、wはvを除くすべてのノード、σ(e)はe（リンクij）を含んだvw間の最短パスの数、σはvw間のすべての最短パスの数を表す

*17:元々は有機体化学の問題に対する答えとして発展したもの。様々な問題に対して応用されている。キーワードは相転移。