DEIM Forum 2017 A3-1

意見形成モデルの影響度曲線における類似ノード群の特性分析
鈴木 優伽†

斉藤 和巳†† 静岡県立大学経営情報イノベーション研究科 〒 422–8526 静岡県静岡市駿河区谷田 52-1
E-mail: †{j16105,k-saito}@u-shizuoka-ken.ac.jp
あらまし Web 空間内に存在する大規模なソーシャルネットワーク等において，オピニオンや情報が形成されるため，意見形成や情報拡散の研究がされている．我々はこれまでの研究で，生物学的知見を基にした意見形成過程のモデル化を試み，異なるネットワークごとの意見形成過程の特性を示した．しかしながら，どのようなネットワーク構造が，それらの特性を有するのか十分な検討はされていない．そのため，本研究では，より詳細な分析の第一歩として，各ノードの意見形成過程における他ノードへの影響度に着目する．具体的には，意見形成過程における影響度が類似したノード群の特性から，ネットワーク構造を分析し，ネットワーク構造と意見形成過程の関係性について示す．
キーワード

影響度曲線，意見形成，類似影響度クラス

1. は じ め にが意見形成を行った際に，他のノードにどう影響を与えるかは，自身の立ち位置（構造）によって多様に変化し，影響度が類似

ソーシャルメディアの登場により，Web 空間内で大規模なしたノードは，類似した構造をもつと考えらえる．そこで，基ソーシャルネットワークが形成されている．また，ソーシャル本的な意見形成モデル [1] から，あるノードが意見形成した際メディアの登場以前より，Web 空間内の多様な電子ネットワーの他ノードへの影響度を図る影響度曲線を導入し，影響度曲線ク上で情報の形成や拡散が行われている．それらネットワークが類似したノード群を類似影響クラスとする．

上のオピニオン形成や情報拡散過程のモデル化は，将来流行

本稿の構成は以下とする．まず，提案するネットワーク構造する話題の特定や，影響度の大きいノードの抽出を可能とす分析法について説明する．次に，データセットを用いて，評価る．そのため，ネットワーク上での意見形成 [1] [2] [3] や情報拡実験の結果を詳細に述べる．最後に，実験結果から本分析法の散 [4] [5] の研究が盛んに行われている．また，従来研究 [6] [7] [8]

有望性を示す．

において，意見形成や情報拡散過程は，対象のネットワーク構造に影響を受けるとされ，それらの関係が分析されている．
一般にネットワーク構造は，ノード間の繋がり（リンク）で表現されるため，ネットワーク全体そのものを単適に示していることが多い．そのため，従来研究 [6] [7] [8] では， ソーシャ

2. 提案分析法
本分析法の手順は以下の通りである．

St1: 大域オピニオン採用付き VoterModel を用いて，意見形成過程におけるノードの影響度曲線を算出;

ルネットワーク 等のネットワークの種類で分類される大域的St2: 影響度曲線からノード群を K-medoids 法でクラス分け;なネットワーク構造と意見形成過程の分析がされている．我々

St3: クラス毎のネットワーク指標の Z-score を計算し，推測も，これまでの研究において，生物学的知見を基にした意見形されるネットワーク構造と意見形成過程の関係を分析;成過程のモデル化を試み，ネットワークの種類で分類した，大以降，各ステップの詳細な説明を述べる．

域的なネットワーク構造と意見形成過程の特性について示して

2. 1 意見形成モデル

きた．しかし，ネットワーク中には，密な関係のノード群の存ノード集合 V とリンク集合 E ⊂ V × V からなる有向ネット

在や，疎なノード群の存在など，大域的な視点では捉えられワークを G = (V, E) とし，局所オピニオン採用でノード v にない構造が存在する．従来の研究と同様，ネットワーク構造が影響を与える親ノード集合を C(v) = {u ∈ V; (u, v) ∈ E} とす

ノードの意見形成に影響を与えるとすれば，それら構造を考慮る．VM では，各ノード v は，親ノード u ∈ C(v) または任意することでより詳細な分析が可能であると考えられる．のノード u ∈ V をランダムに 1 つ選択し，時刻 t でのノード

