DEIM2020 C3-3(day1 p19)

複雑ネットワークにおける出現位置と役割に着目した
効率的な成長誘発エッジ検出手法
稲福 和史†

伏見 卓恭††

佐藤哲司†††† 筑波大学図書館情報メディア研究科 〒 305-8550 茨城県つくば市春日 1-2††† 筑波大学図書館情報メディア研究系 〒 305-8550 茨城県つくば市春日 1-2†† 東京工科大学コンピュータサイエンス学部〒 305-0982 東京都八王子市片倉町 1404-1
E-mail: †{inafuku,satoh}@ce.slis.tsukuba.ac.jp, ††takayasu.fushimi@gmail.com
あらまし

現実の複雑ネットワークの多くは，日々エッジ（及びノード）の追加が行われその構造を変化させる動的

ネットワークである．時間的に変化する動的ネットワークの変化点や変化・成長を誘発する構造を検出することは重要な課題である．本研究では，ユーザ間のコミュニケーションなどによって逐次的に追加されるエッジの出現時点におけるネットワーク構造を特徴量として，将来的な成長を誘発するエッジの抽出手法を提案する．提案手法では，ネッ
トワークの成長を強化と拡張の 2 つの役割で捉え，エッジの出現位置と役割でモデル化する．前者は一般的にネット
ワーク全体の指標である近接中心性で定量化されるが，計算量が大きいことから局地的な指標として隣接スコアを新たに定義する．後者は，リンク元とリンク先の隣接ノード集合の類似度により，強化・拡張の役割を定量化する強化拡
張スコアを定義する．いくつかの人工ネットワークと実際のデータを用いて提案する 2 種類のスコアを算出し，これらのスコアを用いてネットワークの成長を推定できることを検証した．その結果，情報拡散の性質をもつネットワー
クでは，，ネットワークの周縁部で強化する役割が高いエッジが成長を誘発する傾向にあることが明らかとなった．
キーワード 複雑ネットワーク，情報カスケード，Twitter
ネットワークである．フォローネットワークなら新たなユーザ

1 はじめにネットワークは，ノード (点) とそれらの繋がりを表すエッジ(線) を基本要素とするデータ構造である．現実世界の様々な事
象や関係性はネットワークで表現できる．例えば，Twitter やFacebook などの SNS では，ユーザ同士のフォロー関係をフォ
ローネットワークとして表せる．また，その他にも Web 上のハイパーリンクや道路網，商品の同時購入を表す共購買ネット
ワークなど様々な分野に渡ってネットワークが存在する．これらのネットワーク構造を理解することは，SNS のコミュニティ
発見や交雑する道路の発見など，現実世界の課題を解決する有益な知見発掘に繋がる．そのため，無向ネットワークの指標として，平均クラスタ係数 [14] や平均ノード間距離 [17]，次数分
布のべき指数 [1]，有向ネットワークの指標としてモチーフ [10]などが提案されるなど様々な研究が行われている．
その中でも，ノードやエッジの影響力を定量化するのは重要なタスクである．他のノードに対する影響力を定量化した既存指標として，期待影響度や媒介中心性 [6] などが挙げられる．期
待影響度は自身が情報を発するときにどれだけのノードに届けることができるかを定量化したもの，媒介中心性はそのノードがネットワーク中の各 2 ノード間の最短経路上にどの程度出現するかを定量化したものである．しかし，期待影響度や媒介中心性をはじめとする指標の多くは，時間経過を考慮しない静的ネットワークを対象としたものである．一方，実世界の多くのネットワークは，時々刻々とノードとエッジが追加される動的や新しいフォロー関係が生まれる度に，共購買ネットワークなら新たな購買が行われる度に，ネットワーク構造は変化する．
このような動的ネットワークについて，各種指標を算出する場
合には大きく分けて 2 つ課題がある．
第一の課題は，そもそも実際の影響が発生する前に影響力を推定したいという点である．期待影響度や媒介中心性は，計算時点のネットワークに対して与える影響の指標である．しかし，現実での応用を考えるとノードやエッジが出現した時点でそれらが将来的にどの程度影響を与えるのかを推定したい．これが実現できれば，SNS マーケティングやコミュニティの成長予測などに大きく貢献する．第二の課題は，ネットワーク構造が変化する度に各指標の計算をやり直す必要があるため，計算コストが大きい点である．例えば，期待影響度は，伝達できるノード数の期待値を求めるため，全てのエッジについて行う切断・
非切断の判定を充分な回数繰り返す必要がある．また，媒介中心性は，2 ノードの全組み合わせについて最短経路を求める必要があり，静的ネットワークですら大規模な場合には厳密解を求めることが困難である．このような静的ネットワークの指標を動的ネットワークに対してナイーブに適用し，構造変化の度に再計算を行うことは現実的でない．
これらの課題に対し，エッジ出現時の特徴を用いることで今後与える影響について分析できるのではないかと考えた．具体的には「ネットワークの何処に出現したか？」と「コミュニティを強化するか？拡張するか？」に着目する．とあるアイドルのファンからなるネットワークを想定する．このネットワー

