« [はてブ]SBMにおけるブックマーク「サゲ」攻撃の可能性 | トップページ | [Mixi]Mixiの参加者同士が繋がっている事の証明 »

2006.09.30

[Mixi]つながりを表す指標「笠原数」の提案

□はじめに
Mixiを使ったことのある人は自分または他の人マイミクの数を気にした事があるかもしれない。Mixiの興味深さは「ある人」と「ある人」が繋がっている事が「マイミク」というつながりで可視化できることである。これは非常に重要である。というのは、リアルな世界では、ある人とある人が知人かどうかは、その周囲の人に聞いてみるしかないからだ。Mixiはそのつながりを自動的に表示してくれる。

□つながりの科学~ミクロの場合
この「つながり」ということを数学的に言うとどうなるだろうか?「つながり」は数学的に言うところの「グラフ理論」で表される。例えばマイミクの数は辺、あるいはリンクの数となる。Mixiに参加している人は頂点で表される。

もう少しつっこんでみよう。AさんのマイミクBが、AさんのマイミクCとマイミク同士であることも良くある。この「良くある」頻度をクラスター密度呼ぶ。これによって、Aさんの周囲でどのようなマイミクが形成されているか、ある程度の指標を教えてくれる。

□つながりの科学~マクロの場合
ここでよりマクロ問題を考えてみよう。Mixiの参加者であるAさんとBさんをランダムに選ぶ。AさんとBさんは何人のマイミクを介して繋がっているのだろうか?(問題A)そして、どんなAさんでもBさんでも平均どのくらいのマイミクを挟めばつながっているだろうか?(問題B)これは非常に興味深い問題だ。

この手の最初の実験をしたのはミルグラムらの実験である。彼は、アメリカ人におけるまったく他人同士において、何人を介して手紙が届くか実験をした。答えは大抵6次のつながりだったという。
今、1次とはマイミク同士、2次とはマイミクのマイミク同士と考えてもらって構わない。

□Mixiとつながりの科学
この問題をMixiで研究することは有意義なことである。というのは、マイミクという情報が既にサーバにあり、問題AにしろBにしろ計算可能だからである。しかし直感的にわかるように、問題Bは答えがわかるまでに相当大きな計算が必要であることがわかる。

もう少し単純なことを考えよう。
Mixiの参加者である、特定の人を決めておく。この人とAさんがどのくらいのマイミクを挟めば繋がっているだろうか?(問題C)

問題Cは既に特定の人という基準があるので、問題Bに比べると計算が楽である。問題Aと計算量はほぼ同じだが、どんなMixiの参加者からも共通のものさしを与えられる事が違う。

ではこの特定の人を誰にすべきか?という事が挙げられる。重要なことは
・有名人であること
・Mixiに永続的に参加していること
の2つであろう。特に後者を考えるとMixi社長の笠原氏が望ましいと考える。

今、笠原氏とMixiの参加者での繋がりの数(ホップ数)を「笠原数」と定義する。
笠原氏のマイミクは笠原数=1、笠原氏のマイミクのマイミクは笠原数=2である。
ちなみに私は笠原数が2である。(ちなみに笠原氏自身は笠原数は0である)

この手の話は、私がオリジナルではない。グラフ理論の権威であるエルデシュ氏を称えたエルデシュ数を参考にしている。皆様も是非笠原数を計算して欲しい。

□Mixiと笠原数
実はこれからが本題である。
笠原数が3以上についてはMixiで計算する事は面倒である。というのは笠原数が2以下の場合にはMixiが自動的に表示するが、3以上は手計算で調べないといけないからである。

では、笠原数が3以上の人はどのような計算をすればよいだろうか?一番確実なのは、マイミク経由で総当りに調べる事である。しかしこれはとても大変である。

そこで、次のようなアルゴリズムが考えられる。
[アルゴリズム1]マイミクが多い人を優先的に計算する
[アルゴリズム2]ITあるいはベンチャー系に関心がある人を優先的に計算する

アルゴリズム1はMixiのマイミク数がべき乗に分布していることを利用している。つまり、ハブとなる人を経由すれば、おのずと笠原氏とつながるだろうということである。
アルゴリズム2は「笠原氏」と繋がるであろうマイミクを「推定する」している。つまり、たんなる数学的な情報だけでなく、意味的な情報を含めて最短パスを計算する。

