« 2006年9月 | トップページ | 2006年11月 »

2006年10月の6件の投稿

2006.10.29

[P2P]SkipGraphを利用した部分一致検索の提案

□はじめに
最近Structured P2Pの一種であるSkipGraphが注目されている。SkipGraphの特徴の一つとして、ある範囲のNodeIDを保有するノードに対して一斉に各種クエリーを届ける事が出来る事が挙げられる。

SkipGraphのわかりやすい解説は後日として、今回はこのSkipGraphの特徴を利用した部分一致検索を提案する。

□定義
今ハッシュ空間をXとし、ハッシュ空間のノルム(大きさ)を|X|としよう。Xを出力するハッシュ関数をHash()とする。
Xにおいて、prefix1()、prefix2(),prefix3(),prefix4()を定義する。これはp=|X|/4の桁に対して、
prefix1(A)=Aの上位p桁を抽出する関数
prefix2(A)=Aの上位p+1~2p桁を抽出する関数
prefixn(A)=Aの上位(n-1)p+1~np桁を抽出する関数

とする。なお、|prefixn(A)|=|X|/4であることに注意。いま、prefixn(A)が覆う空間をX(n)として、そのハッシュ関数をhash(X(n))とする。
また、A=sum(prefix1(A),prefix2(A),prefix3(A),prefix4(A))となるsum関数を定義する。

□部分一致検索の方法

☆Skipgraphへの情報P登録

ある情報PをSkipgrapghに登録するために、まず、Pを形態素解析で単語pに分解し、更にハッシュ関数hash(p))を掛ける。

今、Pに含まれる単語が4つしかないとすると、p={p1,p2,p3,p4}となる。
ここで、p(n)=hash(pn)とする、更にp(n)の大きさ順にpをソートする。例えばp1>p2>p3>p4としよう。
次にRの計算をする。
R1=sum(p(1),p(2),p(3),p(4))
R2=sum(p(2),p(1),p(3),p(4))
R3=sum(p(3),p(1),p(2),p(4))
R4=sum(p(4),p(1),p(2),p(3))

Rnにおいて、sum(pn,pnを含まない残りの元でp(n)の大きい順にソート)となる。
Pについては、NodeID=Rnとなるノードに格納することになる。

☆情報Pの検索

今、Pを構成する単語Sがあった場合、Pは見つけられるのだろうか?答えはYesである。
まず、s=hash(S)とする。
この際、Skipgraphを使ってsum(s+1,0,0,0)>NodeID≧sum(s,0,0,0)となるノードに検索クエリをPush型でマルチキャストすれば良い。

では、単語S,TのAND検索はどうすればよいか?
この時には
[手順1]s=hash(S)、t=hash(T)を計算する。
[手順2]t>sの場合、Skipnetを使ってsum(s+1,0,0,0)>NodeID≧sum(s,t,0,0)となるノードに検索クエリをPush型でマルチキャストすれば良い。

更に複数単語のAND検索も同様である。

prefixnにおいてn=4としたが、nを大きくすると検索計算量と情報登録するための処理数が大きくなる。nをどの程度にするかはAND検索の頻度や単語数を考慮する必要があるだろう。

□終わりに
部分一致検索をSkipgraphを利用して解決した。Skipgraphの特徴であるPush型マルチキャストを利用してたP2Pシステムは今後増えるだろう。

| | コメント (0) | トラックバック (0)

2006.10.07

[Mixi]IDを利用したマーケティング戦略の提案

□はじめに
Mixiの参加者数が数100万人規模になり、大学生の多くはMixiを使ってコミュニケーションしているとも言われている。つまり、若い世代はもはやMixiはコミュニケーションツールの一部となっている。

ここでMixiのIDについて説明しよう。MixiのIDは参加した順番に番号が振られている。つまり、IDが小さいほど参加した時期が早い事になる。

□IDが小さいほど「有利」なわけ

私がMixiに入ったときには、まだ2万程度のコミュニティだった。このとき今のような盛り上がりを予言していた人は少なかったのではないだろうか?Mixiでコミュニケーションできる人も限られていたし、掲示板も盛り上がりにかけていた時があった。今とは大違いの時代である。

ところで、IDが小さいとどういう特徴を持つだろうか?一旦整理してみよう。

[特徴1]イノベーターやアーリーアダプターが多い。
これは、新しいものや面白そうなものにイノベーターやアーリーアダプタが早くから飛びつくから当然の結果である。または、イノベーターやアーリーアダプタと密接な関係の知人も含まれる

[特徴2]オピニオンリーダーが多い
イノベーターやアーリーアダプターはBlog等を使って情報発信をする人が多い。つまり、オピニオンリーダーが数多く含まれている。

