Information Network or Social Network?

20 %
80 %
Information about Information Network or Social Network?
Science

Published on May 31, 2014

Author: MotokaFukui

Source: slideshare.net

Description

近日中に訂正版上げます

Information Network or Social Network? The Structure of the Twitter Follow Graph Seth A. Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin Twitter, Inc. 東京大学大学院工学系研究科システム創成学専攻 大橋・鳥海研 福井 思佳 2014/5/31 とりらぼ輪読会

目標 • Twitterフォロー・グラフのトポロジー的解析から、 • Twitterはソーシャル・ネットワークなのか、あるい は情報ネットワークなのか?という疑問に答える

定義 • ソーシャル・ネットワーク • 次数相関 degree assortativity :高 • 最短経路長 shortest path length :短 • 連結成分 connected components :大 • クラスタ係数 clustering coefficients :大 • 相互性 reciprocity :高 • 情報ネットワーク • 次数 vertex degrees :高 • 相互性:低 • 2ホップで連結しているノード数 two-hop neighborhoods:多

使用データ • Twitterフォロー・グラフ全データ(2012年後半) • アクティブ・ユーザ数:175,000,000 • 有向リンク数:20,000,000,000 • 双方向リンク:42% →無向リンク:4bl. • 単方向リンク:58% • 国別データ • ブラジル • 日本 • アメリカ

比較対象 • Facebook • ノード数:721,000,000 • 無向リンク数:68,700,000,000 • MSNメッセンジャー • ノード数:180,000,000 • 無向リンク数:1,300,000,000

分析項目 1. 次数分布 degree distributions 2. 連結成分 connected components 3. 最短経路長 shortest path lengths 4. クラスタ係数 clustering coefficient 5. 2ホップで連結しているノード数 two-hop neighborhoods 6. 次数相関 degree assortativity

1. 次数分布 • 【定義】 • Inbound degree (in-degree):フォロワー数 • Outbound degree (out-degree) :フォローイング数 • 【分析対象】 • 全ノード/国別ノードそれぞれに対して • In-degree distribution • Out-degree distribution • Mutual degree distribution

・べき分布 ・ヘビーテール (Out-degreeより もヘビー)

次数分布に関する考察 • Out-degreeの方が上限が高い:直感に反する • ∵フォロワーをフォローし返す著名人の存在 • “non-social”な特徴:社会的関係を維持可能な上限 150[1]

・Out-degree2000 にピーク

次数分布に関する考察 • Out-degreeの方が上限が高い:直感に反する • ∵フォロワーをフォローし返す著名人の存在 • “non-social”な特徴:社会的関係を維持可能な上限 150[1] • Out-degree2,000にピーク:スパム防止 • 2,200フォロワー未満のアカウントへの上限数

高次数多い 国別は いずれも 全体と似た 特徴

次数分布に関する考察 • Out-degreeの方が上限が高い:直感に反する • ∵フォロワーをフォローし返す著名人の存在 • “non-social”な特徴:社会的関係を維持可能な上限 150[1] • Out-degree2,000にピーク:スパム防止 • 2,200フォロワー未満のアカウントへの上限数 • Mutualはin-degree, out-degreeに比べると小さいも のの高次数 • 国別の特徴は全体とほとんど変わらない

統計的な考察 • フィッティング: • In-degree, Mutual degree:べき分布 • Out-degree:対数正規分布 • Out-degreeと他を比較: • 累積分布:大 • 最大次数:小 • →概してユーザのフォローイング数 > フォロワー数

Social graph or Info graph? --次数分布から • ソーシャル・グラフの特徴からは外れる • Out-degree大きすぎる • →個人が維持可能な社会的関係数を超えている

2. 連結成分 • 【定義】 • 強連結 strongly connected graph • :有向グラフにおいて、相異なる全ての頂点間に 経路が存在 • 弱連結 weakly connected graph:強連結でない

連結成分に関する考察 • 最大成分に含まれるユーザの割合: • 弱連結:92.9% • 最大成分以外の成分はほとんどがただ1つのノードか ら構成 • それらを除くと99.94%が最大成分に含まれる • 強連結:68.7% • 他のソーシャル・メディア(99%)より少ない • 30%以上のユーザは1つも双方向リンクを持たない • →情報発信/受信一方に特化

Social graph or Info graph? --連結成分から • ソーシャル・グラフの特徴からは外れる • リンクの双方向性が低すぎる

3. 最短経路長 • 【計算手法】 • 2ノード間に考えられる経路数:N(N-1)=2.6*1020 • 双方向でも7.3*1015 • 計算量大きすぎるため近似解 • Hyper ANF algorithm[2] • HyperLogLog counter[3](cardinality estimation algo)で 種類の数を推定 • The number of shortest paths of length n through which a user is connected can be approximated as the change in her neighborhood size after the nth jump.

