未知のグラフに対する影響最大化アルゴリズムの提案と評価

はじめに
問題の定式化
提案方式
実験
まとめ
未知のグラフに対する
影響最大化アルゴリズムの提案と評価
三原正大 1
津川翔 2
大崎博之 1
関西学院大学理工学研究科 1
筑波大学システム情報系 2
2015 年 05 月 28 日
第 37 回インターネット技術第 163 委員会研究会
1 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
研究の背景
近年、Twitter や Facebook に代表されるソーシャルメディ
アを数多くのユーザが利用している
ソーシャルメディアは、単なるユーザ間の交流のための場
としてだけでなく、情報拡散やマーケティングの場として
も注目を集めている
ソーシャルメディアにおける情報拡散やマーケティングを
効率的・効果的に行うためには、影響力の強いユーザを特
定することが重要である
第 37 回インターネット技術第 163 委員会研究会
2 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
影響最大化
人と人との関係をグラフとし
て表現したソーシャルネット
ワークにおいて、影響力の強
い少数のノード (シードノー
ド) の集合を特定する影響最
大化アルゴリズムの研究が活
発に行われている
第 37 回インターネット技術第 163 委員会研究会
3 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
従来研究と本研究
従来の影響最大化アルゴリズムは、ソーシャルネットワー
クの構造が既知であることを前提としている
⇒ 現実には、ソーシャルネットワークの現在の構造を完全
に把握することは非常に困難である
そこで本研究では、ソーシャルネットワークの構造が未知
であることを前提とする影響最大化問題と、その発見的解
法を提案する
第 37 回インターネット技術第 163 委員会研究会
4 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
重みなし無向グラフ G = (V, E) 上の影響伝搬を考える
▶
各ノードはソーシャルメディアのユーザに相当する
▶
各リンクはユーザ間の関係に相当する
初期状態においては、
V = {v1 , . . . , vN } (N : グラ
フ G のノード数) のみが既
知であり、グラフ G の構
造、すなわち E は未知で
あるとする
1
2
1
4
2
3
real graph
4
3
unknown graph
R 回のラウンドが存在し、各ラウンドにおいて、自由に選
択した m 個のノードの探査と、自由に選択した κ 個のノー
ドからの影響伝搬が可能であるとする
第 37 回インターネット技術第 163 委員会研究会
5 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
ノードの探査
▶
ノード v の隣接ノードのリストを取得できる
ノードからの影響伝搬
▶
影響伝搬のモデルに従う
▶
影響伝搬の結果として、影響を受けたノードのリスト
が得られる
R 回のラウンド中に影響を受けた (重複を除く) ノード数の
合計を最大化することを目的とし、各ラウンドごとに、探
査するノードとシードノードを選択する
第 37 回インターネット技術第 163 委員会研究会
6 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
IMUG のアイディア
( Influence Maximization for Unknown Graphs )
(1) 過去のラウンドにおける m 個のノードの探査と κ 個の
ノードからの影響伝搬の結果から、各ノードの次数を推
定し、
(2) 次のラウンドでは、過去に影響を受けていないノードの
中から次数の期待値が大きい順に κ 個のノードをシード
ノードとして選択する
現実のネットワークでは極端に次数の大きなハブノードが
存在することが分かっている
⇒ ノードの探査は、ハブノードを効率的に発見するのに有
効であるとされる SEC 法を用いる
第 37 回インターネット技術第 163 委員会研究会
7 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
IMUG の各ラウンドにおける動作 (1/2)
step 1. 以下の a, b, c を m 回繰り返す
a) 次数が未知であり、なおかつ次数の期待値が一番大きい
ノードを探査ノード vp として選択する
b) ノード vp を探査し、ノード vp の隣接ノードのリストを
得る
c) ノード vp の次数を既知とするとともに、vp の隣接ノード
の次数の期待値を 1 ずつ増加させる
example
step1-a
1
2
1R
4
3
step1-b,
step1-c
vp
1
2
4
3
1
2
3
4
->
->
->
->
0
0
0
0
1
2
4
3
1
2
3
4
->
->
->
->
3
1
1
1
real graph
▶
ノード番号 -> そのノードの次数の期待値を表す
第 37 回インターネット技術第 163 委員会研究会
8 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
IMUG の各ラウンドにおける動作 (2/2)
step 2. 過去のラウンドで影響を受けていないノードの中か
ら、次数の期待値が大きい順に κ 個のノードをシードノー
ドとして選択する
step 3. 各シードノードから影響伝搬を行い、影響を受けた
ノードのリストを得る
step3
step2
1
2
seed
4
3
1
1
2
3
4
->
->
->
->
3
1
1
1
2
4
3
1
2
3
4
->
->
->
->
3
1
1
1
第 37 回インターネット技術第 163 委員会研究会
2R...
9 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
実験の目的
シミュレーション実験により、提案する IMUG が、未知の
グラフに対する影響最大化アルゴリズムとしてどの程度有
効であるかを評価する
ネットワーク生成モデルを用いて生成したグラフおよび現実
のソーシャルネットワークを表現するグラフ上で、IMUG
を用いた影響伝搬のシミュレーション実験を行い、各ラウン
ドにおいて影響を受けた (重複を除く) ノード数を調査する
さらに、影響伝搬確率やグラフのトポロジの違いが、影響
伝搬の結果にどのように影響するかを議論する
第 37 回インターネット技術第 163 委員会研究会
10 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
実験方法 (1/2)
グラフ : ネットワーク生成モデルを用いて生成したグラフ
▶ ER モデル : 次数分布が二項分布に従うランダムグラフ
を生成
▶
BA モデル : 次数分布がべき分布に従うスケールフリー
グラフを生成
▶ 多くの現実のソーシャルネットワークにおいて、そ
の次数分布はべき分布に従うことが知られている
および現実のソーシャルネットワークを表現するグラフ
影響伝搬のモデル : IC モデル
▶ シードノードは、確率 p (影響伝搬確率) で各隣接ノー
ドに影響を伝搬させる
全ノードペアについて共通の値 p を用いる
第 37 回インターネット技術第 163 委員会研究会
11 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
実験方法 (2/2)
比較対象 :
▶
▶
▶
random - ランダムにシードノードを選択する方式
random-degree - 各ラウンドにおいて過去のラウンド
で探査されていないノードの中からランダムに選択し
た m 個のノードを探査し、過去のラウンドで影響を受
けていないノードの中で次数の期待値が一番大きい
ノードをシードノードに選択する方式
DegreeDiscountIC - グラフの構造が既知の場合に良好
な性能を示すことが知られている既存のアルゴリズム
今回は、IMUG および random-degree のパラメータとし
て m = ノード総数の 0.1 % を用いた
第 37 回インターネット技術第 163 委員会研究会
12 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
実験結果 [ER, BA モデル]
model=ER, N=10000, k=50, p=0.01
250
200
150
100
IMUG
random
random-degree
DegreeDiscountIC
50
0
0
10 20 30 40 50 60 70 80 90 100
round r
average number of active nodes
average number of active nodes
IMUG では、ラウンドが経過するにつれて、探査によって
ハブノードを発見できる可能性が高くなるため、多くの
ノードに影響を伝搬させることができている
⇒ ハブノードが存在することが知られている現実のソー
シャルネットワークにおいて効率的に動作すると期待される
model=BA, N=10000, k=50, p=0.01
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
IMUG
random
random-degree
DegreeDiscountIC
0 10 20 30 40 50 60 70 80 90 100
round r
第 37 回インターネット技術第 163 委員会研究会
13 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
実験結果 [現実のネットワーク]
network=NetHEPT, N=15,233, k=7.7, p=0.01
140
120
100
80
60
IMUG
random
random-degree
DegreeDiscountIC
40
20
0
0
10 20 30 40 50 60 70 80 90 100
round r
average number of active nodes
average number of active nodes
IMUG によって各ラウンドにおいて影響を受けたノード数
は DegreeDiscountIC の 60 - 90%以上
⇒ IMUG は現実のネットワークにおいて効率的に動作する
と言える
network=Amazon, N=262,114, k=9.4, p=0.01
300
IMUG
random
random-degree
DegreeDiscountIC
250
200
150
100
50
0
0
10 20 30 40 50 60 70 80 90 100
round r
第 37 回インターネット技術第 163 委員会研究会
14 / 15
はじめに
問題の定式化
提案方式
実験
まとめ
▶
まとめ
▶ ソーシャルネットワークの構造が既知ではなく、
未知であることを前提とする影響最大化問題と、
その発見的解法 IMUG を提案した
▶ 実験の結果、提案する IMUG が未知のグラフに対
する効率的な影響最大化アルゴリズムとして動作
していることがわかった
▶
今後の課題
▶ IMUG の性能の理論的解析
▶ 探査ノード選択方法の改善
▶ それらに基づく IMUG の改良
第 37 回インターネット技術第 163 委員会研究会
15 / 15

Download Report