DEIM Forum 2013 E4-1

高多重度有向ネットワーク成長モデルの提案
加藤 翔子†

斉藤 和巳†† 静岡県立大学 経営情報学部 〒 422–8526 静岡県静岡市駿河区谷田 52–1
E-mail: †{b09032,k-saito}@u-shizuoka-ken.ac.jp
あらまし 高い多重度の有向リンクを生成することが可能なネットワークの成長モデルの構築へ向け，CNN(Connecting

Nearest Neighbor) モデルを多重有向グラフへ応用したもの (多重有向 CNN モデル) を考える．さらに，リンク多重度優先選択と呼ぶリンク生成方法を用いる確率を，多重有向 CNN モデルと混合させたモデルを新たに提案し，先行論文で提案した，BA(Barabasi-Albert) モデルを多重有向グラフに拡張したモデルと混合させたものも対象とし，現実ネットワークとその構造を比較した．現実ネットワークについては，高多重度リンクが出現するデータとして，Twitter のFavorite と Retweet を多重有向グラフ化したものを用いた．評価実験の結果，リンク多重度優先選択のパラメータを付加することで，提案 BA モデルについてはリンク次数と入次数，提案 CNN モデルについては平均多重度分布とジニ係数分布が，それぞれ類似することを示した．
キーワード

ネットワーク成長モデル，多重有向グラフ

Shoko KATO† and Kazumi SAITO†† School of Administration and Informatics, University of Shizuoka
52–1 Yada, Suruga–ku, Shizuoka, 422–8526 Japan
E-mail: †{b09032,k-saito}@u-shizuoka-ken.ac.jp

1. は じ め に
複雑ネットワークの成長モデルには，スモールワールドモデて，Twitter の Favorite と Retweet を多重有向グラフ化したものを用い，[4] で現実ネットワークにより類似すると示した提案 BA モデルとも比較する．その結果，リンク多重度優先選択

ル [1] やバラバシ=アルバートモデル [2] など，多くのモデルがのパラメータを付加することで，提案 BA モデルについてはリ提案されているが，その多くが単純無向グラフを生成するモデンク次数と入次数，提案 CNN モデルについては平均多重度分ルである．また，多重有向グラフへ向けたアプローチとしては，

布とジニ係数分布について，多重有向グラフに拡張したモデル

クラスタ係数の計算手法の提案 [3] などが先行研究として挙げより Favorite に近い構造や動向を実現できると示した．

られるが，グラフ自体を生成するモデリングに関する研究は見BA モデルや CNN モデルは，どのノード間にリンクを張るられない．従って，現実世界のネットワークの構造を表すことか，即ちノードの選択方法に注目したアルゴリズムであるが，が可能な，リンクの向きや多重度を考慮したモデルの提案が待

我々が提案するリンク多重度優先選択は，どのリンクの多重度たれる．

を増やすか，即ちリンクの選択方法に注目しているため，十分有向リンクの多重度が高い数値を取りうるネットワークのに新規性を有する研究であると考える．

成長モデルの構築へ向け，先だって発表した論文 [4] では，バ

本論文の構成は以下となる．まず，本研究に用いた 3 つのモ

ラバシ=アルバートモデルを多重有向グラフに拡張したもの

デルのアルゴリズムについて説明する．次に，評価に用いた(多重有向 BA モデル) と，それにリンク多重度優先選択と呼データの概要を述べるとともに，評価実験による結果と考察をぶリンク生成方法を用いる確率を新たに付加したモデル (提案報告する．最後に，本論文のまとめについて述べる．

BA モデル) を考え，現実ネットワークと比較した．本論文では，CNN(Connecting Nearest Neighbor) モデル [5] を多重有2. モ デ ル

向グラフへ応用したもの (多重有向 CNN モデル) を考え，さらに，前述のリンク多重度優先選択を多重有向 CNN モデルとノード集合 V とリンク集合 E からなる多重有向グラフを混合させたモデル (提案 CNN モデル) についても考える．評G = (V, E) とする．多重グラフとは、同一ノードペア間に複価実験では，高多重度リンクが出現する現実ネットワークとし数回リンクが生成されることを許容するグラフであり，E は多重集合として定式化される．以下では，ノード v ∈ V が始点となるリンクの本数をノード出次数 d+v

