日本ソフトウェア科学会第 35 回大会 (2018 年度) 講演論文集

グラフ構造の成長と減退を表す指標の提案
松村 俊樹

首藤 一幸

グラフ構造は，Web ページの発展や SNS の利用者の増加に伴い，研究対象として注目を集めている分野である．特に，人間関係等を表すソーシャルネットワークや，電子メール等の一時的なやりとりを表すネットワークにおいて，要素間を繋ぐリンクは動的な変化が激しく，リンク予測問題としてモデル化や解析が進んでいる．リンク予測問題
は，ある要素間に将来的にリンクが発生するかどうかを推定し，ネットワークの成長を予測するものであるが，ネットワークの減退については考察されていない．本研究では，ネットワークの成長と減退の両方に焦点を当て，ネットワークの成長 · 減退を表すグローバル指標を提案する．そのために，リンクの発生しやすさを表す指標の一つである
Jaccard 係数と，それを応用して我々が定義したリンクの消滅しやすさを表す指標の両方を用いる．提案したグロー
バル指標は，現実のネットワークのデータセットを用いて実験し，妥当性を評価する．

において，要素間のリンクが将来的に消滅するかどう

1 はじめにかを推定することは重要である．

グラフ構造の研究は，SNS（ソーシャルネットワー

本研究では，リンク予測に用いられる指標の一つでキングサービス）の発展や，タンパク質の相互作用のある Jaccard 係数 [2] を応用し，ネットワークの成長ような生体ネットワークの重要性の高まりとともに，と減退の両方に焦点を当て，ネットワークが将来成長注目を集めている分野である．グラフの構造を解析すか減退どちらに向かっているかを表すグローバル指標

ることで，ノードの中心性やメッセージを送るためのを提案した．

最短路等の様々な特徴を見出すことができる．特に近本論文の構成は以下の通りである．2 章で言葉の定年のネットワークは，時系列毎のグラフ構造の変化が義や扱うグラフの前提を述べ，3 章でリンク予測問重要視されており，動的ネットワークの研究が進んで題について述べる．4 章では Jaccard 係数を応用し，いる．例えば，SNS やタンパク質の相互作用ネットネットワークの成長 · 減退を表すグローバル指標を提ワークにおいて，要素同士を繋ぐ将来のリンクを予測案する．5 章では，4 章で提案した指標の妥当性につする，リンク予測問題が有名である [1]．

いて現実のネットワークの時間変化のデータで実験をリンク予測問題は，ある 2 つの要素間に将来的に行い，6 章でまとめと今後の課題を述べる．

リンクが発生するかどうかを推定し，ネットワークの成長を予測するものであるが，ネットワークの減退に2 準備ついては考察されていない．一時的なメッセージのや本章では，本研究で用いるグラフ構造の前提や記号りとりを表すネットワークや，共購買ネットワーク等
An index of growth and decline of graph structure.
This is an unrefereed paper. Copyrights belong tothe Authors.
Toshiki Matsumura, Kazuyuki Shudo, 東京工業大学情報理工学院, Dept. of Mathematical and Computing
Science, Tokyo Institute of Technology.

について述べる．
グラフ構造は，ノードとそれらを繋ぐリンクからなるデータ構造である．例えば，SNS ではユーザをノード，ユーザ同士の友達関係をリンクとし，グラフ構造として解析できる．代表的なグラフ構造を成す
データを表 1 に示す．

表1

研究者の共著関係ネットワークなどがこの規則にグラフ構造を成す現実社会のデータの例

ネットワークSNS
WWW
共著ネットワーク
共購買ネットワーク

ノード
ユーザ
ウェブページ
著者
商品

リンク
フォロー関係ハイパーリンク
共著関係
共購買関係

従う傾向が強い．

• Jaccard 係数 (JC) [2]JC(vi , vj ) =|Γ(vi ) ∩ Γ(vj )||Γ(vi ) ∪ Γ(vj )|(2)

本 論 文 で は ，グ ラ フ を G(V, E) で 表 す．

Jaccard 係数は CN を正規化したもので，互い= {v1 , v2 , ..., vn } は ノ ー ド の 集 合 で ，E =の隣接ノードの総数のうち共通の隣接ノードの{(vi , vj )|vi , vj ∈ V, i ̸= j} はリンクの集合である．

割合が大きいほど 2 ノード間にリンクが張られノード数 |V | とリンク数 |E| はそれぞれ n, m とする．

やすいとする指標である．Jaccard 係数はノードノード v と隣接するノードの集合は Γ(v) = {w ∈の類似度としての意味合いも持ち，情報検索の分V |(v, w) ∈ E} と定義する．本論文で扱うグラフ G野でも用いられている．