平均経路長に関する考察(1/3) • 平均経路長: • 双方向グラフ:4.17 • 有向グラフ:4.74 • 他のソーシャル・ネットワークとの比較: • MSNメッセンジャー:6.6 • Facebook:4.74 • FBの方が • 平均次数:高、分岐因子:大、クラスタ係数:高 • なのに、最短経路長はTwitterとほぼ同じ • →ソーシャル・ネットワークが大きくなるほど平均経路長 が小さくなる、という先行研究に反する

平均経路長に関する考察(2/3) • 国別の特徴: • 全体の特徴から大きく外れない中で、 • ブラジルの平均経路長:短 • アメリカの平均経路長:長 • →先行研究と矛盾するというよりは、人間関係の 違いでは

平均経路長に関する考察(3/3) • Spid: • Spid = 分布の分散/分布の平均値 • ソーシャル・ネットワーク:spid < 1 • ウェブ・グラフ:spid > 1 • 双方向グラフのspid:0.115 • 有向グラフのspid:0.108 • →ソーシャル・ネットワークの特徴を持つ • FBのspid:0.09より大 • →Twitterの方が分布がやや大きい

Social graph or Info graph? --平均経路長から • ソーシャル・グラフの特徴を示す • 平均経路長、spidいずれも満たす

4. クラスタ係数 • ソーシャル・ネットワークの特徴:クラスタ係数高

次数が高くなる →クラスタ係数小さくなる

クラスタ係数に関する考察(1/2) • 次数が高くなるとクラスタ係数が小さくなる • 他のソーシャル・ネットワークとの比較: • クラスタ係数はFacebookより小さい • MSNメッセンジャーより大きい • K=5: MSN*1.5=Twitter • K-20: MSN*1.9=Twitter /次数 5 20 100 Twitter 0.4 0.3 0.14 Facebook 0.23 0.19 0.14

日本のみ異なる特徴

クラスタ係数に関する考察(2/2) • 日本の特異性: • クラスタ係数:高 • 双方向性:高 • →双方向グラフはノード数に対してリンク数多 • 次数200-1000の範囲にピーク • →高次数・高クラスタ係数のユーザらによる”cliques”

Social graph or Info graph? --クラスタ係数から • ソーシャル・グラフの特徴を示す • 高いクラスタ係数を持つ

5. 2ホップで連結しているノード数 • 2ホップで連結しているノード:新規リンク予測[5] • 【定義】 • Inbound two-hop:ノードのフォロワーのフォロワー • このユーザから情報を受け取るポテンシャルを持つ • Outbound two-hop:ノードのフォローイングのフォロー イング • このユーザに情報を伝えるポテンシャルを持つ • Unique two-hop neighborhoods • Non-unique two-hop neighborhoods:ユーザのフォロ ワーのinbound degreesの和

2ホップで連結しているノード数に関する考察 • 次数3000以下では、 2ホップで連結しているノード 数は次数の2乗を上回る • →情報収集/伝播いずれにも効率的 • 次数100以下では、uniqueとnon-uniqueが同様の 挙動 • ユーザ数が少ないうちは、新規two-hop neighborhoods のほとんどがunique • 新規inbound two-hop neighborhoods:4770 • 新規outbound two-hop neighborhoods:3573 • Facebookとの比較: • 友達100人のユーザ:平均27,500人の友達の友達 • 2乗より多く、Twitterより少ない

Social graph or Info graph? --2ホップで連結しているノードから • 情報ネットワークとして効率的な構造 • 情報収集/伝播を拡散

6. 次数相関 • ソーシャル・ネットワークと他の大規模ネットワーク を区別する最大の指標[4] • ソーシャルネットワーク:0.1 - 0.4 • Facebook:0.226 • 【定義】

次数相関に関する考察(1/2) • SOD – DOD : 0.272 • 自分のフォロー数が多いほど、フォローイングのフォ ロー数も増加する • ソーシャル・ユーザが他のソーシャル・ユーザを刺激 • →ソーシャル・ネットワークの相互性を示す • SID – DOD : 0.241 • 自分のフォロワー数が多いほど、フォローイングのフォ ロー数も増加する • 有名になるほど他のユーザをソーシャルにする • →ソーシャル・ネットワークの通説と一致

次数相関に関する考察(2/2) • SOD – DID : -0.118 • 自分のフォロー数が多いほど、フォローイングのフォロ ワー数は減少する • SOD, DID個別で見るといずれも増加しているので予想 外の結果 • SID – DID : -0.296 • 自分のフォロワー数が多いほど、フォローイングのフォ ロワー数は減少する • 先行研究と合致しない

Social graph or Info graph? --次数相関から • ソーシャル・グラフの特徴を示す部分とそうでない 部分がみられる • 矛盾する、直感に反する結果

