DEIM Forum 2014 B1-4

枝刈り探索によるソーシャルネットワークでの影響最大化アルゴリズム
大坂

直人†

秋葉

拓哉†

吉田

悠一††

河原林健一††† 東京大学大学院情報理工学系研究科コンピュータ科学専攻 〒 113–8654 東京都文京区本郷 7-3-1†† 国立情報学研究所 〒 101-8430 東京都千代田区一ツ橋 2-1-2
E-mail: †{ohsaka,t.akiba}@is.s.u-tokyo.ac.jp, ††{yyoshida,k keniti}@nii.ac.jp
あらましバイラルマーケティングは「口コミ」を通して商品の購入を効率的に促すマーケティング戦略である．この考えにもとづく影響最大化問題は，影響力の高い少数の頂点集合をソーシャルネットワーク上から選択する問題である．NP-hard に属するため現実的な時間で厳密解を計算することは望めないが，近似比 1 − 1/e を保証する貪欲アル
ゴリズムが知られている．Monte-Carlo シミュレーションによる頂点集合の影響力の計算に膨大なコストがかかるた
め，このアルゴリズムを大規模なネットワークに適用することは困難である．我々は，枝刈り探索及び理論的解析にもとづく Monte-Carlo シミュレーションの回数の削減による影響最大化問題の高速アルゴリズムを提案する．実験により，提案手法が既存手法と同等以上の速度を保ちつつ，ほとんど常に最も影響力の高い頂点集合を選択可能である
ことを示した．
キーワード

ソーシャルネットワーク，影響最大化問題，バイラルマーケティング

1. は じ め につ一方，得られる解の質がネットワーク構造やパラメータ設定に大きく依存するという欠点がある．

バイラルマーケティング [4], [11] とは，商品の無料サンプル

以上の問題を解決するため，本論文は影響最大化問題に対や割引商品を影響力の高い少数のグループ（シードと呼ばれする効率的かつ高精度なアルゴリズムを提案する．ヒューリス

る）に与えることで，多数の人へ商品購入を効率的に促すマー

ティクスにもとづく手法とは異なり，提案手法は貪欲アルゴリ

ケティング戦略である．広告による直接的なマーケティングとズムにもとづきシード集合の影響力を Monte-Carlo シミュレー

は異なり，商品の評判は「口コミ」を通して人から人へ間接的ションによって計算するため，解の精度が理論的に保証される．

に広げられる．このような情報拡散は，ソーシャルネットワー

大規模なネットワーク上での動作を実現するため，提案手法

ク上（頂点が人，辺が人と人との関係に対応する）でモデル化に以下の 3 つの高速化手法を導入する．(1) Monte-Carlo シミュされる．バイラルマーケティング成功のためには，ソーシャル

レーションにより得られたランダムグラフの保持・更新によるネットワークを解析し，少数で効果的なシード集合を見つける

シミュレーション回数の抑制及びその理論的保証，(2) 影響力

ことが求められる．

評価に伴う到達可能性検査のための幅優先探索（BFS）の効率「影響最大化問題」は，影響力が最大のシード集合を選ぶ問

的な枝刈り，(3) 不必要な影響力評価の検知及び除去．

題であり，確率的伝搬モデルによる数学的定式化がなされてい計算機実験により，(1) 提案手法の与える解が既存手法よりる [8]．NP-hard に属する [8] ため，多くの近似アルゴリズムやもほとんど常に優れていること，(2) 数千万辺規模の実ソーシャ

ヒューリスティクスが提案されてきたが，計算時間と精度のトルネットワークに対して既存のヒューリスティクスと同等の速

レードオフはいまだ解決されていない．

度で動作することを示した．

Kempe ら [8] の Monte-Carlo シミュレーションにもとづく貪
欲アルゴリズムは影響最大化問題の最初の手法である．目的関数が劣モジュラ性を有するため，貪欲アルゴリズムが最適解

2. 既 存 研 究
2. 1 Monte-Carlo シミュレーションにもとづく手法の定数近似解を出力することが理論的に保証される．さらに，Monte-Carlo シミュレーションにもとづく手法は，情報拡散

実際のネットワーク上ではほぼ最適な解が得られることが実験をシミュレートすることで頂点集合の影響力を高い精度で得ら的に示されている．しかしながら，貪欲アルゴリズムはスケーれるため，影響力の高いシード集合を出力する．一方で，これラビリティに乏しく，様々な高速化手法 [2], [3], [9], [12], [14] をらを大規模なネットワークに直接適用することは計算時間の観もってしても，数百万頂点規模のグラフに適用することが困難点から困難である．