[特徴3]メジャーなMixi掲示板の管理人である場合がある
これはMixiの掲示板が早いもの順で設置できることと同じである。大抵のメジャーな掲示板は数万人規模のコミュニティになった際に設置される場合が多いと考えられる。また掲示板管理人ということは特徴2と絡み、オピニオンリーダーでもある

[特徴4]アンテナが高い人が多い
これは特徴1からの結果であるが、最新情報に対して非常に敏感な人が多い。

[特徴5]ハブとなる人が多い
IDが小さい人は単なるイノベーター、アーリーアダプタだけでなくハブとなる場合が多い。これは、Mixiという「人」と「人」を結びつける興味を持った人が参加したからだろう。単なる技術ウォッチャーは当時のMixiには興味をあまり示さなかったのだろう。

まとめると、IDが小さい人は最新動向に敏感で、情報発信も積極的に行い、リアルなコミュニケーションの能力の高い人が多いと言える。

□IDが小さい人に対するマーケティング的な魅力

このようなIDを持った人はマーケティング的には非常に魅力である。マーケティング的にはCMを使った手法が盛んであるが、最近非常注目されているのは、口コミ効果による宣伝である。
これをバイラルマーケティングと呼ぶ。SNS自体が「人と人」をつなげるシステムであるから、バイラルマーケティングにはうってつけの媒体である。

このバイラルマーケティングは、製品を広告(というよりも評価)するオピニオンリーダーの存在が重要である。このオピニオンリーダーの評価を元に、他の人は製品の良し悪しを決定する大きな力を持っている。
つまり、MixiIDが小さい人をうまく取り込むことによって、バイラルマーケティングを成功させることができる。

このバイラルマーケティングは大きな投資が必要ないだろう。IDが小さい人の中で製品に興味がある人、Mixiの管理人等をチョイスしてもらって、ユーザに製品を無料で提供あるいは評価に対するインセンティブを与える。このときにメーカーは客観的に製品を評価してもらうように注意する事が必要だ。彼らはアンテナが高く、意図的に好評価を与えようとすると逆効果となる。また、例えユーザがあまりよくない評価をしたとしても、それは有効な情報である。なぜなら製品の改良にフィードバックすればよいのだから。

□Mixiの掲示板とのタイアップ効果

もう一つ、バイラルマーケティングで廉価且つ効果が高い方法を提案しよう。それは掲示板とタイアップすることだ。私はグルメ系の掲示板を持っていて、お店のオーナーと色々とコンタクトをしている機会があるだが、お店側もMixiに対する潜在的な口コミ広告効果の魅力を感じているようだ。あるときにオーナーには、
「Mixiの掲示板ユーザには○○引きなどの特典をつけるといいですよ」
とアドバイスを与えた事がある。

このようにすれば、お店側はぐるなびなどに高い広告費用を払わなくても、大きな宣伝効果を与える事になる。もっともオーナー側は
・掲示板のユーザ層
・掲示板ユーザ層のニーズ
・掲示板のユーザ数
を的確に把握する必要があるし、それをもとに一番コストパフォーマンスに優れた特典を考える必要がある。

□終わりに
MixiのようなSNSではバイラルマーケティング戦略がうまくマッチする。特にIDが参加者順ということを考慮すると、
イノベーター、アーリーアダプター、アーリーマジョリティがうまく分類できることもとても魅力的なシステムだ。これを活用させない手はない。

ただ、このようなIDにおけるマーケティング手法は、ユーザIDによる格差を生む事も確かである。この辺りも慎重に議論する必要があるだろう。IDが大きいと「時代に遅れている」といわれる日が来るのだろうか?

| | コメント (1) | トラックバック (0)

2006.10.06

[DHT]第2回DHT勉強会議事録について

先月行われた第2回DHT勉強会は非常に活発な議論が行われ、とても盛り上がりました。
この度、無印吉澤さんが議事録の公開をしましたので、是非ともDHT勉強会の復習にご覧下さい。
出席されなかった方も、当日の雰囲気が味わえるはずです。

とても詳細な議事録となっています。

無印吉澤:第2回DHT勉強会議事録

| | コメント (0) | トラックバック (0)

2006.10.05

[はてブ]はてなブックマークカウンターを設置しました!

10/4にリリースされた「はてなブックマークカウンター」を早速使用してみました。

★はてなブックマークカウンターとは?★

はてなブックマークカウンタは任意の"ウェブサイト全体"の被ブックマーク数をカウンター画像として表示する機能です。(なお、"特定の記事"の被ブックマーク数もまた別の方法で表示することができます。)
詳しくはhttp://hatena.g.hatena.ne.jp/hatenabookmark/20061004/1159941842またはhttp://b.hatena.ne.jp/help/countをご覧下さい。

