DEIM Forum 2019 D2-2

ソーシャルネットワークにおける特定のユーザを対象とした影響最大化
勝田

健斗†

石川

佳治†

杉浦

健人†

† 名古屋大学大学情報学研究科知能システム学専攻 〒 464–8601 愛知県名古屋市千種区不老町
E-mail: †{katsuda,sugiura}@db.is.i.nagoya-u.ac.jp, ††ishikawa@i.nagoya-u.ac.jp
あらまし

近年，バイラルマーケティングと呼ばれるソーシャルネットワーク上の口コミを利用したマーケティング戦略が普及している．バイラルマーケティングにおける重要な問題は，口コミによる情報拡散が最大となるよう，いかに発信源として適切なユーザを選択するかである．ソーシャルネットワークにおける適切なユーザの特定は影響最大化問題として多く研究されている．既存研究における影響最大化問題は，主にソーシャルネットワークのグラフ上で何らかの情報伝搬モデルを想定し，その想定下でより多くのユーザに情報を伝達できる k 人のシードユーザを選択する最適化問題として定義されている．しかし，一般的な影響最大化問題はソーシャルネットワーク全体に対する影
響の最大化を目的としているが，現実的な問題を考えたとき，ある地域に住んでいるユーザなど特定の条件を満たすユーザにのみ影響を与えたい場合も考えられる．更に，そのような状況では条件を満たすユーザが時間の経過とともに変化することも考えられる．そこで本研究では時間窓を利用し，窓内で条件を満たしたユーザに対する影響力が最大となるシードユーザの特定を目的とする，新しい影響最大化問題を提案する．更に，ストリーム処理に対応した既存アルゴリズムを活用し，提案した影響最大化問題を効率的に解く手法を検討する．
キーワード ソーシャルネットワーク，影響最大化

1 はじめに近年，バイラルマーケティングと呼ばれるソーシャルネット
ワーク上の口コミを利用したマーケティング戦略が普及してい

領域𝑹

領域𝑹
𝑢𝑒

𝑢𝑓

𝑢𝑑

𝑢𝑎

る．企業は，ソーシャルネットワーク上の少数のユーザ（シー

𝑢𝑏

𝑢𝑖

𝑢𝑐

ドユーザ）に対して情報の伝達や試供品の提供を行い，情報の𝑢𝑔

発信や商品の宣伝を依頼する．依頼先のユーザを発信源とす

𝑢𝑎

𝑢𝑏

𝑢𝑒
𝑢𝑖

𝑢𝑓
𝑢ℎ

𝑢𝑔

𝑢ℎ

𝑢𝑑

𝑢𝑐

る口コミ効果により，間接的に大多数のユーザに対して商品やサービスをプロモーションできる．企業は少数のユーザに対す(a)時刻9:00の商業施設(b)時刻15:00の商業施設

る情報発信の依頼により大多数の人数に宣伝可能なため，費用
図 1 例：商業施設でのマーケティング

対効果も高い．
バイラルマーケティングにおいて重要な問題は，口コミによる情報拡散が大きくなるよう，口コミの発信源として依頼すべ

外のユーザ（uf , ug , uh , ui ）に対して宣伝を行っても効果は薄き影響力あるユーザをいかに特定するかである．バイラルマー

いと考えられる．しかし，既存手法によってネットワーク全体

ケティングを背景としたソーシャルネットワークにおける影響力

で影響を最大化してしまうとそうした領域外のユーザにばかりあるユーザの特定は影響最大化問題（influence maximization

宣伝が行ってしまい，本来の宣伝対象に広告が届かない可能性

problem）として多く研究されている [2], [4], [9]．既存研究におがある．

ける影響最大化問題 [2], [9] は，主にソーシャルネットワークの更に，ある特定のユーザへの影響最大化を考えたとき，一度グラフと情報伝搬モデルを基に，より多くのユーザに情報を伝の広告依頼では期待する結果が得られない可能性もある．図 1

達できる k 人のシードユーザ集合を選択する最適化問題としての例を続けて使用する．時刻 9:00 の時点で領域内にいるユー

定義されている．

ザは ua から ue の 5 人であるが，時刻 15:00 の時点ではその上述のようなネットワーク全体での影響最大化がある一方で，

うち 3 人（ua , uc , ud ）が領域外へと移動しており，代わりに現実的な応用を考えたとき，ネットワーク全体ではなくある特

別のユーザ 4 人（uf , ug , uh , ui ）が領域内に入ってきている．

定のユーザにのみ宣伝を行いたいという要求も考えられる．例

つまり，時刻 9:00 の時点でバイラルマーケティングを行ってい

えば，図 1 のようにある商業施設でセールを行い，その広告をたとしても，時刻 15:00 の時点ではほとんどその影響が残って

バイラルマーケティングで行いたいという状況を考える．このいない．したがって，時刻 15:00 においても広告を継続したい

とき，時刻 9:00 の時点で有効な宣伝対象となるユーザは領域

場合，再度適切なシードユーザを選択し宣伝を依頼する必要がR の範囲にいるユーザ（ua , ub , uc , ud , ue ）のみであり，領域ある．

そこで，本研究ではある条件を満たすユーザに対する影響

表 1 本研究で使用する記号

最大化を扱い，更にそれを連続的問合せとして処理する方法

記号説明を提案する．影響最大化問題を連続的に処理するために，本G

ソーシャルネットワーク：G = (V, E, p)

研究ではスライディングウインドウ（sliding window）に基づ

k

シード集合として選択するユーザの数

く時間窓（time window）を使用する．つまり，窓幅 w と移動

Wt

時間窓 Wt = [t − w, t]