今まで、コミュニティの最短パスの計算等は単に数学的な研究結果を考慮してアルゴリズムを計算した場合が多かった。しかし、参加者の特性(特にアルゴリズム2)を利用したコミュニティのつながりに関する研究がもっと盛んに行うべきだと私は思う。つまり今までグラフ理論にプラスした「何か」の情報を加えた研究がこの手の分析には有効だと思うのだ。それはグラフ理論の有向グラフ、重み付けグラフ等に結局は帰するかもしれないが。

もしかすると、「意味のつながり」の近さ(日記やプロフィール、趣味など)を数学的に記述できるようになれば、アルゴリズム2のようなことは自動的に計算できるのかもしれない。

□終わりに
Mixiのようなコミュニティは一見ランダムなつながりだと思われるが、実は最近の研究では色々と特徴があることがわかっている。しかし、どうしてそのような特徴が現れるのかはまだ良くわかってない。
まずは自分の笠原数を計算してみて、グラフ理論そして複雑ネットワークの奥深さを実感して欲しい。

なお、参考書籍として増田 直紀氏らの「複雑ネットワークの科学」をお勧めしておく。

|

« [はてブ]SBMにおけるブックマーク「サゲ」攻撃の可能性 | トップページ | [Mixi]Mixiの参加者同士が繋がっている事の証明 »

パソコン・インターネット」カテゴリの記事

コメント

Nextさん:
実際そうなのですが、どのようにすれば計算量が小さくて笠原数が近似で出るのかが気になっています。

臥龍さん:
笠原数がわかれば、お互いの参加者同士のホップ数の上限が計算できます。

ただし、Mixiには孤立グラフがある場合が想定されるので、必ずしも笠原数が算出できるとは限らないと思います。
詳細は
http://toremoro.tea-nifty.com/tomos_hotline/2006/10/miximixi_75d3.html
をご覧下さい。

投稿: Tomo | 2006.10.01 23:42

始めまして、臥龍といいます。
「笠原数」面白いですね。

2人の人の「笠原数」が分かれば、まったく見ず知らずの人が何人のマイミクで繋がるのか分かるのでは・・・と思ったので

何人のマイミクでつながるかな
http://mixi.jp/view_community.pl?id=1381803

というコミュニティをmixiで作ってみました。

考え方としてはあってますでしょうか?

投稿: 臥龍 | 2006.10.01 15:30

mixiGraphを使えばいいだけの話では?
http://www.fmp.jp/~sugimoto/mixiGraph/

投稿: Next | 2006.10.01 14:03

Ryoさん:
コメントありがとうございます。
IDの小さい方を辿るというのはスマートなやり方ですね。実はマイミクの方もIDの一番小さい方を辿るのがいいのでは?といわれていました。

逆に、IDがある程度中途半端大きい人を辿るのは、やや難しいのでしょうね。

投稿: Tomo | 2006.10.01 08:29

http://mixi.jp/view_bbs.pl?id=10045128&comment_count=14&comm_id=41755
ここにある通り、マイミクの最後の人をたどっていくとだいたい笠原数が分かりますよ。

最適値である保証はありませんが。結構近いと思われます。

投稿: Ryo | 2006.10.01 00:56

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/12100761

この記事へのトラックバック一覧です: [Mixi]つながりを表す指標「笠原数」の提案:

» [J][NEWS][Mixi]つながりを表す指標「笠原数」の提案 [ジャンク☆ニュース 臥龍]
[Mixi]つながりを表す指標「笠原数」の提案 Tomo’s HotLine: [Mixi]つながりを表す指標「笠原数」の提案 mixiユーザーの方は 「全く知らない人同士は何人のマイミクで繋がるんだろう」 ・・・と思ったことはありませんか? 私もずっと疑問でした。6次の隔たりや小さな世界... [続きを読む]

受信: 2006.10.02 01:14

« [はてブ]SBMにおけるブックマーク「サゲ」攻撃の可能性 | トップページ | [Mixi]Mixiの参加者同士が繋がっている事の証明 »