であった．

Kempe ら [8] は影響最大化問題に対する Monte-Carlo シミュ

その結果として，様々なヒューリスティクスが提案されてきレーションにもとづく貪欲アルゴリズムを提案した．影響力

た [1], [2], [5], [6], [7], [13]．これらの手法はシード集合の影響力関数が劣モジュラ性を有するため，貪欲アルゴリズムがほぼを Monte-Carlo シミュレーションではなく高速なヒューリスティ

最適な解を与えることが理論的に保証される．しかし，情報

クスで近似するため，解の精度に関する理論的保証が無い．し

拡散のシミュレーションコストが膨大なため，スケーラビリ

たがって，貪欲アルゴリズムよりも高いスケーラビリティを持ティに乏しいという欠点を持つ．Leskovec ら [9] が提案した

Cost-Effective Lazy Forward (CELF) は，劣モジュラ性を利用す

Algorithm 1 独立カスケードモデルにおける影響最大化問題のることで，Kempe らの貪欲アルゴリズムと同じ性能を保ちつ貪欲アルゴリズム [8]つ，必要な影響力評価の回数を抑える．実験より，貪欲アルゴ

1: S ← ∅リズムと比較して 700 倍の高速化が示されたが，数万頂点のグ

2: while |S| < k do

ラフに対しては依然として数時間以上を要する．Cheng ら [3]3:t ← arg maxv∈V \S σ(S ∪ {v}) − σ(S)が提案した StaticGreedy は，入力グラフより生成したランダム

4:

S ← S ∪ {t}グラフを再利用することで，解の質を保ちつつ，Monte-Carlo

5: return S

シミュレーションの回数を 10,000 から 100 に抑えられることを実験的に示した．しかしながら，実行時間がパラメータ設定

厳密解法は望めないが，影響拡散関数 σ(·) の有する性質を利用に大きく依存することが我々の実験の結果より示された．

した貪欲アルゴリズムが最適解の定数近似解を出力することがJiang ら [6] が提案した Simulated Annealing with Effective Dif-

知られている．集合関数 f : 2V → R は，任意の S ⊂V につい=⊂て f (S) >= 0 ならば非負であるといい，任意の S ⊂=T =V につい⊂て f (S) <= f (T ) ならば単調であるといい，任意の S ⊂=T =V と>v ∈ V について f (S ∪ {v}) − f (S) = f (T ∪ {v}) − f (T ) なら

fusion Values (SAEDV) は，シード集合の近傍の情報のみから影ば劣モジュラであるという．Kempe ら [8] による影響最大化問

響力を近似し，焼きなまし法により高影響力の頂点集合を探索

題の貪欲アルゴリズムを Algorithm 1 に示す．貪欲アルゴリズ

する．Chen ら [1] が提案した PMIA は，伝搬確率の高い経路

ムは，空のシード集合 S = ∅ から開始し，影響拡散の増加量がを探索し，影響力を近似した．Jung ら [7] が提案した Influence

最大の頂点 t = arg maxv σ(S ∪ {v}) − σ(S) を S に追加してRank Influence Estimation (IRIE) は各頂点の影響力を連立方程式

いく．劣モジュラ関数最大化問題に対する貪欲アルゴリズムにで表現し効率的に計算する．

ついて Theorem 3.1 が成立し，独立カスケードモデル上の σ(·)

2. 2 ヒューリスティクスにもとづく手法
Monte-Carlo シミュレーションの使用を避けるべく，様々なヒューリスティクスが提案された．

これらのヒューリスティクスは Monte-Carlo シミュレーショ

について Theorem 3.2 が成立する．

ンにもとづく手法よりも高いスケーラビリティを持つが，解のTheorem 3.1. [10] 非負かつ単調な劣モジュラ関数 f について，

質がネットワーク構造やパラメータ設定に大きく依存する．

S を貪欲アルゴリズムにより得られた集合，S ∗ を f の最大化∗
問題の最適解とすると，f (S) >= (1 − 1/e)f (S ) が成立する．

3. 予 備 知 識

Theorem 3.2. [8] 独立カスケードモデルにおいて影響拡散関数

3. 1 論文中で用いる表記
G = (V, E) をサイズ n の頂点集合 V とサイズ m の頂点集
G

合 E からなる有向グラフとする．u ⇝ v は，グラフ G 上で頂点 u が頂点 v に到達可能であることを意味する．すなわち，Gにおいて u から v への経路が存在する．

