Recommendation of similar users, resources and social networks...

Title

Recommendation of similar users, resources and social networks in a Social Internetworking Scenario

ABSTRACT

類似ユーザやリソース、social networkを推薦する手法を提案
- 一つのsocial networkではなく、複数のsocial networkをつないだもの(Social Internetworking)を対象としている
- 明示的なつながりだけでなく、潜在的なつながりも考慮する。
  - 類似する興味や、類似する行動に基づく。
- 意味的な例外を考慮する。（ユーザ、リソース、social networkの説明文？）
- ローカルな情報だけでなく、social internetworkingにおけるグローバルな情報拡散も考慮する

Introduction

Motivations

ユーザは一つのSNSだけでなく、複数のSNSを利用する。
- Social Internetworking System (SIS)
Open Socialとか、複数のSNSを横断的に利用できるものが出てきている。
- SIS paradigmを実装したと言える

SISはいろんな良い事をもたらす
- あるユーザに関する情報を複数のSNSから収集できれば、そのユーザに対する詳細を知ることが出来る
- 複数のSNSを利用するユーザがより広く情報を拡散できる

SISを効果的に利用するのは難しい
- SISの有効性はユーザ間の交流がより頻繁になり、多くの人々が交流に参加するほど、高まる
- ユーザ数、リソース数が増えると、ユーザが手動で類似ユーザや欲しいリソースを探すのは現実的でなくなる。
- SNSの数は増え続けているため、新しく、面白いSNSを人々が手動で見つけるのは面倒な作業となる。

これらの問題は、自動的にSISを調査し、興味のあるユーザ、リソース、SNSを見つけるツールがあれば緩和される。

多くのSNSがユーザ推薦やコンテンツ推薦を実装している
- 類似度に基づく推薦
- 新しいSNSを推薦することはできない。

既存の推薦システムはSISに応用できない
- １、ユーザが明示的に表している情報しか利用していない（友人関係など）
- コンテンツの評価やコンテンツの投稿などの情報も利用することで、潜在的なユーザ間のつながりを利用することが出来る。（類似する行動をするユーザをつなぐ）
  - コンテンツにタグ付けする、評価するなどの行動は潜在的なつながりをみつけるのに役に立つ
  - 一つの行動（タグ付けだけ、評価だけ）を対象にするのではなく、複数の行動を対象として、それらをうまく合算することでよりよい精度を実現できる
  - synonymyやhomonymyを考慮する
- ２、既存の手法は友人のオーバーラップなどのローカルな情報しか用いていない
  - SNSが大きく、全くオーバーラップがない場合などは、たとえ興味や行動が似ていても推薦されない。

General characteristics of our approach

提案手法の目的は
- 一つのSNSを対象に作られた手法をSISに拡張する
- 上に挙げた二つの問題を解決する

SISを表現するモデルを定義する
- ユーザ、リソース、SNSはノードとして表現
- 行動やつながりはハイパーエッジで表現
  - ハイパーグラフ(Wikipedia)
- 各ノードのプロフィールはタグ集合で表現
  - これを用いた類似度計算の際には、synonymyやhomonymyを考慮する。
- 行動の種類は以下の四つ
  - membership: あるユーザがあるSNSを利用する
  - friendship: あるSNSにおいて二人のユーザが友人関係にある
  - posting: あるSNSにおいてユーザがリソースをポストする
  - evaluatioin: あるSNSにおいてユーザがリソースを評価する
- 新しい行動があらわれてもフレキシブルにモデルに追加できる

ユーザの類似度を計算する時は、一度に一種類の行動を対象に、グラフを構築する
- friendshipが選ばれた時は、ユーザノードとfriendshipエッジでグラフが構築される

Katz coefficientを導入することにより、ユーザ類似度はグローバルパラメータになった
- 共通の友人というローカルな情報ではない
- 共通の友人が全くいなくても類似すると見なせる

The proposed SIS model

ユーザはSISに登録し、興味のあるSNSを閲覧することが出来る。
- ユーザのIDはSIS上で一意
- タグ集合がユーザのひもづけられ、ユーザの興味を表す

