2008-05-27

Vicenc Gomez and Andreas Kaltenbrunner and Vicente Lopez
Statistical Analysis of the Social Network and Discussion Threads
International World Wide Web Conference 2008
pp.645-654
PDFのある場所へのリンク

概要

Slashdot上でのコメントから構成したネットワークの解析と、Slashdotにおけるスレッドの構造の解析を行っている。
assortative mixingではなかった。
次数分布がpower-lawよりもlog-normal distributionでよりよく近似できることを主張。
controversyのdegreeの計り方にはh-indexを利用。

ABSTRACT

Sloashdot上でのコメントによるsocial networkの解析を行う。このnetworkはtraditional social networksに見られたような、giant component、small avarage path lengthやhigh clusteringのfeaturesを示したが、moderate reciprocityとneutral assortativity by degreeの点では違いを見せた。Kolmogorov-Smironow statistical testsを使って次数分布がpower-law distributionよりもlog-normal distributionでうまく説明できることを示す。また、discussion threadsの構造をintuitive radial tree representationを使って学ぶ。conversationの違うnesting levelで一貫して、threadsは強いheterogeneityとself-similarityを示した。これらの結果を使ってpostによりprovokeされたcontroversyのdegreeの計算のsimple measureをproposeする。

1. INTRODUCTION

最初のmessage boardsはUSENETで1979年にあったが、そのコメントによるsocial networkの研究はごく最近。
この形式のnetworksは複雑で、とにかくたくさんメッセージを受け取る。
これらの広大なonline spacesにそんざいするコミュニケーションのパターンを支配するものを理解し、システムのパフォーマンスを改善するための効果的な開発をするために、threadの構造のstatistics governingを解析することは興味深い。
Slashdotの紹介。
1997年にできた。だれかがshort newsをpostし、ユーザーはそれに自由にコメントできる。コメントには-1〜5までのscoreをほかのユーザーが付けることができる。一つのpostに対し、２週間で200くらいのcontributionsがあり、そのほとんどはpost自体にではなくコメントにたいするresponse。これらは複雑ネットワークの典型的なmcroscopic quantitiesのstudyに従うnetworkを構成するのに使えるrelationshipである。
先行研究ではpostとcommentの間の時間に特筆すべき規則性ああることがわかっている。
ここで使うデータは1万newsと2,075,085のコメントと93636のユーザーからな１年間のデータ。
またいくつかのradial tree structureのquantitiesを見ることでdiscussion threadsを特徴付ける。それらはstrong heterogeneityとself-similarityをconversationの違ったレベルのnestingを通して示した。これらの結果を使ってpostによりprovokeされたcontroversyのdegreeの計算のsimple measureをproposeする。

2. THE SOCIAL NETWORK

まず最初に３つの違うVERSIONのネットワークの構成方法を説明しする。
次に得られた値を次数分布に重点をおいて解析する。
最後にコミュニティの構造について簡潔に説明する。

2.1 Building the Network

コメントのauthorとそれにreplyした人との間の関係によりsocial networkを作る。qualityとrepresentativityをimproveするために以下のような方法でコメントをfilterする。
・postに直接のコメントをした時、それ以後その人がdiscussionに参加しなかった場合、postのauthorとその人との間のrelationsはないものとする
・匿名のコメントはdiscard
・scoreが-1のコメントはdiscard
・自身へのreplyはfilter（書き足しや間違いの訂正のために行われることが多い）
filteringの後コメントの数は1,281,888になり、元の63%になった。ユーザーは87%の80,962になった。
以下の３つのタイプのネットワークを構成する。
Undirected dense：undirected edge。重みはお互いへのコメント数の和
Undirected sparse：undirected edge。お互いにコメントし合った場合にのみedgeを張り、重みはそのコメントの少ない方。
Directed：directed edge。重みはコメント数。

2.2 General Description

得られたグラフの構造的なpropertiesをcharacterizeする。
highly sparse。
giant component。
Slashdotのネットワークはcompact communityとsmall proportionの孤立したユーザーという点でtypical social networksと同じ。
平均次数はいずれも高い標準偏差。次数に関する詳しい解析はSection 2.3にて。
average path lengthは最大連結成分のみで計測。どれも小さな値。スモールワールドの特徴。直径も小さい。この結果も他のtraditional social networksと同じ。
クラスタ係数と重みを考慮したクラスタ係数を計算したが、その二つにほとんど違いはなかった。重み付きグラフの詳しい解析はSection 2.5にて。
クラスタ係数はどれも高い値を示した。これもまたスモールワールドの特徴。
degree correlationまたはmixing coefficientはsocial networksにおいて特別に興味のあるquantityであり、この値が高いnetworkはassortative mixing by degreeとして知られており、多くのsocial networksで見られる。
Slashdotではこれは見られなかった。このようなことがonline communitiesでは見られることから*1 *2large online spacesの外で起きるsocial interactionsとの根本的な違いが感じられる。
最後にreciprocityを調べ、ユーザーは自分にコメントしたことのあるユーザーに対してわずかにコメントしやすい傾向があることがわかった。
まとめると、giant cluster、small averge path length、high clusteringがtraditional soacil networksの特徴と一致し、moderate reciprocityと、neutral assortativity by degreeは一致しなかった。Undrected denceとUndrected sparseはかなり違うpropertyでDrectedはその間くらいの値をであった。