3. 2 影響最大化問題の定式化
本論文では，最もスタンダードな情報拡散モデルである独立

σ(·) は非負，単調，劣モジュラである．
したがって，貪欲アルゴリズムは，影響最大化問題の最適解の約 63%近似解を出力する．

3. 4 影響拡散の計算方法
σ(·) の厳密計算は#P-hard に属する [1] ため，既存研究の多 く で は Monte-Carlo シ ミュレ ー ション が 用 い ら れ て い る

カスケードモデル [8] を採用する．独立カスケードモデルは，[2], [3], [8], [9], [12], [14]．シミュレーション回数を R とすると，有向グラフ G = (V, E) と伝播確率関数 p : E → [0, 1]，シード

σ(·) の時間計算量は O(mR) となる．ゆえに，貪欲アルゴリズと呼ばれる頂点集合 S ⊂V を入力とし，以下の確率過程を繰り=返す：

ムの総時間計算量は O(kmnR) となる．さらに，高い精度でσ(·) の値を得るためには，膨大な回数のシミュレーションを必（ 1 ） S に含まれる頂点の状態をアクティブに設定し，V \ S

要とする（典型的には R ≈ 10, 000）．以上より，貪欲アルゴリに含まれる頂点の状態を非アクティブに設定する．

ズムは大規模なグラフにスケールしない．この問題を解決する（ 2 ） 新しくアクティブになった各頂点 u は，非アクティブため，次節で影響最大化問題の高速アルゴリズムを提案する．

な u の各近傍 v を確率 puv でアクティブに変更する．
（ 3 ） 新しくアクティブになった頂点が存在すれば（ 2 ）へ戻り，そうでなければ終了する．

4. 提 案 手 法
本節では，独立カスケードモデルにおける影響最大化問題の独立カスケードモデルにおけるシード集合 S の「影響拡散」

高速アルゴリズムを提案する．以下では，まず，「コインフリッを「独立カスケードモデルにおける S をシードとする情報拡散

プテクニック」を説明し，独立カスケードモデルのシミュレー

において，アクティブになる頂点の数の期待値」で定義する．

ションがランダムグラフ上での到達可能性判定と等価であるこ

以後，S の影響拡散を σ(S) と表記する．影響最大化問題 [8]とを示す．次に，高速化手法を含まない提案手法を説明し，最は，独立カスケードモデルにおいて影響拡散を最大化する大き後に，2 つの高速化手法を導入する．

さ k の頂点集合を求める問題である．

3. 3 貪欲アルゴリズム
影響最大化問題は NP-hard に属する [8] ため，多項式時間の4. 1 コインフリップテクニック
Kempe ら [8] による「コインフリップテクニック」を説明す
る．シード集合を S として独立カスケードモデルをシミュレー