幅 h が入力されると想定し，各窓内で条件を満たすユーザに対w

時間窓の窓幅する影響を最大化する．例えば，図 1 で窓幅 w = 1 : 00 と移

h

時間窓の移動幅

動幅 h = 0 : 30 が入力された場合を考える．このとき，まずU (Wt )

時刻 9:00 の時点では窓 [8 : 00, 9 : 00] の間に領域 R へ訪れたユーザへの影響を最大化する．その後，同様に [8 : 30, 9 : 30],

ターゲットユーザ：時間窓 Wt の窓内で条件を満たしたユー
ザの集合

I − (u)

逆到達集合：ユーザ u の影響元となるユーザの集合

I(u, Wt )[9 : 00, 10 : 00] などの窓においても影響最大化問題を解いていくことで，時刻 15:00 の時点における宣伝の再依頼にも対応できる．

ユーザ u が影響を与えるターゲットユーザ U (Wt ) の部分
集合
シード集合

S
I(S, Wt )シード集合 S が影響を与えるターゲットユーザ U (Wt ) の部分集合

2 問題定義f (S, Wt ) シード集合 S のターゲットユーザ U (Wt ) に対する影響の大きさ

本研究では，最近特定の場所を訪れたユーザなど，ある条件を満たしたユーザに対してバイラルマーケティングによって宣伝を行いたいという状況を想定する．つまり，ソーシャルネッ

1.

𝑢2
𝑢1

く，その部分集合となるターゲットユーザ集合への影響を最大ターゲットユーザ

化する．
経過とともにターゲットユーザが変化しうる点が問題となる．
例えば，ある領域を訪れたユーザを広告の対象とする場合を考

4.

𝑢4程度の時間が経過した後はその領域から離れるユーザも存在

𝑢3

×

𝑢1

𝑢4

○

𝑢6

𝑢5

𝑢2

𝑢3

𝑢1

𝑢6

×

𝑢4

える．このとき，その地域に住んでおり常に領域内にいるようなユーザがいる一方，一時的にその領域を訪れたのみで，ある𝑢2○

トワーク上に存在する全ユーザへの影響を最大化するのではな

ターゲットユーザ集合への影響最大化を考えたとき，時間の

2.

𝑢3

3.

𝑢2
𝑢1

𝑢5

×

𝑢3

○

𝑢4

○

𝑢6

𝑢5

𝑢6

×

𝑢5

図 2 IC モデルの逆伝搬による影響元の特定の例

する．つまり，影響最大化の対象となるユーザは時間とともに増減するため，それを考慮した影響最大化問題の定義が必要とを定義する．逆伝搬は，元々は処理効率化のために提案されたなる．

手法 [9] であり，その名の通り影響を受ける側のユーザから伝

そこで，本研究では影響最大化問題に時間窓（time window）

搬処理を行う．例として，逆伝搬の処理の流れを図 2 に示す．

の概念を導入する．特に，本研究ではスライディングウィン

図において u1 はターゲットユーザであり，この例では u1 に対ドウ（sliding window）に基づき影響最大化を定める．例え

して影響を与えるユーザ，つまりシードユーザの候補を特定す

ば，時間窓の大きさを 1 時間，移動幅を 30 分として考えた場

る．まず，u1 は u2 , u3 , u6 への辺を持つため，IC モデルに基合，{..., [9 : 00, 10 : 00], [9 : 30, 10 : 30], [10 : 00, 11 : 00], ...}

づき各ノードへの伝搬処理を行う．ここでは，u2 及び u6 へのというような 30 分刻みの時間窓がスライディングウィンド

伝搬が成功したとする．次に，u2 は u3 への，u6 は u4 , u5 へ

ウによって生成される．したがって，各時間窓の範囲で条件の辺を持つため，それぞれ同様に伝搬処理を行う．u6 から u4を満たしたユーザをターゲットユーザとみなすことで，時間への伝搬が成功した場合，更に u4 から u3 , u5 への伝搬処理をの経過によるターゲットユーザ集合の変化を考慮した影響の行う．ここで，u5 への伝搬のみが成功したとすると，u1 に影最大化が可能となる．なおこれ以降，本研究では時刻 t を終響を与えうるユーザは {u2 , u4 , u5 , u6 } の 4 人となる．

端とする時間窓を Wt で表す．例えば，上述の時間窓系列は{..., W10:00 , W10:30 , W11:00 , ...} のように表す．

逆伝搬を用いることで，無駄なくターゲットユーザに対する影響の大きさを求められる．ターゲットユーザからの逆伝搬で以下では，まず特定のユーザを対象とした場合の影響の大き得られるユーザ集合（逆到達集合: reverse reachable set ）のさの求め方を説明する．その後，本研究で提案する影響最大

要素は，言い換えればターゲットユーザに対して影響を与えら化問題の定義を示す．なお，本研究で使用する記号についてはれるユーザである．したがって，各ターゲットユーザの逆到達

表 1 にまとめる．

集合を求めその転置インデックスを考えることで，容易にある

2. 1 逆伝搬に基づく影響の大きさの導出

ユーザがターゲットユーザに与える影響の大きさを求められる．

本研究では IC モデルに基づく逆伝搬を用いて影響の大きさ

ある時間窓 Wt においてユーザ u ∈ V がターゲットユーザに与える影響の大きさを以下のように定める．

影響の大きさを基に，シード集合 S が与える影響の大きさを定Algorithm 1 caluculate I − (v) under IC model

める．

Input:［定義 22］ （時間窓 Wt においてシード集合 S が与える影響

Social Graph：G = (V, E, p), Targeted User：v
Output:の大きさ）