クにおいては，中心部には密に結合する古参のファンが，周中心型のモデルである．まず，エッジ毎に拡散確率を設定する．

縁部には新参者のファンが存在していると考えられる．ここ

次に情報源となるノードから隣接するノードに対し，情報を伝で，古参同士，新参同士など近い者同士の間で行われるコミュ

達する．この時，情報伝達の成否は，はじめにエッジごとに設

ニケーションは，コミュニティの結合を強化する役割があると定した確率に独立に従うとする．これを繰り返すことで，情報いえる．逆に，古参と新参の壁を超えて行われるコミュニケー

拡散をシミュレートするのが独立カスケードモデルである．一ションは，コミュニティを拡張する役割があるといえる．この方，線形閾値モデルは情報の受け取り手側のノードを中心に情ように，ファン（ノード）間のコミュニケーションはエッジで報拡散をシミュレートする．各ノードには事前に重みの閾値が表現される．また新たに生成されるエッジの役割によって，ど割り当てられる．情報源ノードから情報が伝達し，各ノードはの程度コミュニケーションを誘発できるか，その影響力は異な受け取った重みが閾値を超えた場合にアクティブノードへと変るのではないだろうか．

化し，さらに隣接するノードへと情報を伝達する．吉川ら [18]

そこで，本研究では上述したエッジ出現時の 2 つの特徴を用は，上述した独立カスケードモデルや線形閾値モデルを拡張し，いてネットワークに与える影響力の分析，高影響エッジの抽出

ソーシャルネットワーク上での期待影響度曲線を推定する手法に取り組む．ネットワークの性質により，成長を誘発するエッを提案している．期待影響度とは情報が伝わったノード数を示

ジの特徴は異なると考えられることから，人工データと複数のす指標であり，これを事前に推定することで様々な応用が期待実データを用いて分析を行う．本研究の目的は，ネットワーク

できる．情報拡散の系列データを EM アルゴリズムによって学の成長を誘発するエッジが出現時にどのような特徴を持つか明

習し，学習したモデルのパラメータを用いたシミュレーション

らかにし，それら高影響なエッジを抽出する手法を確立するこによって期待影響度曲線を高精度に推定している．

とである．

特に Cheng ら [4] と吉川ら [18] の研究は，複雑ネットワーク

本論文の構成について説明する．まず 2 章で，ネットワーク

における情報拡散の規模を推定しようとする点において本研究上を情報が拡散する情報カスケードを扱った研究について説と同じモチベーションを持つ．これらの研究との差異は，ネッ

明し，本研究の立ち位置を明らかにする．その他，動的ネット

トワークの成長という観点に着目し，情報を届けたノード数でワークの生成モデルや分析に関する研究について説明する．3

はなく誘発されたエッジ数を推定の対象とする点，エッジ出現

章で本研究で取り組む問題設定について確認する．4 章で本研

時点で高速に算出できる特徴量を用いる点が挙げられる．

究の提案手法について，ネットワーク上の位置を効率よく定量化する手法とネットワークの拡張・強化を定量化する手法の 2つに大別して説明する．5 章で評価実験に用いるデータセット
をまとめ，6 章で実験内容，結果について説明しそれらの考察を行う．最後に 7 章で本研究をまとめ，研究の貢献と課題について述べる．

2 関連研究3 問題設定：誘発スコア
Twitter を始めとするソーシャルネットワークやメーリング
リストネットワークでは，情報がノード間を連鎖的に伝播する
情報カスケードが発生することが知られている．これは，ユー
ザをノード，インタラクション（Twitter のリプライやメールの送信など）をエッジとする動的ネットワークにおいては，エッジの出現が他のエッジの出現を誘発することであると捉えら

動的ネットワークに関連する研究と本研究の立ち位置についれる．本研究では，動的ネットワークで出現するエッジが，将て説明する．人から人へと情報が伝わる時，情報は二者の間で来的にどの程度のエッジ出現を誘発するのかに着目する．情報やりとりされるだけでなく，受け手が新たな人へと伝達するこ拡散モデルの研究で用いられる線形閾値モデル [15] を応用し，とでより広く拡散する．この情報伝達の連鎖現象を情報カス式 2 で示すエッジの誘発スコア it (u, v) を定量化する．

ケード [2] と呼び，複雑ネットワーク上でこれをモデル化する

図 1 を例に説明する．まず，図 1(a) のノード va , vb , vc

研究が広く取り組まれている．以下，この情報カスケードに関とエッジ e1 , e2 からなるネットワークを考える．ここでは，連する研究について説明する．

時刻 t = 1 において，ノード va から vb に向けて，エッジ

Cheng ら [4] は，Facebook における写真共有において，カ

e1 = (va , vb ) が追加される．その後，同様に時刻 t = 2 におい

スケードがその後も成長を続けるかの予測を行っている．このて，エッジ e2 = (vb , vc ) が追加されている．このネットワーク

研究では，時系列的特徴と構造的特徴がカスケードサイズ予測

では，va から vb ，vb から vc へと連鎖的に情報が伝達されていの重要な変数であることを示している．また，拡散する情報自る．この時，e1 = (va , vb ) は e2 = (vb , vc ) の出現を誘発してい体の分析として，川本ら [19] はマイクロブログ上での社会的影るといえる．すなわち，時刻 t に出現した v への入エッジが，響力を持つ情報カスケードの早期検知を行っている．Twitter