よって，本研究では 類似影響クラス の視点を用いたネット

u のオピニオンを時刻 t + 1 での v のオピニオンとして採用すワーク構造分析法を提案し，従来とは異なる視点で捉えたネッることを繰り返す．本稿では，時刻 t = 0 で，ノード v のみがトワーク構造と意見形成過程の関係について示す．以下に，オピニオン 1 を持ち、他のノード u ∈ V \ {v} はオピニオン 0

類似影響度クラスの概要をしめす．密なコミュニティをもつのとき，時刻 t の経過とともに，ネットワーク上でノード v のノード群，多くのノード間の橋渡し的ノード群，ネットワーク初期オピニオンの影響を受けるノード数の期待値を影響度曲線の端におり孤立傾向をもつノード群が存在すると仮定する．密として分析する．

なコミュニティに属するノードが意見形成を行えば，コミュニいま，時刻 t でノード u がノード v の初期オピニオンを採ティのメンバーの多くに影響を及ぼすが，端に存在するノード用する確率を pv (u; t) で表す．問題設定より，pv (v; 0) = 1 で，では，他のノードに与える影響は少ない．すなわち，各ノード

u=| v なら pv (u; 1) = 0 となり，確率 pv (u; t + 1) は次式で求(a)enron(b)nortredame(d)stanford(e)epinion(g)Collabo:HEP-PH(h)Collabo:ASTRO-PH(h)citation:HEP-PH(i)citation:HEP-TH

図 1 各ネットワークの次数分布解法として貪欲法を採用する．

まる．

pv (u; t + 1) =∑1−α ∑αpv (w; t) +pv (w; t)|C(u)||V| w∈Vw∈C(u)貪欲法では，既に選定した代表ノード集合 P を固定し，以下に示す目的関数を増加させるノード u を代表ノードとして求める．

ここで，α は親ノードからの局所オピニオン採用確率を表し，

1 − α は大域オピニオン採用確率となる．よって，時刻 t で∑J(P ∪ {u}) ={}max γ(v; P), ρ(v, u)v∈V\Pノード v の初期オピニオンの影響を受けるノード数の期待値∑は yv (t) =u∈V pv (u; t) となる．本稿では，最終時刻 T ま

ここで，γ(v; P) は既に選定された代表ノードとの類似度の最でのオピニオン形成過程を考え，ステップ St1 としてベクトル大値を示し，γ(v; P) = maxw∈P (ρ(v, w)) で算出される．以下

yv = (yv (1), · · · , yv (T )) を影響度曲線として算出する．に，貪欲法による K-modoids 法のアルゴリズムを示す．

