« [Mixi]つながりを表す指標「笠原数」の提案 | トップページ | [はてブ]ブックマーク数をべき乗則と考える理由 »

2006.10.01

[Mixi]Mixiの参加者同士が繋がっている事の証明

先日、笠原社長とどの程度で繋がっているかを示す指標「笠原数」を提唱したが、そもそもすべての参加者が笠原社長と繋がっているのか自分で疑問に思った。そこで、今日はMixiの参加者同士が繋がっている事を証明する。(条件つき)

□条件
・参加者は誰かから招待される(一番最初に招待した人を除く)
・招待された人のIDよりも、招待した人のIDの方が小さい
・一番最初に招待する人はID=1の人
(あるいは最初に招待する人はID=1を含めて複数の人だが、必ずID=1とマイミクである)
・マイミクが0の人はMixiの利用ができなくなる(条件1)
・Mixiにおいて、参加者Pが招待者からマイミクをはずされてない事(条件2)または参加者Pが招待者からマイミクをはずされているが、PよりもIDが小さいマイミクが存在する場合(条件3)

次のようなアルゴリズムを考える
参加者AがID=1に辿りつくアルゴリズム

STEP☆
Aのマイミクの中で一番IDが小さく且つAよりもIDが小さい人をPとする
STEP★
Pが存在する場合⇒A=PとしてSTEP☆に戻る
Pが存在しない場合:AさんのID=1の場合:終了


証明:
マイミクの中には原則招待者がいる。つまり、Aさんのマイミクは(招待者からマイミクをはずされない限り)AさんよりIDが小さい人(Bさん)が存在する。また招待者からマイミクをはずされても条件3であれば、同様の議論ができる。今、Aさん⇒BさんのようにIDが一番小さいマイミクを辿るIDに対する関数をfとすると、fは単調減少である。fの下限はID=1であるから、上記アルゴリズムを行えばID=1の人に辿りつく。

これによって、ある制約下のおいて、Mixi参加者は全てID=1の参加者と繋がっている。
つまり、Mixiの参加者同士は必ず繋がっている事になる。

問題は招待者からマイミクをはずされたPさんで、マイミクのIDにおいて全てPよりも大きい場合が存在した場合である。

この場合は結論から言えば、先ほどのアルゴリズムを改良すれば、同様のアルゴリズムでID=1の人と辿れる(場合がある)。例えば、STEP★においてAさんのマイミクの中で複数マイミクを持っていて且つその中でIDが一番小さい人がPさんとなるのが妥当である。本当のSTEP★の処理はもっとややこしいが。

Mixiで孤立するグラフが現れるのはどういう場合だろうか?例を挙げてみよう。
今、AさんとBさんとCさんがいる。AさんはBさんを招待し、BさんはCさんを招待する。ここで、AさんはBさんとのマイミクを止め、且つBさんとCさんは他に招待しない等の場合が考えられる。かなりのレアケースだし、このようなことがMixiで認められているかどうかは私は知らない。

招待者からマイミクをはずされた人が存在した場合のグラフは、一般に複雑になる。場合分けも非常に複雑だろう。本当はMixiの参加者同士が必ず繋がっている事の証明を書きたかったのだが、これについてはきちんとした考察が必要だろう。今問題なのは条件2、条件3をより弱い条件にすることだ。皆様の考察求む!

|

« [Mixi]つながりを表す指標「笠原数」の提案 | トップページ | [はてブ]ブックマーク数をべき乗則と考える理由 »

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

コメント

> Mixiで孤立するグラフが現れるのはどういう場合だろうか?例を挙げてみよう。
> 今、AさんとBさんとCさんがいる。AさんはBさんを招待し、BさんはCさんを招待する

ここで、Aさんが退会すると、孤立グラフになります。SPAM送信ユーザーにかなりこういうのがいます。
なので、必ずしも、ID小さいのをたどっていったからといって、ID=1にたどり着けるわけではないですよ。

投稿: yu | 2006.10.02 18:06

条件として
条件4
参加者Pが招待者からマイミクをはずされているが、PよりもIDが大きいマイミクQがいて、且つそのマイミクQの中に参加者PよりIDが小さいマイミクRが存在する

条件4'(条件4の一般拡張)
参加者Pが招待者からマイミクをはずされているが、PからN次のマイミクQがいて、そのマイミクQの中に参加者PよりIDが小さいマイミクRが存在する

となると、大分条件が緩やかになることがわかりました。

投稿: Tomo | 2006.10.02 00:38

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: [Mixi]Mixiの参加者同士が繋がっている事の証明:

« [Mixi]つながりを表す指標「笠原数」の提案 | トップページ | [はてブ]ブックマーク数をべき乗則と考える理由 »