時刻 t 以降のノード v からの出エッジを誘発するとみなす．こ上で広く拡散した社会的影響力（震災情報やデマ等）を持つツのようにあるエッジが誘発した後続するエッジの数を基本的な

イートについて，テキスト特徴量やネットワーク特徴量が与え誘発スコアとする．

る影響を明らかにしている．また，情報拡散モデルとして広出エッジが複数の入エッジによって誘発されるケースにつく用いられる独立カスケードモデル [7] [8] [9] と線形閾値モデいて，図 1(c) を例に説明する．エッジ e2 = (vb , vd ) に着目

ル [15] [16] について説明する．独立カスケードモデルは送信者

すると，時刻 t = 3 以降に誘発される vd からの出エッジは

e4 = (vd , ve ), e5 = (vd , vf ), e6 = (vd , vg ),e7 = (vd , vh ) の 4 本

t
=1 t
=2

存在する．そのため，エッジ e2 = (vb , vd ) の誘発スコアを 4 としたいところだが，vd にはもう一本の入エッジ e3 = (vz , vd ) が

t
=2

t
=1

存在する．この時，vd の 4 本の出エッジは，これらの 2 本の入

t
=4

t
=3

エッジによって誘発されたと考え，誘発スコアを e2 = (vb , vd )と e3 = (vz , vd ) の 2 本で分け合うこととする．
また，誘発したエッジが間接的に誘発したエッジも誘発スコアに含めることとする．例えば，上述したように e2 = (vb , vd ) と(a) e1 により e2 が誘発される(b) e3 = (vd , vb ) に よ り
i1 (va , vb ) のスコアが確定する

e3 = (vz , vd ) は vd からの 4 本の出エッジを誘発している．そのうちの e5 = (vd , vf ) に着目すると，その先に更に e9 = (vf , vi )

t
=10

t
=3

と e10 = (vi , ve ) の 2 本のエッジが存在することが分かる．こt=4

れらもまた，e2 = (vb , vd ) と e3 = (vz , vd ) とによって誘発されたエッジであるとみなせる．最終的に，e2 = (vb , vd ) とさらに 2 本のエッジでそれらを分け合うため，誘発スコアはそt=8

れぞれ 3.0 となる．

st ((u, v)) =| OV(v)|| IV(v)|


0




it ((u, v)) =

t
=2

t
=1

e3 = (vz , vd ) は合計で 6 本のエッジを誘発しているといえる．

t
=5
t
=7

t
=9

t
=6

(1)

(| OV(v)| = 0)(Σst (u, v) + x∈OV(v)(| OV(v)| > 0){st ((v,x))+it ((v,x))})| IV(v)|(c) 複数のエッジによって誘発される場合及び誘発が連鎖する場合

図 1: 誘発スコアの模式図(2)
また，図 1(b) のようなケースにおいて上述した算出方法で

ワーク（コミュニティ）を強化したのか拡張したのかという特は，e1 = (va , vb ) の誘発スコアが 2 となるように古いエッジほ徴が，ネットワークの成長と大きく関わると考えた．そこで，

ど誘発スコアが次々と累積され大きくなってしまう問題がある．

エッジの「出現位置」と「強化・拡張」を定量化する手法を提これに対処するため，各エッジについてスコアを確定するタイ

案する．まず，本研究で用いる用語や変数について整理する．

ミングを設ける．ノード v への入エッジの誘発スコアは，スコその後，ネットワーク上の「位置」を効率よく定量化する手法，

アが 0 を上回っている状態で，新たにノード v への入エッジがリンク元とリンク先の関係に基づき「強化・拡張」を定量化す出現したタイミングで確定する．

る手法について説明する．

図 1(b) で時系列に構造変化を追いながら説明する．まず，
時刻 t = 1 で e1 = (va , vb ) が出現する．この時点で誘発スコ

4. 1 準備

ア i1 (va , vb ) は 0 である．次に，時刻 t = 2 で e2 = (vb , vc ) が本研究で用いる用語や変数について整理する．提案手法出現する．これは誘発されて出現されたエッジであるので誘発

は，ノード集合 V と有向エッジ集合 E からなる有向グラフ

スコア i1 (va , vb ) = 1 となる．時刻 t = 3 で vb に対して新たG = (V, E) を対象とする．ここで，ノードは SNS などにおけな入エッジ e3 (vd , vb ) が発生する．この時 e1 (va , vb ) の誘発ス

るユーザを表し，有向エッジ e = (u, v) はユーザ u から v へ

コアは 1 なので，スコアが確定する．時刻 t = 4 で新たなに情報を伝達するなどのコミュニケーションを表す．特に，本稿

e4 = (vb , ve ) が出現するが，これは e3 = (vd , vb ) のみによってでは時間とともにエッジが 1 本ずつ追加されることで成長す誘発されたエッジであるとみなす．これにより，古いエッジほる動的グラフを対象とする．時刻 t までに行われたコミュニ

