mixi engineer blog

*** 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers *** ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

mixiのスモールワールド性の検証

初めまして、mixi開発部のfujisawaです。

マイミクシィの友人関係を使って、mixiのスモールワールド性について調べましたので、その結果について書きたいと思います。

スモールワールド性とは

スモールワールド性とは、人間関係のネットワークなどでよく見られる性質で、文字通り「世間は狭い(It's a small world!)」ということを表しています。「知り合いを6人介するだけで、世界中の人々と間接的につながることができる」という『6次の隔たり(Six Degrees of Separations)』という言葉でもよく知られています。 一般にスモールワールドは以下の特徴を持っています。
  1. 誰に対しても少ない人数を介するだけで到達できる(平均距離が小さい)
  2. 自分の友人同士が友人関係にあることが多い(クラスタ性が高い)
1の距離とは、ネットワーク中のノードをたどった回数、すなわち友人を介した回数のことで、スモールワールドネットワークではこの距離が平均して小さくなる傾向にあります。

2のクラスタ性は、内輪づきあいの多さを表し、クラスタ係数という値で表現されます。このクラスタ係数が1に近いほど人間関係が密であり、0に近いほど疎であると考えられます。そしてスモールワールドネットワークではクラスタ係数が高くなる傾向があります。

たとえば下の図ではAはB、C、Dと友人関係にありますが、B、C、Dのそれぞれ(BとC、BとD、CとDの3ペア)が友人関係にある割合がAのクラスタ係数となります。ここでBとD、CとDが友人であるとすると、全体の3ペアの内2ペアが友人関係にありますので、Aのクラスタ係数は2/3=0.66..になります。このようにして他のノードのクラスタ係数も求めて、その平均を使用してグラフのクラスタ性を測ります。

cluster

次節では実際にmixiのマイミクシィの友人ネットワークを使用して、平均距離、平均クラスタ係数を求め、mixi上でスモールワールド性が成り立つかを検証したいと思います。

調査内容

まず試しに、筆者のmixi IDから残りの各ユーザ(2008年1月時点でmixi全体で約1300万人)までの最短距離(マイミクシィをたどった回数)を求めて、各距離ごとのユーザ数の分布を求めてみました。
距離 その距離のユーザ数 到達できるユーザ数 到達できるユーザの割合(%)
0 1 1 0.0000
1 37 38 0.0003
2 1103 1141 0.0087
3 58042 59183 0.4519
4 1896588 1955771 14.9341
5 7524544 9480315 72.3910
6 3046429 12526744 95.6533
7 338875 12865619 98.2410
8 33520 12899139 98.4969
9 5658 12904797 98.5401
10 2043 12906840 98.5557
... ... ... ...
160 1 12912255 98.5971
161 0 12912255 98.5971
距離が6で全体の95.7%、距離が7では98.2%のユーザをカバーできており、ほとんどのユーザに6、7人経由する以内で到達できていることが分かります。また平均距離は5.1になりました。まだ平均クラスタ係数は求めていませんが、筆者のIDで試した限りではスモールワールド性が成り立ちそうな期待が持てます。

ただしよく見てみると、距離が161のところで到達できるユーザ数の増加がなくなり、全体の98.6%のユーザまでしか到達できていないことが分かります。おそらくユーザの退会などにより、残りの1.4%のユーザはマイミクシィのつながりが切れているようで、他の大多数のユーザからはマイミクシィをたどる方法では到達することができません。そこでこの1.4%のユーザは対象から外して、もう一度調べようと思います。

またユーザによってマイミクシィの数はさまざまですので、その差異が少なくなるようにランダムに選択したユーザ1000人(1000人では少ないかもしれないのですが...)で同様に各距離の到達ユーザ数を調べ、その平均を求めるようにしました。その結果が以下の表になります。
距離 その距離のユーザ数の平均 到達できるユーザ数の平均 到達できるユーザの割合(%)
0 1 1 0.0000
1 22.3 23.3 0.0002
2 1302.5 1325.7 0.0103
3 70180.8 71506.5 0.5538
4 1526938.9 1598445.4 12.3793
5 5450652.5 7049097.9 54.5923
6 4317887.9 11366985.8 88.0325
7 1289133.9 12656119.6 98.0163
8 213414.6 12869534.3 99.6691
9 31455.8 12900990.1 99.9128
10 5188.6 12906178.7 99.9529
... ... ... ...
163 0.0 12912255.0 100.0000
距離が6では88%、距離が7の段階で98%のユーザに到達できています。平均最短距離は5.4となり、平均して6人程度という非常に少ない人数を介するだけで、他のユーザにたどり着けることが分かります。

また同様にランダムに1000人を選択し、その1000人の平均クラスタ係数を求めたところ、0.2になりました。一般にスモールワールドではクラスタ係数は0.1以上であるといわれているようですので、この0.2という値はスモールワールド性を表すのに適した値であると思われます。
ちなみに平均クラスタ係数が0.2ということは、100人の友人がいる場合はその友人同士の間で990ペアが友人であるということになります(0.2 × (100 × 99 / 2))。

また距離が1の場合のユーザ数に注目してみると、距離が1ということはユーザのマイミクシィそのものであるので、1ユーザあたりのマイミクシィの数は平均して22.3人ということも分かります。

まとめ

mixi上のマイミクシィネットワークを使用して、スモールワールド性について調査しました。その結果ユーザ間の平均距離は5.4、平均クラスタ係数は0.2となり、スモールワールド性が成り立ちそうであることが分かりました。

実は今回の調査よりも前に、mixi中のネットワークの分析を行い、スモールワールド性についても検証した研究報告がすでに存在します(『「複雑ネットワーク」とは何か―複雑な関係を読み解く新しいアプローチ』の167ページに掲載されています)。ただこの研究が行われたときからユーザ数が大きく増加していること、また何より自分がミクシィに入社したらこれはぜひ調べてみたい!と思っていたので、今回の調査を行いました。やはり実際に自分で確かめると楽しいですね。

これからも面白い現象を分析しつつ、サービスの開発に活かせていければと思います。