は，連結で重み無しの無向グラフであり，自己ループ• Adamic/Adar (AA) [6]Vと多重辺を含まないものを仮定する．

AA(vi , vj ) =3 リンク予測問題

vk ∈Γ(vi )∩Γ(vj )リンク予測問題は，ネットワーク構造において，既知の部分から未知の部分を推定する問題である．例えば，SNS におけるユーザのリコメンド機能や，タンパク質の相互作用ネットワークにおける未知の相互作用の発見に用いられる．

ある．次数の低いノードを共通隣接ノードにもつほど，リンクが張られやすいとする指標である．

• Preferential Attachment (PA) [7]PA(vi , vj ) = |Γ(vi )| · |Γ(vj )|[3]．一方は，グラフ構造の性質を用いるものであり，他方は，ノード毎の属性情報を用いるものである．また，その 2 つを合わせたものもある [4]．ノードの属性情報を用いるアプローチは，解析するネットワークがもつ特徴に大きく依存してしまうため，本研究では，グラフの構造情報を用いたアプローチを考える．
グラフ構造からリンク予測を行うアプローチでは，リンクが張られていない各ノードペアを，様々な指標を用いてランキング付けすることを行う．これらの指標をリンク指標と呼び，以下はその具体例である．

• Common Neighbors (CN) [5]1(3)log |Γ(vk )|Adamic/Adar は CN に重みをもたせた指標でリンク予測のアプローチは大きく分けて 2 種類ある

CN(vi , vj ) = |Γ(vi ) ∩ Γ(vj )|∑(4)

PA は 2 つのノードの各次数が高いほどリンクが張られやすいとする指標であり，複雑ネットワークの生成モデルである Barábasi-Albert モデルに基づいたものである．

4 グラフの成長 · 減退を表す指標の提案
本研究では，ネットワークの指標を定義することが目的のため，[0, 1] の範囲に正規化された Jaccard 係数について考察する．リンク予測問題では，Jaccard
係数はリンクの発生しやすさを表すリンク指標であるが，これを応用してリンクの消滅しやすさを定義す(1)

CN は共通の隣接ノードが多いほど，そのノード間にリンクが張られやすいとする指標である．友達関係で例えると，共通の友人が多いほどその 2人も友人である可能性が高いとする手法であり，る．従来の Jaccard 係数を JC+ としたとき，リンクの消滅しやすさ JC− は，直観的には JC+ と相反すると考えられる．そのため，JC− を以下のように定義する．

表22002 年 8 月の Gnutella ネットワークのノード数 · リンク数と S(G)（時系列順）

時刻123456789

ノード数10,876

8,846

8,717

6,301

8,114

26,51822,68736,68262,586

リンク数

39,994

31,83931,525

20,77720,01365,36954,70588,328147,892+JC の総和27,78723,807

22,94019,491

24,16963,81452,99689,719152,193JC− の総和39,89631,751

31,44020,67225,89865,24354,597

88,123

147,624

4

S(G) × 10 (λ = 1.0)

-2.0

-2.0

-2.2

-0.59

-0.53

-0.041-0.062

0.024

0.023

4

S(G) × 10 (λ = 0.9)

-1.4

-1.2-1.4

0.47

0.26

0.140.150.15

0.10

4S(G) × 10 (λ = 0.8)

-0.69

-0.41

-0.58

1.4

1.0

0.33

0.36

0.29

0.17

4S(G) × 10 (λ = 0.7)

-0.024

0.40

0.25

2.5

1.8

0.52

0.57

0.42

0.25

S(G) × 104 (λ = 0.6)

0.65

1.2

1.1

3.5

2.6

0.70

0.79

0.55

0.32

S(G) × 10 (λ = 0.5)

1.3

2.0

1.9

4.6

3.4

0.89

1.0

0.68

0.40

JC− (vi , vj ) = 1 − JC+ (vi , vj )(5)4160000

リンク数140000

これらを用いて、ネットワークの成長 · 減退を予測

120000する指標 S(G) を定義する。S(G) の定義には、前述

100000の JC+ と JC− およびパラメータ λ を用いる。

80000

ノード数

60000

1S(G) = n(n−1)( ∑2(vi ,vj )∈E/−λ40000

JC+ (vi , vj )∑JC− (vi , vj )(6)20000)

0123456789(vi ,vj )∈E

この値が正の値を取ればネットワークは成長傾向に

図1