2.3 Degree Distributions

次数分布による解析。
cumulative distributionの書き方が今まで見て来た論文とは違う。縦軸に横軸の次数以下の次数の人の割合をとっている。今までは以上の人。しかも縦軸がlogじゃない。
Directed以外の２つのnetworkは同じような感じなのでDirectedのみ解説。
先行研究とは違い、writingとbeing repliedは似たprocessでcaracterizeできた。
予想通り、distributionはheavy-tailを持っていた。
驚いたことにtailに属していたのはauthor of postsではなく一般のユーザーだった。
データを説明するのに最適な近似を見つけるためにpower-law（PL）とtruncated log normal（LN）*3を比べた。
結果見た目はLNが良かった。
Kolmogorov-Smirnov testの結果もやはりLNが良かった。

2.4 Mixing by Score

次数以外でassortative mixingがあるか調べる。
ユーザーのscoreをそのユーザの書いたコメントのscoreの平均とする。
scoreは最初１。匿名の場合２。
１０以上のコメントを書いたユーザーのみを対象とし、その数は18,476で全体の23%になった。
ユーザーscoreの分布はbimodal profileを示し、ユーザーが２つのクラスに分けられることをindicateした。
ユーザーごとにscoreの標準偏差を調べたところ、４分の３以上のユーザーが１以下の値になり、ユーザーscoreが良くユーザーを特徴付けていると言える。
assortativity coefficientは0.036でscoreに関してもneutrally mixedであったが、コメントの52%が評価の高いユーザーから高いユーザへのもので、高いユーザーが受け取ったコメントは全体の74%であることから、偏りがあることはわかった。
scoreの高いユーザーがコメントをされやすいのか、scoreの高いコメントがreplyされやすいのかを調べたところ、scoreの高いコメント程replyされやすい傾向があったが、scoreが２以下の場合，scoreの高いユーザーの書いたコメントの方がreplyされやすい傾向があるということもわかった。

2.5 Community Structure

Undireced denceを使用。
agglomerative clusteringを使用。重み付きグラフのクラスタリング方法。*4
λを決めて、エッジがそれより重いノード同士をまとめる方法。λを最大から次第に小さくしていく。
エッジの重みの分布を見たところ、大多数は小さい値。重みを考慮してもクラスタ係数に差が出なかったことの原因はこれだと思われる。
最大では108。
λを小さくしていき、大きさが２以上のクラスターの数の変化を調べたところ、λ〜10くらいから増え、λ=3で最大になり、そこからまた減る。
２つの最大クラスターのサイズの変化を調べたところ、最大のものはとても早くサイズが大きくなり、２番目のクラスターは小さいままだった。

3. STRUCTURE OF THE DISCUSSIONS

discussion threadの構造についての情報を解析する。
postは平均で195のコメントを受けており、半分以上のpostは160のコメントを受けている。多いものでは1000以上のコメントを受けているpostもある。
コメントの数だけではinteractionのdegreeを計るには十分でない。
例えば少数のユーザーによるlong dialogue chainはreciprocal interactionの高いdegreeを意味するが、この方法では捉えられない。
個々のpostのレベルでinterctionを計るためにsingleユーザーによるコメント数で最大のものを計る。
この値によるpost数の分布を調べたところ、４が最大だった。半分くらいのpostが少なくとも５回以上のsingleユーザーによるコメントを受けていた。
Threadsによりlevel of interactionにかなり違いがある。
これからtree structureについてより詳細に学ぶ。

3.1 Radial Tree Representation