ど誘発スコアが大きくなることを防ぐ．

ケーションを表す有向エッジの集合を E (t) = {e1 , e2 , ....., et }誘発スコアはネットワークの成長と共に累積していく値であで表す．このとき，はじめてコミュニケーションを行ったノーるが，本研究ではこれをエッジ出現時の特徴から分析・推定すドを追加したノード集合 V (t) を定義する．そして，グラフ

ることを目指す.

G(t) = (V (t) , E (t) ) におけるノード u の隣接ノード集合を
N V (t) (v) = {(u, v) ∈ E (t) ∨ (v, u) ∈ E (t) } と表記する．

4 提案手法4. 2 ネットワーク上の位置の推定手法：隣接スコア

1 節でも説明したように，動的ネットワークにおけるノード

ネットワーク上の位置を求める方法として，近接中心性やエッジの影響力を定量化・予測することは重要なタスクであ(Closeness Centrality) [6] を用いることが考えられる．しかし，る．我々は，エッジがどの位置に出現したのか，そしてネット

近接中心性は計算量が大きく，ネットワークを更新する度に最初から計算をやり直すのは現実的ではない．そこで，新規のす．実データにおいては，同一のノードペア間に同じエッジがエッジがネットワーク上のどの位置に出現したかを高速に近似付与される重複エッジが存在する．これを異なるエッジとみなする手法を提案する．

しエッジ数をカウントしたものが動的エッジ数，同じエッジで

近接中心性は多くのノードにより短い距離で到達できるほど中心部だとする指標である．極端なケースとして，自ノードかあるとみなすのが静的エッジ数である．それぞれのネットワー
クの詳細について，以下で説明する．

らすべての他ノードに直接リンクしている場合，近接中心性は1 になる．すなわち，直リンク数が多いほど中心部に位置しや
すいといえる．そこで，隣接ノード集合のサイズが大きいほど

表 1: ネットワークのノード数及びエッジ数
ネットワーク名

ノード数

静的エッジ数 動的エッジ数

中心部に位置するとみなす隣接スコアを提案する．本研究では，

CNN1K-NW

497

994

994

エッジ毎にスコアを算出したいので，エッジの両端から隣接

CNN10K-NW

5,032

9,994

9,994

ノード集合を取得する．それらの和集合サイズをネットワーク
全体のノード数で除して正規化した値を隣接スコアとし，ネッ
トワーク上での位置指標として用いる．具体的には，有向エッ

Reply-NW

1,233

1,622

1,971

Mention-NW

31,94744,56651,472Retweet-NW

45,80462,81774,380

Eucore-NW

984

24,926332,330

ジ et = (u, v) の隣接スコア nt (u, v) を時刻 t におけるノード

u と v の隣接ノード集合を用いて式 3 のように定義する．
nt (u, v) =|N V (t) (u) ∪ N V (t) (v)||V (t) |5. 1 Connecting Nearest Neighbor (CNN) モデル(3)

また，隣接ノード集合の大きさはノードの次数に等しい．そのため，本手法は次数中心性 [6] の拡張であるともいえる．

4. 3 ネットワークの強化と拡張：強化拡張スコア

Connecting Nearest Neighbor モ デ ル (以 下 ，CNN) は ，Vazquez [13] により提案された「友達の友達は友達になる」
性質を有するネットワーク生成モデルである．新たなエッジとノードを追加する処理，ポテンシャルリンクを実リンクへと変換する処理を確率 p で選択することを繰り返しネットワー

情報拡散ネットワークにおいて新たなエッジが出現するとき，クを構築する．ポテンシャルリンクとはいわばエッジ候補のリンク元とリンク先との関係によりそのエッジの役割は大きことであり，これらからエッジを選ぶことで「友達の友達は友く異なる．例えば，リンク元とリンク先が同一のコミュニティ

達になる」性質が生まれている．処理の選択を行う確率パラを形成している場合には，エッジの役割はおしゃべりなどのコメータを p = 0.5，ループ回数 l を 100, 1,000, 2,000, 3,000,

ミュニティを強化する情報伝達である．逆に，リンク元とリン

4,000, 5,000, 6,000, 7,000, 8,000, 9,000, 10,000, 100,000 とし，

ク先の関係が薄い場合には，情報拡散やはじめましての挨拶な

各ループ回数毎にそれぞれ 10 種，合計 120 個のネットワーク

どのコミュニティを拡大する役割だといえる．本節では，このを生成した．ネットワークの規模はループ回数 l に比例して大ようなエッジの役割を定量化する強化拡張スコア j((u, v)) を提きくなる．また，p = 0.5 であるので，エッジ数はおよそルー案する（式 4）．

プ数と等しく，ノード数はループ数の 21 程度である．加えて具体的には，エッジ両端のノードに関する隣接ノード集合のCNN モデルでは重複エッジが発生しないので，静的エッジ数

Jaccard 係数を求めることで，リンク元とリンク先の関係の強と動的エッジ数の数は等しい．生成した 120 個のネットワーク

さを定量化する．

のうち，表 1 には，ループ数 l=1000 の CNN1K-NW とルー