2002 年 8 月の Gnutella ネットワークのノード数とリンク数の推移あり，負の値を取ればネットワークは減退傾向にあることが見込まれる．適切な λ を定めることができれば，同種のグラフでも同様の結果が得られると考えられる．

5 実験
本章では，4 章で定義した指標 S(G) の妥当性を実験により考察する．具体的には，様々なパラメータ λで現実のネットワークの成長に則した値が得られるかどうかを調べる．

タセットを用いて行った．表 2 は，2002 年 8 月のGnutella ネットワークの概要である．Gnutella はファイル共有ソフトの一つであり，ノードはクライアント，エッジはクライアント間の繋がりを表す．

5. 2 評価
図 1 は，2002 年 8 月の Gnutella ネットワークのノード数とリンク数の推移である．リンク数の増減に着目すると，時刻 1 から時刻 4 までは単調に減少しており，その後は時刻 7 に一度落ち込むものの，増加

5. 1 データセット
実 験 は ，Stanford Network Analysis Project（SNAP）†1 で公開されているネットワークのデー†1 https://snap.stanford.edu/data/

傾向にあることがわかる．つまり，S(G) の値が時刻1 から時刻 4 までで負の値を取り，その後は時刻 7 以外で正の値を取れば理想的である．
今回用意したデータセットで実験を行った結果を示まれることが見込まれる．
× 10−4

λ=0.50.0005

5.0

λ=0.6

λ=0.7

λ=0.8

λ=0.9

λ=1.0

最後に，S(G) の定義の考察を深めることで，より良い結果が得られる別の定義ができるのではないかと

0.00044.0考える．また，本論文ではリンク指標として Jaccard

0.00033.0

係数を選択しグローバル指標化を行ったが，他のリ

0.00022.0

ンク指標に対しても一般化できることが望ましい．

0.0001

1.000

Jaccard 係数は SNS 等の人間関係のネットワークで-1.0-0.0001有効である一方で，交通ネットワーク等には逆効果に-0.0002-2.0なる．そのため，本論文のグローバル指標化を各リン-0.0003-3.01

図22345678

2002 年 8 月の Gnutella ネットワークの S(G) の推移（λ = 0.5, 0.6, 0.7, 0.8, 0.9, 1.0）

ク指標について一般化することが今後の課題である．
謝辞
本研究は JSPS 科研費 16K12406 の助成を受けたものです。本研究の一部は、国立研究開発法人新エネ

したものが表 2 の下部であり，それをグラフに表しルギー・産業技術総合開発機構（NEDO）の委託業務たものが図 2 である．これらを見ると，λ = 0.8, 0.9として行われました。

で，時刻 7 以外の 7 つの時刻で Gnutella ネットワー
クの成長 · 減退に則した結果が得られていることがわ

参 考 文 献かる．

[1] Linyuan Lü and Tao Zhou. Link prediction incomplex networks: A survey. Physica A: statisticalmechanics and its applications, Vol. 390, No. 6, pp.
1150–1170, 2011.
[2] Christopher D Manning, Christopher D Manning,and Hinrich Schütze. Foundations of statistical natural language processing. MIT press, 1999.
[3] Lise Getoor and Christopher P Diehl. Link mining: a survey. Acm Sigkdd Explorations Newsletter,Vol. 7, No. 2, pp. 3–12, 2005.
[4] Mohammad Al Hasan, Vineet Chaoji, Saeed
Salem, and Mohammed Zaki. Link prediction using supervised learning. In SDM06: workshop onlink analysis, counter-terrorism and security, 2006.
[5] Mark EJ Newman. Clustering and preferential attachment in growing networks. Physical review E,Vol. 64, No. 2, p. 025102, 2001.
[6] Lada A Adamic and Eytan Adar. Friends andneighbors on the web. Social networks, Vol. 25,No. 3, pp. 211–230, 2003.
[7] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, Vol.
286, No. 5439, pp. 509–512, 1999.

6 まとめと今後の課題
本論文では，Jaccard 係数を応用して，ネットワー
クの成長 · 減退を表す指標 S(G) を定義した．S(G)が正の値をとるとネットワークは成長傾向にあり，負の値をとるとネットワークは減退傾向にある．パラメータを λ = 0.8, 0.9 と定めることで，Gnutella ネットワークにおいて現実の成長ほぼ則した結果が得られることを実験で示した．今後，多種多様なデータセッ
トでも実験を行うことが望まれる．
また，今回の指標ではノードの増減については考察していない．ネットワークではノードの増減によるリンクの増減も当然起こり得ることであるため，ノードの増減を組み合わせることによってより良い指標が生