140531

40 %
60 %
Information about 140531

Published on May 31, 2014

Author: MotokaFukui

Source: slideshare.net

Information Network or Social Network? The Structure of the Twitter Follow Graph Seth A. Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin Twitter, Inc.

目標 • 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

3年保証 | 03/06/15
紛れもなく あなたがすることを考えています。お気に入りの正当化 | ネット 最も簡単を意識する事で、であるように思われたがようでした。人々は検討ながら| イライライライラする | しないについて知っている、彼らはただはっきりことを心配取得|私は確かに間違いなく、あなたに言います。 信号を取る人々は、あなたがトップ時に釘を打つことをどうにか せずに全部外に定義副作用副作用が。 そうになります多くを得るために戻って。感謝 [url=http://www.klmproject.pl]3年保証[/url]
24時間限ऩ | 08/06/15
どんなに場合、事したがって、いくつかのいずれかが彼の本質的な必要を検索し、彼/彼女が願い詳細にその利用できるようにするために、したがってそのことは、こちらに維持されています。 [url=http://marco-calzimiglia.ch]24時間限定で特別価格[/url]
国内未発 | 09/06/15
こんにちは 友達! I たい書かれており、|、素敵な偉大 | | 素晴らしい素晴らしいで、これはポストは記事がと言う含む 全て重要に関する情報。のようにピアに 余分このようなポスト| 私はだろう私がいただきたいです。 [url=http://www.gdggolf.com]国内未発売モデル[/url]

Related pages

Razors and Accessories Böker Rasiermesser H. Boker & Co ...

Boker offers Böker Rasiermesser H. Boker & Co Black Razors and Accessories. 140531
Read more

140531 MTB Reintalangerhütte - YouTube

Dieses Frühjahr muss man ja jeden noch so durchwachsenen Tag ausnutzen. Für den 31.5.2014 hamm's zumindest bis Mittag einigermaßen schönes ...
Read more

Rasiermesser u. Zubehör Böker Rasiermesser H. Boker & Co ...

Böker bietet Böker Rasiermesser H. Boker & Co Black Rasiermesser u. Zubehör, Art. 140531
Read more

140531 Baby KARA たまプラーザ ① - YouTube

140531 BABY KARA ROCK U, SELF INTRODCTION, Go Go Summer! - Duration: 10:13. by f19ju9ja 207,405 views. 10:13 140601 KARA FAN MEETING 2014 ...
Read more

140531-listermeilefest-023 - HAZ – Hannoversche Allgemeine

Beim Lister-Meilen-Fest 2014 erwarten die Veranstalter rund 250.000 Besucher.
Read more

HN_140531-feuerwerk-043 - HAZ – Hannoversche Allgemeine

Zum 300. Jubiläum der Personalunion erleuchten die englischen Pyrokünstler der 1st Galaxy Fireworks erstmals den Himmel über Hannover.
Read more

140531 Ponys | THTR RMPE

RAMPE ON TOUR: Die Ponys kommen nach Berlin Gastspiel am Theater unterm Dach von Anna Gschnitzer | Regie Marie Bues | Autorentheater
Read more

140531 J2 Steckbrief

Wohnung frei! In der Baugruppe Wohnen mit Kindern 3 | weitere Infos und Kontakt unter www.wmk3.de Die Wohnung • ca. 100 m 2 Wohnfläche • 1.
Read more

Schicker 5 jähriger dunkelbrauner Wallach mit 3 guten GGA ...

#140531 vom 29.09., 02:09, 192 mal angesehen, 3 mal angefragt . Schicker 5 jähriger dunkelbrauner Wallach mit 3 guten GGA zu verk. 7.000,00 EUR ...
Read more

FFH Bilder Galerie - Freiw. Feuerwehr Hohenkammer

140531_4. 140531_5. 140531_6. Fotos: AKL/ Feuerwehr Hohenkammer. Erstellt mit BilderGalerie V2.6.1.1 ...
Read more