せたネットワーク生成モデルを提案する．2. 1 同様，新ノードとし，v が終点と生成確率を α とし，ノード数 M とリンク数 N 程度のネットなるリンクの本数をノード入次数 d−v と呼ぶ．また，リンクワーク生成では，α = M/N に設定する．この新ノードが始点

e = (u, v) ∈ E の多重度をリンク次数と呼び de と表記する．となるか終点となるかは 1/2 の確率で決まる．次に，新ノードまた，ノード v の隣接ノード集合を A(v) と表記する．リンク

は生成されずリンクのみ追加されるケースにおいて，潜在リン

e = (u, v) ∈ E に対して，x ∈ A(v), x =| u のとき f = (u, x)

ク選択とリンク多重度優先選択のどちらを選ぶかの確率を γ と

または f = (x, u) のリンクを考える．同様に，x ∈ A(u), x =| vする．リンク数 N のネットワーク生成アルゴリズムは以下とのとき f = (v, x) または f = (x, v) のリンクを考える．このなる．

ようにして，リンク e から導かれるリンク f の集合をリンク

e の潜在リンク集合 F (e) と呼ぶ．ここで，このモデルは多重S1. V = {u, v, x}, E = {e = (u, v)}, G = (V, E) で初期ネッを許すため，実リンク e = (v, x) と潜在リンク f = (v, x) は同トワークを設定する.

時に存在して良いとする．

S2. 確率 α で新ノード生成 S3.，さもなければ，リンク追加

2. 1 提案 BA モデル
本稿では，BA モデル [2] で提案されたのと同様に，確率−P (v) ∝ d+v や P (v) ∝ dv でリンクの始点や終点となるノード

S4. のいずれかを (N − 1) 回繰り返す．
S3. V に新ノード w を加え，ノード次数優先選択確率 P (v)
で v を選び始点か終点かで E に (w, v) か (v, w) を加える．

を選ぶノード次数優先選択を考える．そして，リンク多重度優S4. 確率 γ でリンク多重度優先選択でリンク追加 S5.，さも先選択と呼ぶ，確率 P (e) ∝ de でリンク e の多重度を一つ増なければ，潜在リンク選択でリンク追加 S6. を実行する．

やすメカニズムを新たに提案し導入する．

S5. リンク多重度優先選択確率 P (e) でリンク e を選び E に以下では，ノード次数優先選択とリンク多重度優先選択を混

e を加え，e の多重度を一つ増やす．

合させたネットワーク生成モデルを提案する．まず，新ノード

S6. リ ン ク 多 重 度 優 先 選 択 確 率 P (e) で e を 選 び ，x ∈生成確率を α とする．ここで，ノード数 M とリンク数 N 程A(v), x =| u または x ∈ A(u), x =| v であるような x を度のネットワーク生成では，α = M/N に設定する．ただし，ノード次数優先選択確率 P (x) で選び，始点と終点のどちらとこの新ノードが始点となるか終点となるかは 1/2 の確率で決なるかを 1/2 の確率で決める．x と u または v を端とする潜まるとする．次に，新ノードは生成されずリンクのみ追加され在リンク f を実リンクにし，E に加える．

るケースにおいて，ノード次数優先選択とリンク多重度優先選択のどちらを選ぶかの確率を β とする．リンク数 N のネットワーク生成アルゴリズムは以下となる．

S1. V = {u, v}, V = {(u, v)}, G = (V, E) で初期ネットワー
クを設定する.

S2. 確率 α で新ノード生成 S3.，さもなければ，リンク追加
S4. のいずれかを (N − 1) 回繰り返す．
S3. V に新ノード w を加え，優先選択確率 P (v) で v を選
び始点か終点かで E に (w, v) か (v, w) を加える．

