DEIM Forum 2014 B1-5

マイクロブログにおける対話手段と投稿内容に着目した
ユーザ推薦に関する研究と分析
岡本

大輝†

豊田

正史††

喜連川

優†††,††† 東京大学情報理工学系研究科 〒 113–0033 東京都文京区本郷 7–3–1 東京大学 情報理工学系研究科†† 東京大学生産技術研究所 〒 153–8505 東京都目黒区駒場 4–6–1 東京大学 生産技術研究所††† 国立情報学研究所 〒 101–8430 東京都千代田区一ツ橋 2–1–2
E-mail: †{hokamoto,toyoda,kitsure}@tkl.iis.u-tokyo.ac.jp
あらましソーシャルネットワークサービス等では，ユーザ推薦によって，他ユーザと効率的に，そして円滑に，コミュニケーションを取ることが可能になる．ユーザ推薦には，ソーシャルネットワークのグラフ構造に着目した手法
や，投稿内容に基づく手法等が提案されているが，これらはソーシャルメディアの環境によって様々な併用方法が考えられる．本論文では，マイクロブログサービスの１つである Twitter 上において，ユーザ間の対話関係からグラフを構築し，対話の種類や回数，投稿内容の類似度を活用した Random Walk 手法を提案し，その精度と意義を検証した．
キーワード

Micro Blog, Twitter, User Recommendation, Random Walk

1. ま え が き
近年，社会生活における web の重要性が増し，人々は web
上でも社会活動や経済活動を行うようになった．そうした中で，して，コンテンツに着目した手法について論じる．次に，SNSにおけるユーザ推薦をリンク予測問題へと帰着させることを示し，ソーシャルグラフに着目した手法について論じる．

2. 1 特徴量に着目したユーザ推薦

web ユーザに対する情報推薦は，web サービスにおいて非常に広く一般的な推薦手法の一つとして，ユーザの特徴量に着目重要な技術となっており，その精度を高める研究は数多くなさした手法が存在する．推薦の候補 (ユーザ推薦の場合はユーザ)れている．例えばユーザに商品を推薦することで，購買行動がの特徴を元に，推薦の対象たるユーザとの親和性の高い候補を活発になる．また，ユーザにユーザを推薦することで，ユーザ推薦するものである．

間にコネクションが生じ，サービスの利用率を高めることが可能となる．

Hannon らは，Twitter におけるユーザ推薦において，ユー
ザのツイート内容と，フォロウィー/フォロワーのリストを利

一方で，web 自体の肥大化と多様化に伴い，web ユーザの数用した content based の手法を提案した．彼らは，ユーザのツが増加し，web の使い方も様々に変化・多様化している．そう

イートに含まれる名詞のベクトルと，ユーザのフォロウィー/した中で，推薦の手法もまた，様々なサービスやユーザの目的

フォロワーのリストを，それぞれユーザの特徴量と見做し，機に適応する必要がある．このような環境の中で，これまで盛ん

械学習によって特徴量に重み付けを行い，類似するユーザを推に研究されてきた，ソーシャルネットワークのグラフ構造に着薦した [10]．

目した手法に加え，グラフに依拠しない様々な指標を併用し，状況や目的に適した推薦手法の提案が必要とされる．
本稿では，ソーシャルネットワークにおけるユーザ推薦を目Wang らはさらに，マイクロブログの機能とユーザのアク
ティビティに着目し，他ユーザの投稿の拡散回数や拡散力を特徴量として，ユーザへのツイート推薦を行った [13]．

的とし，マイクロブログサービスである Twitter の API を利用

いずれの実験も結果的に，2-hop(隣接ユーザの隣接ユーザ)

し，そのデータを用いた実験を行う．実験においては，Twitterまでは特徴量による作用が及ぶが，より遠方のユーザに対するのグラフ構造と，グラフに因らない特徴として，ユーザが投稿

特徴の作用に関しては言及していなかった．

するテキストの内容の両方に着目し，それらを併用する．また，

2. 2 ネットワーク構造を用いたユーザ推薦

実験の結果や使用したデータを分析し，ユーザがサービスを利SNS におけるユーザ推薦を始めとして，特定の環境下のユー用する際の特徴や，グラフ構造との相関性を議論する．そして，

ザに対して，同一のサービスを利用するユーザを推薦する際にユーザの用途や特徴によって，最適な推薦手法にどのような違は，一般的にそのネットワーク構造に着目したアプローチが用いが現れるのか，その考察を行う．