j((u, v)) =|N V (u)) ∩ N V (v)||N V (u) ∪ N V (v)|プ数 l=10,000 の CNN10K-NW を示した．

(4)
5. 2 Higgs Twitter Dataset

Jaccard 係数は 2 つの集合の類似度を測る指標であり，共通集

Higgs Twitter Dataset 1 [5] は，2012 年 7 月にヒッグス粒子

合を和集合で除することで算出する．あるエッジについて，2が発見された際の，ヒッグス粒子に関するツイートのインタラ

つの隣接ノード集合の重複が多いほど関係が強く，逆に重複がクション（リプライ，メンション，リツイート）を収集したデー

少ないほど関係の薄いノード間をつなぐエッジとなる．すなわ

タセットである．具体的には，2012 年 7 月 1 日から 2012 年 7

ち，エッジ et = (u, v) について，Jaccard 係数 j(et ) が 1 に近

月 7 日の期間における，lhc, cern, boson, higgs のキーワード

いほどネットワークの強化，0 に近いほどネットワークの拡張を含むリプライツイートとメンションツイートの送信ユーザとを意味する．

宛先ユーザ，キーワードを含むツイートの投稿者とそれをリツイートしたユーザ，各インタラクションの発生時刻が記録され5 データセットている．つまり，時刻 t にユーザ u がユーザ v へとリプライを本研究の評価実験では，Connecting Nearest Neighbor モデ

送ると，ユーザ u からユーザ v に有向エッジ et = (u, v) が付ルで生成した人工ネットワークと Twitter のインタラクション与される．このようなエッジの付与をインタラクションの発生

データセット及び電子メールのやりとりのデータセットを用い順に行うことで，動的なネットワークを構築する．本研究では，る．ここでは，これらのデータセットについて説明する．
ネットワークのデータソース，呼称，規模について表 1 に示

1：https://snap.stanford.edu/data/higgs-twitter.html

インタラクション種別に 3 種のネットワークを構築した．各均値を用いる．

ネットワークの規模を表 1 に示す．なお，本研究では構築され

6. 1. 2 近似の妥当性

たネットワークのうち，最終時刻における最大連結成分を抽出

5 節で構築したネットワークを対象に隣接スコアと近接中している．また，本節冒頭でも言及したとおり，実データには心性を算出し，その妥当性を評価する．具体的な評価指標と同じノードペア間に繰り返しエッジが付与される重複エッジがして，上位 (下位)x%のエッジを抽出した際の再現率を算出し存在するが，本研究ではこれらは異なるエッジとして扱う．リ

た．近接中心性上位 x%(及び下位 x%) のエッジを正解エッジ

プライツイートからなるネットワークを Reply-NW，メンショとし，隣接スコア上位 x%(及び下位 x%) のエッジを抽出する

ンツイートからなるネットワークを Mention-NW，リツイート

時，正解エッジをどの程度抽出できるか（再現率）を検証すからなるネットワークを Retweet-NW とする．

る．CNN4 種 (ループ回数 l = 100, 1, 000, 10, 000, 100, 000)，

5. 3 email-Eu-core temporal network

Reply-NW, Mention-NW, Retweet-NW, Eucore-NW，合わ
せて 7 つのネットワークで実験した．また，ベースラインとし

email-Eu-core temporal network 2 [11] は，ヨーロッパの研てランダムにエッジを抽出した際の再現率も併せて算出した．

究機関における電子メールのやり取りを収集したデータセット

図 2 に正解エッジ割合に対する再現率の推移を示す．横軸が正である．時刻 t にユーザ u からユーザ v にメールを送信したと解エッジの割合，縦軸が再現率，青いプロット線が提案手法に，き，有向エッジ et = (u, v) が記録されている．データの収集期

赤い線がランダム抽出に対応する．

間は 803 日間であり，研究機関外との送受信は含まれていない．

上位 10%のエッジを正解とすると，ランダム抽出したエッジ

本データセットから構築したネットワークを Eucore-NW とすに正解が含まれる確率は 10%である．赤いプロット線に着目する．こちらも 5. 2 節と同様，最終時刻における最大連結成分をると，実際に再現率はおよそ x%を示し，一定のペースで推移し抽出しており，重複エッジは異なるエッジとして扱っている．

6 評価実験

ている．一方，提案手法について，CNN ではネットワークの規模が大きいほど再現率が下がる傾向にあるものの，ランダム抽
出のそれを大きく上回っている．また，実データも全てのネッ

本節では 5 節で構築したネットワークを用いて，提案手法のトワークでベースラインを上回る結果となった．特に図 2(c),

有効性を評価する．隣接スコアと強化拡張スコア，誘発スコア

図 2(d) の Eucore-NW は，上位・下位ともに 8 割近い再現率の関係について示す．

を示している．また，Reply-NW, Mention-NW, Retweet-NW
もベースラインと比較して概ね 20%程度高い再現率を示してい

6. 1 隣接スコアはネットワーク上の位置を効率よく定量化できるかる．Reply-NW のみ，Recall@worst10 ，Recall@worst20 が低めであるものの，Recall@worst30 以降は大きくスコアを伸ば