Reverse Reachable Set：I − (v)

シード集合 S ⊆ V 及び時間窓 Wt が与えられたとする．このと

1: I − (v) = ∅き，シード集合 S が影響を与えるターゲットユーザの部分集合

2: queue = ∅I(S, Wt ) 及びその影響の大きさ f (S, Wt ) を以下の式で求める．

3: queue.push(v)4: while queue =| ∅ do5:u = queue.pop()

6:

neighbors = {r | (r, u) ∈ E}

7:

for r ∈ neighbors do

8:

rand = a random value in [0, 1]

9:

if pur > rand ∧ r ∈/ I − (v) ∧ r =| v then10:

I − (v) = I − (v) ∪ {r}11:queue.push(r)∪I(u, Wt )

(3)

u∈S

f (S, Wt ) = |I(S, Wt )|(4)

なお，式 (4) は劣モジュラ関数である．
次に，上述のシード集合が与える影響の大きさを用いて，特定のユーザを対象とした影響最大化問題を以下のように定める．
［定義 23］ （特定のユーザを対象とした影響最大化問題）

end if

12:
13:

I(S, Wt ) =ソーシャルネットワーク G = (V, E, p)，シード集合の最大要素

end for

14: end while

数 k ，窓幅 w，及び移動幅 h が与えられたとする．このとき，

15: return I − (v)処理の開始時刻を ts = 0 とみなし，スライディングウィンドウに基づく時間窓 Wt の系列を {Ww , Ww+h , Ww+2h , ...} とする．
各時間窓 Wt について，以下の最適化問題の解となるシード集［定義 21］ （時間窓 Wt においてユーザ u が与える影響の大合 S ⊆ V を出力する．

きさ）
ある時間窓 Wt におけるターゲットユーザの集合を U (Wt ) で，

maximizef (S, Wt )あるユーザ u ∈ V の逆到達集合を I − (u) ⊆ V で表すとする．

subject toS⊆V

このとき，あるユーザ u ∈ V が時間窓 Wt において影響を与えるターゲットユーザの部分集合 I(u, Wt ) 及び影響の大きさ f (u, Wt ) はそれぞれ以下の式で求める．なお，本研究では

I(u, Wt ) をユーザ u の影響集合と呼ぶ．

(5)

|S| <
=k
この新しく定義した影響最大化問題は，時間窓 Wt の窓内で条件を満たしたターゲットユーザへの影響を最大化し，スライディ
ングウィンドウに基づく複数の時間窓により対象となるユーザ

I(u, Wt ) = {v | v ∈ U (Wt ) ∧ u ∈ I − (v)}(1)

f (u, Wt ) = |I(u, Wt )|(2)

最後に，ユーザ v の逆到達集合を求める具体的なアルゴリズ
ムを Algorithm 1 に示す．1 行目では，逆到達集合 I − (v) を空集合に初期化する．2，3 行目の queue は，ターゲットユーザの影響元となるユーザを一時的に格納するデータ構造であり，初期状態として与えられたターゲットユーザ v を格納する．4 行
目から 14 行目のループで queue 内の各ユーザを起点とした逆伝搬を行う．6 行目の neighbors はユーザ u と隣接するユーザの集合を表し，その全てのユーザについて影響元のユーザとなるかを調べる．7 行目から 13 行目では，伝搬確率 pur でユー
ザ r がユーザ u の影響元となり, 逆到達集合 I − (v) と queueにユーザ r が追加される．このとき，既に影響元となっている
ユーザは除外される．以上の処理を逆伝搬可能なユーザがいな
くなるまで繰り返し，最終的な逆到達集合 I − (v) を出力する．

2. 2 特定のユーザを対象とした影響最大化問題
ソーシャルネットワークにおいて特定のユーザに対する影響を最大化するため，時間窓を用いた新しい影響最大化問題を定義する．
まず，前節で定義した，時間窓 Wt においユーザ u が与えるの変化を考慮する．
例として，表 2，3，4 を用いて，提案する影響最大化問題における k = 2 のシード集合の特定を示す．なお，ここでは隣接する 2 つの時間窓 Wt 及び Wt+h を考える．時間窓 Wt におけるターゲットユーザを U (Wt ) = {u1 , u2 , u3 , u4 }, 時間窓 Wt+h
におけるターゲットユーザを U (Wt+h ) = {u3 , u4 , u5 , u6 , u7 }とする．各ターゲットユーザの逆到達集合を表 2 で示す．この逆到達集合から転置インデックスを用いて時間窓 Wt における各ユーザの影響集合を求めると表 3 のようになる．したがって，影響を与えられるターゲットユーザの数が最も大きくなるよう

2 人のシードを選択すると，{v1 , v3 } もしくは {v2 , v3 } が時間
窓 Wt における最適なシード集合となる．一方，時間が h 経過
した後の時間窓 Wt+h では，時間窓 Wt の時点と比べて u1 , u2がターゲットから外れ，代わりに u5 , u6 , u7 が加わったことになる．それに伴い，各ユーザの影響集合も表 4 のように変化するため，ターゲットユーザへの影響を最大化するシード集合は{v2 , v3 } 一つとなる．このように，各時間窓で異なるターゲッ
トユーザを扱い，それぞれで最適なシード集合を求めるのが本研究における影響最大化問題である．

表 2 ユーザの逆到達集合

Algorithm 2 Greedy Algorithm

ユーザ

逆到達集合

u1

v1 , v 2u2

v3 , v 4u3

v3 , v 4u4

v3 , v 5

1: caluculate I − (u) for u ∈ U (Wt ) under IC model from G

u5

v1 , v 3