考察(1/3) • 個別のユーザにとって、Twitterは • 情報ネットワークからスタート • 有名なユーザをフォロー:preferential attachment • →徐々にソーシャル・ネットワークとしての要素強まる • 有名かどうか以外の基準でフォロー • 所属コミュニティを発見(現実のつながり、共通の興味など) • →リンクが追加された順序を考慮した分析へ

考察(2/3) • 利用時間が増えるにつれフォロワー数は増加 • 新規ユーザと古参ユーザが混在 new experienced

考察(3/3) • 次数相関への説明 • SID – DOD, SOD – DODの正の相関 : • 利用時間が増えるにつれフォロワー数は増加 • Figure7 (b)より • SOD – DODの負の相関 : • フォロー数の多いユーザは、フォローイング数の 少ないユーザをフォローする傾向 • Figure7 (c)より • →著名人よりも社会的つながりを優先

今後の展望、結論 • Twitterはソーシャル・グラフの特徴を示す部分とそ うでない部分がみられる • Twitterにおける行動に2つの流れがあるのでは? • ①情報収集 • ②双方向的な社会的つながり • ソーシャル・ネットワークなのか、あるいは情報ネッ トワークなのか、特徴を精査 • 直感的には、ユーザの混在が要因?

参考文献 • [1] R. Dunbar. Neocortex size as a constraint on group size in primates. Journal of Human Evolution, 1992. • [2] P. Boldi, M. Rosa, S. Vigna. HyperANF: approximating the neighborhood function of very large graphs on a budget. WWW 2011. • [3] P. Flajolet, C. Fusy, O. Gandouet, and F. Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm Analysis of Algorithms, 2007. • [4] M. Newman and J. Park. Why social networks are different from other types of networks. Physical Review, 2003. • [5] P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, and R. Zadeh. WTF: The Who to Follow service at Twitter. WWW 2013.

Add a comment

Comments

即日発送 | 03/06/15
このウェブサイトは、この素晴らしいですサイト。 これは、特にのために時間| もののためにあなたのためにあなたに感謝するために 素晴らしい読み!私は間違いなく本当に好きのお気に入りとして保存| |それすべてののビット少し とiもあなたはウェブサイト 新しいものを見るために。 [url=http://arkesa.lt]即日発送[/url]
送料無料 | 08/06/15
感謝、ウェブサイトは は便利。 [url=http://www.senludwika.pl]送料無料市場[/url]
今年の春 | 08/06/15
| 学ぶ読み ちょうどここのものを| 私が持っている私がしました。 確か 値する再検討のためのブックマーク。 I 驚きどの多く しよう あなたが置く 作成のの一種 優れた有益サイト。 [url=http://www.havemantimmerwerken.nl]今年の春秋も最注目[/url]

Related presentations

How organisms adapt and survive in different environment.

Aplicación de ANOVA de una vía, modelo efectos fijos, en el problema de una empres...

Teori pemetaan

Teori pemetaan

November 10, 2014

learning how to mapping

Libros: Dra. Elisa Bertha Velázquez Rodríguez

Materi pelatihan gis

Materi pelatihan gis

November 10, 2014

learning GIS

In this talk we describe how the Fourth Paradigm for Data-Intensive Research is pr...

Related pages

The Social Network | Sony Pictures

David Fincher's The Social Network is the stunning tale of a new breed of cultural insurgent: ... Information. The Studio. About Sony Pictures; Divisions;
Read more

Social network - Wikipedia, the free encyclopedia

A social network is a social structure made up of a set of ... have developed core principles about the interactions of social structure, information, ...
Read more

Social networking service - Wikipedia, the free encyclopedia

A social networking service (also social ... Most social network services are ... and third parties frequently use information posted on social ...
Read more

The Social Network – Wikipedia

2016 belegte The Social Network bei einer Umfrage der BBC zu den 100 bedeutendsten Filmen des 21. Jahrhunderts den 27. Platz. Literatur Ben ...
Read more

Social Networks - Journal - Elsevier

Social Networks is an interdisciplinary ... a substantive foundation based on the social network ... If you require any further information or ...
Read more

social network - definition of social network in English ...

Definition of social network in ... embeddedness in a social network more broadly. Social isolation is not ... each other by posting information ...
Read more

Social Network Definition | Gründerszene

Was ist ein Social Network? Social Networks sind Gemeinschaften innerhalb des Internets. tweet.
Read more

The Official Site of The Global Information Network

ABOUT GIN will give you an overview of the benefits you can receive with the Global Information Network. Read More ...
Read more

Plag — Information Network

Plag — Information Network. 1 1 1 1. Einloggen. Schreib uns. FAQ. Blog. Manifest; Tutorial; Design-Kit Pressematerial. Datenschutzrichtlinien AGB. Assign ...
Read more