4. 2 節で，エッジ両端の隣接ノード集合からネットワーク上している．これらのことから，近接中心性の上位（下位）エッの位置を効率よく定量化する隣接スコアを提案した．この手法

ジ抽出について，提案手法の隣接スコアは有効だといえる．

について，本節では効率性と正確さの観点から評価を行う．
また 5 節で説明したように，CNN は規模別に 12 種類，さ1.0

らにそれぞれの規模について 10 パターンの異なるネットワー

100 (
100 (
1000 (
1000 (
10000 (
10000 (
100000 (100000 (0.4
0.2

ワークに対し様々な評価指標を算出するが，特に断りの無い限

0.0

20

40

り，CNN の評価指標は各規模毎に平均値を取るものとする．
隣接スコアが正しくネットワーク上の位置を定量化している
Recall@topx

か評価するために，近接中心性との比較を行う．近接中心性は，標である．しかし，最もよく知られている Freeman による近60x%る必要があることから，比較に用いることができない．そこで，
非連結なノードとの最短経路長は無限であるとみなし，調和平均を用いてスコアを算出する調和近接中心性 [12] [3] を用いる．

)
)
)
)

0.6
100 (
100 (
1000 (
1000 (
10000 (
10000 (
100000 (100000 (

0.4
0.2

)
)

0.0

100

20

1.0

0.8

0.8

0.6
reply (
reply (
mention (mention (retweet (retweet (eucore (eucore (

0.4

0.0

20

40

60

x%

80

40

60

x%

80

)
)
)
)
)
)
)
)

100

(b) CNN 下位

1.0

0.2

接中心性 [6] は，ネットワークが一つの連結成分から構成され

80

)
)

(a) CNN 上位

6. 1. 1 エッジの調和近接中心性あるノードから他のノードへ平均的にどれくらい近いか示す指Recall@worstx

0.8

0.6

)
)
)
)
)
)
)
)

100

(c) Higgs 及び Eucore 上位

Recall@worstx

トワークは合計で 120 個存在する．本節においては，各ネット

Recall@topx

クを生成している．すなわち，CNN によって生成されたネッ

1.0

0.8

0.6
reply (
reply (
mention (mention (retweet (retweet (eucore (eucore (

0.4
0.2
0.0

20

40

60

x%

80

)
)
)
)
)
)
)
)

100

(d) Higgs 及び Eucore 下位

図 2: 上位/下位 x%抽出時の再現率

また，隣接スコアはエッジに関する指標であるのに対し，調和
近接中心性はノードに対して求められるスコアである．そのた6. 1. 3 計 算 効 率

め本研究では，エッジ両端ノードの調和近接中心性スコアの平5 節で構築したネットワークを対象に隣接スコアと近接中心性を算出し，その処理時間を比較する．CNN 全 12 種と Reply-

2：https://snap.stanford.edu/data/email-Eu-core-temporal.html

NW, Mention-NW, Retweet-NW，Eucore-NW について，両指標の計算時間を図 3 に示す．CNN についてはネットワーク
数が多いことから，折れ線グラフで示した．横軸がネットワー

表 2: 重回帰分析の決定係数・偏回帰係数
偏回帰係数

ネットワーク

決定係数 R2（バー）が隣接スコア，オレンジの線（バー）が近接中心性に

CNN1K-NW

0.167

1.051

0.820

対応する．まず，CNN について，どの規模においても隣接ス

CNN10K-NW

0.170

1.080

0.879

コアが 10 倍から 100 倍程度高速に動作していることが分かる．

Reply-NW

0.154-0.3370.418

また規模が大きくなるほど，処理時間の差も大きくなる傾向に

Mention-NW

0.654-0.6800.520

ある．実データについても，比較的小規模な Reply-NW の処

Retweet-NW

0.699-0.761

0.455

Eucore-NW

0.042

0.660

-0.249クの規模及び種別，縦軸が計算にかかった秒数を示し，青い線

理時間差は 10 倍程度，最も大規模な Retweet-NW では 100 倍

隣接スコア 強化拡張スコア

近い差となっており，CNN と同様である．このことから，提案手法は近接中心性よりも効率よくネットワーク上の位置を定は，エッジの出現時期による不均衡を補正するための処理であ量化できるといえる．

る．例えば，最初に出現する e1 の隣接スコアは，ネットワー
ク G 中に e1 を構成する 2 ノードしか存在しないため，必ず 1( )になる．また，最終時刻 T に出現するエッジ eT は，その後に102発生するエッジがデータセット中に存在しないため，誘発スコ

101

アが 0 以上になることはない．このようにデータセットが有限であるため生じる問題を回避するため，データセットの中央部100分を分析に用いることとした．なお，表 1 に示すネットワーク

10 1の規模や，誘発スコアは最終時刻 T 時点のものである．

10 2

6. 3 隣接スコア，強化拡張スコア，誘発スコアの関係

10 3

102

103

(

104

)

105

隣接スコア，強化拡張スコア，誘発スコアの関係を分析する．

3 指標の散布図を図 4 に示す．横軸が強化拡張スコア，縦軸が隣接スコア，プロット点の色が誘発スコアの色に対応してい(a) CNNる．なお，誘発スコアはランキングをとった上で 0-1 の範囲に収まるように正規化を行った．色が赤いほど誘発スコアが高く，