2: caluculate I(u, Wt ) for u ∈ C(Wt )

u6

v2

u7

v2 , v 5

Input:
Social Graph：G,Seed Size：k，Targeted Users：U (Wt ),Output:Seed Set：S▷C(Wt ) = ∪v∈U (Wt ) I − (v)3: S = ∅4: for i = 1 to k do

表 3 I(u, Wt )表 4 I(u, Wt+h )

ユーザ

ユーザ

影響集合

5:

vi = arg max δ(S, Wt , v)

6:

S = S ∪ {vi }v∈C(Wt )\S

影響集合

v1

u1

v1

u5

v2

u1

v2

u6 , u7v3

u2 , u3 , u4v3u3 , u4 , u5v4u2 , u3v4

u3 , u7

v5

u4

v5

u4

7: end for
8: return S

表 5 例：時間窓 Wt における影響集合
ユーザ

3 影響最大化の手法について
3. 1 貪欲法に基づく単純な解法
前節で定義した関数 f (S, Wt ) は劣モジュラ関数であり，本I(vi , Wt )v1{u1 , u2 , u3 , u4 , u5 }v2

{u1 , u2 , u5 , u7 }v3

{u3 , u4 , u8 , u9 }v4

{u3 , u4 , u5 }v5

{u3 , u6 }研究で扱う影響最大化問題も NP 困難な問題 [2] である．つまり，グラフの規模やシード集合の要素数 k が大きいとき，実時をターゲットユーザに対して影響力のあるユーザ集合として出間で最適解を求めるのは難しい．

力する．

一方，劣モジュラ関数であるがゆえに，貪欲法を用いること

貪欲法によるシード選択の例を表 5 を用いて説明する．時間で各時間窓における影響最大化の近似解を近似度 1 − 1/e で求

窓 Wt におけるシードの候補ユーザとその影響集合は表 5 で示められる [3]．つまり，スライディングウィンドウによって生成すものとし，シード集合 S の大きさを k = 2 とする．まず，シーされる各時間窓 {Ww , Ww+h , Ww+2h , ...} に対して，それぞれド集合 S を空集合に初期化する．その後，式 (6) に基づき影響の時間窓が終端に達した時点で貪欲法を適用することで近似解の大きさ f (S, Wt ) が最も増加するユーザをシードとして追加しが求められる．ただし，本研究では特定のユーザを対象としたていく．ループ一巡目では，f (∅, Wt ) = 0 であるため，単純に影影響最大化問題を扱うため，貪欲法の各ステップでシードを選響を与えるターゲットユーザ数が最も多いユーザ v1 をシードとぶ際の指標には以下の式を用いる．

して選択する．二巡目では，I({v1 }, Wt ) = {u1 , u2 , u3 , u4 , u5 }に対する増分が最も大きいユーザを選ぶため，ユーザ v3 をδ(S, Wt , u) = f (S ∪ {u}, Wt ) − f (S, Wt )(6)

具体的に，貪欲法を用いた影響最大化アルゴリズムの流れを Algorithm 2 に示す．なお，ある時間窓 Wt における影響最大化を想定する．Algorithm 2 ではソーシャルネットワーク

G = (V, E, p)，ターゲットユーザ U (Wt )，シード数 k を入力とし，k 人のシード集合を出力する．1 行目では IC モデルに基づ
きターゲットユーザの逆到達集合を作成する．ここで，時間窓

Wt のターゲットユーザに対してシードの候補となるユーザ集
合を候補集合（candidate set）と定義し，C(Wt ) で表す．また，シードの候補集合 C(Wt ) 内のユーザをシードの候補ユーザと呼ぶ．ターゲットユーザの逆到達集合がターゲットユーザに影響を与えるユーザの集合であるため，作成した逆到達集合の和集合が時間窓 Wt におけるシードの候補集合となる．次に，2行目でシードの候補ユーザに関して，式 (1) を用いて影響集合を導出する．そして，4 行目から 7 行目のループで δ(S, Wt , u)が最も大きな値となるシードの候補ユーザ u をシードとして選択していく．最終的にシードを k 人選択した後，シード集合 S

2 人目のシードとして選択する．結果として，シード集合はS = {v1 , v3 } となる．
3. 2 SSM アルゴリズムに基づく連続的処理
貪欲法により近似解を求められる一方，貪欲法の処理手順はストリーム処理に向かないという問題がある．Algorithm 2 の

5 行目に示すように，貪欲法ではループの各ステップでシード集合が与える影響力の増分値が最も高いユーザをシードとして追加していく．この処理を行うためには，そもそも対象となる
ターゲットユーザ U (Wt ) が全て判明している必要がある．つまり，時間窓 Wt = [t − w, t] について影響最大化問題を解く
とき，貪欲法では時刻 t になるまで一切の処理を行えない．しかし，時刻 t 以前，つまり [t − w, t) の間にも対象となるター
ゲットユーザは逐次追加される．そのようなユーザの追加に対してストリーム処理に基づきシード集合の更新を行うことができれば，時刻 t まで全ての処理を待つ必要がなくなり，時刻 tとなってからシード集合を出力するまでのレイテンシの削減が

期待できる．

Algorithm 3 SSM Algorithm（Parameter:k, ϵ）

そこで本研究では，既存研究にて提案された SSM（streaming// Initialize

submodular maximization）アルゴリズム [1] を本研究の問題

1: OI = {(1 + ϵ)i | i ∈ Z}

定義に合わせて拡張する．SSM アルゴリズムは，ストリーム

2: For each α ∈ OI ， Sα = ∅処理に対応した劣モジュラ関数最大化のアルゴリズムである．

3: m = 0