いられる [17]．ネットワーク構造に着目する場合，ユーザ推薦

2. 関 連 研 究はネットワーク内のリンク予測問題に帰着する．
以下では，データ構造の表現に則り，推薦候補および被推薦

近年，Web 上においても，様々なコンテンツやユーザを，効の対象となるオブジェクトをノード，オブジェクト同士のリン率的に，かつ的確に推薦する手法について，多種多様な研究がク関係をエッジと表現する．また，ノード A とエッジを形成し行われている．本章では，まず，広く推薦に用いられる手法とているノードの集合を Γ(A) とする．

2. 2. 1 グラフ上の近縁性を表す指標

い独特な機能をいくつか備えている．本稿ではそれらの機能に

ユーザ推薦においては，グラフ構造を利用した様々な手法がついて説明する．

•

考案されている．

短文投稿

最もシンプルな推薦手法として，2 つのノードに共通する隣アメリカの Twitter，中国の weibo 等のマイクロブログサービ

接ノードの数を数えて，数が多い順に推薦するというものがスは，ユーザによる短文投稿を主な機能とする．投稿の内容，ある [2] [1]．また，共通する隣接ノードの数に，分母として両または投稿すること自体をツイートと表現し，ユーザはあらか

者の隣接ノードの集合の論理和をとった Jaccard’s coeﬃcient

じめ決められた文字数の中で，自由かつ手軽にテキストを投稿という指標がある [2]．推薦候補に隣接ノードが多い場合，無することができる．

用にスコアが高くなることを防ぐことができる．さらに，ノー•ユーザのフォロー

ド A とノード B に共通する隣接ノードであるノード C の隣接

マイクロブログのユーザが，特定の他ユーザの投稿を容易に閲ノードが少ないほど，C による A と B 近縁性が高まるとした覧できるようになる機能である．Twitter を利用した研究には，

Adamic Adar の評価指標がある [3]．Jaccard’s coeﬃcient と他ユーザのフォローを推薦するものもある [10]．

同じく，多数の隣接ノードを保有するノードによって，近縁性

Score(A, B) =∑Γ(A) ∩Γ(B)1log(Γ(C) )•投稿によるインタラクション

マイクロブログには，特定のユーザや投稿に対して特殊な投稿が不当に高まることを抑制することができる．

を行うことで，他ユーザとインタラクションを行う機能が存在(1)

する．本論文では，このインタラクションを用いたユーザ推薦を行う．

推薦の対象となるノードから離れたノードも評価できる指標と（ 1 ） リプライ

して，ノード A からノード B へ，距離 l で移動する経路の集

投稿文内に，@マークの後にユーザ ID を伴う (@USERID) こ(l)
合 pathsA,B を用いた Katz の指標がある [11]．

とで，そのユーザに対して言及を行う投稿のことを，リプライ

Score(A, B) =∞∑(reply) という．リプライを受け取ったユーザは，常時見ている
β

l

(l)
· |pathsA,B |

(2)

l=1

ユーザの投稿とは別に，自分へのリプライとしてその投稿に注目することが可能となる．リプライは，ある投稿に対して (そ一般的に，β は 0 以上 1 未満の値をとり，β が小さいほど，A，の投稿者に対して) 行われる場合や，相手のユーザの投稿と無B 間の短距離経路が重視される．

関係に行われる場合などがあるが，いずれのリプライ投稿にも明確な相手が存在する．マイクロブログの短文投稿という特性

2. 2. 2 Random Walk

から，リプライは同一ユーザ間で短時間に繰り返されることが推薦される対象 (target) となるノードを s として，s の隣接ある．

ノードへとランダムで移動する動点の挙動を考える．動点はエッジに従ってさらに隣接ノードへの移動を繰り返し，最終的（ 2 ） リツイート
リツイート (retweet) とは，他のユーザの投稿を自らの投稿とに動点が存在する確率が高いノードを s に推薦する [4] [16]．s

同様の扱いで再投稿・拡散する機能である．あるユーザが別のと同じ距離に存在する複数の候補ノードの中でも，より s に近ユーザの投稿をリツイートした際には，投稿主のユーザに対ししい対象を推薦する手法として，よく用いられている．
さらに Backstorm らは，facebook において友人関係をエッジとして，エッジの形成時間，インタラクションの回数，友人申請の方向などをエッジの特徴量とした．それらの特徴量を元に機械学習を行い，エッジにウエイトを付与してランダムウォー
クを行う Supervised Random Walk を提案した [7]．

