DEIM Forum 2023 3a-5

ソーシャルネットワークの特徴に基づいた有向ネットワーク生成モデルの提案
山川衛†

田島 敬史†† 京都大学情報学研究科 〒 606-8501 京都府京都市左京区吉田本町 36-1
E-mail: †yamakawa.mamoru.75s@st.kyoto-u.ac.jp, ††tajima@i.kyoto-u.ac.jp
あらまし Web グラフやソーシャルネットワークサービス (SNS) 上のフォローグラフにおいては，相互フォローが重要な役割を果たしていることが多く，近年はこれらに着目したネットワークの分析に関する研究が盛んになっている．
また，近年はクラスター係数を高めるために Edge Rewiring を採用したネットワーク生成モデルも多数存在するが，非常に実行時間がかかるため，Edge Rewiring を用いない同程度の特徴を持ったモデルの提案は重要であると考える．そこで本稿では，まず，日本の Twitter ユーザのフォローネットワークを解析し，その結果にもとづき相互フォローを考慮した新たな枝の選択方法を用いる有向ネットワーク生成モデルを提案する．また，このモデルにより生成したネットワークと実際の SNS との性質の類似性を比較検証する．
キーワード ソーシャルネットワークグラフ，ランダムグラフ生成，成長ネットワーク頂点数になるまで以下を繰り返すモデルである．

1 はじめに1998 年に Watts–Strogatz (WS) モデル [1] が提案されて以来，様々な人工的なネットワーク生成手法が提案されてきている．
現在は Twitter をはじめとした SNS 上のフォローグラフを研究で扱うことも多くなってきており，相互エッジが存在する有向ネットワークの効率的な生成は重要であると考える．そこで本稿では Twitter のフォローグラフなどの相互エッジが存在する有向ネットワークを生成する手法を提案する．
今回は日本の Twitter ユーザ 27,500,000 人によるネットワー（ 1 ） 新しい頂点をエッジを m 個持った状態でネットワークに追加する（ 2 ） 次数に応じた確率で m 個の頂点を選択し，新しい頂点が持つエッジを接続する．

BA モデルの次数分布はべき乗測に従い，スケールフリー性を持つ．

2. 2 Holme-Kim モデル
Holme-Kim モデル [3] は，m0 個の頂点から開始し，目標の頂点数になるまで以下を繰り返すモデルである．

クを解析し，現在の Twitter のネットワークがどのような性質（ 1 ） 新しい頂点をエッジを m 個持った状態でネットワークを持っているかの解析を行った．その結果，ネットワークの次に追加する数分布は低次数ではべき乗分布に沿わないことが判明した．

（ 2 ） 次数に応じた確率で頂点 v を選択し，新しい頂点が持この結果をもとに，本稿ではユーザの優先的選択を考慮したつエッジを接続する．

有向ネットワーク生成手法を提案した．提案手法はノードが新（ 3 ） 確率 p で v の隣接点を 1 つ選び，新しい頂点が持つ規接続を行う際に優先的選択の方法を複数から選択するものとエッジを接続する．確率 1 − p で (2) と同様の優先的選択を行う．

なっている．パラメータの変化による次数分布の変化の観察を（ 4 ） 残り m − 2 本のエッジの接続先を (3) と同様に決定行った結果，提案モデルはパラメータの調整によって実データする．の低次数で見られる分布と高次数で見られる従来のべき乗分

Holme-Kim モデルは BA モデルの拡張の一つであり，BA モデ布の両方を表現できることが判明した．この結果から，実際のルのクラスター係数が小さいという欠点を克服するために提案

SNS ではノードの次数によってパラメータが変化していると考されため，スケールフリー性と高クラスター性を持つ．

えられるため，今後は次数によってパラメータを変化させるモデルを作成し検証していきたい．

2. 3 CNN モデル
Connecting nearest-neighbor (CNN) モデル [4] は 1 つの頂点と2 関連研究
ここではネットワーク生成モデルの中でも，成長ネットワークに関する先行研究を説明する．

2. 1 BA モデル
Barabási-Albert モデル [2] は m0 個の頂点から開始し，目標の空の辺集合から開始し，目標の頂点数になるまで以下を繰り返すモデルである．
（ 1 ） 確率 1 − µ で新しい頂点をグラフに追加し，ランダムに頂点 j を選択し新規頂点と接続する (このとき新規頂点と jのすべての neighbor との間に潜在エッジを張る)（ 2 ） 確率 µ で潜在エッジをランダムに選択し，エッジに変表 1 データセットの各指標|V|

27,500,000|E|

8, 740, 471, 435

reciprocal follow

996, 963, 609

one-way follow

6, 746, 544, 217
2.05 × 10−5

D換する．