本研究で提案した影響最大化問題も劣モジュラ関数最大化であるため，SSM アルゴリズムにより時間窓 Wt での影響最大化を
ストリーム的に処理する．つまり，時区間 [t − w, t) における// If data v is inputed
4: m = max(m, g(v))
i5: O = {(1 + ϵ)i | m <= (1 + ϵ) <= 2 · m · k}

6: Delete all Sα such that α ∈/O

逐次的なターゲットユーザの追加に対し，適宜シード集合 S を

7: for α ∈ O do

更新し，時刻 t におけるシード集合出力までのレイテンシの削8:減を目指す．

9:

以下では，まず SSM アルゴリズムの概要を紹介し，その後本研究の問題定義に合わせて SSM アルゴリズムを拡張する．

3. 2. 1 SSM アルゴリズム

α−g(Sα )
2if δg (v | Sα ) >= k−|S | and |Sα | < kαSα = Sα ∪ {v}

10: end for// If output is required
11: return arg max g(Sα )α∈O

SSM（streaming submodular maximization）アルゴリズ
ム [1] は，一連のデータから劣モジュラ関数の値が最大となる要素を k 個選択する際，劣モジュラ関数に渡される要素を 1 度
のみ調べるだけで処理が可能な手続きを提供する．すなわち，大規模なデータやストリームデータに対する劣モジュラ関数最大化を考える際，任意の順番で各データを 1 度のみスキャンし，その場でスキャンした要素を劣モジュラ関数最大化の解として選択すべきか決定できる．また，劣モジュラ関数最大化に対する一般的なアプローチでは全てのデータを読み込んだ後でなければ解を出力できないが，SSM アルゴリズムでは全てのデー
タを調べなくてもデータをいくつか読み込んだ時点でその時点の解を出力可能である．なお，SSM アルゴリズムの目的である劣モジュラ関数最大化は，|S| <= k の制約の中で g(S) の値を最大化することである（劣モジュラ関数 g ，整数 k ，集合 S ）．

SSM アルゴリズムでは，劣モジュラ関数 g と劣モジュラ関数の最適な最大値 OP T が与えられたとき，以下を満たす要素

v を劣モジュラ関数を最大化する候補解 CS の要素として選択する．なお，候補解 CS は集合である．

g(CS ∪ {v}) − g(CS) >=解に要素 v を追加する．SSM アルゴリズムでは複数の候補解が生成されるが，最終的な解は複数の候補解の中で劣モジュラ関数の値が最も大きい候補解を出力する．なお，SSM アルゴ
リズムは 1/2 − ϵ の近似を保証する．

SSM アルゴリズムの一連の流れを Algorithm 3 に示す．1行目から 3 行目は，SSM アルゴリズムの初期化処理を示す．

4 行目から 10 行目は，入力要素 v に対する処理を表す．4 行
目では，単一要素の劣モジュラ関数の最大値を更新する．5 行
目では，式 (8) を用いて，推定値の更新を行う．6 行目では，
これまで使用した推定値の中で新しく更新した推定値に対して範囲外になるものがあれば，その推定値に対応する候補解を削除する．7 行目から 10 行目では，各推定値ごとに式 (7)を用いて要素 v を候補解として選択するかを決める．なお，

δg (v | Sα ) = g(CS ∪ {v}) − g(CS) である．11 行目は，複数の候補解の中で劣モジュラ関数の値が最も大きい候補解が最終的な解として出力されることを示す．

3. 2. 2 SSM アルゴリズムの適用− g(CS)∧ |CS| < k (7)k − |CS|

OP T
2

また，最適な最大値 OP T は求めることができないため，単一要素の関数値の最大値 m を用いて式 (8) を満たす値を最適な

本研究では，時間窓を用いた影響最大化問題を解くために

SSM アルゴリムを適用する．本研究の影響最大化問題では，影響最大化の対象となるユーザの追加に対して新しいシードの候補集合が生成されるため，シードの候補ユーザを劣モジュラ関数の入力要素として SSM アルゴリズムを実行することにより，最大値として推定する．

シードの更新が可能となる．
i
O = {(1 + ϵ)i | m <= (1 + ϵ) <= 2 · m · k}(8)i は整数であり，式 (8) を満たす i の数だけ推定値も存在する．
また，ϵ は SSM アルゴリズムの入力パラメータであり，解の品
質を調整する．ϵ の値が小さいほど多くの推定値を列挙できる
ため，解の品質は良くなる．しかし推定値が多いほど，それに対応して考慮すべき候補解の数も増えるため，実行時間は大きくなる．逆に，ϵ の値が大きければ解の品質は少し下がるがア
ルゴリズムの実行時間は少なくなる．導出された複数の推定値に対しては，各値（α ∈ O）ごとに式 (7) に基づいて候補解を構築していく．すなわち，SSM アルゴリズムの入力要素 v に対して式 (7) が満たされれば，使用した推定値に対応する候補

SSM アルゴリズムを用いた影響最大化の流れを Algorithm
4 に示す．ここでは，時間窓 Wt のターゲットユーザに対する
シード集合を導出する．入力はソーシャルグラフ G，整数 k ，パラメータ ϵ であり，出力はシード集合 S である．本アルゴリ
ズムは，窓内で影響最大化の対象となるユーザが追加されるたびにリアルタイムに実行されるものと想定する．1 行目から 3
行目は，時間窓に対する初期化処理を示す．4 行目からは，ター
ゲットユーザ u に対する処理を示す．5 行目では，シードの候補集合を空集合で初期化する．6 行目では，ターゲットユーザ

u に対して IC モデルをもとに逆到達集合を作成する．7 行目では，シードの候補集合を導出し，候補ユーザの影響集合を作成