Random Walk を用いた推薦手法は，ネットワーク構造を用いて近接性の高いユーザをランキングすることにより推薦を行うが，これまでに提案された手法では，ユーザの投稿内容までは考慮されていなかった．また，投稿内容を用いた推薦手法では，ネットワーク構造が十分に考慮されていなかった．

3. マイクロブログにおけるユーザ推薦てリツイートしたユーザを通知する仕組みがある．リツイート
は，ユーザが興味を持った話題や意見を，自身をフォローする
ユーザに拡散する場合に行われるほか，投稿主に対する対話や意思表示の手段として行われる場合もある [14] [15]．

3. 2 ユーザ推薦における投稿内容の活用
マイクロブログは短文投稿を主な機能とするサービスである．
それと同時に，投稿を用いて他のユーザとコミュニケーションを行うこともできる．他のユーザとのコミュニケーションが可能であるため，ユーザを推薦する技術も存在し得る．現在，Twitter では他ユーザを推薦する機能が実装・提供されている．
しかしながら，マイクロブログの主たる機能である短文の投稿を活用したユーザ推薦の研究は多くない．投稿内容の活用がマイクロブログニオケルユーザ推薦において有効であることは，本章では，マイクロブログの機能と特徴について説明し，本論文の実験の目的について述べる．

3. 1 マイクロブログの機能
本論文で扱う Twitter は，マイクロブログと呼ばれるサービスの一種である．マイクロブログは，他のウェブサービスに無Hannon らの研究 [10] でも示されているが，フォローユーザの推薦に留まり，限定的なものであった．
そこで本論文では，Twitter におけるユーザ推薦を目的とし，ソーシャルネットワークとユーザの投稿内容を併用したユーザ推薦の実験を行う．その後，実験の結果を検証し，投稿内容に基づいた推薦が有効に作用する状況や用途について考察を深−→ −→tf · idf ベクトルを，それぞれ式 6 の t u , t v とすることで，める．

以下の 3 種類のウエイトを生成する．

4. 提 案 手 法
本章では，マイクロブログにおいて投稿内容を活用したユー
ザ推薦の有用性を検証を目的として，今回行った実験の詳細を
説明する．

•

全ての投稿の類似度に基づくウエイト wt−all(u,v)•

リプライ投稿の類似度に基づくウエイト wt−reply(u,v)•

リツイート投稿の類似度に基づくウエイト

wt−retweet(u,v)
4. 1. 3 複合ウエイト
上記のインタラクションを用いたウエイト 2 種類，投稿内容

4. 1 Weighted PageRank
本論文では，Random Walk による推薦手法を基にして，投の類似度を用いたウエイト 3 種類から，それぞれ 1 種類ずつ

稿内容も考慮するように拡張した推薦手法を提案し，実験と検を用いた複合ウエイトを作成し，推薦に利用する．インタラク

証を行う．

ションを用いたウエイトを wi(u,v) ，投稿内容の類似度を用い本手法では，推薦対象となるユーザ s を起点とし，他ユーザたウエイトを wt(u,v) とすると，遷移確率行列の要素 w(u,v) は，とのリンクをたどる Randam Walk を行い，各ステップにおい以下の式で定義される．