ユーザがリソースをポストする
- リソースのIDはユーザに対して一意
  - 二つのリソース（別のユーザにポストされた）が同一であるかを決定するのは難しいため
- タグ集合がリソースにひもづけられ、リソースのコンテンツを表す

ユーザがリソースを検索する
- クエリとしてタグ集合を入力
- あるリソースにアクセスすると、ユーザはそのリソースを評価することが出来る（スコアを与える）

ユーザ同士は、同意が取れればあるSNSにおいて友人になる

ユーザは四つの行動を取ることが出来る
- membership: ユーザ $u_i$ がSNS skに登録する
- friendship: ユーザuiがユーザujとSNS skにおいて友人になる
- posting: ユーザuiがリソースrjをSNS skにおいてポストする
- evaluation: ユーザuiがリソースrjに対してスコアv([0, 1]の実数)を割り当てる。SNS skにおいて

Definition 2.1

ユーザはタプルによって表される
- $ID_{u_i}$ はユーザ $u_i$ のＩＤ。SIS内でユニーク
- はユーザの興味を表すタグ集合。
  - ユーザ $u_i$ がリソースを検索したり、ラベリングしたりするのに頻繁に使ったタグ

Definition 2.2

リソースはタプルで表される
- $ID_{r_j}$ と $UserID_{r_j}$ はリソース $r_j$ とそれをポストしたユーザのＩＤを表す。ペア $<ID_{r_j}, UserID_{r_j}>$ でSIS内でユニーク
- $T_{r_j} = \{t_1, t_2, ..., t_m\}$ はリソース $r_j$ のコンテンツを表すタグ集合

Definition 2.3

ＳＮＳはタプルで表される
- $ID_{s_k}$ は $s_k$ のＩＤ
- $T_{s_k}=\{t_1, t_2, ..., t_n\}$ はＳＮＳ $s_k$ 内で頻繁に用いられるタグ集合

提案モデルは少ない労力で新しい種類のユーザアクションを追加できるという意味でフレキシブル

タプル $D_{u_i}$ と、ユーザ $u_i$ に関連するアクションをまとめたものをプロフィール $P_{u_i}$ と呼ぶ

Recommendation of similar users, resources and social networks

ユーザに類似するユーザやリソース、SNSを推薦するアプローチを提案する

ノードの類似度の計算はひもづけられているタグ集合のジャッカード係数の計算による
$J(A,B) = \frac{|A \cap B|}{|A \cup B|}$
ジャッカード係数には以下の二つのデメリットがある

synonymyやhomonymyを考慮できない
ユーザアクションを使えない

提案手法では、タグ集合とユーザアクションの両方を用いる。

Recommendation of similar users

タグとアクションを一つの枠組みで扱うために、二つのタグ集合の類似度をアクションのようなもので表現する（Virtual sharing action)

２ユーザの間にsharing actionがあるということは、それらのユーザがある程度の割合のタグを共有しているということ
sharing actionはハイパーグラフにハイパーエッジを追加することで表現する

ユーザアクション（membership, friendship, posting, evaluation, sharing)を表現するUAction Graph（ハイパーグラフでない）を定義する

UActをアクションタイプとし、アクションタイプごとにUAction Graphを定義する
あるアクションタイプのUAction Graph内のエッジには、重みがつけられる。
- ユーザuiとul間のエッジの重みはで定義される。UActの種類によって、numilとdenilは次のように定義される。
  - membership: numilはuiとulが共通して参加しているSNSの数。denilはuiとulが参加しているSNSの数（和集合の要素数）
  - friendship: numilはuiとulが友人になっているSNSの数。denilはuiとulが共通して参加しているSNSの数
  - posting: numilはuiがポストしたリソースを少なくとも一つとulがポストしたリソースを少なくとも一つを表すトピックの数。denilはuiもしくはulがポストしたリソースを表すトピックの数。
  - evaluation: $w_{il} = \frac{\sum_{r_j \in RSetVal_{il}}1-|v_{ij}-v_{lj}|}{|RSetVal_{il}|}$ RSetValilはuiとulが共通して評価したリソースの集合。vijはuiがrjに与えたスコア。
  - sharing: $w_{il} = J^{*}(T_{u_i}, T_{u_j})$