S4. 確率 β でリンク多重度優先選択でリンク追加 S5.，さもなければ，ノード次数優先選択リンク追加 S6. を実行する．

S5. リンク多重度優先選択確率 P (e) でリンク e を選び E にe を加え，e の多重度を一つ増やす．
S6. ノード次数優先選択確率 P (v) で始点 u と終点 v を選びE に (u, v) を加える．
本稿では便宜上，この方法で生成するモデルを提案 BA モデルと呼ぶ．

2. 2 CNN モデル

本稿では便宜上，この生成法を提案 CNN 法と呼び，γ = 0とした特別なものを多重有向 CNN 法と呼ぶ．

3. 評 価 実 験
評価に用いたデータについての概要，および評価実験の結果とそれに基づく考察を述べる．

3. 1 データ概要
本稿で取り扱うデータは，Twitter の Favorite，Retweet の2 機能を多重有向グラフ化したデータである．いずれもユーザーをノード，「Favorite する・される」「Retweet する・される」の関係をリンクとしてネットワークを構築した．

Favorite ネットワークのデータ取得期間は 2011 年 5 月 1 日から 2012 年 2 月 12 日までであり，189,717 ノードと 33,456,690多重リンクをもつ有向ネットワークである．このデータはFavotter（注 1）の「今日の人気」ページから取得したものである．
Retweet ネットワークのデータ取得期間は 2011 年 3 月 7 日 0時から同月 11 日 12 時までであり，776,572 ノードと 2,181,151多重リンクをもつ有向ネットワークである．このデータは鳥海

CNN モデル [5] で提案されたのと同様に，ノード v の潜在ら [6] のデータを加工したものであり，転載元の発言にコメント

リンク集合 F (e) から潜在リンク f = (v, x) ∈ F (e) をランダをつけるなどして自分の発言として投稿する「非公式リツイー

ムに一つ選んで実リンクにする潜在リンク選択を考える．そしト」は除外している．て，2. 1 で提案したリンク多重度優先選択のパラメータをこちらにも導入する．
以下では，潜在リンク選択とリンク多重度優先選択を混合さ（注 1）：http://favotter.net/

71056105favorite
propBA0.7CNN
propCNN0.2

410
number of nodes

10
number of links

10favorite
propBA0.7CNN
propCNN0.2

4103102310210101

101

100

10 01001

10210310multiplicity

41010 0105102

図 1 Favorite リンク次数分布610degree81010

図 2 Favorite 入次数分布

3110favorite
propBA0.7CNNpropCNN0.20.90.8favorite
propBA0.7CNN
propCNN0.20.7210

Gini coefficientsavg. multiplicity

4101100.60.50.40.30.20.1

010 010110210310in−degree410

図 3 Favorite 入隣接数毎平均多重度分布

3. 2 実 験 結 果
図 1，2，3，4，5，6，7，8 は ，Favorite ネット ワ ー ク やRetweet ネットワークと同規模の人工ネットワークを多重有向
CNN モデルと提案 CNN モデルを用いて生成し，その構造を提案 BA モデルと共に比較した結果である．Favorite ネット
ワークのリンク次数分布は緑の□，入次数分布，入隣接数毎平均多重度分布，入隣接数毎平均ジニ係数分布は青の□でプロッ
トし，提案 BA モデルを用いたものはマゼンダ色の○，多重有向 CNN モデルを用いたものは黄色の×，提案 CNN モデルを用いたものはシアン色の＋でプロットした．
リンク多重度優先選択を用いる確率 β と γ は，Favoriteと の 比 較 で は β = 0.7, γ = 0.2 ，Retweet と の 比 較 で はβ = 0.6, γ = 0.2 で設定した．それぞれ，0 < β < 1，0 < γ < 1の範囲で実験し，β については，最もリンク次数分布が現実ネットワークと近似するものを目視で推定し設定値とした．γ については，値が高くなるに連れ平均多重度分布や平均ジニ係数分布が上にシフトするため，平均多重度分布や平均ジニ係数分布にバラつきが出るもののうち最も低い値とした．