て一定の確率で s に戻る，Random Walk with Restart 手法 [4]{を基にする．また，遷移確率の決定にあたり，ユーザ間のインw(u,v) =タラクション回数や投稿内容の類似度などを考慮して，遷移確率に重み付けを行う．遷移確率行列を M とすると，k 回遷移後→の存在確率のベクトル −rk の更新式は，以下で表わされる．

−→→→
r k+1 = (1 − α)M −r k + α−
r0

(3)

→
ただし，−
r 0 は，ユーザ s のみ 1 で残りは 0 となるようなベクトルである．αは，各ステップにおいて s に戻る確率を表し，(1 − β)wi(u,v) + βwt(u,v)
0 (u, v 間にエッジが無い場合)(7)

こうして定義された遷移確率行列において，あるユーザがエッジを形成するユーザに対して，これらの重みに比例した確率で遷移を行うよう正規化を行う．
なお，今回の実験では，複合でない 5 種類のウエイトを用いた実験を行い，その結果を元に，(Wi , Wt ) の組み合わせを決定する．

今回の実験では Supervised Random Walk 手法 [7] において用

4. 2 データセット

いられていた 0.3 を値として用いた．

Twitter 社が提供する API を用いて，ツイートを公開して遷移確率の決定にあたり，インタラクションに係る 2 種類と，いるアカウントからツイートを収集した．著者の使用している

投稿内容の類似度に係る 3 種類の，計 5 種類の特徴量を用いる．

Twitter アカウントを起点として，ソーシャルグラフ上で近傍それぞれから算出したウエイトと，適切に選んだ 2 種類の複合に存在するユーザがフォローしているユーザを順次集めて，最ウエイトを，各エッジのウエイトとして実験を行う．

終的に 250,000 ユーザの tweet データを取得した．その中で，4. 1. 1 インタラクション回数を用いたウエイト

特に 2013 年 8 月から同年 9 月まで (以下，訓練期間) のデータ

ユーザ間のインタラクション回数は親密性を表すため，回数と，2013 年 10 月 (以下，テスト期間) のデータを抽出した．

が多いほど高い確率で遷移するような重み付けを行う．ユーザ間で行われたインタラクションの回数を元に，全てのエッジにリプライ，リツイートに基づいた 2 種類の重みを設定する．
ユーザ u，ユーザ v 間のリプライ回数を nreply(u,v) ，リツ
イート回数を nretweet(u,v) として，ウエイト wi−reply(u,v) と

wi−retweet(u,v) を以下のように定義する．
wi−reply(u,v) = 1 −1
1 + nreply(u,v)

wi−retweet(u,v) = 1 −1
1 + nretweet(u,v)

4. 2. 1 グラフの構築
今回の実験は，マイクロブログサービスでのユーザ推薦の精度の向上と，着目するインタラクションの違いによる，投稿内
容を活用した推薦の差異の分析を主目的とする．Twitter におけるユーザ同士のインタラクションは，いくつかの形態が存在するが，今回の実験では，リプライまたはリツイートのうち，(4)いずれかが 2 ユーザ間に存在する場合に，エッジを形成するも
のとした．

(5)

4. 2. 2 ユーザの分類構築したグラフをもとに，以下の条件を満たすユーザを推薦の候補ユーザとする．

4. 1. 2 投稿内容の類似度を用いたウエイト訓練期間でリプライまたはリツイートによってエッジが形成•

自動投稿アカウントではない

された 2 ユーザで，両ユーザの tf · idf ベクトルのコサイン類•

訓練期間で 100 件以上のツイートを取得できた

似度を，投稿内容の類似度に基づくウエイト Wt(u,v) として定•訓練期間でデータセット内のユーザとインタラクション

義する．

−
→
−
→
wt(u,v) = cos( t (u) , t (v) )

をしている

(6)

なお，インタラクションの有無によって作成された 3 種類のさらに，候補ユーザのうち，テスト期間において•新たに 10 以上のユーザとリプライを交わす•

新たに 10 以上のユーザとリツイートを交わす

以上の 2 条件を満たすユーザを，積極的にインタラクションを

表 1 各期間のエッジ数
テスト期間に新たに生成
テスト期間 されるエッジ

行うユーザとして，ランダムに 1000 ユーザを抽出し，推薦の対象ユーザとした．

4. 2. 3 tf · idf ベクトルの作成
訓練期間において，各ユーザが投稿したツイートに形態素解析を行い，ユーザ毎に名詞セットを抽出した．リプライとリツ
イートは投稿によって行われることから，名詞セットにその特性を反映させるために，ツイートをインタラクションの有無で

訓練期間
ユーザ数
リプライによるエッジ
2,569,214
リツイートによる
エッジ
8,521,830
全てのエッジ(重複を除外)10,134,638

分類し，以下の 3 種類のそれぞれ名詞セットを抽出した．

•

全てのツイート内容から抽出した名詞セット•

リプライツイート内容から抽出した名詞セット•

リツイートの内容から抽出した名詞セット

209,743
1,450,987

454,361

3,866,848

2,339,750

4,889,299

2,552,946

表 2 ユーザ分類別次数候補ユーザ 対象ユーザ

161927

1000

27.45

86.04

の特徴量とする．ユーザ v における名詞 noun の tf ·idf(v,noun)

ユーザ数
リプライによる
平均隣接ユーザ
リツイートによる
平均隣接ユーザ

94.16

156.16は，以下の式で表される．

平均隣接ユーザ

111.10210.45

また，各名詞セットから tf · idf ベクトルを生成し，各ユーザ

count(v,noun)|U |tf · idf(v,noun) = ∑
· log
(8)
|u
:
u
∋ noun|count(v,N )
Nの，リプライ回数とリツイート回数の平均値を計算し，さらに，対象ユーザから各候補ユーザに至る最短経路において，経路上

なお， count(v,noun) は，ユーザ v の一つの名詞セットに含まれる noun の数， |U | は候補ユーザ数， |u : u ∋ noun| は名詞

noun を発していた候補ユーザの数である．
これにより，各ユーザごとに以下の 3 種類の tf · idf ベクトルを生成した．

•••−→
全てのツイートから作成した tf · idf ベクトル t all−→
リプライツイートから作成した tf · idf ベクトル t reply−→
リツイートから作成した tf · idf ベクトル t retweet

4. 2. 4 グラフとユーザの分析の各エッジの両端に存在するユーザの tf · idf ベクトルのコサ
イン類似度も計算した (表 4)．ユーザ A，ユーザ B の tf · idf
ベクトルのコサイン類似度は，以下の式で表される．

−→−→t (A) · t (B)−→−→cos( t (A) , t (B) ) = −→−→| t (A) || t (B) |(9)

なお，分析に用いる tf · idf ベクトルは，全てのツイートか−→ら作成したもの ( t all ) とした．2 ユーザの tf · idf ベクトルのコサイン類似度は，ユーザ同士の投稿内容の類似度を示す．
図 1 と表 3 から，今回構成したグラフでは 3hop に候補ユー以上の条件で構築したグラフと，ユーザの分析を行った．

ザのピークが存在するが，リプライ，リツイートのいずれの正4. 2. 5 エッジに関する分析

例ユーザも，訓練期間においては約 90

図 1 に，訓練期間，テスト期間でそれぞれ構築したグラフ

また，表 4 より，正例ユーザへ至る経路上では，平均より多のエッジ数を示す．実験においては，テスト期間に新たに生成

くのインタラクションが行われている傾向があり，特にリプラされるエッジを正例エッジ，正例エッジで隣接することになる

イで顕著であることがわかる．さらに，正例ユーザへの経路でユーザを正例ユーザとして，推薦の精度の検証に用いる．

は，平均より投稿内容類似度が高くなることがわかる．

また，候補ユーザと対象ユーザのそれぞれで，インタラク

以上から，ユーザ推薦の実験をするにあたり，今回構築したションの種類別に隣接ユーザ数を算出した．その結果を表 2 にグラフの構造を参照し，近傍のユーザを推薦することの有意性示す．

が示された．また，ユーザ同士のインタラクションの回数と，集計の結果から，

投稿内容の類似度に着目することで，推薦の精度が向上する可（ 1 ） テスト期間のリプライの 6 割以上は訓練期間でインタ能性があることが示された．

ラクションを行ったユーザ同士のもである（ 2 ） リツイートは交流の無かったユーザ同士でも多数行わ

5. 実験と結果の考察れている

5. 1 推薦の精度の評価方法という 2 点を述べることができる．また，選択した対象ユーザ

本稿では，Twitter のユーザに対し，その目的に応じて最適が平均より活発にインタラクションを行っていることもうかがなユーザ推薦を行うことを目的とする．グラフを活用したユーえる．

ザ推薦では，テスト期間のデータから作成されたグラフで新た

4. 2. 6 対象ユーザを起点とした経路探索に得られるエッジを正例エッジとして，手法に基づく予測と比訓練期間のグラフ上で，1000 人の対象ユーザを基点として較して精度を検証することが一般的であるが，今回の実験では，経路探索を行い，候補ユーザまでの距離と，正例ユーザまでの正例の条件を

距離を分析した (図 1，表 3)．

（ 1 ） リプライによるもの

併せて，候補ユーザまでに至るまでの経路に存在するユーザ（ 2 ） リツイートによるもの

表 5 各ウエイト単独による推薦 (Precision@10)
正例の条件
リプライ リツイート

いずれかの
インタラクション

Wi−reply

0.08190.04900.1108Wi−retweet

0.02330.07850.0940Wt−all

0.04840.07390.1083Wt−reply

0.0472

0.05390.0878Wt−retweet

0.03750.07190.0979Wbaseline

0.05370.06240.1003

表 6 各ウエイト単独による推薦 (Mean Average Precision)
正例の条件
リプライ リツイート

図 1 対象ユーザと候補ユーザの経路距離とユーザ分布
表 3 対象ユーザを起点とした候補ユーザの分布

いずれかのインタラクション

Wi−reply

0.10930.04440.0887

Wi−retweet

0.03470.06940.0740Wt−all

0.06630.06590.0873Wt−reply

0.06240.05020.0726

Wt−retweet

0.0511

0.06350.0779Wbaseline

0.0766

0.06160.0892hop 数による累積率 (％)
2
全候補
ユーザ
リプライ
による
正例ユーザ
リツイート
による
正例ユーザ
全ての
正例ユーザ

3

4

平均総数

5

24.343 92.206 99.795 99.993

し，正例となる候補が出現した時点での精度の平均値．

209,742

AP(NT RU E ) =90.239 99.895 99.993

100

1

∑

NT RU ENT RU E

K =1

K
(10)
rank of Kth T RU E

13.391

但し，NT RU E は 1 ユーザが有する全ての正例の数である．
90.161 99.971

100

100

31.42689.999 99.946 99.998

100

42.428•Mean Average Precision (MAP)

推薦候補のスコアランキングを上位から検証し，正例となる候補が出現した時点での Average Precision の平均値．ランキン
グの上位に正例が集中していると高い値となる．

表 4 候補ユーザへの経路上のエッジ特徴量
リプライ
リツイート
全候補
による
による
ユーザ 正例ユーザ 正例ユーザ

M AP =

1
NT RU E∑NT RU E

AP(K)

(11)

K =1

リプライ回数2.24287.54773.6453

リツイート回数

2.51362.76653.2995

5. 2 実 験 結 果

投稿内容の類似度 0.0303

0.04290.0478

本項ではまず，前章で定めた 5 つのウエイトについて，それぞれ単独で用いて推薦を行った場合の精度を評価する．ま（ 3 ） それらのいずれか

た，比較の為に全てのエッジのウエイトを均一としたウエイトの 3 パターンで変え，各ウエイトによる精度の変化と最適な推(wbaseline ) を用いた推薦の結果も記載する．

薦手法を検証する．

表 5，表 6 から，正例となるインタラクションの回数を利用

エッジに加える様々なウエイトを，それぞれ変化させながら，したウエイトを用いることで，ベースラインより良い精度とな

Prec@10，Mean Average Precision の 2 つの指標を用いて，推ることがわかる．また，投稿内容の類似度を用いた結果に着目

薦の精度を評価する．また，Mean Average Precision の説明

すると，いずれの正例条件であっても全ての投稿内容を用いたの過程で，Average Precision にも言及する．

ウエイトで精度が高くなった．

•

実験の結果から，正例となるエッジの条件別に 2 種類の複合

Precision@10 (Prec@10)

1 ユーザに対する推薦候補として、スコアが高くなった上位 10ユーザの中での精度．今回のデータでは，推薦のターゲット
ユーザがテスト期間に新たに 10 以上のエッジを形成するため，推薦の精度の評価としてこの値を使用する．

•

Average Precision (AP)

1 ユーザに対する推薦候補のスコアランキングを上位から検証

ウエイトを提案し，式 7 の β の値を変えながら精度を検証した．正例とするエッジの条件，および組み合わせたウエイトの種類は以下のとおりである．

•

リプライによるエッジを正例とする場合

リプライの回数に基づくウエイト (Wi−reply ) と，全ての投稿
内容に基づくウエイト (Wt−all ) を用いる．

•

リツイートによるエッジを正例とする場合

図 2 リプライによるエッジを正例とした際の精度

図 3 リツイートによるエッジを正例とした際の精度

リツイートの回数に基づくウエイト (Wi−retweet ) と，全ての投の条件とした場合の比較を行う．Precision@10 は一般的に，候稿内容に基づくウエイト (Wt−all ) を用いる．

補中に占める正例の数が多いほど高くなる傾向がある．表 3 に

以下，図 2 にリプライによるエッジを正例とした際の実験結よると，リツイートによる正例ユーザの数はリプライによる正果を，図 3 にリツイートによるエッジを正例とした際の実験結

例ユーザの 2 倍以上存在する．しかしながら，均一なウエイト

果を，それぞれ示す．いずれも，β が大きいほど投稿内容の類(Wbaseline ) を用いた場合には，リツイートを正例とした場合の似度の重要性が高まる．

精度の比は 1.2 未満であり，リプライ回数によるウエイトでリ

5. 3 実験結果の考察と検証

プライを予測する場合と，リツイート回数によるウエイトでリ

本項では，前項までの実験結果と 4. 2. 4 で行った分析結果をツイートを予測する場合を比べると，リプライを用いた場合が元に，各ウエイトの特性や作用，および Twitter ユーザの特徴についての考察を述べる．

•

インタラクション回数によるウエイト

高精度となっている．
このことから，リプライ関係によるユーザの親近性は，リプライ回数に顕著に反映され，将来のリプライを予測する際には，

表 5，表 6 から，正例とするインタラクションの回数をウエイ

既知のリプライ回数を参照することが有効であると述べること

トとして用いた場合に，精度が向上することがわかる．一方で，ができる．

正例ではないインタラクションのウエイトを用いても，それぞれ精度が低下してしまっている．

•

投稿内容類似度によるウエイト

ツイート内容の類似度による推薦の結果にも着目する．正例とこれにより，Twitter のユーザは，リプライとリツイートをするインタラクションによらず，ツイートを分類せずに全ての明確に違う機能として活用し，頻繁にリプライを交わす相手のツイート内容の類似度を用いた場合に，精度が高くなることがツイートを頻繁にリツイートするとは限らないと述べることがわかる．ここで，ベースラインとの比較を試みる．リプライにできる．

よるエッジを正例とする場合には，どの類似度を用いてもベー

また，表 5 で，リプライ，リツイートをそれぞれ正例エッジ

スラインより精度が低下した．一方で，リツイートによるエッジを正例とする場合には，全てのツイート内容，リツイートの内容のいずれの類似度を用いても，ベースラインより精度が向上している．表 4 によると，リツイートによるエッジで正例となるユーザへの経路では，リプライによる正例となるユーザへの経路より，隣接ユーザ同士の類似度が高い傾向があった．
以上のことから，Twitter のユーザは，他のユーザからリツ
イートを行う際には投稿内容を加味しており，その傾向はリプライよりも顕著であると推察できる．

•

複合ウエイト

まず，図 2 に着目する．いずれもリプライ回数によるウエイトと投稿内容類似度によるウエイトを結合した場合の結果を示しているが，リプライを正例として予測する場合には，投稿内容による改善が見られないことがわかる．一方，図 3 に着目する．
リツイート回数と投稿内容類似度によるウエイトを結合し，リツイートを正例として予測した際の精度であるが，両者を単体で用いた場合より改善していることがわかる．

図 4 Mean Average Precision の差によるユーザ数

ここで，複合ウエイトを用いてリツイートを予測する際に見

表 7 4 分割交差検定による結果と比較られた改善の有意性を検証するために，Wilcoxon の符号付順
位和検定と，4 分割交差検定を実施する．
（ 1 ） Wilcoxon の符号付順位和検定
各候補ユーザに対し，– リツイート回数によるウエイトで推薦を行った場合– 複合ウエイト (β = 0.4) で推薦を行った場合

Prec@10MAP

Wi−retweet

0.07840.0693Wt−allβWi−retweet + (1 − β)Wt−all(4 分割交差検定)

0.07380.06590.08390.0745

Wbaseline

0.06240.0616以上の 2 回の推薦で得られた Mean Average Precision の，差の絶対値の順位と分布をもとに，有意性を評価する．
検定にあたり，Mean Average Precision の差による対象ユー
ザのヒストグラムを示す (図 4)．

ンに基づくユーザ推薦の精度の向上を目的として，インタラク
ションの回数とユーザの投稿内容の類似度に着目した Random

Walk に基づく推薦手法を提案した．この手法では，ユーザの検定の結果，検定統計量 Z0 は 8.065 ，正規分布に従った有インタラクションを元にソーシャルグラフを構築し，インタラ

意確率は 7.323e − 16 となる．これは，「複合ウエイトを用いた

クション回数と投稿内容の類似度をエッジのウエイトとして，推薦の精度はリツイートの回数によるウエイトを用いた推薦のウエイトを遷移確率として Random Walk によるユーザ推薦

精度と差はない」とする帰無仮説を棄却するに値する低確率でを行った．また，推薦するユーザとの関係がリプライによるもある．

のか，リツイートによるものかを区別し，ウエイトに用いる特（ 2 ） 4 分割交差検定

徴量が各条件下で推薦の精度に与える影響を検証した．

1000 人の対象ユーザをランダムに 4 分割し，3 つを訓練事例と実験の結果，リプライを正例として予測する際には，リプラ

して，ウエイトの結合割合 β を学習し，残る 1 つに適用する交イの回数によるウエイトのみを利用し，投稿内容の類似度によ差検定 4 回を行った．得られた結果を表 7 に示す．

るウエイトを加味することによる精度の向上が見られないこと

Precision@10，Mean Average Precision のいずれでも，交が判明した．一方で，リツイートを予測する際には，リツイー

差検定によって得られた平均値は，結合前のウエイトから得らトの回数によるウエイトのみではなく，投稿内容の類似度によれた値より大きくなった．この検定においても，ウエイトの結るウエイトを併せることで，精度が向上した．また，Wilcoxon

合による精度の向上の有意性が示されている．

の符号付順位和検定を行うことで，精度向上が有意であること

以上 2 つの検定から，リツイートを予測する場合に，リツを示した．

イートの回数だけでなくユーザの投稿内容の類似度を用いると，以上のことから，Twitter においてユーザが他者とインタラ精度が向上すると述べることができる．一方で，リプライを予クションを行う際には，インタラクションに応じた特徴がある

測する場合の結果についても検定を行ったが，有意な精度改善ことが示された．まず，ユーザ同士のリプライ関係の強さは，は見られなかった．これにより，リプライを予測する際には，その回数に顕著に表れ，リプライを予測する際には回数を活用

リプライの回数だけでなくユーザの投稿内容の類似度にも着目することで，精度が向上する．一方，リツイートを予測する際することで，精度が改善することが示された．

には，その回数のみならず，ユーザの投稿内容の類似度を活用

6. ま と め
本論文では，ソーシャルネットワークにおけるインタラクショすることで，精度が向上する．これにより，ユーザは Twitter
において，他者とリプライを交わす際には，相手のユーザとの既存の関係性が重視され，他者のツイートをリツイートする際

には，既存の関係性に加えて投稿の内容が重視されている，と述べることができる．
今回の研究により，インタラクションに応じた特徴量の選択と活用が，よりユーザの需要に即した推薦が可能であることが
示された．

文

献

[1] M.E.J.Newman，Clustering and preferential attachment ingrowing networks，Physical Review E - Volume 64，2001.
[2] G. Salton, M. J. McGill, Introduction to modern information retrieval, 1986.
[3] Lada A Adamic, Eytan Adar, Friends and neighbors on theWeb, Social Networks, 2003.
[4] Sergey Brin, Lawrence Page, The anatomy of a large-scale
hypertextual Web search engine, Computer Networks and
ISDN Systems, 1998.
[5] David Liben-Nowell, Jon Kleinberg, The Link-Prediction
Problem for Social Networks, The American Society for Information Science and Technology, 2007.
[6] Jonathan L. Herlocker, Joseph A. Konstan, Lorgen G. Terveen, John T. Riedl, Evaluating collaborative ﬁltering recommender systems, ACM Transaction on Information Systems, 2004,[7] Lars Backstorm, Jure Leskovec, Supervised random walks:predicting and recommending links in social networks,
WSDM, 2011,[8] Fouss F., Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative
Recommendation, IEEE Transactions on Knowledge andData Engineering, 2007.
[9] Jure Leskovec, Daniel Huttenlocher, Jon Kleinberg, Predicting Positive and Negative Links in Online Social Networks,
WWW, 2010.
[10] John Hannon, Mike Bennett, Barry Smyth, Recommending twitter users to follow using content and collaborativeﬁltering approaches, RecSys, 2010.
[11] Katz L., A new status index derived from sociometric analysis, Psychometrika 18(1), 1953.
[12] Glen Jeh, Jennifer Widom, SimRank: a measure ofstructual-context similarity, KDD, 2002.
[13] Beidou Wang, Can Wang, Jiajun Bu, Chun Chen, et al.,Whom to Mention: Expand the Diﬀusion of Tweets by @Recommendation on Micro-blogging Systems, WWW, 2013.
[14] Danah Boyd, Scott Golder, Gilad Lotan, Tweet, Tweet,
Retweet: Conversational Aspects of Retweeting on Twitter, System Sciences (HICSS), 2010.
[15] Haewoon Kwak, Changhyun Lee, Hosung Park, Sue Moon,
What is Twitter, a social network or a news media?, WWW,
2010.
[16] Sergey Brin, Lawrence Page, The PageRank Citation Ranking: Bringing Order to the Web, 1998.
[17] Lise Getoor, Christopher P. Diehl, Link mining: a survey,
SIGKDD, 2005.