Algorithm 4 SSM Algorithm for IM (time window：Wt )ユーザの処理は Algorithm 4 の 9 行目から 15 行目に該当する．

Input:
Social Graph：G = (V, E, P ), Seed Size：k， Parameter：ϵ,Output:はシード集合 Sα の影響力，q は推定値 α とシード集合 Sα に

1: OI = {(1 + ϵ)i | i ∈ Z}
2: For each α ∈ OI ， Sα = ∅（as much as necessary）
3: m = 0

6:caluculate I − (u) under IC model from G

7:caluculate I(v, Wt ) for v ∈ C(Wt )8:for v ∈ C(Wt ) do

▷ C(Wt ) = I − (u)

10:
11:

Delete all Sα such that α ∈/O

12:for α ∈ O do
if δ(Sα , Wt , v) >=Sα = Sα ∪ {v}

16:

いた影響最大化では，最初にユーザの追加に対して 1 人のユー
ザが与える影響力の最大値 m を更新する．今回は v1 が最初の入力であるため，m = f (v1 , Wt ) = 1 となる．次に，式 (8) にm = max(m, f (v, Wt ))i
O = {(1 + ϵ)i | m <= (1 + ϵ) <= 2 · m · k}

13:

対してユーザ v をシードとして追加したときの影響力の増分値
まず，v1 の処理について説明する．SSM アルゴリズムを用C(Wt ) = ∅14:

より定められる閾値，δ(Sα , Wt , v) は現在のシード集合 Sα にを示す．

4: for u ∈ U (Wt ) do
5:15:

図 3 における表の記号は，α は適切なシード集合が与える影響力の推定値，Sα は各推定値に対応するシード集合，f (Sα , Wt )Seed Set：S

9:のユーザを順番に SSM アルゴリズムで処理していく．なお，各

α −f (S ,W )αt2k−|Sα |

基づいて推定値 α を導出する．推定値 α が求められたら，次は各推定値ごとにシードの計算を行う．そして，各推定値に対して現在のシード集合 Sα と合わせて閾値 q を計算する．そのand |Sα | < kend forend for17: end for// If Wt is finished
18: return arg max f (Sα , Wt )α∈O

後，影響力の増分値 δ(Sα , Wt , v) を計算し，閾値を超えていた
場合はシードとして選択する．図 3 の表では，v1 をシードとして選択したときの影響力の増分値は 1 であり，推定値 1.2 に対して計算された閾値 0.2 や推定値 5.16 に対して計算された閾
値 0.86 よりも高いため，それぞれのシード集合に対して v1 が追加される．なお，表に示す推定値 e は複数ある中の一部であることに注意する．
次に，v2 の処理について説明する．v2 のターゲットユーザ

する．8 行目から 16 行目では，シードの候補ユーザを入力要素

に対する影響力は f (v2 , Wt ) = 3 であり，v1 の影響力より大きとした SSM アルゴリズムによりシード集合の候補解を更新す

い．そのため，m の値が更新される．また，m の値が変更される．候補解の更新の流れは Algorithm 3 の 4 行目から 10 行目

ることで，考慮する推定値 α も変化する．ここでは，3 以上 18と同様である．ここまでの処理は時間窓の窓内でストリーム的以下の推定値のみを考えるため，3 より低い推定値に基づいてに処理することを想定する．18 行目は，時間窓が終端に達した

導出したシード集合は削除する．今回で言えば，α = 1.2 に対ときの処理を示す．ここでは，最終的に存在する複数の候補解応するシード集合が削除されたことになる．以降の処理は，v1の中で最も影響力が高い候補解を見つけ，時間窓 Wt におけると同様に各推定値に対して閾値を計算し，閾値よりも影響力のシード集合として出力する．

増分値が高ければシードとして選択する．図 3 の表では，v2 のなお，Algorithm 4 ではターゲットユーザ 1 人ずつに対してシード集合を更新していく場合の処理を示したが，現実的な問

増分値が各閾値よりも高いためシードとして追加されたことになる．残りの v3 , v4 の処理も同様に行う．

題を考えた場合，複数のターゲットユーザが同タイミングで追今回の例のように，SSM アルゴリズムを用いた影響最大化

加されることもあり得る．その際は，複数のターゲットユーザ

では各推定値に対してシード集合を別々に計算していくため，に対してバッチ処理を行う．複数のターゲットユーザの処理を複数のシード集合が計算されることになる．これらは全て最終

まとめることで，窓内でのシード集合の更新回数の削減が期待的なシード集合の候補解である．最終的な解を出力したい場合できる．SSM アルゴリズムで複数のターゲットユーザを処理は，複数のシード集合の中で影響力が最大のシード集合を結する際，1 人ずつ処理するよりもバッチ処理が効率的であるこ果として出力する．今回の例でいえば，v4 の処理終了後にはとは実験でも示す．

{v1 , v2 , v3 }, {v2 , v4 }, {v2 } の 3 つのシード集合が存在する．こ3. 2. 3 具 体 例の中で 1 番影響力のあるシード集合は {v1 , v2 , v3 } と {v2 , v4 }本項では，SSM アルゴリズムを用いたシード集合の特定例

であり，今回の例ではこのどちらかのシード集合が SSM アルを述べる．例として k = 3，ϵ = 0.2 の条件でシード集合を計算する．ここでは，影響最大化の対象となるターゲットユーザの集合は {u1 , u2 , u3 , u4 , u5 } を想定し，ターゲットユーザに対す
るシードの候補ユーザおよびその影響集合は表 6 で示されるものとする．
シードの候補ユーザからシード集合を計算する流れを図 3 に示す．今回の例ではシードの候補ユーザは 4 人いるため，4 人