Slashdotの表示システムはデフォルトでは、直接のコメントは全て表示され、それより深いレベルのコメントはscore４以上の場合全て表示され、score１〜score４では省略されて表示され、score１以下は隠される。
discussionsの構造を利用して視覚化して調査する。
postを中心として直接のコメントはfirst nesting level、次はsecondといった具合。
結果それぞれの特徴にはかなりの相違が見られた。
たくさんのreplyがfirst levelに見られるが、深さは小さいもの。
２人で相互にコメントし合いとても深くなっているもの。
時にはdiscussionの中心が枝の途中で始まっているものもある。
nesting levelとコメントの数の関係を調べた。
level1とlevel2で最も多く、後は減少した。
これらの理由として、ユーザーが全ての知識を公開した、あるいはより新しい記事に移行したことなどが考えられる。
また深いコメントにアクセスしづらいということも原因かもしれない。
このようにあまり深いレベルまで議論が続かないと思われるが、maximum depthの分布を見ると、そうではなく、深さ７までは上がっていき、それからは下がっていくような形になった。
これまでに計った量ではdiscussion threadsのapparent heterogeneityは捉えられなかったので、与えられたnesting levelでどのようにcommentsがgenerateされるのかを見る。
ここではcomments（もしくはpost）のreplyの数の分布を見る。
まず、確率の差がかなりあり（three oderers of magnitude）、discussion threadsにかなり相違があることがわかる。
つぎに、level０（postへの直接のreplyの分布）とそれ以外（それぞれの深さでのcommentsへのreplyの分布とで明らかな違いがある。level０ではlog-logでbell-shapeに従うが、それ以外では確率は単調減少であった。これはpostとcommentsではreplyの起こり方に違いがあるということを表している。
面白いことにこのような違いはlevel１以降では見られない。
ちなみにscoreのnesting levelへの依存は無かった。
それぞれの結果はまるで違うが、どれもLN fitで説明できた。が、KS-testsではLN hypothesisはlevel２より深いところでしか許されなかった。

3.2 The H-index as a Structural Measure of Controversy

このsubsectionではcontroversyのdegreeを計るために前出の結果を用いる。
コメントの総数で計ろうとすると、first levelのコメントだけ多く、あとはとても少ない
ようなdiscussion threadsが高く評価されてしまう。
かといって、深さで計ると２人だけでコメントし合っているだけのthreadが高く評価されてしまう。
h-index*5 *6 *7 *8を使うことを提案する。
今回は、それぞれのpostのh-index hを次のように定義する。
h-index＝そのnesting level以上のコメント数が存在する最大のnesting level。
たとえばfirst levelで９コメント、second levelで９コメント、third levelで６コメント、fourth levelで3コメントならばh-index=3になる。
h-indexによるpostの数のhistogramはコメント数や最大の深さによるものに比べて傾きが緩やかになった。
コメント数、深さともにh-indexとの正の相関が見られたが、たくさんのコメントを受けていたり、深さが大きくともh-indexが特に大きくないものがあることが観察された。
h-indexによりランク付けした結果の上位１５位のコメント数、深さ、Titleを調べた。

4. CONCLUSIONS

解析は関係が明確な友人関係やアフィリエーションネットワークよりもgenericな関係の隠されたネットワーク構造を理解するためのステップとして行われた。
Slashdotネットワークはtraditional social networksとは離れた特有の特徴を示した:neutral mixing by degree、almost identical in and out degree distribution、only moderated reciprocity、absence of a comple community structure。
この結果から、ユーザーは違った意見をもったときにcommentする傾向があることが予想される。
良いコメントはreplyされやすく、良いユーザーはあまり良くないコメントをした場合でも比較的replyされやすい。
self-similarityのような特徴が違うnesting levelで見られた。これはstrong heterogeneityにもかかわらず、simple depth-invariant mechanismが存在することを意味する。
nested discussionsのdyneamicsの詳細についてはongoing researchのtopic。
h-indexを使い、controversyのdegreeを計った。efficientlyであったが、その値とcontroversyのsubbjective sensationとの関係を知るには人の感覚がいる。

*1:P. Holme, C. R. Edling, and F. Liljeros. Structure and time evolution of an internet dating community. Social Networks, 26(2):155–174, 2004.

*2:K.-I. Goh, Y.-H. Eom, H. Jeong, B. Kahng, and D. Kim. Structure and evolution of online social relationships: Heterogeneity in unrestricted discussions. Phys. Rev. E, 73(6):066123, 2006.

*3:M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226–251, 2003.

*4:M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167–256, 2003.

*5:J. E. Hirsch. An index to quantify an individual’s scientiﬁc research output. Proc. Natl. Acad. Sci. USA, 102(46):16569–16572, 2005.

*6:T. Braun, W. Glanzel, and A. Schubert. A Hirsch-type index for journals. Scientist, 19:8–8, 2005.

*7:A. Sidiropoulos and Y. Manolopoulos. Generalized comparison of graph-based ranking algorithms for publications and authors. Journal of Systems and Software, 79(12):1679–1700, 2006.

*8: L. Bornmann and H. D. Daniel. What do we know about the h index? J. Am. Soc. Inf. Sci. Tech., 58:1381–1385, 2007.