102

青いほど誘発スコアは低い．また，誘発スコア i(e) = 0 のエッ

( )

101

ジについてはノイズとして除外している．
図 4(d) の Mention-NW と図 4(e) の Retweet-NW をみる

100と，左上から右下にかけて色が青から赤へと顕著に変化してい10 1

る．これはネットワークを周縁部で強化するエッジほど，誘発10 2

スコアが高くなる性質を持つことを意味する．これらのエッジ

10 3

は，いわばネットワークの周縁部で新たなコミュニティ形成を
reply

mentionretweeteucore担うエッジだと考えられる．コミュニティそのものを誘発することから，誘発スコアが大きくなる傾向になるといえる．

(b) Higgs 及び Eucore

この結果をより定量的に評価すべく，隣接スコアと強化拡張

図 3: 隣接スコアと近接中心性の計算時間比較

スコアを説明変数，誘発スコアを目的変数として重回帰分析を行った．この際，各変数のべき乗分布を考慮しいずれも常用対数をとった．自由度調整済み決定係数 R2 と各説明変数の偏回

6. 2 誘発スコアの推定

帰係数を表 2 に示す．Mention-NW と Retweet-NW の決定係

本 節 で は 隣 接 ス コ ア と 強 化 拡 張 ス コ ア を 用 い て ，後数はいずれも 0.7 弱であり，一般に説明力が高いといえる数値

続 す る エッジ の 誘 発 ス コ ア に つ い て 分 析 す る ．分 析 対 象

である．ここで重要なのは，説明変数の隣接スコアと強化拡張

は，CNN1K-NW, CNN10K-NW，Reply-NW, Mention-NW,

スコアはいずれもエッジの出現時点で算出される指標であるのRetweet-NW，Eucore-NW とした．なお，CNN は各規模毎にに対し，目的変数の誘発スコアは最終時刻に算出される指標で10 パターン存在するが，本節では表 1 に示したネットワーク

ある点である．すなわち，Mention-NW と Retweet-NW に関を用いる．

しては，エッジの出現時点で大きな誘発スコアを持つエッジのまた，本研究で用いるネットワークは，時系列のエッジリス

推定が可能だといえる．

ト E = {e1 , e2 , ...., eT }(T は最終時刻) によって与えられる．本

一方，CNN10K-NW，CNN-100K-NW，Reply-NW，Eucore-

節では，このエッジリストのうち前半の 25%と後半の 25%を

NW については目論んだ結果は得られなかった．この理由は除いた中央部分 50%のエッジについてのみ分析に用いる．これ

6. 4 節で考察する．

(a) CNN1K-NW(b) CNN10K-NW(c) Reply-NW(d) Mention-NW(e) Retweet-NW(f) Eucore-NW

図 4: 隣接スコア，強化拡張スコア，誘発スコアの関係 ((i(e) > 0))

6. 4 考察Eucore-NW は，メンションやリツイートと異なり情報の拡散

本節では，主に 6. 2 節で行った実験について考察を行う．

が発生しにくいネットワークだと考えられる．例えば，Eucore-

まず，図 4 で顕著に傾向が現れ重回帰モデルが高い精度を

NW は電子メールのネットワークであるが，拡散する必要の示した Mention-NW と Retweet-NW について考察する．これあるメールは (データセットの対象外である) メーリングリス

らのネットワークで多くのエッジを誘発する傾向にあったのトなどで一斉に配信されるのではないか．また，Twitter におは，ネットワークを周縁部で強化するエッジであるが，これらけるリプライは，そもそも限られたユーザ同士のやり取りのたは具体的にどのような役割を果たしたのだろうか．そもそも，めの機能だといえる（多くのユーザと共有するためにはリツ

多くの影響を与えることは，多くの会話や情報発信を誘発す

イートやメンションが用いられる）．すなわち，Reply-NW やることを意味する．ネットワークの周縁部ではノードやエッジ

Eucore-NW は，本研究で議論するコミュニケーションが拡散が少ないことから，中心部と比べて自身が他者に与える影響

していくような変化に乏しいネットワークである．そのため，は大きい．その上で親しい相手とリンクしネットワークを強化

誘発スコアによって成長を表せなかったと考えられる．また，したということから，これらのエッジは周縁部の小規模なコ

CNN モデルのネットワークについて，ノード追加時に設定さミュニティの起点であったと考えられる．コミュニティの起点

れるエッジがポテンシャルリンクを誘発すると想定していたが，は，その後のコミュニティ全体を誘発するので，必然的に大き

期待通りの挙動を示さなかった．これについては，ノード追加

な誘発スコアを示す．また，メンションやリツイートはシェア

処理と実リンク変換処理の確率パラメータ p の設定により好転の意味合いが強い行動でもある．すなわち，情報が狭いコミュする可能性がある．後者の処理が多くなるように p を設定する

ニティに閉じず拡散される性質も併せ持つ．これらを踏まえる

ことで，誘発されるエッジが増え，提案手法と誘発スコアの間と，Mention-NW や Reply-NW は，ネットワークの周縁部にに何らかの関連が観察できると期待している．また，異なるア