ゴリズムの解として出力される．

表 6 例：シードの候補ユーザと影響集合

で SSM アルゴリズムによるシード集合の更新を行う．シング
ルスレッドで行われるため各時間窓に対する処理は順番に行う

シードの候補ユーザ 影響集合

v1

{u1 }

しかないが，各ターゲットユーザの逆伝搬集合などは全ての時

v2{u2 , u3 , u4 }間窓で共有でき，メモリの使用量を抑えられる．

v3{u2 , u3 }一方，2 つ目の方法として分散ストリーム処理に基づく方法

v4{u4 , u5 }がある．各時間窓に対する処理はそれぞれ独立であるため，マルチスレッドないしマルチノードで計算を行えば，並列数の許す限り各時間窓に対する処理を並列実行できる．その分多くの

𝛼
1.2
5.16

𝑆𝛼
∅
∅

計算資源を必要とし，かつ逆伝搬集合などの共有も行えないが，

𝑚 = 𝑓 𝑣1 , 𝑊𝑡 = 1① 𝒗𝟏 を入力

𝑓(𝑆𝛼 , 𝑊𝑡 )00𝑞𝛿(𝑆𝛼 , 𝑊𝑡 , 𝑣𝟏 ) new 𝑆𝛼
0.2 <
1
{𝑣1 }
0.86 <
1
{𝑣1 }

※𝑞 =
② 𝒗𝟐 を入力

𝑚 = max(1, 𝑓 𝑣2 , 𝑊𝑡 ) = 3𝛼𝑆𝛼𝑓(𝑆𝛼 , 𝑊𝑡 )

3.58
15.41

{𝑣1 }
∅

1
0

𝛼
−𝑓 𝑆𝛼
2

𝑘− 𝑆𝛼

𝑞 𝛿(𝑆𝛼 , 𝑊𝑡 , 𝑣𝟐 ) new 𝑆𝛼0.36 < 3{𝑣1 , 𝑣2 }2.57 < 3{𝑣1 , 𝑣2 }スループットや遅延といった性能を優先したい場合はこちらも選択肢となる．

3. 3 索引の構築
本研究の影響最大化アルゴリズム（Algorithm 2，Algorithm4）の過程ではターゲットユーザの逆到達集合を作成する．ここで，各ユーザに対する逆到達集合は IC モデルにより求められるが，どの時間窓でも逆到達集合の求め方は変わらない．そ③ 𝒗𝟑 を入力

𝑚 = max(1, 𝑓 𝑣2 , 𝑊𝑡 ) = 3𝛼𝑆𝛼𝑓(𝑆𝛼 , 𝑊𝑡 )3.58

{𝑣1 , 𝑣2 }4

𝑞 𝛿(𝑆𝛼 , 𝑊𝑡 , 𝑣𝟑 ) new 𝑆𝛼−2.2 < 0{𝑣1 , 𝑣2 , 𝑣3 }5.16

{𝑣1 , 𝑣2 }4

−1.4 <

0{𝑣1 , 𝑣2 , 𝑣3 }

6.19

{𝑣2 }

3

0.05

≮

0

{𝑣2 }

15.41

{𝑣2 }

3

2.57

≮

0

{𝑣2 }

④ 𝒗𝟒 を入力のため，事前にソーシャルネットワークにおけるユーザの逆到
達集合の索引を構築することで，影響最大化アルゴリズムの実
行時間を削減可能である．
また，ソーシャルネットワークの規模が大きい場合，あらかじめ全ユーザの逆到達集合を作成することは現実的ではない．
その際は事前に作成する索引の上限を設け，索引に存在しない

𝑚 = max(3, 𝑓 𝑣4 , 𝑊𝑡 ) = 3𝑓(𝑆𝛼 , 𝑊𝑡 )𝑞𝛿(𝑆𝛼 , 𝑊𝑡 , 𝑣𝟒 )new 𝑆𝛼ターゲットユーザの逆到達集合は，影響最大化アルゴリズムの3.58 {𝑣1 , 𝑣2 , 𝑣3 }

4

−2.2

/

{𝑣1 , 𝑣2 , 𝑣3 }過程で作成する．索引の上限は索引の作成時間や索引の大きさ

5.16 {𝑣1 , 𝑣2 , 𝑣3 }

4

−1.4

/

{𝑣1 , 𝑣2 , 𝑣3 }

6.19

{𝑣2 }

3

0.05 <

1{𝑣2 , 𝑣4 }

15.41

{𝑣2 }

3

2.57

≮

1

{𝑣2 }

𝛼

𝑆𝛼

図 3 SSM アルゴリズムを用いたシード集合の導出例（逆到達集合の数）などがあげられる．

4 実

験

実験では，The Koblenz Network Collection [6] の実世界のネットワークデータを用いた．今回使用したデータセットを表 7

3. 2. 4 複数の時間窓に対する処理方法に示す．また，元のデータセットには辺の伝搬確率があらかじ

こ れ ま で は あ る 時 間 窓 Wt に 対 す る SSM ア ル ゴ リ ズ
表 7 データセット

ム の 適 用 に つ い て 述 べ た が ，本 研 究 で は 複 数 の 時 間 窓

Dataset{Wt , Wt+h , Wt+2h , ...} に対する処理を述べる．ここまで述
べたように，SSM アルゴリズムを提案手法に合わせて拡張することで，ある時間窓 Wt における影響最大化問題の解はスト

頂点数

辺の数

Digg

30,39885,247

Epinions

131,828

840,799

Facebook