Tomo's Hotlineのタイトルの下にある、[B]マークの横にある数字が、Tomo's holtine全体においてブックマークされている総数を表します。もう750もブックマークされているのですね!ありがたいことです。

なお、この[B]マークをクリックすると、Tomo's Hotlineの注目のエントリーが簡単にみることができます。

この「はてなブックマークカウンター」は簡単にBlogやWebサイトに設置することができます。皆様も是非設置しましょう!

| | コメント (0) | トラックバック (0)

2006.10.03

[はてブ]ブックマーク数をべき乗則と考える理由

□はじめに

複雑ネットワークの研究が進み、べき乗則に対して関心が集まっている。色々な社会現象でべき乗則にしたがっていることが発見されているが、私は恐らくはてブのブックマーク数もべき乗則に従っていると考えている。今日はその理由を書いてみたい。
参考:
べき乗則:はてなダイアリー

□バラバシ=アルバートのネットワーク
複雑ネットワーク系で注目されている一つがバラバシ=アルバートネットワーク(BAネットワークと呼ぶ事にする)である。これは、リンクが多いノードほど、新たに参加するノードはリンクをしやすいと仮定してネットワークを作った例である。詳細は下記を参照。
http://f39.aaa.livedoor.jp/~hukuryu/barabasialbert.html

このBAネットワークのリンク数はべき乗則に従う事が知られている。

このネットワークモデルを見ると、あるリンクを持つ強者に対して、更リンクを強化するように外部作用が働くときに、リンク数がべき乗則に従うだろう、というアナロジーが頭に浮かぶ。(仮定1)
このような仮定が一般的に証明されるのは難しいと思われるが、BAネットワークのようにあるモデルを作れば個々には証明できるだろう。

□ブックマーク数が多いほどブックマークがされやすい理由

さて、はてブの話に戻そう。今、はてブのブックマーク数がべき乗則に従うという結論に導くには仮定1を使い、はてブのブックマーク数が多いほどブックマークがされやすい事を言えれば良い。

ところで、はてブには、記事がリリースされてブックマークする際のフェイズが3つあると考えられる。

□ブックマーク数が2以下のとき[フェーズ1]
このときにはタグサーチ等をしない限り、はてブユーザはブックマークに気づかない
□注目のエントリーに掲載される[フェーズ2]
注目フェーズに掲載され、ある程度のはてブユーザが目にする事ができる
□最近の人気エントリーに掲載される[フェーズ3]
一般にフェーズ2よりもトップページに滞留する時間が長い。フェーズ2よりもはてブユーザが目にする確率が高くなる

つまり、フェーズが大きくなるほどはてブユーザの目にさらされる時間が長くなり、そのため結果的にはブックマークされやすくなる事がわかる。

もう一つここで注意しないと行けないのが、フェーズ2にしろフェーズ3にしろ、ブックマーク数が多いという事実にがあれば、はてブユーザは記事を「読んでみたい」と思う事である。

その理由として

[心理状態1]ブックマーク数が多いから、この記事は面白そうだ。
[心理状態2]ブックマーク数が多いという事は、多くの人が記事読んでいる事。流行に乗り遅れないように読まないと。

とユーザが感じるのではないのかと私は分析する。特に心理状態2については、他人の行動や外的変化に敏感な人がなりやすい(特にイノベーターに多いと思われる)心理状態だろう。

結論として、最近の人気のエントリーの中にあっても、よりブックマーク数が多い記事ほどブックマークがされやすくなる可能性がある。

もちろん、はてブのトップページを見ずに、記事を直接読んで(RSSリーダーやブラウザのブックマーク等)はてブのブックマークをする人もいるが、数100ブックマークに達すには、やはりはてブの人気エントリーの表示効果がとても大きいと私は思う。

□終わりに

今回ははてブのブックマーク数がべき乗則に従っていると考える理由を説明した。BAネットワークを変形したはてブユーザの行動モデルを作れば、恐らく数学的にはべき乗則に従うことだろう。また理論だけでなく、実際にはてブブックマーク数がべき乗則に従うかどうかも測定する必要があるだろう。

注意しないといけないのは、仮に現在べき乗則に従っていたとしても、そのような自体が今後も続くかという事である。現在のはてブのユーザ層(イノベーターやアーリーアダプタ)からメインユーザ層がアーリマジョリティにシフトしてもべき乗則になるのか、私はとても興味がある。恐らく行動モデルに変形が加えられ、べき乗則から外れていくのではないかと私は推測している。

*追記:はてブ開始当初はべき乗則に従っていたようです。
はてなブックマークは今何件?

| | コメント (0) | トラックバック (1)

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をより弱い条件にすることだ。皆様の考察求む!

| | コメント (2) | トラックバック (0)

« 2006年9月 | トップページ | 2006年11月 »