おける小規模なコミュニティの出現・成長を促し，さらにそのプローチとして CNN で設定したネットワークを用いた，情報

コミュニティの周縁部に新たなコミュニティが発生することで，拡散のシミュレートが挙げられる．より情報拡散の文脈に近い

成長を繰り返すネットワークだと考えられる．そのため，周縁人工データを用いることで，提案手法の有効性や改善など様々

部におけるコミュニティ形成に貢献したエッジが高い誘発スコ

な示唆が得られると考えている．

アを得たと考えられる．
一方，CNN1K-NW，CNN10K-NW，Reply-NW，Eucore-

7 ま と めNW では，提案手法と誘発スコアの間に明確な関係は見られ現実世界の複雑ネットワークは，時々刻々と変化する動的なかった．この原因について考察する．まず，Reply-NW や

ネットワークである．これらのネットワークにおいて，後続するノードやエッジを誘発する高影響な構造を推定・抽出することは重要なタスクである．本研究では，出現時の特徴を用いてネットワーク成長を誘発するエッジを効率的に抽出する手法を[12]提案した．具体的には「エッジの出現位置（隣接スコア）」と「ネットワークを強化したか，拡張したか（強化拡張スコア）」の 2 点を用いた．Twitter の情報拡散ネットワークを用いた実[13]

験により，ネットワークを周縁部で強化するエッジがその後多くのエッジを誘発することを明らかにした．また，提案手法が[14]

既存手法に比べ高速に動作することを示した．
今後の課題は次の通りである．まず，情報拡散をシミュレー[15]

トした人工データでの検証が挙げられる．情報拡散の文脈に近い人工ネットワークを用いることで，提案手法の改善に大きな[16]

示唆が得られると考えている．また，本研究ではネットワーク
構造のみを特徴量とする手法を提案した．しかし，実際の情報[17]

拡散を分析する上では，情報の内容そのものに着目することも重要である．ネットワークベースの手法とコンテンツベースの[18]

手法を相補的に用いることで，より精緻な分析や推定モデルの構築が可能だと考えている．
[19]

謝

辞

本研究は JSPS 科研費 JP16H02904 の助成を受けたものです．ここに記して謝意を示します．

文

献[1] A. Albert and A. L. Barabási. Statistical mechanics of complex networks. Rev. Mod. Phys, pages 47–97, 2002.
[2] S. Bikhchandani, D. Hirshleifer, and I. Welch. A theory offads, fashion, custom, and cultural change as informationalcascades. Journal of political Economy, 100(5):992–1026,
1992.
[3] P. Boldi and S. Vigna. Axioms for centrality. Internet Mathematics, 10(3-4):222–262, 2014.
[4] J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, andJ. Leskovec. Can cascades be predicted? In Proceedingsof the 23rd international conference on World wide web,pages 925–936. ACM, 2014.
[5] M. De Domenico, A. Lima, P. Mougel, and M. Musolesi.
The anatomy of a scientific rumor. Scientific reports, 3:2980,
2013.
[6] L. Freeman. Centrality in social networks: Conceptual clarification. Social Networks, 1(3):215–239, 1979.
[7] J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex systems look at the underlying process ofword-of-mouth. Marketing letters, 12(3):211–223, 2001.
[8] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the
spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conferenceon Knowledge discovery and data mining, pages 137–146.
ACM, 2003.
[9] M. Kimura, K. Saito, and H. Motoda. Blocking links tominimize contamination spread in a social network. ACM
Transactions on Knowledge Discovery from Data (TKDD),
3(2):9, 2009.
[10] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan,
D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. Science (New York, N.Y.),298(5594):824–827, 2002.
[11] A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in tem-poral networks. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM
’17, pages 601–610, New York, NY, USA, 2017. ACM.
Y. Rochat. Closeness centrality extended to unconnected
graphs: The harmonic centrality index. Technical report,
2009.
A. Vázquez. Growing network with local rules: Preferential
attachment, clustering hierarchy, and degree correlations.
Physical Review E, 67(5):056104+, 2003.
S. Wasserman and K. Faust. Social Network Analysis:
Methods and Applications. Cambridge University Press,
1994.
D. J. Watts. A simple model of global cascades on random
networks. Proceedings of the National Academy of Sciences,
99(9):5766–5771, 2002.
D. J. Watts and P. S. Dodds. Influentials, networks, andpublic opinion formation. Journal of consumer research,
34(4):441–458, 2007.
D. J. Watts and S. H. Strogatz. Collective dynamics of‘small-world’ networks. Nature, 393(6684):440–442, 1998.
吉川友也, 斉藤和巳, 元田浩, 大原剛三, and 木村昌弘. 情報拡散モデルに基づくソーシャルネットワーク上でのノードの期待影響度曲線推定法. 電子情報通信学会論文誌 D, 94(11):1899–1908,2011.
川本貴史, 豊田正史, and 吉永直樹. マイクロブログにおける社会的影響力を持つ情報カスケードの早期検知に向けて. 第 8 回
Web とデータベースに関するフォーラム論文集, pages 48–55,
2015.