Algorithm 2 独立カスケードモデル下の影響最大化問題の高速v の「利得」と呼び σGi (v | S) と表記する．Gi の構築後，次アルゴリズム数最大の頂点 hi を選択し，hi の子孫からなる集合 Di と hi のRequire: G = (V, E), p : E → [0, 1], k, R (# of DAGs)

先祖からなる集合 Ai を計算する．また，利得の再計算フラグ

1: for i = 1 to R doを表す変数 latesti [v] を初期化する．これらは後述の高速化手

2:Ei′ ← 各辺 e を確率 pe で残すことで得られる辺集合

3:G′i = (V, Ei′ ) の強連結成分を計算

4:

Gi = (Vi , Ei ) ← G′i より構築された頂点重み付き DAG

5:hi ← Vi において最大の次数をもつ頂点

6:

GiDi ← {v ∈ Vi | hi ⇝ v}
Gi

7:

Ai ← {v ∈ Vi | v ⇝ hi } \ {hi }8:latesti [v] ← false for all v ∈ Vi

後半のパートでは，利得の近似値を計算し，シード集合を選択する．以後，j 番目のシードを選択するフェーズを「j 番目のフェーズ」と呼ぶ．関数 G AIN(i, v) は，compi [v] を始点とす
る BFS を行い，Gi における v の利得を返す．v の影響拡散の増加量 σ(S ∪ {v}) − σ(S) の近似値を各 DAG の σGi (v | S) の平均値で計算し，影響拡散の増加量が最大の頂点 t をシードと9: S ← ∅10: while |S| < k do
11:1t ← arg maxv∈V R

12:

S ← S ∪ {t}13:for i = 1 to R do

14:

法に用いられる．

して選択する．関数 U PDATE DAG(i, t) は compi [t] から到達可∑R

i=1 G AIN (i, v)

能な頂点を Gi から除く．したがって，|S| + 1 番目のフェーズ
では，compi [v] から到達可能な頂点の重みの合計値は新しい利得 σGi (v | S ∪ {t}) に一致する．

U PDATE DAG(i, t)

BFS がおよそ knR 回行われるため，Algorithm 2 の時間計算

15: return S

量は貪欲アルゴリズムから本質的には改善されていない．提案

トした結果，アクティブになる頂点集合の分布を DG (S) と定義

手法を高速にするため，2 つの高速化手法を提案する．1 つ目
は BFS 内で探索される頂点の数を抑える「枝刈り BFS」，2 つする．各辺 e ∈ E を確率 pe で残すことで得られるランダムグ

目は「不必要な利得の再計算を避けることによる高速化手法」

ラフを Gp とし，Gp において頂点集合 S から到達可能な頂点である．これらの高速化手法は影響拡散の近似値に影響を与え′集合の分布を DG(S) と定義する．ここで，2 つの分布 DG (S)′と DG(S) は等しい [8]．したがって，以後はランダムグラフ上での到達可能性のみを考える．

ないため，提案手法の精度は保たれる．

4. 3 高速化手法 1： 枝刈り BFS
BFS 内で探索される頂点の数を抑える方法を議論する．ま4. 2 提案手法のあらまし

ず，全ての頂点から BFS を行うときの時間計算量を考える．各

提案手法は次の 5 ステップから構成される：(1) 入力から複数のランダムグラフを生成し，(2) 各ランダムグラフから頂点重み付き非循環有向グラフ（DAG）を構築し，(3) 各頂点の影
響拡散の増加量を，各 DAG においてその頂点から到達可能なBFS で訪れられる頂点数の総和は，任意の頂点 h に対して (hの先祖の数)×(h の子孫の数) 以上である．この値は頂点数の自乗オーダーになりうるため，BFS 全体のコストは大きい．枝刈り BFS のアイデアは次の通り：

頂点の総重みの平均で近似し，(4) 影響拡散の増加量が最大の頂点をシードとして選択し，(5) 各 DAG を更新する．

Algorithm 2 に提案手法の擬似コードを示す．R は生成する
DAG の個数を表すパラメータである．提案手法は 2 つのパートに分かれる．前半のパートでは，R 個の頂点重み付き DAG

G1 , G2 , · · · , GR を生成する．i 個目の頂点重み付き DAG Gi の構築方法は次の通り．まず，各辺 e ∈ E を確率 pe で残した辺集合 Ei′ を得る．次に，G′i = (V, Ei′ ) の強連結成分分解を行

頂点 v が頂点 h に到達可能ならば，v から BFS を行う際に h から到達可能な頂点を枝刈りすることができる．
図 1 を例に枝刈り BFS を説明する．頂点 h は最大の次数を有するため，図のグラフにおいてハブであるとみなせる．また，

h の先祖と子孫はそれぞれ {a, b, c} と {h, d, e, f } である．頂点
a から普通の BFS を行うと {a, c, h, d, e, f } を訪れる．しかし，い，v ∈ V を含む強連結成分 compi [v]，強連結成分 v に含まれ（hi の先祖・子孫を前計算すれば）a が h を訪れることは既知でる頂点の数 weighti [v] を計算する．最後に頂点重み付き DAGあり，したがって，h の子孫を訪れることが分かるため，このGi = (Vi , Ei ) を次のように構築する：Vi = {compi [v] | v ∈V }, Ei = {(compi [u], compi [v]) | uv ∈ Ei′ }．ここで，ランダムグラフ G′i において頂点集合 S から到達可能な頂点数と頂点重み付き DAG Gi において {compi [t] | t ∈ S} から到達可能な頂点の総重みは等しい．以下，この値を σGi (S) と表記する．
すなわち，BFS は冗長である．枝刈り BFS では，{h, d, e, f } を枝刈りすることで {a, c} のみを訪れる．同様に，b からは，普通の BFSを行うと {b, c, h, d, e, f } を訪れるが枝刈り BFS では {b, c} のみを訪れる．
枝刈り BFS を Algorithm 3 に示す．頂点 v から BFS を開始
する前に，v が hi の先祖であるかを調べる．もし v が hi の先G′iσGi (S) = {v ∈ V | ∃t ∈ S, t ⇝ v}∑=
weighti [v].
Gv∈Vi :∃t∈S,compi [t] ⇝i v

また，σGi (S ∪ {v}) − σGi (S) の値を Gi における S に関する

祖であれば，hi から到達可能な頂点を除いたとみなした枝刈
り BFS を行い，そうでなければ，通常の BFS を行う．枝刈り

BFS を行った場合の頂点 v の利得は，hi の利得と枝刈り BFS
で訪れた頂点の総重みの和に厳密に一致する．2 番目のフェー
ズ以降に行われる BFS の回数が次に提案する高速化手法によ# of vertices visited during
Vertex normal BFSℎpruned BFS

a

6

2

b

6

2

c

5

1

図 1 枝刈り BFS の例

比較して理論的に抑えられることを示す．
以後，2 つのグラフサンプリングにもとづく手法を考える．

1 つ目は，事前に生成したサンプルを全体のフェーズを通して再利用する「再利用アルゴリズム」（提案手法に対応する），2
つ目は，各フェーズでグラフをサンプリングし直す「再標本アAlgorithm 3 高速化手法 1： 枝刈り BFS による到達可能な頂点

ルゴリズム」である．本節では，再利用アルゴリズムが再標本の重みの合計値の計算

アルゴリズムよりもサンプルの数において効率的であることを

1: function G AIN(i, vV ∈ V )

示す．

2:

v ← compi [vV ]3:

return 0 if v ̸∈ Vi

4:return δi [v] if latesti [v]5:latesti [v] ← true

6:

if v ∈ Ai ∧ |S| = 0 then

7:
8:
9:

まず，Hoeffding の不等式を導入する．

Theorem 5.1 (Hoeffding の不等式). X1 , . . . , Xn を [0, 1] の範囲∑の値を取る独立確率変数とする．X = n1 n
i=1 Xi と定義すると
2
Pr[|X − X| > t] <= 2 exp(−2nt ).

δi [v] ← G AIN(i, hV ) s.t. compi [hV ] = hi
else

Lemma 5.2. G を グ ラ フ， S を 頂 点 集 合 族 と す る ．R =δi [v] ← 0

10:

Q ← 頂点 v のみを有するキュー

11:

X ← {v}

12:

while Q =| ∅ do以上の確率で，任意の S ∈ S に対して σ(S) = σG (S) ± ϵn が13:

頂点 u をキュー Q からデック

14:

if v ∈ Ai ∧ u ∈ Di ∧ |S| = 0 thencontinue15:
16:

δi [v] ← δi [v] + weighti [u]17:for all uw ∈ Ei do
if w ̸∈ X ∧ w ∈ Vi then18:

O( ϵ12 log |S| log 1δ ) とし，G1 , . . . , GR を G からサンプルしたグ∑R
1
ラフの集合とする．σ(S) = R
i=1 σGi (S) とすると，1 − δ
成立する．

Proof. σGi (S) ∈ [0, n] であるから，頂点集合 S ∈ S について，
1
σ (S), . . . , n1 σGR (S) に Hoeffding の不等式を適用すると，
n Gi
2
<

次が得られる：Pr[|σ(S) − σ(S)| > ϵn] = 2 exp(−2ϵ R). S 内の全集合について union bound をとると，全ての S ∈ S につい19:

頂点 w をキュー Q にエンキュー

2て |σ(S) − σ(S)| <= ϵn が成立する確率は 1 − 2 exp(−2ϵ R)|S|20:

X ← X ∪ {w}以上である．R の値を R = O( ϵ12 log |S| log 1δ ) とすることで，

21:

所望の確率が得られる．

return δi [v]Algorithm 4 高速化手法 2: 利得再計算の抑制
1: function U PDATE DAG(i, tV ∈ V )2:
3:

G を n 頂点グラフとし，k をシード集合のサイズとする．

t ← compi [tV ]GiGi

for all v ∈ Vi : ∃u, t ⇝ u ∧ v ⇝ u do

4:latesti [v] ← false5:Vi ← Vi \ {v | t ⇝i v}

次に，再利用アルゴリズムと再標本アルゴリズムが必要とするサンプルの数を解析する．

Gi ∈ {1, . . . , k} について Si を i 番目のフェーズで選ばれたシー
ド頂点集合とする．i ∈ {0, . . . , k − 1} について i 番目のフェーズにおいて σ(·) の値を計算すべき頂点集合の族を Si とする．
すなわち，Si+1 = {Si ∪ {v} | v}．S = ∪k−1
i=0 Si+1 とする．

り減らされるため，枝刈り BFS は最初のフェーズにおいてのみ行われる．

4. 4 高速化手法 2： 利得再計算の抑制
利得の再計算を抑制する方法を議論する．新しいシード頂点

t をシード集合に追加後に頂点 v の利得が変化する必要条件はSi (i = 1, . . . , k − 1) 及び S は確率変数である．
再 利 用 ア ル ゴ リ ズ ム は ，ま ず グ ラ フ G1 , . . . , GR を サ ン
プ リ ン グ し ，各 頂 点 集 合 S に つ い て ，σG (S) を σ(S) :=∑R
1i=1 σGi (S) で見積もる．以下の定理が成り立つ．
RnTheorem 5.3. R = O( log k+log
log 1δ ) と設定する．1 − δ 以上
ϵ2「v から到達可能なある頂点が t からも到達可能」であるため，の確率で，再利用アルゴリズムによる任意の頂点集合 S ∈ S の

この条件を満たさない頂点については利得の再計算を行わない．

σG (S) の見積もりは，σ(S) = σG (S) ± ϵn を満たす．

Algorithm 4 に利得再計算の抑制手法を示す．まず，新しいシード t を始点とする BFS を行い，次に，t から到達可能な頂

Proof. |S| <= kn であるから，定理は Lemma 5.2 から直ちに得られる．

点から逆方向 BFS を行う．逆方向 BFS で訪れた各頂点 v について利得の再計算フラグを設定し（latesti [v] を false に設定する），最後に t の子孫を Gi から取り除く．

5. 理論的解析

再 標 本 ア ル ゴ リ ズ ム は ，i 番 目 の フェー ズ に お い て ，Gi1 , . . . , GiR をサンプリングし，各頂点集合 S について σG (S)∑R
1の値を σ i (S) := R
j=1 σGi (S) で見積もる．
j

Theorem 5.4.
本節では，提案手法の Monte-Carlo シミュレーションの回数（＝生成する DAG の数）が Kempe ら [8] の貪欲アルゴリズムとnlog 1δ ) とすると，1 − δ 以上の確率
R = O( logϵ2で，任意の頂点集合 S ∈ Si ，インデックス i について再標本ア
ルゴリズムの見積もりは σ i (S) = σG (S) ± ϵn を満たす．

表 1 データセット
データセット|V ||E| 辺の向き

Epinions

76K 509K 有向

DBLP

655K

LiveJournal

4.8M

Twitter30days

6.2M

62M 有向Ours(200)
StaticGreedy(200)
IRIE

PMIA
SAEDV
HighDegree

Random2.0M 無向2500

69M 有向

500

Influence Spread

3000

600
Influence Spread

700

400
300
200

1500
1000
500

100

Proof. |Si | <= n であるから，定理は Lemma 5.2 から直ちに得
られる．

2000

0

0
0

10

20
30
Size of Seed Set

40

50

0

(b) Epinions (P = 0.01)
n再標本アルゴリズムはサンプル数 O( k log
log 1δ ) を必要とす
ϵ2

50

40

50

40

50

40

50

2500

2000
250

Influence Spread

6. 計算機実験

40

300
Influence Spread

で十分であるため，より効率的である．

20
30
Size of Seed Set(c) Epinions (P = 0.025)

350

n
る一方，再利用アルゴリズムは，サンプル数 O( log k+log
log 1δ )
ϵ2

10

200
150
100

1500

1000

500
50

複数のソーシャルネットワークに対する計算機実験を行い，

0

0
0

10

提案手法と既存手法との性能比較を行う．

6. 1. 1 データセット

50000

表 1 に示す有向グラフ 3 つと無向グラフ（双方向グラフとみ

40000

50

0

10

20
30
Size of Seed Set(e) DBLP (P = 0.025)
35000045000

30000035000

Influence Spread

Influence Spread

Epinions（注 1）: Epinions.com (www.epinions.com) から得られ40(d) DBLP (P = 0.01)

6. 1 実 験 設 定なす）1 つを用いる．各ネットワークの詳細を以下に示す．

20
30
Size of Seed Set

30000
25000
20000
15000

250000200000150000100000

10000

たネットワークである．各頂点はユーザーに対応し，各辺は

50000

5000
0

ユーザー間の信頼関係に対応する．

0
0

10

20
30
Size of Seed Set

40

50

0

10

20
30
Size of Seed Set（注 2）: Michael Ley による DBLP Computer Science Bibliog-(f) LiveJournal (P = 0.01)

raphy Database から得られた共著ネットワークである．
LiveJournal (www.livejournal.com) のソーシャルネットワークである．各頂点はユーザーに対応し，各辺はユーザー間の信頼関係に対応する．

Twitter30days: Twitter (twitter.com) より抽出した 2013 年

Influence Spread

LiveJournal（注 1）:(g) LiveJournal (P = 0.025)

30000

30000025000

250000Influence Spread

DBLP

20000
15000
10000
5000

4 月分の日本語のツイート情報からなるグラフである．各頂点
はユーザーに対応し，各辺はユーザーからユーザーへのリプライに対応する．

6. 1. 2 伝 播 確 率

200000150000100000
50000

0

0
0

10

20
30
Size of Seed Set

40(h) Twitter30days (P = 0.01)

図2

50

0

10

20
30
Size of Seed Set(i) Twitter30days (P = 0.025)

設定ごとの影響拡散の値の比較

各辺の伝播確率はパラメータ P に設定する．様々な伝播確率に対するアルゴリズムの振舞を調査するため，P の値は

SAEDV [6]: 焼きなまし法によるアルゴリズムである．各パラ

P = 0.01, 0.025, 0.05, 0.075, 0.1 とする．

メータの値は [6] と同様に設定する．

6. 1. 3 アルゴリズム

HighDegree: k 頂点を次数順に選ぶ．

アルゴリズムの一覧を以下に示す．

Random: k 頂点をランダムに選ぶ．

Ours(R): 提案手法．DAG の数 R の値は 200 に設定する．

6. 1. 4 実 験 環 境

StaticGreedy(200) [3]: 入力グラフからランダムグラフを生成し，C++で実装された各アルゴリズムを Linux サーバー（CPU:

影響拡散を計算する．ランダムグラフの数は 200 に設定する．

PMIA [1]: 最も伝搬確率の高い経路を探索し，影響拡散の値をIntel Xeon X5670 (2.93 GHz)，メモリ: 48GB）で実行した．
6. 2 結果・考察

計算する．パラメータ θ の値は [1] と同様に 1/320 に設定する．

6. 2. 1 影響拡散の比較

IRIE [7]: 連立方程式で近似した影響拡散を効率的に計算する．

図 2 に設定ごとに各アルゴリズムが出力したシード集合の影

パラメータ α と θ の値は [7] と同様に 0.7 と 1/320 にそれぞれ

響拡散を示す．シード集合のサイズ k の値は 1 から 50 まで設設定する．停止条件も [7] と同様に設定する．

定する．SAEDV は貪欲法にもとづいていないため，k の値を10, 20, 30, 40, 50 に設定する．PMIA は LiveJournal (P >= 0.075)（注 1）：http://snap.stanford.edu/data/ より入手可能（注 2）：http://research.microsoft.com/en-us/people/weic/ より入手可能

においてメモリ不足により停止し，StaticGreedy(200) は Epin-ions (P >= 0.05)，DBLP (P >= 0.05)，LiveJournal (P >= 0.01)，
Twitter30days (P >0.01)
においてメモリ不足により停止したた=

10000

1000

10000

10000

100

1000

1000

1
0.1

10

1

Running Time[s]10

Running Time[s]100

Running Time[s]Running Time[s]

1000

100

10

Ours(200)
StaticGreedy(200)
IRIE
PMIA
SAEDV
HighDegree
Random

100

10

0.1

1

1

0.01
0.01

0.1
0.01

0.1
0.01

0.01
0.001
0.01

0.025

0.05
Value of P

0.075

0.1

(a) Epinions

0.025

0.05
Value of P

0.075

0.1

(b) DBLP

0.025

0.05
Value of P

0.075

0.1

0.025

(c) LiveJournal

0.05
Value of P

0.075

0.1

(d) Twitter30days

図 3 設定ごとの実行時間の比較

め，これらの設定の結果は得られなかった．得られたシード集

めに必要な Monte-Carlo シミュレーションの回数が既存の貪欲合の影響拡散の値を得るため，10,000 回の Monte-Carlo シミュ

アルゴリズムと比較して抑えられる理論的根拠を示した．実

レーションを行い，平均値を影響拡散の値とした．アルゴリズ

験結果より，提案手法は数千万辺を持つグラフに対して既存のム間の影響拡散の差が比較的小さいため，P = 0.05, 0.075, 0.1

ヒューリスティクスと遜色ない速度で動作し，様々な設定下にについての結果は省略する．

おいて既存手法と比較してほとんど常に最良の解を与えること提案手法 Ours(200) は全ての設定においてほぼ最良の解を出力している．StaticGreedy(200) もほぼ同様の結果を示した．
ヒューリスティクスにもとづく手法（PMIA，IRIE，SAEDV）
は LiveJournal (P = 0.01) と Twitter30days (P = 0.01) において，Ours(200) よりもそれぞれ 13%・7%以上低い影響拡散の値を示した．特に，DBLP (P = 0.025, k = 50) における IRIE の影響拡散 (= 1354) は Ours(200) の影響拡散 (= 2510) のおよそ半分であり，DBLP (P = 0.025, k = 1) における PMIA の影響
拡散 (= 216) は Ours(200) の影響拡散 (= 713) の三分の一以下であった．SAEDV はほぼランダムなシード集合を返していると思われる．明らかに，Random と HighDegree の計算した解は芳しくない．結果より，ヒューリスティクスにもとづく既存手法はグラフや確率の設定に性能が影響される一方，提案手法はほとんど常に最良の解を出力することが示された．

6. 2. 2 実行時間の比較
図 3 に各アルゴリズムの計算時間（k = 50）を示す．実行
時間にはグラフの読込時間は含まれていない．PMIA と Static-

Greedy(200) は，上述の設定においてメモリ不足により停止したため，実行時間が得られなかった．最も速い手法は Random，

2 番目に速い手法は HighDegree である．StaticGreedy(200) は
多くの設定において 1 時間以上を要した後，メモリ不足により動作を停止した．PMIA の実行時間は P の値が 0.075 を超えると爆発的に増加している．IRIE と SAEDV は P の値による実行時間の変化が見られなかった．Ours(200) は既存手法と比較して最速ではないが，IRIE と SAEDV とほぼ同速であり，

StaticGreedy(200) と PMIA に比較してロバストな性能を示した．
以上の結果より，提案手法の性能は様々なグラフ・確率の設定に対して既存手法より頑健でありながら，ほぼ最も影響拡散の高い解を出力すると結論づけられる．

7. お わ り に
本論文では，独立カスケードモデル上の影響最大化問題に対する効率的かつ高精度な手法を提案した．ネットワークに存在するハブを利用することで，提案手法は幅優先探索の大幅な高速化を可能とした．さらに，高い精度のシード集合を選ぶた

を示した．
文

献

[1] Wei Chen, Chi Wang, and Yajun Wang. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In KDD, pages 1029–1038, 2010.
[2] Wei Chen, Yajun Wang, and Siyu Yang. Efficient Influence Maximization in Social Networks. In KDD, pages 199–208, 2009.
[3] Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, andXueqi Cheng. StaticGreedy: Solving the Scalability-Accuracy
Dilemma in Influence Maximization. In CIKM, pages 509–518,
2013.
[4] P. Domingos and M. Richardson. Mining the Network Value of Customers. In KDD, pages 57–66, 2001.
[5] Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan. SIMPATH: An
Efficient Algorithm for Influence Maximization under the Linear
Threshold Model. In ICDM, pages 211–220, 2011.
[6] Qingye Jiang, Guojie Song, Gao Cong, Yu Wang, Wenjun Si, andKunqing Xie. Simulated Annealing Based Influence Maximization
in Social Networks. In AAAI, pages 127–132, 2011.
[7] Kyomin Jung, Wooram Heo, and Wei Chen. IRIE: Scalable and Robust Influence Maximization in Social Networks. In ICDM, pages
918–923, 2012.
[8] D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the Spread of
Influence through a Social Network. In KDD, pages 137–146, 2003.
[9] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos,
Jeanne VanBriesen, and Natalie Glance. Cost-effective Outbreak Detection in Networks. In KDD, pages 420–429, 2007.
[10] G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical
Programming, 14:265–294, 1978.
[11] M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites
for Viral Marcketing. In KDD, pages 61–70, 2002.
[12] Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. Communitybased Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks. In KDD, pages 1039–1048, 2010.
[13] Hwanjo Yu, Seung-Keol Kim, and Jinha Kim. Scalable and Parallelizable Processing of Influence Maximization for Large-scale Social Networks. In ICDE, pages 266–277, 2013.
[14] Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, and Li Guo.
UBLF: An Upper Bound Based Approach to Discover Influential
Nodes in Social Networks. In ICDM, pages 907–916, 2013.