DEIM Forum 2016 G6-2
Twitter におけるアーリーアダプター推定手法の評価
今森 大地
†田島 敬史
††
京都大学大学院情報学研究科
〒 606–8501 京都府京都市左京区吉田本町
E-mail:
†
[email protected],
††
[email protected]
あらまし
Web では日々新しい話題が生まれ，その話題に関する情報を発信する情報源も新たに出現し続けている．
また，既知の話題に対してさえ新しい情報源が出現する．このような現状で，我々が情報を探すときに，新規情報源
を無視することはできない．しかし一方で，出現から時間が経過して評価が定まった情報源に比べて，新規情報源の
中から良いものを探すのは難しい．そこで我々は他者に先駆けて優良な情報源を発見する能力に優れたユーザ，すな
わちアーリーアダプターに注目し，新規情報源の優良さを推定する手法を提案する．我々は以前にフォローの模倣に
注目してアーリーアダプターを推定する手法を提案した．加えて，本研究ではフォロー順序に注目した新たな手法を
提案し，その二つの手法と各種ベースラインを用いて比較実験を行った．
キーワード
アーリーアダプター, ソーシャルネットワーク, マイクロブログ, リンク伝搬, 新規情報源, リンク予測,
リンク推薦, グラフ分析, 影響力
1.
は じ め に
SNSやマイクロブログなどのソーシャルメディアでは，一 般の人々を含む非常に多くのユーザが情報源となって情報を発 信することができるようになった．情報源の増加に伴い，そこ で発信される情報の話題も豊富になり，その移り変わりも激し くなっている．加えて，近年では，TwitterやFacebookなど のソーシャルメディアにおいて，情報源となるユーザ数が日々 増加している．例えば，Twitterでは，2015年10月平均で月 間3億2000万人のユーザがいると発表されている（注1）．特に Twitterなどのマイクロブログは，Facebookのような社会的繋 がりと関係の深いソーシャルメディアと比べると，より変化の 激しいメディアである．そして，このように多様な話題が移り 変わり，日々新しい情報源が出現するマイクロブログにおいて， 多くのユーザからフォローされる人気の情報源も次々と新しく 登場する．日々新しく出現する将来人気がでるだろうアカウン トを早期発見することは，バイラルマーケティングやトレンド 抽出といった応用面で重要である．加えて，人気のある情報源 というのは多くのユーザから支持されているということであり， 人気のある情報源が発信する情報の質は高い傾向にある．つま り，情報源の人気度というのは，発信される情報の質を近似す るのに有効な指標であると考えられる．Webページにおける情 報源の質を推定する手法としてはPageRank [9]やHTIS [5]の 成功が知られている．また，マイクロブログへの同様の試みと して，TwitterRank [12]がある．これらの手法は情報源への参 照者がもつ性質とその数に注目し，そこから情報源の価値を推 し量る手法である． しかし一方で，新規情報源は新しいがゆえに，発信する情報 （注1）：http://files.shareholder.com/downloads/AMDA-2F526X/ 1430844265x0x856826/E036FA55-51C4-4F04-91C3-DDE9B94DAA08/ 2015 Q3 Earnings press release.pdfの質に見合っただけの被参照数を得ることができておらず，そ の時点での参照者の数や参照者の性質によって情報源の将来獲 得する人気度を推定することは難しい問題である． 本研究では，Twitter上で新規情報源の将来の人気度を予測 する手法を提案する．新規情報源の将来の人気度を推定するた めに，PageRank [9]やHITS [5]と同様にその時点でのフォロ ワーの数やフォロワーの性質を用いる． 既存手法と違うのは，“そのフォロワーにフォローされている ということは，その情報源のフォロワー数が今後増えることが 期待される”というフォロワーの性質に注目する点である．こ のような性質をもつユーザを本研究ではアーリーアダプターと 呼ぶ．別の言い方をすると，アーリーアダプターとは，将来人 気となる情報源を早く発見する能力を持つユーザのことである． また，アーリーアダプターの性質を説明するための重要な概念 としてフォローの模倣がある．フォローの模倣とは，あるユー ザが他のユーザのフォローを参考にして，自身もおなじ情報源 に対して参照を張る行為を意味する． 我々は以前に，フォローを模倣されることが多いユーザは アーリーアダプターである，という仮定のもと，triadと呼ば れる“フォローによって形作られる三角形”によってフォロー の模倣を発見することでアーリーアダプターを見つける手法[1] を提案した．その手法では，将来人気がでる情報源の早期発見 において，順位相関値による評価ではベースラインよりも高い 精度を示すことがわかっている．一方で，順位相関値の絶対値 は提案手法を含めたすべての手法でたかだか中程度の相関を示 すにとどまっている．加えて，nDCG [4]を評価尺度とした場 合の実験では，ベースラインの方が高い精度を示した． そこで，本研究では，アーリーアダプターを発見するための 別のアプローチを提案する．本アプローチでは，ある情報源 のフォロワーの中で，その情報源を何番目にフォローしたのか というフォローの順序に注目し，その情報源をいち早くにフォ ローしているフォロワーに対して高いスコアを与える．また，
このスコアは対象の情報源のフォロワー数が多いほど高くなる． つまり，フォロワー数が多い情報源を早くにフォローしていた ユーザのスコアが高くなるようにスコアを定義する．本研究で はこのスコアをアーリーアダプタースコアと呼び，アーリーア ダプタースコアが高いユーザがアーリーアダプターとなる．こ のように，各ユーザのアーリーアダプタースコアを推定するこ とでアーリーアダプターを発見することができるようになるが， 一方で，どのような関数に基づいてスコア付けをするべきかは 自明ではないという問題がある．そこで，スコア付けの関数を 構成するために再びフォローの模倣の概念を用いる．4. 2節で は，フォローの模倣に基づいて計算されたスコアが，アーリー アダプターの性質をうまく表現していることを示す． 提案手法を用いて将来人気がでる情報源を早期発見すること は，バイラルマーケティングやトレンド抽出といった応用面で 有用であると考えられる．また，今後人気がでる新規ユーザは その後たくさんのフォロワーを持つ可能性があることから，リ ンク予測に用いることも可能である． 提案手法を評価するために，実際のTwitter上のデータを用 いて実験を行った．この実験に用いるTwitter のグラフデー
タは我々が新たに2015年に Twitter REST APIを用いて収
集したものである．このグラフデータには日本語を使用言語と して設定している大部分のアカウントが含まれる．実験では， グラフデータが収集された時点での新しいユーザを抽出し，そ れらがクロール後数十日でどれだけ人気になったかを推定し た．提案手法とベースラインによって将来の人気のランキング を作成し，そのランキングの精度をスピアマンの順位相関係数 とnDCG [4]を用いて評価した．その結果，我々が以前に提案 した手法は多くの場合でベースラインを上回る精度を示した． そして，今回提案する手法では，従来の手法が苦手としていた nDCGでベースラインを上回る精度を示した．一方で，提案手 法は作成から四週間ほど経った新規情報源のその後の人気の推 定を得意としていることもわかった．すなわち，提案手法では， 作成から時間が経ってその新規情報源の将来の人気を推定する ために必要な情報が蓄積されるのを待つ必要がある． 以下，2章でまず関連研究について述べ，続いて3章でアー リーアダプタースコアから新規情報源の将来の人気度を推定方 法を述べる．4章では，アーリーアダプタースコアを推定する 手法について述べる．5章では実験に用いるデータとベースラ インを紹介し，実験結果を示す．最後に6章では，まとめと今 後の課題を述べる．
2.
関 連 研 究
ソーシャルネットワーク上でのユーザの振る舞いを考える際 に，人間の社会的振る舞いを無視することはできない．社会学 では古くから人間の社会的振る舞いについて研究されてきた． また，このような社会的振る舞いがWeb上のソーシャルネット ワークにも現れることを示す研究もされてきた[2], [3], [8], [11]． その中に，triadic closureという三角形にもとづいて人間の繋 がりを説明しようとする研究がある[10]．triadic closureが表 す関係は，ソーシャルネットワーク上の参照関係を分析する上 でも重要なものである．我々はこれまでにこの関係を基礎とし て，フォローの模倣を推定し，アーリーアダプターを発見する 手法を提案した[1]． ソーシャルネットワーク上での影響力についても多くの研究 がされている．本論文では，参照関係の模倣，すなわち参照関 係に関する影響力に注目するが，従来から，情報発信に関する 影響力についての研究は多くされてきた．情報発信に関して影 響力の大きいユーザは，情報源として有益であることが多い． また，影響力のあるユーザは発信した情報が多くの他ユーザに 伝わるため，マーケティングの観点からも有用である．これら のことから，情報発信に関して影響力の高いユーザを推定でき れば，ユーザ推薦への利用や効率的なマーケティングに活用す ることができる．Kwakら[6]は，Twitter上のユーザに対し て，PageRank，フォロワーの数，リツイートされた数によって ランク付けされた3つのランキングを比較することで，フォロ ワーの数とツイートの人気の間に差があることを示し，フォロ ワーの数だけが影響力ではないことを示唆した．また，Weng ら[12]は，フォロワーの数だけでなく，ユーザが関心を持って いる話題や実際にツイートが読まれるであろう確率を考慮して ユーザの影響力を推定するTwitterRankを提案している．こ のように情報発信に関する影響力を推定する研究は多く存在す る．しかし，これらの手法は，まだ十分にフォロワー数が増加 していない新規情報源の将来の人気を測定するという用途には 向いていないと思われる．このことから，本論文の目的である， 将来の人気予測に用いることは難しいと考えられる． ソーシャルネットワーク上のリンク予測に関しても研究が行 われている．Liben-Nowellら[7]は，リンク予測を定式化し， ネットワーク上のノードの近さを尺度としたリンク予測を提案 している．Zhangら[13]は，リンク形成における仲介者に注目 し，リンク形成に関して各ノードがどの程度仲介者として機能 するかを確率モデルを用いて推定することで，どのノード間に リンクが形成される可能性が高いかを予測する手法を提案して いる．3.
フューチャーポピュラリティースコア
本節では，新規情報源の将来の人気を推定する方法を提案す る．まずはじめに本研究で用いる記号の定義を行う．その後， アーリーアダプターとアーリーアダプタースコアについて説明 を行う．次に，アーリーアダプタースコアから 新規情報源の将 来の人気を表す指標であるフューチャーポピュラリティースコ アを計算する方法を述べる．本節の最後に，我々が以前に提案 したtriadに基づいたアーリーアダプター推定の方法とその評 価を示す． 3. 1 記号の定義 D(V, E)をTwitterユーザ間のフォローによる有向グラフと する．V はノードの集合であり，すべてのユーザを表す．Eは辺 の集合であり，各辺hu, viはユーザuのユーザvへのフォローを 表す．u∈ V に対して，F riends(u)はuのフレンド集合,すな わち情報源集合を表す．u∈ V に対して，F ollowers(u)はuの フォロワー集合．また，F ollowersnr(u)はuを一方的にフォローしており，uからはフォローされていないようなuの非相互フォ
ロワー集合を表し，同様にF riendsnr(u)はuに一方的にフォ
ローされており，uをフォローしていないようなuの非相互フレ
ンド集合を表す．F ollowOrders(u)は，uがsをF ollowers(s)
の 中 で 何 番 目 に フォロ ー し た の か を 表 す．す な わ ち ，1 <=
F ollowOrders(u) <= |F olowers(s)|, F ollowOrders(u)∈ Nと
なる． 3. 2 アーリーアダプタースコア 本節ではアーリーアダプタースコアの説明を行うが，そのた めの準備として，まずはアーリーアダプターとフォローの模倣 について言及する． 3. 2. 1 アーリーアダプター アーリーアダプターとは人気のある情報源すなわちフォロ ワー数の多い情報源をいち早くフォローしている能力のある ユーザである，と定義する．アーリーアダプターは既に人気の ある情報源を他ユーザに先駆けてフォローしており，また，将 来人気になる新規情報源をもフォローする． 次にアーリーアダプターの性質を説明する重要な概念として フォローの模倣がある． 3. 2. 2 フォローの模倣 あるユーザは情報源をフォローする際に，他ユーザがフォロー している情報源を真似してフォローすることがある．このよう な活動をフォローの模倣と呼ぶ．本研究では，他者より人気情 報源を早くフォローするという性質からアーリーアダプターは 他者にフォローをよく模倣され，また，フォローをよく模倣さ れるユーザはアーリーアダプターであると仮定する．よって， 今後フォローの模倣という概念がアーリーアダプターを推定す る上で重要な要因となる．一方で，我々が以前に提案したtriad によってフォローの模倣を発見する手法と，今回新たに提案す るフォロー順序に注目した手法では，フォローの模倣の定義が 異なることに注意したい．前者の定義は4.章の定義2で，後者 の定義は定義5で示している． アーリーアダプタースコアは，各ユーザがどの程度アーリー アダプターとしての性質を持っているかを判断するための指標 として定義される．提案手法でアーリーアダプタースコアをど のように定義するかの詳細は4. 2節で述べる．また，先に述べ たようにアーリーアダプターはその性質から，フォローの模倣 と重要な関係にあるが，実際に我々の以前の研究[1]や，本研 究ではフォローの模倣を用いてアーリーアダプタースコアを計 算するような定義を用いている．今後，ユーザu∈ V のアー リーアダプタースコアをE(u)と記述する． 3. 3 フューチャーポピュラリティースコアとは 本節では，アーリーアダプタースコアを用いてフューチャー ポピュラリティースコアを定義する． 定義1. ユーザu∈ V のフューチャーポピュラリティースコア Ft(u)は以下のように定義される． Ft(u) = X v∈F ollowers(u) E(v) (1) ユーザu ∈ V のフューチャーポピュラリティースコアは，u
u
w
v
u, v
v, w
u, w
図 1 triad のフォロワーv∈ F ollowers(u)のアーリーアダプタースコア E(v)を足し合わせることで定義される． この定義は，アーリーアダプタースコアの高いユーザに多く 参照される情報源は，将来人気になる可能性が高いという仮定 に基づいて行われている．アーリーアダプタースコアを適切に 定義することで，このフューチャーポピュラリティースコアの 定義は妥当なものとなる． 以上の議論から，アーリーアダプタースコアを適切に定義す ることで，フューチャーポピュラリティースコアを計算できる ようになった．そこで，本研究でのアーリーアダプタースコア の定義を示す前に，我々の以前の研究[1]においてどのように アーリーアダプタースコアを定義し，どのような性能を示した かを述べる．4.
アーリーアダプタースコアの推定
本章では，以前に我々が提案したtriadと呼ばれるフォロー 関係による三角形に注目したアーリーアダプタースコア推定手 法の紹介に加えて，新たにフォロー順序に注目した手法を提案 する．アーリーアダプタースコアを推定することが出来れば， 3章で述べたように，フューチャーポピュラリティースコアを 計算することができる． 4. 1 Triad に基づいた手法 本節では，我々が以前に提案したtriadと呼ばれるフォロー 関係による三角形に注目した手法[1]について説明する．triad とは，図1に示したような三角形である．この手法では，フォ ローの模倣を以下のように定義する． 定義 2. あるユーザu, v∈ V において，uがvのフォローを 模倣するというのは，vのフォローしている情報源すなわち F riends(v)を参考に，uもw∈ F riends(u)をフォローする という行為を意味する．また，あるユーザuを模倣するのはu のフォロワーF ollowers(u)のみであると仮定する． そして，triadが存在すると，上記のようなフォローの模倣 が行われた可能性が存在する．そこで，グラフ上からtriadを 数え上げることで，フォローの模倣が起こった回数を推定する ことができる． あるユーザのアーリーアダプタースコアを以下のように被模 倣数を用いて定義する． 定義3. v∈ V のアーリーアダプタースコアEt(v)は，以下によって定義される．
Et(v) = |Copy(v)|
|F ollowers(v)| × |F riends(v)| (2)
ここで，vを模倣することによって形成されたフォローの集
合をCopy(v)とする．すなわち，hu, wi ∈ Copy(v)におい
て，uはvのフォローhv, wiを模倣することで，hu, wiを形
成したということを示している．また，Copy(v)の定義より，
Copy (v )⊂=Friends(v )×Followers(v)となる．この式の分子は，
uが自身のフォローを他ユーザから模倣された回数であり，分 母はvが自身のフォローを模倣される機会の回数を表している． ただし，分母が0になる場合は，Et(v) = 0とする．Et(v)は vが自身のフォローを模倣された割合であると考えられる． 以上の定義において，実際のソーシャルグラフ上からCopy(v) を直接得ることはできない．そこで我々はソーシャルグラフ上 からtriadのような構造の特徴を発見し，フォローの模倣が行 われた痕跡を見つけることで|Copy(v)|を推定する方法を提案 している[1]． 4. 2 フォロー順序に基づいた手法 本節では，フォロー順序に基づいたアーリーアダプタースコ アを導入することでアーリーアダプターを推定する方法を提案 する．3.節で述べたように，アーリーアダプターとは，人気情 報源すなわちフォロワー数の多い情報源をいち早く見つける能 力をもつユーザのことである．そこで，アーリーアダプターを 発見するために，各ユーザの“フォロワー数の多い情報源をい ち早く見つけた実績”を求め，それをアーリーアダプタースコ アとすることを考える．すなわち，フォロワー数の多い情報源 を早くにフォローしていたユーザに高いスコアが与えられるよ うにアーリーアダプタースコアを定義する．ある情報源sの フォロワー数をn =|F ollowers(s)|とし，sをi(1 <= i <= n)番 目にフォローしたフォロワーをfisとする．f s i に与えられるス コアは，iを固定した場合はnが大きくなるに連れて大きくな り，nを固定した場合は，iが大きくなるに連れて小さくなる ようにしたい．そこで，上記の性質を満たすようなアーリーア ダプタースコアを以下のように定義する． 定義 4. あるユーザv∈ V のアーリーアダプタースコアE(v) を以下のように定義する． E(v) = P
s∈F riends(v)a(|F ollowers(s)|, F ollowOrders(v))
|Friends(v)| (3) ただし，a(n, i)は以下の様な性質をもつ． • nの増加関数 • iの減少関数 ここで，nが|F ollowers(s)|，iがF ollowOrders(v)に対応 する． 上記の定義では，a(n, i)を具体的にどのような関数として 定義するかは示しておらず，上記のような二つの性質をもつ a(n, i)は無数に考えられる．そこで，次節では，フォローの模 倣という概念を取り入れることでa(n, i)が与えられることを 示す． 4. 2. 1 フォローの模倣に基づくモデル 本提案手法では，フォローの模倣を以下のように定義する． 定義5. 情報源sをフォローしているユーザu∈ F ollowers(s) は，F ollowers(s)のなかで，自身より早くsをフォローしてい るユーザのどれかを真似してsをフォローすると考え，このよ うな活動をフォローの模倣と呼ぶ． ある情報源sのフォロワー集合F ollowers(s)にフォローの模 倣に基づいたスコアを与えることを考える．アーリーアダプター はその性質から，フォローを模倣される可能性が高い．そこで， フォローを模倣された数をスコアとして足しあわせて， アー リーアダプタースコアとして用いる事を考える．F ollwoers(s) の中でi番目にsをフォローしたユーザをfs i とすると，fisは fs 1, f2s, ..., fi−1s のどれかを模倣してsをフォローしたと考える． そこで，fiがf1s, f2s, ..., fi−1s に均等にスコアを分配する．この ようにスコアを配分すると，最終的に，各フォロワーが得るス コアの総和が被模倣回数の期待値となる．まずはじめに，各 fs k(1 <= k <= |F ollowers(s)|)がすべてに等しく1の価値を持っ ており，それを模倣した可能性があるユーザに均等に分配する という単純なモデルを考える． 定義6. フォロワー数nのある情報源sをi番目にフォローし たsのフォロワーfisのスコアa(n, i)を決定するための被模倣 数期待値モデルを以下のように定義する． • 各フォロワーfs k(1 <= k <= |F ollowers(s)|)はすべて等し く1の価値を持つ． • fs i はf1s...fis−1を等しく模倣した可能性があり，各々に 自身の持つ価値1を均等に分配する． • fs i が得るスコアas(fis)は，他のフォロワーから分配さ れたスコアの和である． 被模倣数期待値モデルを数式で表現すると，以下のように なる． a(n, i) = n X j=i+1 1 j− 1 (4)
n =|F ollowers(s)|, i = F ollowOrders(u)である．jはfis
よりも後にsをフォローした各ユーザのフォロー順を表してい る． 1 j−1はfjsがfisに与えるスコアを表している．また，この ように求められたスコアa(n, i)はnの増加関数であり，iの減 少関数であることから，定義4で述べた性質を満たすことがわ かる． 次に，重み付き被模倣数期待値モデルを提案する． 定義7. フォロワー数nのある情報源sをi番目にフォローし たsのフォロワーfisのスコアa(n, i)を決定するための重み付 き被模倣数期待値モデルを以下のように定義する． • 各フォロワーfs k(1 <= k <= |F ollowers(s)|)ははじめにス コアをもつ． • fs i はf1s...fis−1を等しく模倣した可能性があり，自身の 持つスコアas(fsk)を価値として，各々に均等に分配する． • fs i が得るスコアas(fis)は，はじめから与えられている スコアと他から得るスコアの総和である．
被模倣数期待値モデルとの違いは二点ある．一つ目は，各フォ ロワーがはじめから同じスコアを持っているという点で，も う一つは，自身が他ユーザから得たスコアを価値として，自身 が模倣した可能性のあるユーザに均等に分配する点である．た だし，自身が得たスコアを与えると言っても，自身のスコアが 減るわけではないことに注意したい． 重み付き被模倣数期待値モデルを数式で表現すると，以下の ようになる． 8 > > > > < > > > > : a(n, i) = n X j=i+1 a(n, j) j− 1 + (5) n X i=1 a(n, i) = n (6)
ここで，n =|F ollowers(s)|, i = F ollowOrders(u)である．
(6)において，総和をnとしているのは，各フォロワーに与 えられるスコアを情報源sのフォロワー数nに応じて変化させ るためである．すべてのフォロワーに等しく与えられるスコア であるが，これは，今後フォロワー数がnよりも増えた場合 に，増えたフォロワーから分配されるだろうスコアを表してい ると考えられる． 重み付き被模倣数期待値モデルによって得られるスコアa(n, i) が定義4で述べた性質を満たすことを示す．まず，(5)，(6)を 解くと一般項を計算することができ， a(n, i) =1 i n Hn , for (1 <= i <= n) (7) となる．ここで，Hnは一般に調和数と呼ばれ，Pni=11i のこと を表す． このように求められた重み付き被模倣数期待値モデルによる スコアa(n, i)が定義4における性質を満たすことを示す．そ のためには， n Hn がnの増加関数であることを示せば良い． n Hn <n + 1 Hn+1 ⇔ nHn+1< (n + 1)Hn ⇔ (n + 1)Hn− nHn+1> 0 (8) より，n/Hnの単調性を示すために (n + 1)Hn− nHn+1> 0 を示す．1 <= nにおいて， (n + 1)Hn− nHn+1 = (nHn+ Hn)− (nHn+ n· 1 n + 1) = Hn− n n + 1 = (1 1− 1 n + 1) + ( 1 2− 1 n + 1) +· · · + ( 1 n− 1 n + 1) > 0. (9) これより， n Hnは単調増加であり，そのことから(7)はnの 単調増加関数であることがわかった． 図 2 各点はターゲットとなる新規ユーザを表し，横軸はクロール開始 から何日後にクロールされたのか，縦軸はそのユーザが作成さ れてから何日後にクロールされたかを表している．赤線は一日 ごとの平均を示している．
5.
実
験
5. 1 実 験 結 果 本研究の評価実験を行うためのデータセットとして，日本語 を使用言語としているTwitter上のすべてのアカウントを含む ような大規模なグラフデータを用いる．グラフの詳細は以下の ようになっている． • フォロワー数・フレンド数ともに多いアカウント @Twit-terJPを基点にした幅優先探索でアカウントの言語設定が ja になっているものをたどり，到達可能なすべての言語設定がja のユーザを収集 • 収集したフォロー関係の内，言語設定がjaとなってい ないアカウントを含むものを除去． • ユーザ数|V | = 42, 867, 281 • フォロー関係数|E| = 4, 253, 181, 701 • クロール期間は2016年11月3日から2016年12月 10日． 5. 2 実験の詳細 （1） クロール開始から一ヶ月前以降に作成されたすべての新規 ユーザを実験のターゲットとし，これをT と記す．各々 のターゲットはcreated-crawledとcrawled-atという二つ のパラメータを持つ．created-crawledはそのターゲット ユーザが作成されてから何日後にクロールされたかを 表す．crawled-atはそのターゲットユーザがクロール開 始から何日後にクロールされたかを表す．そしてTba はcreated -crawled = aとcrawled -at = bをもつターゲット
集合を表す．例えば，T3014は作成から14日後，かつ，ク
ロール開始から30日後にクロールされた新規ユーザを表
がどのような関係にあるのかを示した．各点がターゲット を表し，横軸は各ユーザがクロール開始から何日後にク ロールされたのか，縦軸は作成から何日後にクロールされ たのかを表す．また，赤線は各日の平均を表す．T0-7は緑 色，T14は青色，T0-714 は黄色の長方形内のターゲットに対 応している． （2） このように抽出したターゲットから，情報源として使われ ているアカウントを特定するために，フレンド数/フォロ ワー数という比を使う．この比をff とする．Twitterの各 アカウントは大きくわけて，情報を発信する情報源アカウ ントと知り合いとのコミュニケーションや情報収集に使わ れる非情報源アカウントの二つがある．前者はff が小さ い傾向があるといえる．反対に，後者はそのフォロワーや フレンドに相互フォローが多い傾向にあり，ff が大きくな る．そこで，ターゲットユーザの中から情報源アカウント を選択するために，ff に上限をつける． （3） このように設定したターゲットについて提案手法とベース ラインを用いて将来の人気度を推定した． （4） 正しい将来の人気度とするために，各ターゲットの非相互 フォロワー増加数を2016年12月13日から毎日収集した． （5） 各種法で推定した将来の人気度によるランキングと，正解 となる将来の非相互フォロワー増加数によるランキングを 比較した．比較にはスピアマンの順位相関係数とnDCG を用いた．順位相関係数はランキングの全体の精度を評価 する尺度であり，nDCGはランキング上位の精度に重きを おいて評価する尺度である． 次に，実験に用いる提案手法，ベースラインの紹介をする． 5. 2. 1 提 案 手 法 • 被模倣数期待値モデルに基づく提案手法,定義6の被模 倣数期待値モデルに基づいてアーリーアダプタースコアを計算 し，そこからフューチャーポピュラリティースコアを求める手 法である．以下ではこの手法をF と記す． • 重み付き被模倣数期待値モデルに基づく手法,定義7の 重み付き被模倣数期待値モデルに基づいてアーリーアダプター スコアを計算し，そこからフューチャーポピュラリティースコ アを求める手法である．以下ではこの手法をFwと記す． • 被模倣数期待値モデルに基づく提案手法 + 非相互フォ ロー, F の計算を非相互フォローグラフ上で行ったもの．以下 ではこの手法をF (f )と記す． • 重み付き被模倣数期待値モデルに基づく手法 + 非相互 フォロー, Fwの計算を非相互フォローグラフ上で行ったもの． 以下ではこの手法をFw(f )と記す． • Triad に基づく手法,我々が以前に提案したtriadに基 づく手法で将来の人気度を推定する．この手法にも多くのバリ エーションが存在するが，ここで非相互フォローを考慮し，被 模倣率にアーリーアダプターのフォロワー数を乗算することで リンク伝播としてアーリーアダプタースコアを考える手法を採 用した．以下ではこの手法をFt(f )と記す． 5. 2. 2 ベースライン • フォロワー数,情報源の当時のフォロワー数を将来の人 気度を表す指標とみなす手法．以下では，F W と記す． • 非相互フォロワー数,情報源の当時の非相互フォロワー 数を将来の人気度を表す指標とみなす手法．以下では，F Wnr と記す． • フレンド数,情報源の当時のフレンド数を将来の人気度 を表す指標とみなす手法．以下では，F Rと記す． • 非相互フレンド数,情報源の当時の非相互フレンド数を 将来の人気度を表す指標とみなす手法．以下では，F Rnr と 記す． • PageRank, PageRankアルゴリズム[9]によって計算 された値を将来の人気度の指標とみなす手法．以下では，PR と記す． • 非相互PageRank,非相互フォローグラフ上で PageR-ankアルゴリズム[9]を用いて計算された情報源の将来の人気 度の指標とみなす手法．以下では，PRnr と記す． • HITS，HITSアルゴリズム[11]を用いて計算された オーソリティ度を情報源の将来の人気度の指標とみなす手法． 以下ではHITSと記す． • 非相互HITS，非相互フォローグラフ上でHITSアルゴ リズム[11]を用いて計算されたオーソリティ度を情報源の将来 の人気度の指標とみなす手法．以下ではHITSnr と記す． 本実験ではまず，Tn, n = 1, 7, 14, 28に対して各手法で将来 の人気度を推定し，それを正解であるm日後の非相互フォロ ワー増加数によるランキングと比較し評価した．評価にはスピ アマンの順位相関係数とnDCGを用いて評価を行った．表1は T14における将来の非相互フォロワー増加数と各種法との順位 相関値を示している．5日から35日先の予測に関してはFt(f ) が他手法よりも高い相関値を示している．一方で，40日から 50日先の予測では，P RやF Wがより高い値を得ている．こ の原因は図2によってより推測できる．図2においてT14は青 枠の長方形内のターゲット集合を表しているが，これらのター ゲットはcrawled-atが小さい集合と大きい集合の二つに分割さ れていることがわかる．そして，5日から30日先を予測する場 合には対象はcrawled-atが大きなターゲットだけだが，35日 から50日先の予測する場合にはcrawled-atが小さなターゲッ トそこに含まれる．このcrawled-atが小さなターゲット集合が 先程述べた変化の影響であると考えられる．次に，crawled-at の大小，すなわちクロールされたタイミングが早いか遅いかに よってターゲットとなるユーザにどのような性質の差があるか を考える．我々は早い段階にクロールされたターゲットは情報 発信型のユーザではなく，コミュニケーションを目的とした非 情報源アカウントであるものが多いと仮定する．この仮定は図 3によって支持される．この図は横軸がクロール開始から何日 後にクロールされたのかを表し，縦軸はフレンド数/フォロワー 数の比ff を表している．この仮定にもとづいて，我々はフレン ド数/フォロワー数の比によってターゲット集合を絞り込む．本 研究ではこの比をff と表記する．ff が大きいユーザは非情報
図 3 各点はターゲットとなる新規ユーザを表し，横軸はクロール開始 から何日後にクロールされたのか，縦軸はそのユーザのフレン ド数/フォロワー数の比を表している．赤線は一日ごとの平均を 示している． 表 1 T14における将来の非相互フォロワー増加数と各手法との順位 相関値
Target Data Set T14
days ahead 5 10 15 20 25 30 35 40 45 50 data size 11663 11663 11663 11663 11663 12945 15264 20815 20815 20815 FW 0.42 0.44 0.43 0.44 0.41 0.39 0.35 0.27 0.26 0.25 FWnr 0.44 0.44 0.42 0.42 0.37 0.34 0.24 0.09 0.08 0.07 FR 0.24 0.27 0.28 0.29 0.27 0.25 0.20 0.09 0.09 0.09 FRnr 0.20 0.23 0.23 0.24 0.21 0.16 0.08 -0.03 -0.04 -0.04 PR 0.25 0.28 0.29 0.29 0.28 0.29 0.30 0.30 0.30 0.29 PRnr 0.27 0.29 0.28 0.29 0.26 0.22 0.14 0.07 0.06 0.05 HITS 0.42 0.44 0.43 0.43 0.40 0.33 0.19 0.05 0.05 0.05 HITSnr 0.41 0.41 0.39 0.39 0.33 0.25 0.07 -0.07 -0.07 -0.07 F - 0.43 0.45 0.44 0.44 0.41 0.39 0.34 0.25 0.24 0.24 f 0.45 0.45 0.42 0.42 0.36 0.34 0.23 0.06 0.05 0.04 Fw o 0.43 0.45 0.44 0.44 0.41 0.39 0.34 0.24 0.24 0.23 f,o 0.45 0.45 0.43 0.43 0.37 0.34 0.24 0.07 0.06 0.05 Ft - 0.41 0.43 0.42 0.43 0.4 0.38 0.33 0.27 0.27 0.26 f 0.46 0.48 0.48 0.48 0.44 0.41 0.34 0.26 0.25 0.24 源アカウントであり，ff が小さいユーザは情報源アカウントで あるとする．本実験に際して，我々はff < 1.0という基準で， 情報源アカウントかどうかを判定する． Tn (ff < 1.0)に対して各手法で将来の人気度を推定し，そ れを正解であるn日後の非相互フォロワー増加数によるラ ンキングと比較し評価した．評価にはスピアマンの順位相関 係数とnDCG を用いて評価を行った．表2，3は，それぞれ T14 (ff < 1.0)，T28 (ff < 1.0)に対する順位相関の結果を示 している．この表から，作成から二週間の時点での推定では， Ft(f )が他の手法に比べて高い精度を示していることがわか る．一方，作成から四週間たったターゲットに対する推定で は，Fw(-)またはFw(f )が他の手法を上回る結果となっている． 表4，5は，それぞれT7 (ff < 1.0)，T28(ff < 1.0)に対する nDCG@kの結果を表している．表4を見ると，F , Fw, Ftが ほとんどの場合でベースラインを上回る数値を出している一方， 表 2 T14(ff < 1.0) における将来の非相互フォロワー増加数と各手 法との順位相関値
Target Data Set T14(ff < 1.0)
days ahead 5 10 15 20 25 30 35 40 45 50 data size 8076 8076 8076 8076 8076 8218 8644 9112 9112 9112 FW 0.34 0.36 0.36 0.36 0.36 0.36 0.33 0.28 0.28 0.26 FWnr 0.38 0.38 0.37 0.37 0.35 0.33 0.26 0.19 0.18 0.16 FR 0.20 0.23 0.24 0.24 0.26 0.26 0.24 0.20 0.21 0.20 FRnr 0.31 0.31 0.30 0.30 0.29 0.27 0.19 0.13 0.12 0.10 PR 0.19 0.21 0.22 0.22 0.24 0.25 0.26 0.26 0.26 0.26 PRnr 0.36 0.37 0.36 0.36 0.35 0.34 0.30 0.24 0.23 0.21 HITS 0.35 0.36 0.36 0.36 0.36 0.34 0.24 0.17 0.17 0.16 HITSnr 0.36 0.36 0.34 0.34 0.32 0.27 0.13 0.05 0.04 0.03 F - 0.36 0.38 0.37 0.37 0.37 0.37 0.33 0.28 0.28 0.27 f 0.39 0.39 0.37 0.37 0.35 0.34 0.26 0.19 0.17 0.15 Fw - 0.36 0.37 0.37 0.37 0.37 0.36 0.33 0.28 0.28 0.27 f 0.39 0.39 0.37 0.38 0.36 0.34 0.27 0.20 0.18 0.16 Ft - 0.33 0.35 0.36 0.36 0.36 0.36 0.33 0.28 0.28 0.27 f 0.40 0.42 0.42 0.42 0.41 0.41 0.36 0.30 0.30 0.28 表 3 T28(ff < 1.0) における将来の非相互フォロワー増加数と各手 法との順位相関値
Target Data Set T28(ff < 1.0)
days ahead 5 10 15 20 25 30 35 40 45 50 data size 5408 7856 9158 9293 9503 9785 10271 10964 10964 10964 FW 0.14 0.23 0.30 0.31 0.28 0.29 0.27 0.26 0.26 0.25 FWnr 0.22 0.28 0.33 0.32 0.31 0.30 0.25 0.23 0.22 0.21 FR -0.02 0.07 0.16 0.17 0.16 0.17 0.16 0.17 0.16 0.16 FRnr 0.14 0.20 0.25 0.24 0.24 0.22 0.18 0.16 0.15 0.14 PR 0.00 0.10 0.18 0.20 0.19 0.21 0.21 0.22 0.23 0.22 PRnr 0.21 0.26 0.31 0.31 0.31 0.30 0.26 0.25 0.24 0.23 HITS 0.17 0.20 0.26 0.25 0.21 0.20 0.16 0.16 0.15 0.15 HITSnr 0.19 0.24 0.27 0.26 0.24 0.21 0.15 0.14 0.13 0.12 F - 0.18 0.26 0.32 0.33 0.30 0.30 0.28 0.27 0.27 0.26 f 0.24 0.30 0.34 0.33 0.32 0.31 0.26 0.24 0.23 0.21 Fw - 0.18 0.26 0.33 0.33 0.30 0.31 0.29 0.28 0.27 0.26 f 0.24 0.30 0.34 0.34 0.32 0.31 0.26 0.24 0.23 0.22 Ft - 0.04 0.12 0.19 0.21 0.21 0.23 0.23 0.23 0.24 0.23 f 0.13 0.20 0.27 0.27 0.26 0.27 0.25 0.24 0.24 0.24 三つの手法のうち，どれか一つが常に高い値を取るというわけ ではない．表5を見ると，F (f )がすべての場合で他の手法を 上回っていることがわかる．これらの結果を合わせて考えると， 提案手法Fは作成から四週間程度の時間がたったターゲットに 対して他手法よりも高い精度で将来の人気を予測できて言える． 一方で，FtはF に比べて早い段階で他手法を上回っている． しかし，ランキングの上位が正解していることを高く評価する nDCGに関しては，提案手法はT7の時点でもFtにも劣らな い精度を出しており，加えてT28においては，T7の時よりも 高い精度で推定できている．作成されてから一週間や二週間と いった早い段階での予測において，提案手法の精度が他手法ほ ど高くない理由として，提案手法がFtやPageRank, HITSの ようにグラフ全体の情報をうまく扱えておらず，局所的な情報 によって各ターゲットの将来の人気を予測しようとしているこ とがあげられる．このことは，計算量の点から考えると利点で もあるが，一方で，提案手法の改善の余地を示唆しているとも 言える．
6.
まとめと今後の課題
本研究では，フォロー順序に基づいてアーリーアダプターを 発見し，アーリーアダプターは人気情報源をいち早く見つける 能力に優れているという仮定のもと，フューチャーポピュラリ表 4 T7(ff < 1.0) における，30 日後の非相互フォロワー増加数を ゲインとした nDCG@k
Target Data Set T7 (ff < 1.0) @50 @100 @150 @200 @250 data size 8252 8252 8252 8252 8252 FW 0.18 0.20 0.21 0.21 0.21 FWnr 0.18 0.21 0.21 0.21 0.22 FR 0.02 0.03 0.15 0.15 0.15 FRnr 0.08 0.08 0.08 0.08 0.17 PR 0.04 0.04 0.05 0.05 0.05 PRnr 0.03 0.04 0.13 0.13 0.14 HITS 0.03 0.03 0.04 0.05 0.13 HITSnr 0.04 0.05 0.15 0.15 0.18 F - 0.18 0.18 0.21 0.21 0.22 f 0.18 0.21 0.22 0.22 0.22 Fw - 0.18 0.18 0.21 0.21 0.21 f 0.18 0.21 0.22 0.23 0.23 Ft - 0.19 0.19 0.19 0.23 0.23 f 0.19 0.20 0.23 0.23 0.24 表 5 T28(ff < 1.0) における，30 日後の非相互フォロワー増加数を ゲインとした nDCG@k
Target Data Set T28(ff < 1.0) @50 @100 @150 @200 @250 data size 9785 9785 9785 9785 9785 FW 0.15 0.19 0.20 0.20 0.22 FWnr 0.22 0.26 0.28 0.30 0.32 FR 0.04 0.05 0.07 0.08 0.08 FRnr 0.10 0.14 0.15 0.15 0.17 PR 0.14 0.16 0.18 0.19 0.19 PRnr 0.17 0.18 0.18 0.19 0.19 HITS 0.06 0.06 0.07 0.14 0.15 HITSnr 0.08 0.08 0.09 0.10 0.11 F - 0.12 0.17 0.18 0.18 0.20 f 0.22 0.29 0.30 0.31 0.32 Fw - 0.12 0.15 0.17 0.19 0.20 f 0.20 0.28 0.28 0.29 0.29 Ft - 0.11 0.12 0.14 0.14 0.16 f 0.18 0.20 0.21 0.22 0.22 ティースコアを計算する手法を提案した．アーリーアダプター スコアは，人気情報源すなわちフォロワー数の多い情報源を他 ユーザよりも早くにフォローしていたユーザに多く与えられる が，どのような関数にしたがってスコアをつけるべきかという のは自明ではない．そこで，アーリーアダプターの性質と関連 の深い，フォローの模倣という概念を導入し，フォローの模倣 に基づくモデルを構築することで，どのような関数に基づいて スコアをつければよいかという問題に根拠を与えた．提案手法 の評価を行うために，実際のTwitter上のデータを用いて実験 を行った．実験の結果，我々が以前に提案したtriadに基づい た手法は多くのケースでベースラインを上回る結果となった． そして，提案手法では，以前に提案した手法が苦手としていた nDCGによる評価でいい精度を示した．一方で，提案手法は， 作成から四週間ほど経過した新規情報源による推定を得意とし ていることがわかった．言い換えると，新規情報源が作成から 4週間ほどたち，将来の人気度を推定するために必要な情報が 十分蓄積されるのを待つ必要があるということである．提案手 法は以前に提案した手法に比べてシンプルな手法であり，この ことが対象となる新規情報源の情報を十分扱えていないことに つながっているといえる．一方で，シンプルであるのは利点で もあり，提案手法は以前に提案した手法やその他のベースライ ンに比べて計算量が小さい．このことを踏まえ，提案手法には より早い段階で新規情報源の将来の人気度を推定できるように するための改善の余地が存在している.
謝
辞
本研究はJSPS科研費26280112, 26540163の助成を受けた ものです。また，本研究の一部は京都大学学術情報メディアセ ンターのスーパーコンピュータを利用して実施しました．ここ に記して，謝辞を示します． 文 献[1] I. Daichi and T. Keishi. Twitter におけるフォローに関する 影響力に基づくハブ度の推定. In DEIM, 2014.
[2] J. Hopcroft, T. Lou, and J. Tang. Who will follow you back?: reciprocal relationship prediction. In CIKM, pages 1137–1146. ACM, 2011.
[3] H. Hu and X. Wang. How people make friends in social networking sitesa microscopic perspective. Physica A: Sta-tistical Mechanics and its Applications, 391(4):1877–1886, 2012.
[4] K. J¨arvelin and J. Kek¨al¨ainen. Cumulated gain-based eval-uation of ir techniques. ACM Transactions on Information Systems (TOIS), 20(4):422–446, 2002.
[5] J. M. Kleinberg. Authoritative sources in a hyperlinked en-vironment. Journal of the ACM (JACM), 46(5):604–632, 1999.
[6] H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In WWW, pages 591–600. ACM, 2010.
[7] D. Liben-Nowell and J. Kleinberg. The link-prediction prob-lem for social networks. Journal of the American society for information science and technology, 58(7):1019–1031, 2007. [8] V.-A. Nguyen, E.-P. Lim, H.-H. Tan, J. Jiang, and A. Sun. Do you trust to get trust? a study of trust reciprocity behav-iors and reciprocal trust prediction. In SDM, pages 72–83, 2010.
[9] L. Page, S. Brin, R. Motwani, and T. Winograd. The pager-ank citation rpager-anking: Bringing order to the web. 1999. [10] A. Rapoport. Spread of information through a population
with socio-structural bias: I. assumption of transitivity. The bulletin of mathematical biophysics, 15(4):523–533, 1953. [11] D. M. Romero and J. M. Kleinberg. The directed closure
process in hybrid social-information networks, with an anal-ysis of link formation on twitter. In ICWSM, 2010. [12] J. Weng, E.-P. Lim, J. Jiang, and Q. He. Twitterrank:
find-ing topic-sensitive influential twitterers. In WSDM, pages 261–270. ACM, 2010.
[13] J. Zhang, C. Wang, P. S. Yu, and J. Wang. Learning latent friendship propagation networks with interest awareness for link prediction. In SIGIR, pages 63–72. ACM, 2013.