BA モデルは優先的選択を行うがクラスター性はなく，CNN モデルは優先的選択を行わないがスケールフリー性とクラスター性を表現できるモデルとなっている．

3 データセット
3. 1 概図 1 次数の確率分布

要

今回は，2015 年に収集した lang=ja の約 4 千万の Twitter ユー
ザのうち，その当時のフォロワー数が多い方から 2750 万ユー
ザについて，2021/12 （から 2022/1 にかけて）時点でのフォロワー，フレンドのリストを Twitter 社から購入して作ったフォローネットワークを解析した．フォローネットワークは有向グ
ラフ G = (V, E) で定義され，各 i ∈ V はユーザを，(i, j) ∈ E はi が j をフォローしているという関係を表す．なお，枝の両端のうちどちらかが 2750 万ユーザに含まれてない枝はフォローネットワークの作成時に削除している．また，ネットワークを解析する際の指標として以下を定義する．

In-degree
ユーザ i の In-degree I(i) は i の入次数であり，これは Twitterにおけるフォロワー数に該当する．

図 2 次数の確率の累積分布関数

Out-degree
ユーザ i の Out-degree O(i) は i の出次数であり，これは Twitter山なりの分布となっており，高次数では本来のスケールフリーにおけるフレンド数に該当する．

ネットワークにみられるロングテールの分布となっていること

Reciprocal-degree
ユーザ i の Reciprocal-degree R(i) は (i, j), ( j, i) ∈ E となるよ
うな j ∈ V の数で定義する．これは Twitter における相互フォが分かる．また，Out-degree が 103 と 104 の間に集中しているが，これは Twitter のフォロー制限の上限までフォローを行っているユーザが多いためと考えられる．

ロワー数に該当する．

Degree
ユーザ i の次数 deg(i) は I(i) + O(i) で定義する．

Reciprocal follow

1∑
Reciprocal follow はR(i) で定義する．
2 i

One-way follow
One-way follow は |E| −密度
有向グラフの密度 D は∑i R(i) で定義する．

|E|で定義される．
|V|(|V| − 1)

3. 2 解 析 結 果
27,500,000 ノード (|V| = 27, 500, 000) 全体が作るネットワー
クにおいて，各指標は図 1 のようになった．図 1，2 はそれぞれデータセットにおける Reciprocal-degree，In-degree，Out-degree，degree の確率分布と累積分布関数をプロットしたものである．
図 1 から各次数分布は低次数帯ではべき乗則に従っておらず，4 モデル概要
この節では，提案手法のモデルの解説を行う．なお，提案モデルの疑似コードは Algorithm1，2 に記載している．
提案モデルは入力として頂点数 N とパラメータ µ1 ，µ2 ，α が与えられ，ネットワークの頂点数が N になるまで確率的に以下を繰り返すモデルである．
（ 1 ） 確率 µ1 でフォロー行動を行う既存ノード i をランダムに選択する．その後，i は入次数に応じた確率でノード j をランダムに選択し接続を行う．その後， j は確率 α で i と接続を行う．
（ 2 ） 確率 µ2 でフォロー行動を行う既存ノード i をランダムに選択する．その後，i は (A2 )i j に応じた確率でノード j をランダムに選択し接続を行う．その後， j は確率 α で i と接続を行う．

Algorithm 1 generate graph(N, µ1 , µ2 , α)Require: N ∈ N, µ1 , µ2 >= 0, 0 <= µ1 + µ2 < 1, 0 <=α<=1
1: V = {0}2: E = ∅3: G = (V, E)
4: n = 1
5: while n < N do
6:

p = rand()7:
8:

A = adjacency matrix of G
if p <= µ1 then（ 3 ） 確率 1 − (µ1 + µ2 ) で新規ノード i をネットワークに加9:randomly select i from Vえる．この時，新規ノードは入次数に応じた確率で既存ノード10:

図 3 2-hop 先の優先的選択

j を選択し接続する．その後， j は確率 α で i と接続を行う．