63,741 1,634,070

リーム処理によって低遅延で求められる．しかし，本研究ではスライディングウィンドウに基づく複数の時間窓を想定するため，それらをいかに効率よく処理するかも重要な課題である．
まず，1 つ目の方法として，シングルスレッドで全ての時間
窓を処理する方法がある．この方法では，ターゲットユーザ集
合を時間窓毎に分けて管理し，ある時刻でターゲットユーザが追加された場合は対応する全ての時間窓に対してそのユーザを追加する．例えば，窓幅 1 時間，移動幅 15 分のスライディ
ングウィンドウを用いる場合を考える．時刻 9:00 から処理を開始した場合，9:30 の時点では 3 つの時間窓 W10:00 = [9 :00, 10 : 00], W10:15 = [9 : 15, 10 : 15], W10:30 = [9 : 30, 10 : 30]
に対する処理が始まっている．したがって，9:35 の時点であるユーザ u がターゲットユーザとなったとき，3 つの時間窓

W10:00 , W10:15 , W10:30 それぞれにユーザ u を追加し，それぞれ

め付加されていなかったため，Tr モデル（{0.1,0.01,0.001}からランダムに選択）または WC モデル（辺の確率 = 1/ 頂点の入次数）を用いて伝搬確率を付与し，計 6 種類のグラフを用意した．実験では，1 つの時間窓におけるターゲットユーザが n
人であると仮定し，影響最大化問題を解いて k 人のシード集合を出力した．6 種類のグラフに対する実験結果は同じ傾向が見られたため，ここでは Facebook のデータに対する実験結果を示す．
まず，貪欲法と SSM アルゴリズムを用いた手法のレイテン
シの計測結果を図 4，5 に示す．ここでは，n 人のターゲット
ユーザを読み込んでから k 人のシード集合を得られるまでの時間を計測した．結果として，シード集合の要素数やターゲット

人数にかかわらず，貪欲法よりも SSM アルゴリズムの方が低レイテンシでシード集合を出力可能であった．すなわち，貪欲
法よりも SSM アルゴリズムを用いた手法が提案した影響最大化問題を効率的に解けると考えられる．

図 7 ターゲットユーザの処理単位と窓内での総実行時間の関係

図 4 レイテンシ (k を変化)

図 5 レイテンシ (n を変化)

次に，逆到達集合の索引がある場合とない場合で，SSM アル
ゴリズムの窓内での処理時間を比較した．実験結果は図 6 に示

図 9 影響力 (n を変化)

図 8 影響力 (k を変化)

す．結果として，事前の索引構築により窓内での処理時間を削減可能であった．しかし，処理時間の削減率はわずかであった
ため，実際には IC モデルの逆伝搬処理より SSM アルゴリズムのシード集合更新の処理に時間がかかっていると考えられる．

5 ま と め本研究ではスライディングウインドウに基づく時間窓を導入した新しい影響最大化問題を提案した．提案した影響最大化問
題は影響最大化の対象を限定し，対象となるユーザの変化が表現可能であった．また，提案した影響最大化問題の解法として
貪欲法と SSM アルゴリズムを用いた手法を挙げた．実験ではSSM アルゴリズムを用いた手法が効率的であることを示した．

謝
図 6 窓内での処理時間（索引あり，なし）

次に，窓内でターゲットユーザを 1000 人処理する際，ター
ゲットユーザ 1 人ずつに対してシード集合を更新していく場合と 10 人，100 人，1000 人とターゲットユーザをまとめてシード集合を更新していく場合で窓内での総実行時間を計測した．
計測結果は図 7 に示す．結果として，ターゲットユーザをまとめて処理したほうが実行時間は少なくなった．このことから，
窓内でのターゲットユーザの処理はマイクロバッチ処理が重要であると考えられる．
最後に，貪欲法と SSM アルゴリズムで得られたシード集合の影響力の比較を行った．シード集合の影響力の計測結果は図8，9 に示す．ここでは，貪欲法よりも SSM アルゴリズムの方がシード集合の影響力が下がる結果となった．しかし，貪欲法と SSM アルゴリズムの近似率の差ほど，実際の影響力の差はなかった．さらに，k の値が小さい時は貪欲法と SSM アルゴ
リズムの差も少なくなった．また，影響最大化問題は NP 困難
な問題であるため，貪欲法で求めたシード集合が最も基本的なものである．今回の SSM アルゴリズムは貪欲法と同程度の結果が得られたといえるため，SSM アルゴリズムで求めたシー
ド集合の影響力は問題ないものと考える．

辞本研究の一部は科研費（16H01722）による．

文

献[1] A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A.
Krause. Streaming submodular maximization: Massive datasummarization on the fly. In KDD, pp. 671-680, 2014.
[2] D. Kempe, J. Kleinberg, and Ė. Tardos. Maximizing the
spread of influence through a social network. In KDD, pp.
137-146, 2003.
[3] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265-294, 1978.
[4] N. Ohsaka, T. Akiba, Y. Yoshida, and K.Kawarabayashi.
Dynamic influence analysis in evolving networks. PVLDB,
9(12):1077-1088, Aug. 2016.
[5] Y. Wang, Q. Fan, Y. Li, and K.-L. Tan. Real-time influence maximization on dynamic social streams. PVLDB,
10(7):805-816, 2017. content...
[6] The koblenz network collection. http://konect.uni-koblenz.de/.
[7] W. Chen, L. V. Lakshmanan, and C. Castillo. Informationand influence propagation in social networks. Synthesis Lectures on Data Management, 5(4):1–177, 2013.
[8] 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.
[9] C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In Proc. SODA,
pages 946–957, 2014.