2. 2 K-medoids クラスタリング
ノード群を影響度曲線 yv (v ∈ V) を基に K-medoids 法でクA1. k = 1，P0 ← ∅，γ(v; ∅) ← 0 で初期化;{}A2. ŵk = arg maxw∈V\Pk−1 J(Pk−1 ∪ {w} を求める;ラスタリングする．K-medoidos クラスタリングは，ノード集A3. Pk = Pk−1 ∪ {ŵk } とする;

合 V とその要素 v, u ∈ V 間の類似度 ρ(u, v) が与えられたとA4. k = K ならば PK を出力して終了;

き，以下の目的関数を最大にするような代表ノード集合 P を求A5. 各ノード v ∈ V に対し，γ(v; Pk ) を求め，k = k + 1 とめる．

J(P) =して A2 へ戻る;∑v∈V{}
max ρ(v, u)u∈P

K = |P| 個の代表ノード集合を抽出し，残りのノード群を最も類似する代表ノードのクラスに割り当てることで，ノード集合

V を K 個のクラス V 1 , V 2 , · · · , V K に分割する．ここでは，類似度 ρ(v, u) を次式で定義する．

∑Tt=1 yv (t)yu (t)√∑ρ(v, u) = √∑TT
22j=t yv (t)j=t yu (t)また，ノード集合 V の部分集合 Q ⊂ P ⊂ V に対し，目的関数

J(P) は以下のサブモジュラ性 [9] を有する．
J(Q ∪ {w}) − F (Q) > J(P ∪ {w}) − F (P)w ∈ P であることに注意．サブモジュラ性を有する関数の最適化問題は，貪欲解法を用いることで最悪ケースの解品質を得られることが保証されている．[Leskovec] よってここでは，近似そして各ノード v を最も類似する代表ノードのクラスに割り当てる．以降では割り当てたクラス V 1 , V 2 , · · · , V K を類似影響クラスとする．

2. 3 Z-score
得られた類似影響クラスを分析するために，Z-score を導入する．ノード v ∈ V に対し，次数，クラスタ係数，近傍
次数，近接度，媒介度を属性とし，D(v)，CC(v)，N D(v)，CL(v)，BW (v) とする．すると，全ノードでの属性値の平均µD , · · · , µBW と標準偏差 σD , · · · , σBW が計算できる．一方，ノード集合のクラス分類結果を V 1 , V 2 , · · · , V K とすれば，各1K
V k での 各 µ1D · · · µK
D ，σD · · · σBW が求まる．このとき，各クラスにおける属性 m ∈ {D, CC, N D, CL, BW } の Zscore を√kzm= |V k |(µkm − µm )/σm として算出する．

(a)enron(b)nortredame(d)stanford(e)epinion(g)Collabo:HEP-PH(h)Collabo:ASTRO-PH(h)citation:HEP-PH(i)citation:HEP-TH

図2

各ネットワークの次数と近傍次数の分布

3. 2 影響度曲線に基づく分析

3. 評 価 実 験

図 1 に，各ネットワークデータでの，類似影響クラスにおけのうち，る代表ノード w ∈ P の 影響度曲線を示す．ただし，代表ノーエンロンの Email ネットワーク，ノートルダム大学・スタンドごとに異なる色で彩色する．図 1 から，影響度曲線は以下

フォード大学の Web サイトのハイパーリンクからなる Webの 2 つに分類可能である．(a1) 影響度がステップごとに大き（注 2）く変化し曲折する曲線．(a2) 比較的なだらかな曲線．図 1 かのユーザ関係ネットワーク，論文の共著者・論文引用データから，(a)enron，(b)nortredame(c)，stanford の情報ネッワークらなる研究者ネットワークを用いる．論文の共著者ネットワー

では (a1) の傾向が強く，(c)epinions のソーシャルネットワー

クデータは，High Energy Physics・AstroPhysics のデータをク，(d)(f)(g)(h)(i) の研究者ネットワークでは (a2) の傾向が強用い，それぞれ Collabo:HEP-PH・Collabo:ASTRO-PH と表いことが見て取れる．しかるに，(a1) の傾向が強い場合は，情記する．また，論文引用ネットワークデータは，High Energy

報ネットワークのような少数の情報発信源的ノードと多数の情Physics Phenomenology・High Energy Physics Theory のデー

報受信的ノードから構成されるネットワーク構造，すなわち，タを用い，それぞれ citation:HEP-PH・citation:HEP-TH とリンクの受け渡し数に差異がある２部グラフ的ネットワーク構する．ノード数は 265214，325729，281903，75879，12008，

造であると考えらえれ，(a2) の傾向が強い場合は，共著者ネッ

18772，34546，27770 であり，リンク数は 420045，1497134，

トワーク内で見られるような，比較的多数のノードが均等に繋281903，508837，118521，198110，421578，352807 である．

がっているネットワーク構造であることが示唆される．

スタンフォード大学が提供するデータセット（注 1）

ネットワーク，オンラインソーシャルサイトのエピニオン

3. 1 ネットワーク全体の特徴

3. 3 Z-score による抽出クラスの特徴分析

対象ネットワークの全体的な特徴を明らかにするために，図 1

図 4 に，各属性の Z-score を類似影響クラスごと示す．彩色に，ネットワークごとの次数分布を示す．また図 2 に，x 軸を自には，図 3 の代表ノードに用いた色と，同じ色を対応させてい身の次数，y 軸を近傍ノードの総次数を自身の次数で除した値とることに注意．図 3 と 4 から，(a1) の傾向が強いクラスは，クした分布を示す．図 1 から，どのネットワークにおいても次数分ラスタ係数が低く近傍次数の値が高く，(a2) の傾向が強いクラ布はスケールフリー性を持つことが確認できる．図 2 をみると，

スは，次数，近傍次数，近接度の値が高いことが分かる．すな自身の次数と近傍ノードの総次数は，右肩上がり・右肩下がりのわち，(a1) 傾向のクラスは，自身は周りと密な関係を持たない関係になることがわかる．特に，(b)nortredame，(c)stanford

が，友人が沢山のオピニオン発信先をもつような橋渡し的な構では右肩下がり，(g)Collabo:HTP-PH，(g)Collabo:HTP-PH造である考えられる．一方，(a2) 傾向のクラスは，ネットワー

では右肩上がりの傾向が強いことがわかる．すなわち，右肩下クの中心性指標の値が特に高いため，ネットワーク全体の中心がりのネットワークでは，ノード同士の繋がり方に差がみられ，に位置していると考えられる．また両者は，情報ネットワーク・右肩上がりのネットワークでは，どのノード同士も比較的同程ソーシャルネットワーク・研究者ネットワークで共通の特徴で度に繋がっていると考えられる．

ある．これより本分析法が，ネットワークのタイプや大域的な構造に囚われない視点からの分析が可能であることが示唆される．

（注 1）：https://snap.stanford.edu/data/index.html（注 2）：http://www.epinionglobal.com/(a)enron(b)nortredame(d)stanford(e)epinion(g)Collabo:HEP-PH(h)Collabo:ASTRO-PH(h)citation:HEP-PH(i)citation:HEP-TH

図3(a)enron(g)Collabo:HEP-PH

類似影響度クラスごとの影響度曲線(b)nortredame(d)stanford(e)epinion(h)Collabo:ASTRO-PH(h)citation:HEP-PH(i)citation:HEP-TH

図 4 類似影響度クラスごとのネットワーク統計量の Z-score

4. お わ り に本研究では，ネットワーク構造がオピニオン形成に影響を与[4]えるという先行研究から，オピニオン形成過程からネットワーク構造を分析する方法を提案し，ネットワーク構造と意見形成[5]過程の関係について分析することを試みた．評価実験では，本分析法が一定の有用性を示す事を確認した．今後は，さらに多様なネットワークへ適応し提案法の有用性を評価する．
謝辞

本研究は，科研費 (No.16H02904) の補助を受けた．
文

[6]
[7]
[8]

献

[1] Even-Dar, E. and Shapira, A.: A note on mximizing thespread of influence in social network, In WINE 2007, pp.
281–286 (2007).
[2] Wu, F. and Huberman, B.: How public opinion forms, InWINE 2008, pp. 334–341 (2008).
[3] Zhen, W., Yi, L., Lin, W. and Yan, Z.: Freezing period[9]strongly impacts the emergence of a global consensus in thevoter model, Scientific Reports (2013).
Kempe, D., Kleinberg, J. and Tardos, E.: Maxmizing thespread of influential through a social network, In WINE
2007, pp. 137–146 (2007).
Leskovec, J., Krause, A., Guestrin, C., Faloutos, C., VanBriesen, J. and Glance, N.: Cost-eﬀective outbreak detection in networks, In KDD 2007, pp. 420–429 (2007).
Varshney, K.: Bounded confidence opinion dynamics in social netWork of bayesian decision makers, arXiv (2013).
Gargiulo, F. and Huet, S.: Opinion dynamics in a groundbased society, EPL, Vol. 91, No. 5 (2010).
Mahdi, J.: Social power and opinion formation in complex
networks, Physica A: Statistical mechanics and its applications, Vol. 392, No. 4, pp. 959–966 (2013).
G. L.and Wolsey, L. A.and Fisher, M. L.: An analysis ofapproximations for maxi-mizing submodular set functions,
Mathematical programming, Vol. 14, pp. 265–294 (1978).