11:j)+1select j with probability ∑ I((I(j)+1)j,i<else if p = µ1 + µ2 then12:

ここで，A は各試行時点でのネットワーク全体の隣接行列で，randomly select i from V

13:select j with probability ∑Ai j は枝 (i, j) が存在する場合に 1，存在しない場合には 0 とな

14:る行列であり，µ1 ，µ2 ，α は以下の条件を満たす実数である．

15:

•
•
•
•

0<
= µ1 + µ2 < 1µ1 >=0µ2 >=00<=α<=1

また，(1)，(3) でノード i が接続先としてノード j を選択する

else
i=n

16:

randomly select j from V

17:

V =V ∪i18:(A2 )i j2j,i (A )i j

n=n+119:end if

20:

add edge(G, i, j, α)

21: end while

確率，(2) ででノード i が接続先としてノード j を選択する確率はそれぞれ以下の値となる．
I( j) + 1
• ∑j,i (I( j) + 1)
(A2 )i j• ∑2j,i (A )i j
(A2 )i j は i から j までの 2-hop の経路の数，つまり j をフォローしている自分のフレンドの数となる．例えば図 3 では i のフォロー候補としては j と k が存在するが，(A2 )i j = 2，(A2 )ik = 1 であり， j は k よりも 2 倍の確率で優先的に選択される．

Algorithm 2 add edge(G, i, j, α)Require: Directed graph G = (V, E), i, j ∈ V, 0 <=α<=1
1: if (i, j) < E then2:

E = E ∪ (i, j)

3:

p = rand()4:

if p <= α and (i, j) < E then5:
6:

E = E ∪ ( j, i)
end if

7: end if(1)，(3) における優先的選択は BA モデルにおいてノードが新規参入した際の優先的選択行動と同一の行動であり，また (2)G1における 2-hop 先の優先的選択は Twitter では「自身のフレン|V|ドの多くがフォローしているフレンドをフォローする行為」にµ1

該当し，Twitter 上でも起こる可能性の高いフォロー行動であµ2
αり，i が (A2 )i j の値が大きい j をフォローした場合の方がネットある．各試行におけるユーザの行動は Holme Kim モデルと近いものとなっているが，Holme Kim モデルでは 2-hop 先のノードを選択する際は最初に接続した頂点の隣接点しか選択できな
いのに対して提案モデルでは全ての 2-hop 先のノードを選択できる点，提案モデルは 2-hop 先のノードも優先的選択を行うという点で異なっており，また確率 α による接続は Twitter におけるフォローバックに該当し，フォローバックを明示的に考慮する点も本モデルの特徴となっている．

5 実験・評価
5. 1 µ1 , µ2 の比率による変化
ここでは提案モデルによって生成されたネットワークと実G3G4G5G6G7

10,0000 0.15 0.30 0.45 0.60 0.75 0.90.9 0.75 0.60 0.45 0.30 0.1500.1
表 2 各グラフの生成時のパラメータ

ワークに含まれる三角形の数が増加するため，Holme Kim モデルや CNN モデルと同様にクラスター性を高めるための行動でG2データとの比較，また三つの行動の比率によるネットワークの変化の観察を行う．今回は表 2 で示すように頂点数 |V| = 10, 000，α = 0.1 を固定し，µ1 , µ2 を変化させた 6 グラフのネットワーク指標を分析した．各グラフについて各指標は表 3 のように，各グラフ次数分布と累積分布関数はそれぞれ図 4 から 17 のようになった．
図 4 から 17 から見て取れるように，reciprocal-degree をのぞ
く三つの次数分布がパラメータ µ2 の割合が増加するほど山なりになっていき，テールの部分が短くなっている．この山なりの分布は図 1 の低次数で得られた分布の傾向と一致しており，低次数のユーザのフォロー行動の多くは提案モデルの (2) に示す

2-hop 先のユーザに接続する行動である可能性がある．実デー
タは図 1 で見られるように低次数ではこの山なりの分布，高次表 3 各ネットワークの指標の値|V||E|
reciprocal follow
one-way follow
D⟨C⟩

G1G2G3109,26810,446
88,3760.00109
0.00165

108,030
10,196
87,6370.001080.00190109,067
10,28688,4950.00109
0.00257

G4
10,000109,637
10,38688,8640.001100.00487

G5G6G7108,022
10,46087,1010.001080.01238

107,657
10,59286,4730.00108
0.03321103,137
10,28982,5590.01030.12241G′5G′6G′7

124,622
27,871
68,8800.001250.03081

117,884
21,844
74,1950.00118
0.06749

104,949
13,19878,5520.001050.17760

表 4 各ネットワークの指標の値|V||E|
reciprocal follow
one-way follow
D⟨C⟩

G′1G′2G′3

140,955
42,80455,3460.001410.00857

136,350
39,50457,3420.001360.00922

134,705
36,85460,9970.00135
0.01181G′410,000129,837
32,59864,6410.001290.01914

図 4 G1 の次数分布

図 5 G1 の累積分布関数

図 6 G2 の次数分布

図 7 G2 の累積分布関数

数ではロングテールをもつべき乗分布となっているため，次数に応じて µ1 , µ2 の値が変わることによって次数分布を表現できる可能性がある．また reciproccal-degree の分布についても同等の変化がみられるがパラメータの変化による影響がその他の次数分布より少なく，この実験で変化をさせていない α によって分布が大きく変化すると考えられる．

5. 2 α の設定方法による変化

続する確率 α ji を以下で定義する．

α ji =I(i) + 1
I(i) + I( j) + 2

α ji は I(i) よりも I( j) が大きければ大きくなり， j は自分よりIn-degree の大きい i ほど接続 (フォローバック) しやすくなる．
この α ji は，より Twitter 上のフォローバックに近い確率でフォローバックが起こると考える．

先ほどのモデルではフォローバックの際にノードの特徴に関α ji が与える影響を調べるため，α 以外のパラメータを表 2 と係なく一定の確率を用いていたが，2 ノードの次数の積に応じ同様に設定し，パラメータ α として α ji を採用したグラフ G′1て接続確率を決定する Chung-Lu モデル [5] のように，次数に〜G′7 を作成し，グラフの性質の変化を観察した．生成した G′1応じて 2 点の接続確率を決定するものも存在する．そのためこ〜G′7 について，G1 〜G7 と同様に解析した結果，各指標は表 4，こでは，α を変化させることで発生する分布の変化を観察する．

次数分布が図 18〜図 31 になった．

本節では α のかわりに提案モデルの各試行において j が i に接各 Gi と G′i を比較すると，reciprocal-degree 以外の分布は同図 8 G3 の次数分布

図 9 G3 の累積分布関数

図 10 G4 の次数分布

図 11 G4 の累積分布関数

図 12 G5 の次数分布

図 13 G5 の累積分布関数様の性質を見せているが reciprocal-degree の分布に変化がみられ，G′i はよりその他の分布に形がより近づいている．これは

α ji を用いたことで I(i) に応じて R(i) が増えやすくなったためであると考えられる．また，µ1 が上昇するほど reciprocal followの割合が減少するという性質がみられた．i が j をフォローし∑た場合，I( j) は 1 増加するが k (A2 )k j の値は I(i) 増加する．これにより，I(i) > 1 の場合 (A2 )i j の増分の方が大きくなり，I(i)に応じた優先的選択よりも (A2 )i j に応じた優先的選択の方が，I( j) の大きい j が選ばれやすくなるため，α ji が小さくなりやすいのではないかと考えられる．

6 結論

本稿では，Twitter の日本人ユーザ 27,500,000 人から成るネットワークについての解析を行い，2-hop 先のノードを参照した優先的選択を行う成長ネットワークモデルを提案した．実デー
タの解析から，現在のネットワークの次数分布は低次数ではスケールフリーネットワークの特徴であるべき乗則に従っておらず山なりの分布になっており，高次数では従来のべき乗分布の性質を示すことが分かった．また，提案モデルは複数の優先的選択を行い，高いクラスター性を目指すモデルであったが，単純なパラメータでは実データの低次数で見られる分布と高次数で見られる分布のどちらか一方しか表現できなかった．この

図 14 G6 の次数分布

図 15 G6 の累積分布関数

図 16 G7 の次数分布

図 17 G7 の累積分布関数

図 18 G′1 の次数分布

図 19 G′1 の累積分布関数

結果から，実データではノードの次数に応じてパラメータが変化する必要があると考えられる．また，今回用いた実データはフォロワー数を上位から取得していることによるバイアスがある可能性があり，新たにフォロワー数によらないサンプリング

[2]
[3]

方法を用いたデータセットを作成し同様の検証を行っていくことで，Twitter のフォローネットワークの解析を行っていきたい．

[4]

7 謝

[5]

辞

本研究は JSPS 科研費 21H03446 の助成を受けたものです．

文

献[1] Duncan J Watts and Steven H Strogatz. Collective dynamics ofsmall-world networks. nature, Vol. 393, No. 6684, pp. 440–442,1998.
Albert-László Barabási and Réka Albert. Emergence of scaling inrandom networks. science, Vol. 286, No. 5439, pp. 509–512, 1999.
Petter Holme and Beom Jun Kim. Growing scale-free networks withtunable clustering. Physical review E, Vol. 65, No. 2, p. 026107,
2002.
Alexei Vázquez. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Physical Review E, Vol. 67, No. 5, p. 056104, 2003.
Fan Chung and Linyuan Lu. Connected components in randomgraphs with given expected degree sequences. Annals of combinatorics, Vol. 6, No. 2, pp. 125–145, 2002.

図 20 G′2 の次数分布

図 21 G′2 の累積分布関数

図 22 G′3 の次数分布

図 23 G′3 の累積分布関数

図 24 G′4 の次数分布

図 25 G′4 の累積分布関数

図 26 G′5 の次数分布

図 27 G′5 の累積分布関数

図 28 G′6 の次数分布

図 29 G′6 の累積分布関数

図 30 G′7 の次数分布

図 31 G′7 の累積分布関数