Yes, There is a Correlation From Social Networks to Personal Behavior on the Web
Parag Singla and Matthew Richardson
Yes, There is a Correlation From Social Networks to Personal Behavior on the Web
International World Wide Web Conference 2008
pp.655-664
PDFのある場所へのリンク
概要
social networkと個人の属性の関係を調べた論文。
メッセンジャーからネットワークを構成。
個人の属性として、検索エンジンのクエリーログ、年齢、性別、地域を用いている。
結果
性別以外で隣人との属性が似ている傾向が見られた。性別は逆の結果。
chatに費やした時間が長い程その傾向が強かった。
単位メッセージあたりの時間が長い程傾向は弱くなった。
距離２の隣人でもその傾向は見られたが、距離１の隣人よりは弱かった。
1. INTRODUCTION
"A man is known by the company he keeps."
付き合っている仲間を見ればその人の人となりがわかる。
「social interacitonとpersonal behaviorとの関係」はsociologistsの長年のtopic。
この論文では「良くお互いにtalkしてる人たちは似てるの？」をインターネットのcontextから調査する。
この関係はsociologiacal questionに過ぎない訳ではなく、例えば検索エンジン、広告、chat clientsなどにとって有益。
この関係を分析するのに必要なデータは２つ。
１．誰と誰がコミュケーションしているのか
→instant messaging networkより
２．その人の特徴
→search historyとdemographicsより
instant messaging(IM)は利用者が増えており、2005年にはインターネットユーザーの18%が日常的に使用しているとの調査がある。メールに比べてinformalな'friends'のネットワークが得られる。
search historyからはpersonal interstersts and behaviorがわかる。インターネットユーザーの63%が日常的に検索エンジンを利用しているとの調査がある（前述の調査と同論文）。demographicsのデータはIMユーザーの年齢、性別、zip (地理的な位置）。
この論文で誰とtalkしているかと、何を検索しているかの間に強い関係があることを示す。相関が検索のカテゴリー、年齢、zipともあり、負の相関が性別との間で見られた（ユーザーが異性とtalkすることが多いことが原因と考えられる）。この相関がtalk時間が長い程強いこともわかった。面白いことにこの関係は単位メッセージあたりにかけた時間が長い程弱くなった。つまり簡単なメッセージをやり取りする（恐らくformalityの必要ないcloserな関係であることを示している）間柄だと相関が強くなることもわかった。また単位メッセージあたりにかけた時間が長いほどその相手が異性であることが多いこともわかった。また共通の友人を持つ２人には何が起こるのか、demographicsを共有している２人に何が起こるのかも示す。
今回はIMと検索のcontextしか実験していないが、この結果が他の様々なネットワーク、behaviorにも共通の結果たと期待している。例えばネットワークでは、オンラインシステム、newsgroups、social web sites、behaviorではwhat Web sites user visit、where they shop、などなど。
2. THEORY
U=set of user characteristics
Su = the set of pair wise similarities which exit aomgst users in set U
ユーザー間のrelationshipは２人の間のsimilarityにのみdepend onし、個々のcharacteristicsにはnot depend onと仮定する。
数式がいっぱい。Bayesの考え方が多用されてる。よくわからん。
3. DATASETS
MSN Messenger instant messaging networkのデータと、Windows Live Searchのデータを使っている。
3.1 Sosial Network Data
2006年夏のMSN Messenger network。joining a chat session、chat invites、leaving a chat sessionなどがその時間とともに記録された生データ。最終的なデータは162Mのユーザーを含む25Gのchat session。3.3Gの一回以上interactしたユーザーのペアができ、ユーザー間で平均８回interactしていた。
オリジナルのいつchatが始まったか、その長さなど、たくさんの情報を含んでいる。この論文ではそれらをreduceした。使ったデータはユーザー間の総session時間、総session回数、総message送信回数（ユーザー１、ユーザー２）。
3.2 Personal Interests Data
people's intersts and characteristicsの情報として2006年夏のMicrosoft Web search dataを使用。30Mのユーザーによってなされた0.5Gの検索を含む。平均17回の検索をしていることになる。生データは20以上のattributes（年齢、郵便番号、性別などや、query query categoryなど）を含むので、Messengerデータと同様に7 relivant fieldsにreduceした。使ったのはquery list、main-category list、sub-category list、age group、gender、zip。main-category、sub-categoryはopen directory project dmozに従ったもの。
3.3 Joining the Data
前述の２種類のデータを合わせた。chatのペアにそのままqueryなどのデータをくっつけただけ。13Mのユーザーからなる76Mの組ができた。
4. EXPERIMENTS
たくさんの実験をした。最初の実験のsetはtalking on messengerとsimilarity of various attributesとの基本的な相関。さらにattributesを固定した場合にtalk timeが相関にどう影響するのか、直接繋がっておらず共通の隣人がいる場合にはどうなのか、を実験した。まずsimilaritiesの計算方法を説明し、そのご実験の詳細に進む。
4.1 Computing the Similarities
それぞれのattributeを独立して考える。
確率はランダムにユーザーのペアを選んで計算。
大まかに分けて２種類の計算方法がある。
・Single-valued attributes：単純に全体の数分の、attributesが同じだったペアの割合。年齢、性別、zipがそれにあたる。
・Multi-valued attributes：確率の平均をとる。クエリーやクエリカテゴリー等の計算にはこれを使う。比べる２つの集合の、要素数同士を掛け合わせたものを分母とし、分子は一致した要素の数。それを選んだ全てのペアで平均する。
クエリーの場合単語に分けた方がより良いsimilarityの計算になることもあるので、新しいattirbuteを導入する。例えば{"Red Dog", "Smart Dog", "Bulldog"}という集合だった場合、{Red, Smart, Bulldog, Dog, Dog}という集合になる。これをwordと呼ぶ。
multi-valued attributesの計算には他にもいろいろ方法があり、それはfuture work。
4.2 Establisshing the Correlation
talkしてない人よりtalkしている人との方がsimiralityが高いことを示したい。
条件を与えずにペアを選んだときのattributeのsimilarity（Baseline）とIMでtalkしたことあるペアを選んだときのattributeのsimilarity（Messenger）を比較している。結果は以下の通り。
予想通りMessengerのほうが高いsimilarityを示した。ただ、性別に関しては逆だった。
クエリーのsimilarityに関しては、２人のinterestが似ているのか、talk中にその同じような検索をしているのかを調査することがfuture work。
4.3 Varying the Talk-time
どちらもtalkしたことある人でもより長い時間talkしている人との方がsimilarityが高いことを示したい。
ユーザーのペアを総talk時間で5つに分割。
それぞれの部分に同じ数のペアが入るように分割。
それぞれの部分でattributeのsimilariityを計算し、Baselineも加えて比較。
全ての部分で、性別以外はBaselineより高いsimirality。性別以外のattributeは総talk時間の増加とともに単調増加した。性別だけはBaselieよりは低いsimilarityで上下した。
さらに、たくさんの短いsessionをしているペアと、数回の長いsessionをしているペアを区別したい。直感的には表面的な付き合いと、深い付き合いとの違いと思える。
平均talk時間でユーザーのペアを５つに分割しBaselineとともに比較したところ、総talk時間の時の結果とqualitatively similarだった。
最後に単位メッセージあたりにかけた時間により５つに分割し、比較している。 この時間が長いということは、会話に興味が無いか、何を書くかにとても気を使っているか、単純に長いメッセージを書いているか、ということを示している。
すべてのquery attributeとzipではsimilarityはtime spent per messageの増加とともに減少する傾向が見られた。これはshorter messagesが近い友人を示し、そのペアはinterestsを共有しているということ。ただ最も時間を長くかけているペアの部分だけは例外だった。この結果の原因を調べるのはfuture work。
性別に関してはtime per messageの増加とともにsimilarityは減少した。異性との間ではより単位メッセージに時間をかけるということ。
4.4 Conditioning on Personal Attributes
talkしたことのある人がsiimlar interestsを持つと示して来たが、それがただ単に同じ年代、同じzipだからじゃないの？という当然の疑問に対し、年代・zipを固定したときのsimilarityの比較によって答える。
前述のMessenger、Baselineの定義に加え、personal attributesを固定して、talkしたことあるペアを選ぶConditioned Messenger（C-Messenger）、ランダムにペアを選ぶConditioned Baseline（C-Baseline）を定義する。
全てのpersonal attributesを固定した場合、C-BaselineとBaselineはかなり近い値。demographicsが同じでもランダムに選んだ場合similarityはあまり違わない。messenger pairsに関してはそうではなく、demographicsが同じペアの方がsimilarityは高かった。より重要なのはC-Messengerの方がC-Baselineよりsimilarityが高かったということ。このことからtalkしたことのある間柄だと実際にinterstsを共有していると言える。
zip、年代、性別を固定した場合もそれぞれにたような結果になった。
4.5 Effect of Indirect Links
talkしたことのある人のtalkしたことのある人との間のsimilarityはどうなるのかを知りたい。共通の友達がいる場合のsimilarityも直接chatした場合のような傾向があるのか。
そのために2-hop networkを作る。もとのネットワークで２ステップで繋がっているノードにエッジを張る（１ステップで行ける場合も２ステップで行ければOK）。
ネットワークが大きくなりすぎるためサンプリング。sizeがもとのネットワークと同じになるくらい。
Baselineと1-hopと2-hopでsimilarityを比較。予想通り、ほとんど2-hopのsimilarityはBaselineと1-hopの間の値になった。全てのquery attibutesとzipで2-hopのsimilarityはちょうど中間くらいの値になり、年代は1-hopにかなり近い値になった。性別のsimilarityは2-hopが一番高くなった。
全体的に言えば、共通のtalking friendがいる場合はランダムなペアに比べるとよりsimilarだと結論できる。
5. RELATED WORK
ノードとエッジの関係を知ることはcomputer scienceだけでなくsociologyとsocial networkingの分野でもactive topic。
social networkingではsimilar characteristisの人が繋がりやすいというideaをhomophilyと呼ぶ。
McPherson et al*1→現実世界でのhomophilyの働きについてexcellent reviewを与えた。
Sproull and Patterson*2→online communitiesへの参加が物理的な世界での日々の生活と振る舞いにどう影響を及ぼしているか議論している。
real-world social networksはin the literatureでたくさん研究されている。たとえばsexual relationとdiseaseを含むようなネットワーク*3 *4。
統計学の分野ではsocial networksのmodelingが盛ん。例えばHandcock and Raftery's model*5。social networkのmodelingはviral marketingにも応用されている*6 *7 *8 *9。
Webではconnectedなページは同じtopicのことが多い。この"Web homophily"はWeb pageからcommunityを見つけたり*10 *11、rannkinngするのに利用できる*12。
Leskovec and Horivits*13ではこの論文の期間ともかぶっているmessengerデータを用いて解析している。
6. FUTURE WORK
この分野ではfuture workにもたくさん方向性がある。まずkeyword serch similarity と IM talk timeの正の相関をclick on advertisementsでも調べたい。そしてユーザーが誰とtalkしているかが与えられたとき、そのユーザーのcharacteristicsが予測できるようなモデルを作りたい。これにより、personalizeされた検索結果や、本人ですら気がつかない新しいqueryを示したりできるようになる。
multi-user chat sessionの利用。
queryを時間軸にそって観察し、social networkを介して情報がどのように伝わるのかを調べたい。またその伝播のkey usersの特定。
queryのclassifiy。navigational、transactional、informational。そしてそれをモデルに組み込む。
最後に、今回の実験結果が他のdomainでもそうなのかを調べたい。例えばonline gaming environmentやsocial networking sites。
7. CONCLUSION
ランダムなペアより、IMでtalkしたことのあるペアの方が明らかにinterstsを共有していた。総talk時間が長い程その傾向は強くなった。さらに直接talkしていなくとも、共通の友人がいればその傾向を示した。
今回の結果は準備段階に過ぎないが、この分野での更なる調査がインターネットのための現行のアプリケーションや新しいアプリケーションの発達への道を切り開くと信じている。
*1:M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a feather: homophily in social networks. Annual Review of Sociology, 27:415–444, 2001.
*2:L. Sproull and J. Patterson. Making information cities livable. Communications of the ACM: Special Issue on Information Cities, 47:2:33–37, 2004.
*3:P. Bearman, J. Moody, and K. Stovel. Chains of affection: the structure of adolescent romantic and sexual networks. American Journal of Sociology, 110:44–91, 2004.
*4:K. Eames and M. Keeling. Monogamous networks and the spread of sexually transmitted diseases. Math. Biosci., 189:115–130, 2004.
*5:M. Handcock and A. Raftery. Model-based clustering for social networks. J.R. Statist. Soc., 170:1–22, 2007.
*6:P. Domingos and M. Richardson. Mining the network value of customers. In 7th Intl. SIGKDD, pages 57–66, 2001.
*7:M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In 8th Intl. SIGKDD, pages 61–70, 2002.
*8:D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence in a social network. In 9th Intl. SIGKDD, pages 137–146, 2003.
*9:J. Leskovec, L. Adamic, and B. Huberman. The dynamics of viral marketing. In ACM Conference on Electronic Commerce, pages 228–237, 2006.
*10:G. Flake, S. Lawrence, and C. L. Giles. Efficient identification of web communities. In Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 150–160, Boston, MA, August 20–23 2000.
*11:IM environment are significantly more likely to share interests than a random pair of users. Our analysis is based on a probabilistic D. Gibson, J. M. Kleinberg, and P. Raghavan. Inferring web communities from link topology. In UK Conference on Hypertext, pages 225–234, 1998.
*12:M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in PageRank. In Advances in Neural Information Processing Systems 14, pages 1441–1448, 2002.
*13:J. Leskovec and E. Horvitz. Planetary-scale views on a large instant-messaging network. In 17th Intl. WWW, 2008. To appear.