5100 010110210310in−degree410図 4 Favorite 入隣接数毎ジニ係数分布

Favorite ネットワークとの比較において，図 3， 4 より，平均多重度分布とジニ係数分布ともに，提案 CNN モデルは他のモデルよりバラつきが顕著であり，Favorite に動向が類似しているが，全体的に現実より高い値をとっている．これは，提案CNN モデルにおけるノード次数やリンク次数の取りうる値がFavorite より広いことが影響すると考えられ，図 1， 2 のリンク次数分布と入次数分布から推察することができる．

Retweet ネットワークとの比較において，図 7， 8 より，平均多重度分布とジニ係数分布ともに，多重有向 CNN モデルと提案 CNN モデルは，提案 BA モデルよりバラつきが顕著であり，Retweet に動向が類似するが，多重有向 CNN モデルは全体的に現実より低い値をとり，提案 CNN モデルは高隣接数において高い値をとる．これは，提案 CNN モデルにおけるノード次数やリンク次数の取りうる値が Retweet より広いことが影響すると考えられ，図 5， 6 のリンク次数分布と入次数分布から推察することができる．

510761010retweetpropBA0.6CNN
propCNN0.2

61054

number of nodes

number of links

10retweet
propBA0.6
CNN
propCNN0.2

510410310210310210101101100010 010121010 010310101210310

multiplicity

41010510degree

図 5 Retweet リンク次数分布

図 6 Retweet 入次数分布

1retweetpropBA0.6
CNN
propCNN0.2

retweetpropBA0.6
CNN
propCNN0.2

0.9
0.8

avg. multiplicity

Gini coefficients

0.7
0.6
0.5
0.4
0.3
0.2
0.1

010 010110210in−degree

3104100 010図 7 Retweet 入隣接数毎平均多重度分布

4. お わ り に121010in−degree

310

図 8 Retweet 入隣接数毎ジニ係数分布謝辞

本 研 究 は, 科 学 基 礎 研 究 費 補 助 金 基 盤 研 究(C)(No.22500133) の補助を受けた.
高次数な有向リンクを有するネットワークの成長モデルの構築へ向け，提案 BA モデル，多重有向 CNN モデル，提案 CNN
モデルの 3 つのモデルについて，現実ネットワークとその構造を比較した．現実ネットワークについては，高多重度リンクが出現するデータとして，Twitter の Favorite と Retweet を多重有向グラフ化したものを用いた．
評価実験により，リンク多重度優先選択のパラメータを付加することで，どちらのモデルも多重有向グラフに拡張したモデルより Favorite に近い構造や動向を実現できると示したが，提案 BA モデルについてはリンク次数と入次数，提案 CNN モデ
ルについては平均多重度分布とジニ係数分布が優れた結果となり，課題が残る分析を互いが補う形となっている．
従って，今後の課題としては，BA モデル，CNN モデル，リンク多重度優先選択の 3 つを融合させたモデルについて検討する予定である．

文410

献

[1] D. J. Watts, S. H. Strogatz, “Collective dynamics of ‘smallworld’ networks”, Nature, Vol. 393, pp. 440-442, 1998.
[2] A-L. Barabasi, R. Albert, “Emergence of Scaling in RandomNetworks”, Science 286(5439):509-512, 1999.
[3] 鈴木智也，「情報伝達に基づいた有向重み付き複雑ネットワーク解析」，情報処理学会論文誌 数理モデル化と応用 2(1), 70-78,
2009[4] 加藤翔子, 斉藤和巳, 「リンク多重度優先選択を付与した嗜好
ネットワーク成長モデルの提案」, 第 9 回 ネットワーク生態学シンポジウム, 2012.
[5] A. Vazquez, “Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations”, Physics Review E 67, 2003.
[6] 鳥海不二夫，篠田孝祐，栗原聡，榊剛史，風間一洋，野田五十樹,「震災がもたらしたソーシャルメディアの変化」, ネットワークが創発する知能研究会 (JWEIN’11), 2011.