情報拡散過程のダイナミクス： 非線形モデルの提案と情報予測
12
0
0
全文
(2) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). 表 1. 既存手法との比較. Table 1 Capabilities of approaches. Only our approach meets all specs.. パワー則による減衰. C-S √. K-SC. システム同定 非線形性 周期性 将来予測の能力. SI. AR. √. √. √ √. SPIKEM √ √. √. √. √. √. ントの質・注目度 β ，(c) イベント直後（時刻 nb ）に影響 を受けるノード（ユーザ）の数 Sb が与えられたとき，情報 拡散過程のダイナミクスを表現する． もう 1 つの重要な問題は，情報拡散過程のパターンが与 えられたうえで，そのダイナミクスを図 1 にあるように， 単一のモデルで表現することである． 図1. 問題 2 情報拡散過程のパターンが与えられたとき，少 オンラインメディア上に現れる 6 つの代表的な情報拡散パター ン（K-SC [43]）と SpikeM の効果. Fig. 1 Modeling power of SpikeM: six types of spikes (K-SC from [43]) in dots, and our model fit in solid red line.. ない数のパラメータを用いて，それらのダイナミクスを柔 軟に表現する非線形モデルを推定する． ここで重要な点として，情報拡散の分析において，モデ ルの各パラメータは直感的な意味を持つことが望ましい．. データを用いた先行研究 [6] では，情報拡散には 4 種類. たとえば，ユーザの総数，ニュースの注目度等の意味のあ. （endogenous-subcritical，endogenous-critical，exogenous-. る数値をパラメータとして扱いたい．逆にいえば，自己回. subcritical，exogenous-critical）のパターンがあり，ブロ. 帰モデル（AR: autoregressive model）のような既存のモ. グデータを用いた文献 [43] では，図 1 にあげるように，. デルでは，a1 ，a2 といった，係数値を用いて時系列データ. 主に 6 種類の拡散パターンが存在すると主張されている．. を表現するため，パラメータ単体では意味を持たず理想的. 一方，本研究では，まったく別の視点からこの問題に取り. とはいえない．加えて，情報拡散のモデルはシンプルであ. 組む．我々の手法は，“単一のモデル” によって，これらの. るべきである．すなわち，モデルパラメータはできる限り. 様々な情報拡散のパターンを表現する．提案モデルである. 少ない方が望ましい．. SpikeM [27] *1 はシンプル（データセットのサイズと比較 し少ない数のパラメータ）であるにもかかわらず，上記の あらゆるダイナミクスを生成することができる．. 1.1 関連研究と本研究の位置づけ 本研究で提案する非線形モデル SpikeM は，(a) 情報の. 図 1 は，オンラインメディアにおける 6 つの代表的な情. 拡散過程においてパワー則に基づく減衰パターンを有し，. 報拡散のパターン（黒点線）と，それに対する SpikeM の. (b) 有限のノード（ユーザ）を仮定し，(c) 周期性を持つ．. 学習結果（赤線）である．それぞれのシーケンスは 1 時間. 従来研究には，これらの特長をすべて持つモデルは存在し. ごとの情報の伝播数で，長さは 5 日間である．SpikeM は. ない．たとえば，AR や ARIMA に代表される時系列モデ. 7 つのパラメータを使用することによって，6 種類すべて. ルは線形であり，指数則に基づく減衰パターンを持つため，. の拡散パターンを高精度で表現することができる．. 実データのパターンを表現できない．加えて，無限大に発. 本論文の目的は，ブログ等に代表されるオンライン上の. 散する可能性がある．表 1 は既存研究と SpikeM の能力. 情報拡散過程を，時系列モデルとして表現することである．. の比較である．Crane と Sornette らによる C-S 法 [6] は，. 以下では簡略化のために主にブログの例について言及する. ノード（ユーザ）の総数に関する有限性を保証していない．. が，提案手法は他の様々な拡散過程（購買数の変化，コン. K-SC [43] による代表的な拡散パターン（図 1）はパラメ. ピュータウィルスの伝染，Twitter 上での噂の伝播等）に. トリックなモデルではなく，将来予測の能力を有さない．. おいてもモデル化が可能である．本論文で取り組む問題は. SI モデルは数理疫学における代表的な非線形モデルであ. 以下のとおりである．. り，マーケティングにおける新製品の拡散過程を表現する. 問題 1 事前情報として，(a) ブログユーザの数 N とネッ. Bass モデル [3] に近い性質を持つ．SI モデルはピーク時ま. トワーク構造，(b) あるイベントの発生時刻 nb とそのイベ. での拡散過程とその後の減衰両方において，指数則に従う. *1. ソースコード：http://www.cs.cmu.edu/˜yasuko/SRC/ spikeM.zip. c 2013 Information Processing Society of Japan . という性質を持つため，実データにおけるパワー則の減衰 パターンを表現できない．. 12.
(3) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). 1.2 本論文の貢献. SpikeM の中で最も重要な要素は減衰関数 f (τ ) である．. 本論文では情報拡散過程の解析ためのモデルとして. これは，時間 τ が経過するにつれて，そのブログポストが. SpikeM [27] について述べる．SpikeM は以下のような特. どの程度の影響力を与えるかを示す．なお，既存の数理疫. 長がある．. 学モデルである SI モデルでは，減衰関数 f () を定数であ. • 既存研究における情報拡散モデルを一般化し，文. ると仮定している．これはたとえば，1 度病気になった患. 献 [20], [43] を含む様々なパターンを表現する．. 者がそれ以降つねに一定の確率で病気を他者へ感染させる. • 少ないパラメータ数で構成され，それぞれのパラメー. ようなケースである．しかし，近年の分析によると，情報. タが直感的な意味を有する．. 拡散における影響力はパワー則に基づき時間とともに減衰. • SpikeM の利用により，将来の予測や外れ値検出等の. していく例が数多く見られている．. 重要なアプリケーションを実現する．. 2. 提案モデル. 提案モデルは以下のような振舞いをする．. • イベント（ニュース）が発生する時刻 nb までは何も 起きない．. 本章では，ネットワーク上における情報拡散過程を表現. • 時刻 nb にイベントが発生すると同時に，即座に Sb 人. するモデルである SpikeM について述べる．提案モデル. のブログユーザがそのニュースに関する記事をブログに. は，図 1 にあげられるような実際の情報拡散過程における. ポストする．. 特徴を表現する必要がある．その特徴とは，まず (a) 無限. • 他のブログユーザが，すでにポストされたイベントに. 大に発散することなく必ず収束することを保証し，(b) 情. 関する記事を読み，一定の確率でそのニュースの影響を. 報拡散はパワー則に基づき減衰していくこと，そして，(c). 受ける．その後イベントの影響を受けた（ニュースにつ. 周期性を持つことである．(a) については，ネットワーク上. いて通知された）ユーザは自身のブログ内でそのニュー. のユーザの数を有限とすることで解決できる．(b) につい. スについて言及（ポスト）する．. ては，ネットワークの各ノード（ユーザ）の感染力をべき指. 本手法ではモデルをシンプルにするため以下の条件も加. 数（たとえば −1.5）によって減衰させることで表現するこ. える．. とができる．(c) については，ユーザの時間帯ごとの活動の. • ブログユーザは同じニュースに関する記事を 1 度しか. 変化を考慮することでモデルをより現実的なものとする．. ポストしない．. • それぞれのイベントは完全独立の関係にあり，1 つの 2.1 SPIKEM の概要. イベントに対し外部ショックは 1 度しか加えられない．. ここでは，提案するモデルの概要を示すと同時に，SpikeM. 我々の目的は，時刻 n においてブログポストを行った. を構成するパラメータの説明を行う．提案モデルは，初め. ユーザの数 ΔB(n) を，時刻 n とその他のパラメータに関. に N 人のブログユーザを想定する．この時点では，どの. する式で表現することである．ここでのパラメータとは，. ユーザもイベント（ニュース）について知らされておらず，. ブログユーザの総数 N やニュースの影響力の強さ β 等で. ブログサイトにも記事をポストしていないものとする．続. ある．この時点では，まだ周期性については考慮しない．. いて，時刻 nb に特定のイベントが発生する．ここでいう. この基本的なモデルを SpikeM-Base と呼ぶ．. イベントとは，たとえば，インドネシアの津波のニュース の速報や，選挙活動のスピーチに関する話題を指す．する と時刻 nb においてまず，即座に Sb 人のユーザが自身のブ ログにポストする．本論文では，このようなイベントを外. 2.2 SPIKEM-BASE SpikeM は次にあげられる 2 つの状態のノード（ブログ ユーザ）から構成される．. 部からのショックと呼ぶ．nb はイベントの誕生時刻，Sb. • U（Un-informed）：ニュースの内容をまだ通知されて. はイベントの外部からのショックの強さを示す．. いないブログユーザ. さらに，ニュース（イベント）の質，注目度に関するパ. • B（Blogged）：ニュースを通知され，その後ブログに. ラメータとして β を用いる．もし β = 0 だった場合，その. ニュースの内容をポストしたユーザ. ニュースは誰からも注目されていないため，すぐに消えて. 時刻 n の時点でまだそのニュースの影響を受けていない. しまう．β が高い値の場合は，より多くのユーザが興味を. ユーザの数を U (n) とする．時刻 n にニュース内容を通知. 持ち，ブログポストを行う．ここで，β ∗ N は，初期のイ. されたユーザの数を ΔB(n) とする．1 度ニュースについ. ベントの強さ（イベントの影響力）を示す．これは，1 人. て通知され影響を受けたユーザは，その噂についてただち. のユーザがニュースを知らされたときに，次の時刻に何人. に（時刻 n に）自分のブログへポストすることとする．. のユーザが影響されるかを表現する*2 ．. モデル 1（SPIKEM-Base） 提案モデル SpikeM-Base は，以下の 2 つの式から構成される．. *2. 厳密には N − 1 人であるが，簡略化のために N とする．. c 2013 Information Processing Society of Japan . 13.
(4) 情報処理学会論文誌. Vol.6 No.5 11–22 (Dec. 2013). データベース. ΔB(n + 1) n = U (n) · ΔB(t) + S(t) · f (n + 1 − t) + . 表 2. Table 2 Symbols and definitions.. (1). t=nb. U (n + 1) = U (n) − ΔB(n + 1). (2). ここで，. f (τ ) = β ∗ τ −1.5. 主な記号と定義. (3). 記号. 定義. N. あるイベントに影響されるユーザの潜在的な人数. nd. シーケンスの長さ. n. 時刻（n = 0, . . . , nd ）. U (n). Un-informed：ニュースの内容を通知されていないユーザ数. B(n). Blogged：ニュースの内容を通知されたユーザの総数. ΔB(n) 時刻 n においてニュースを通知されたユーザ数. であり，初期状態を次のように設定する．. ΔB(0) = 0, U (0) = N また，外部ショックとして S(n) を考える．これは，イ ベントの誕生時刻 nb に与えられる影響の大きさで，次の ような式で表現される．. . S(n) =. 0. (n = nb ). Sb. (n = nb ). f (τ ). あるブログポストの τ 時刻後におけるの影響力（感染力）. β. イベント（ニュース）の影響力の強さ. S(n). 時刻 n における外部ショックの大きさ. nb. ニュース速報が報道された時刻（イベントの誕生時刻）. Sb. イベント誕生時刻 nb における外部ショックの強さ. Pp. 周期（1 日周期等）. Pa. 周期の振幅. Ps. 周期の位相. (4) 時間帯ごとの活動の変化は，モデル 1 では表現できない．. 2.2.1 提案モデルの根拠. モデル 2（SPIKEM） 提案モデル（SpikeM）は，以下. ここではモデル 1 の細部を考察する．. • 部分式 ΔB(t) + S(t) は，時刻 t における，ニュースを 通知されたユーザの数，外部ショック（ニュースサイトに よる報道等）の強さの和である．この部分式が他のユー ザに与える影響力（感染力）は，時間の経過とともに減少. の式によりブログユーザの周期的な活動を表現する．. ΔB(n + 1) = p(n + 1)· n U (n) · ΔB(t) + S(t) · f (n + 1 − t) + t=nb. し，これを減衰関数 f () で表現する．最終的には，イベ ントの誕生時刻 nb からのすべての時刻（t = nb , . . . , n） における部分式の影響力の総和を計算することで，現時 刻における全体での影響力を得る．. • 影響力を示す f () は，パワー則に従う．ここでは，先 行研究 [2], [21] に基づき，−1.5 のベキ指数を用いる．. (5). p(n) = 1 − 12 Pa sin P2πp (n + Ps ) + 1. (6). ここで，U (n)，S(t)，f (n) は，モデル 1 と同様とする． モデル 2 はモデル 1 に周期関数 p(·) を加えたものである．. • 時刻 n の時点でまだニュースを知らされていない U (n). このモデルでは，ニュースを受け取る可能性のあるユーザ. 人のユーザのうち，新たにニュースの影響を受けるユー. の数 U (·) が時間帯によって変動する．たとえばユーザが. ザの数は，過去すべての時刻における影響力の総和と. 就寝している時間帯にはニュースの拡散力が弱まり，少人. U (n) の積により決定される．. 数しかそのイベントの影響を受けない（感染しない）．周. • ノイズ は，イベントとは独立の要因を示す．たとえ. 期関数 p(·) は以下で構成される．. ば，Twitter における #egypt というハッシュタグは，一. • 周期 Pp ：24 時間等の周期性を示す．. 般的な意味におけるエジプトに関するツイートと，2012. • 位相 Ps ：周期のずれを示す．. 年 11 月にタハリール広場で起きた抗議デモのニュース. • 振幅 Pa ：周期性の強弱を示す．. に関するツイートが独立に存在している．多くの場合に. たとえば毎日昼に活動が大きくなる場合，Pp = 24 hours，. おいて， 0 となる． 上記の定義に加えて，B(n) =. n t=0. Ps = 18 となる．振幅 Pa が大きいと，時間帯によるユー ΔB(t) となり，ブ. ログユーザの総数 N は固定であると考える．つまり，. ザの活動量に差が出る．周期性が見られない場合，Pa = 0 となる．. B(n) + U (n) = N である． 2.4 モデルパラメータの学習 2.3 周期性をともなう情報拡散モデル：SPIKEM-FULL. 提 案 モ デ ル は 7 つ の パ ラ メ ー タ で 構 成 さ れ る：θ =. 本章の冒頭で示したとおり，ユーザの活動には周期性を. {N, β, nb , Sb , , Pa , Ps }. 実 際 の シ ー ケ ン ス X(n)，n =. ともなうことがある．たとえば，夜中や明け方は，ブログ. 1, . . . , nd が与えられたとき，本手法は最小二乗法に基. の活動を停止しているユーザが多く，一方で日中には大量. づき次式で表現されるエラーの総和が最小になるようなパ. のブログポストが発生していると考えられる．このような. ラメータを選ぶことでモデルの学習を行う：. c 2013 Information Processing Society of Japan . 14.
(5) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). 表 3. K-SC（図 1）における 6 つの情報拡散パターンに対する学習 モデルのパラメータの値. Table 3 The model parameters of our SpikeM best fitting on six patterns of K-SC (see Fig. 1). C1. C2. C3. C4. C5. C6. N. 2407. 1283. 1466. 3079. 4183. 3435. β∗N. 0.95. 1.00. 0.86. 0.92. 0.79. 0.69. nb. 26. 17. 40. 35. 0. 34. Sb. 4.73. 0.06. 114.13. 23.24. 2.58. 45.58. . 0.36. 0.01. 0.43. 1.48. 0.32. 13.97. Pa. 0.18. 0.06. 0.22. 0.38. 0.28. 0.39. Ps. 12. 5. 7. 6. 2. 2. モデルは，上昇，減衰ともに指数則に基づくという性質が あるため，拡散プロットにおいては高い精度である一方， 減衰時にはうまくパターンを表現していない．. 3. 評価実験 図 2 SpikeM と SI モデルによる図 1（C1）の学習結果の比較．提 案手法（赤線）は指数則に基づき拡散し，パワー則で減衰する． 一方 SI モデル（青線）は，拡散，減衰ともに指数則に従う. Fig. 2 Fitting results of SpikeM vs. SI for pattern C1 in Fig. 1.. SpikeM の有効性を検証するため，実データを用いた実 験を行った．本実験は，以下の諸問題に取り組む．. ( 1 ) 実データを用いた提案モデルの精度の検証（Q1-3） ( 2 ) SpikeM を用いた予測精度の検証（Q4）. The original sequence (in gray circles), and our model (red line) have an exponential rise and a power-law drop.. D(X, θ) =. 3.1 データセット 本論文では以下のデータセットに対し評価実験を行った．. nd . (X(n) − ΔB(n))2 .. (7). • MemeTracker *3 : このデータセットはアメリカ国内の ブログにおいて 3 カ月間（2008/8/1–10/31）に発生した. n=1. フレーズ（meme）を集めたものである．フレーズは，主. なお，SpikeM は強い非線形性を持つため，モデルの学. に政治や時事ニュース等に関連する内容である．本研究. 習にはパラメータの発散に頑健なレーベンバーグ・マル. ではフレーズの中から特に出現回数の多かった 1,000 個. カート法（LM: Levenberg-Marquardt）[22] を用いた．. 2.5 モデルの分析—指数則とパワー則 SpikeM は，既存の拡散モデルとは決定的に異なる特長 がある．それは，指数則で情報が拡散したのちパワー則. のフレーズとそのフレーズが頻出する 1 週間のシーケン スを選び使用した．. • Twitter *4 : こ の デ ー タ は ，Twitter 内 で 8 カ 月 間 （2011/6/1–2012/1/1）に現れたハッシュタグを収集した ものである．本実験では，700 万以上のツイートの中か. で減衰していくことである．本節では，実データを用い て提案モデルの表現能力を分析する．図 2 は，図 1（パ ターン C1）の情報拡散過程をそれぞれ SpikeM と SI モ. ら，頻出するハッシュタグを 10,000 件選び使用した．. • GoogleTrends *5 : このデータセットは，Google による 検索クエリの頻度を集計したものである．各シーケンス. デルを用いて学習した結果である．ここで，ブログユーザ. が各クエリ（たとえば “tsunami” や “harry potter”）の. ΔB() の波がピークに達した時刻を nmode とする（この場. 出現頻度を表す．. 合 nmode = 42）．図 2 (b)，(d) はイベント誕生の時刻 nb からピーク nmode までの間のシーケンスを x 軸の方向に 反転したプロットであり，これを拡散プロットと呼ぶ．同 様に，図 2 (c)，(e) はピーク nmode から時刻 n までの部分 シーケンスを示しており，これを減衰プロットと呼ぶ．そ れぞれ，線形スケール，対数スケールにおいて比較を行っ た．図に示すとおり，実データは指数則の上昇と，パワー 則の減衰パターンを持っており，SpikeM は高い精度での フィッティングに成功している．一方，既存手法である SI. c 2013 Information Processing Society of Japan . 3.2 Q1：K-SC クラスタにおけるモデルの精度 このデータセットに関する結果はすでに 1 章の図 1 に おいて示している．図 1 のとおり，SpikeM は，ブログ メディアにおける代表的な拡散パターンを高精度で表現し ている．表 3 はモデルの学習結果の詳細である．SpikeM *3 *4 *5. http://memetracker.org/ http://twitter.com/ http://www.google.com/insights/search/. 15.
(6) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). は 7 つのパラメータで表現され，それぞれが拡散パターン. るが，C2 はより強い影響力 β ∗ N = 1.0 を持っているパ. の具体的な振舞いを説明している．まず，潜在的なユーザ. ターンであることが分かる．外部ショックの強さ Sb につ. の総数 N はすべてのシーケンスパターンにおいて 2,000∼. いては，パターン C3 が時刻 nb = 40 において Sb = 114 と. 3,000 の間となっている．これはピーク時の値が 100 にな. いう高い値を持っている．これは，C3 が他のパターンに. るようにデータを正規化しているためである．続いて，イ. 比べ，外部からのショックを強く受けていることを意味し. ベントの影響力の値である β ∗ N は 0.7 − 1.0 の間となっ. ている．パターン C4，C5，C6 は，強い周期性がある点が. ている．C1 と C2 は非常に近い性質を持ったパターンであ. 特徴的である．これは Pa 0.4 というパラメータによっ. 表 4 K-SC における SpikeM と SI モデルの精度比較（RMSE ）. Table 4 Fitting accuracy of SI vs. SpikeM on six patterns of K-SC. SpikeM consistently outperforms SI with re-. て確認できる．C4 と C5 の違いは位相のずれ（Ps = 6, 2） による違いが顕著であり，一方 C6 は強いバックグラウン ドノイズ = 13.97 を含む．このことから，C6 は情報拡散. spect to accuracy (RMSE ) between the original val-. パターンのほかに，独立要因による影響を受けていると考. ues and the models.. えられる．. Pattern. C3. C4. C5. C6. 表 4 は，フィッティングの精度比較である．ここでは二. C1. C2. SPIKEM. 1.84. 1.61. 0.97. 4.08. 3.33. 5.89. 乗平均誤差（RMSE ）を用いて実データとモデルの比較を. SI. 15.64. 6.78. 19.65. 25.29. 20.36. 21.76. 行った：RMSE =. 1 nd. nd n. (X(n) − ΔB(n))2 . ここでは. 図 3 MemeTracker データにおける代表的な情報拡散パターンと，SpikeM による学習結果. Fig. 3 Results of SpikeM fitting on six patterns from MemeTracker dataset.. c 2013 Information Processing Society of Japan . 16.
(7) 情報処理学会論文誌. Vol.6 No.5 11–22 (Dec. 2013). データベース. 図 4. Twitter データにおける 3 つのハッシュタグの拡散と，SpikeM の結果. Fig. 4 Results of SpikeM fitting on three hashtags from Twitter dataset.. SpikeM と既存手法である SI モデルを比較した．2 章の. can” を利用しているのと同時に，Barack Obama の選挙. 図 2 で比較したとおり，SI モデルはパワー則に基づく減. 活動におけるスローガンの意味としてこのフレーズをブ. 衰パターンを有しないため，正しくパターンを表現できな. ログ内でポストしているためと考えられる．加えて，時. い．一方，我々の提案モデルは高い精度で盛り上がりと減. 刻 n = 120 付近には外れ値が観測されるが，我々の手法. 衰の両パターンを正しく表現できることが分かる．. は情報拡散の本質をとらえることができるためノイズに 頑健であり，局所的なノイズの影響を受けない．. 3.3 Q2：MemeTracker データとモデルの比較 図 3 は MemeTracker データにおける提案モデルの学習 結果（赤線）である．ここでは，K-SC で発見された 6 つの 代表的なクラスタ（C1–C6）に類似するシーケンスを選び，. 3.4 Q3：その他のデータにおけるモデルの検証 3.4.1 Twitter データ上の情報拡散 図 4 は，Twitter データのハッシュタグにおけるモデ. 学習結果を示した．表は各シーケンスに関連するフレーズ. ルの学習結果である．Twitter は MemeTracker データに. （meme）であり，これらのフレーズはすべて 2008 年におけ. 非常によく似た拡散パターンを持つことが分かる．ここ. るアメリカの政治ニュースに関連する内容である．各シー. では頻出する 3 つのハッシュタグについてのみ結果を. ケンスはそれぞれ線形スケール（上段） ，対数スケール（下. 示す：(a) #assange：このハッシュタグは WikiLeaks の. 段）で示している．提案手法である SpikeM は，パワー則. 創立者 Julian Assange に関するニュースの拡散過程であ. に基づく拡散パターンを柔軟に表現することができる．特. る．まず初めに少人数による言及があり，その後ピーク. に，図中の対数スケールにおいて，提案モデルは実データ. 時（2011/12/5）に向かって情報が伝搬しているのが分か. の減衰パターンを正しくとらえていることが確認できる．. る．(b) #stevejobs：Steve Jobs の死去（2011/10/5）直後. 以下では，各パターンについて詳細を考察する．. にニュースが発生し，急激にユーザに伝わると同時に，長い. • パターン C1，C2：潜在的なユーザの総数 N 500 は. 期間にわたって話題が広がっている．(c) #arresteddevel-. ほぼ同様であるが，パターン C2 は C1 よりも急激に情. opment：これは映画 “Arrested Development” に関する話. 報が拡散している（情報拡散の強さは β ∗ N = 1.4）．. 題である．明確な周期性がある．. • パターン C3：強い外部ショックと緩やかな減衰を持. 3.4.2 GoogleTrends データ上の情報拡散. ち，微かに周期性を帯びている．. 情報拡散のパターンは，Blog や Twitter をはじめとす. • パターン C4，C5：明確な周期性を持つ．パターン C5. るソーシャルネットワークだけではなく，Google 等の検. の “lipstick on a pig” は 6 つのシーケンスの中で潜在的. 索エンジン内のクエリにおいても観測される．図 5 は，. ユーザの総数が最も多い（N = 6259）．. GoogleTrends データにおける情報拡散パターンの例であ. • パターン C6：フレーズ “yes we can” は，全体的に一. る．図 5 (a) は外部からの強いショックが要因となり発生. 定数の周期的なノイズも観測できるが，それと同時に時. したイベントの例（2005 年に発生したインドネシアの大地. 刻 n = 40 付近に強い情報拡散パターンが発生している．. 震に関するニュース）である．一方，図 5 (b) は 2007 年に. これは，ブログユーザが日常的なフレーズとして “yes we. 公開されたハリーポッターの映画が，口コミ等によって広. c 2013 Information Processing Society of Japan . 17.
(8) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). まっていく過程が示されている．図に示すとおり，2 つの. 拡散過程も予測することができる．これに関しては 4.1 節. 異なる性質を持つパターンを SpikeM は正しく表現して. で詳しく述べる．. いる．. 4. アプリケーション. 3.5 Q4：SPIKEM を用いた拡散過程の予測. これまで述べたように，提案手法である SpikeM では直. 上に示したとおり，SpikeM は様々な拡散パターンを表. 感的な意味を持つパラメータを推定することができる．本. 現することができる．これを利用することで，将来の拡. 章では，提案手法およびそれらのパラメータの活用方法に. 散過程を予測することができる．図 6 は，MemeTracker. ついて議論すると同時に，実用的なアプリケーション例と. データ（図 3 Meme #9，#13）を用いた予測結果である．. して代表的な 3 つについて紹介する．. まず初めに，時刻 n = 54 および n = 60 までのシーケンス （黒線）を用いてそれぞれモデルの学習を行う．その後学習. 4.1 “What-if ” シナリオと将来予測. したモデルを用いて以降 5 日間のパターン（赤線）を予測. 3.5 節においてすでに SpikeM の予測能力について紹介. した．提案モデルの精度を比較するため，既存手法である. したが，ここではさらに重要なアプリケーションとして，. AR（青線）の予測結果も示した．AR の係数は SpikeM. “what-if” シナリオにおける将来予測問題に取り組む．具. のパラメータ数と同様の 7 に設定した．図に示すとおり，. 体的には，3.5 節の予測問題がシーケンスのピーク時まで. AR が長期的な予測に失敗しているのに対し，提案手法. のパターンを用いて，その後の動きを予測していたのに対. は正しく将来の拡散過程を予測している．より具体的に. し，この “what-if” シナリオではピーク以前のダイナミク. は，2 つのシーケンスに対する SpikeM の予測時のエラー. スも予測する．これは容易に解決できる問題ではない．な. がそれぞれ RMSE = 9.26，8.93 だったのに対し，AR は. ぜなら，一般的な情報拡散過程では，非常に短い期間の間. RMSE = 13.98，14.19 となった．ここでさらに重要なこと. にピーク点に達してしまうからである．しかしこれが繰返. に，SpikeM は，上記のようなピーク時以降のパターンだ. しのあるイベントであればどうだろうか．この “what-if”. けではなく，イベントの発生直後からピーク時にかけての. シナリオでは，単体のイベントに対して予測をするのでは なく，過去に起きたイベントの情報を用いることで，次の イベントの拡散過程を予測する．ここで，ハリーポッター の映画を例として考える．もしハリーポッターの映画の続 編が近日公開されるとしたら，ソーシャルメディア上でど のように話題が盛り上がるかを事前に予測できるだろうか． 図 7（GoogleTrends ）を用いて問題を定義する．まず，事 前情報として，(a) 2009 年に発表された過去の映画 “Harry. 図 5 GoogleTrends データにおけるモデルの学習精度（赤線）. Potter and the Half-Blood Prince”（n = 185）の拡散パ. Fig. 5 SpikeM fitting on GoogleTrends dataset: the volume. ターンと (b) 次に発表予定となっている続編 2 つの公開日. of searches for the keyword (in black dots) and fitting results (in red lines). Note that the window size is per week.. 時（水色矢印で示される点，時刻 n = 255，289） ，(c) 公開 日時以前 8∼2 週間前のアクセス数（水色線）が与えられ るとする．ここでの目標は，これらの情報から続編 2 つの 情報拡散過程を推定し，ピーク点を予測することである．. 4.1.1 解決法 SpikeM は，N の値からハリーポッターに興味を持つ. 図7. 映画ハリーポッター（GoogleTrends ）における情報拡散パター ンの予測. 図 6. MemeTracker データにおける情報拡散過程の予測. Fig. 6 Results of tail-part forecasting on MemeTracker data.. c 2013 Information Processing Society of Japan . Fig. 7 Results of “what-if” forecasting for the Harry Potter series.. 18.
(9) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). 図 8 GoogleTrends データにおける外れ値検出. Fig. 8 Outlier detection on GoogleTrends dataset.. 可能性のあるユーザの数を，β の値からこのイベントの影 響力（口コミによる情報伝搬の強さ）を推定することがで きる．そこで本手法では，すべてのイベント（ハリーポッ ターシリーズ）の情報拡散過程においてこれらの潜在的な. 図 9. MemeTracker と Twitter データにおけるパラメータ（N ， β ∗ N ，Ps ）の分布の様子. Fig. 9 Reverse engineering: pdf of three parameters: N, β ∗ N, Ps over 1,000 memes/hashtags. (a) MemeTracker : total potential bloggers N 1, 000, and strength of. パラメータを共通化することを考え，それぞれのイベント. “first burst” β ∗ N 1.0. More than 90% of the memes. 間の違いは，外部ショックの強さ (nb , Sb ) のみであるとす. have clear daily periodicity with high activities around. る．以下で処理の流れを示す．. 6 pm (i.e., Ps 0). (b) Twitter : similar trends except. ( 1 ) まず初めのピーク点前後のパターン（黒線）を用いて. more spread in Ps , possibly, due to multiple time zone.. パラメータ θ を学習する．. ( 2 ) 学習した θ を固定したうえで，水色線（n = 250，280） で示す部分シーケンスを用い，2 つの新たなイベントに 対する外部ショックの強さ (nb , Sb ) をイベントそれぞれ に対し推定する．. ( 3 ) 固定したパラメータ θ と新たに推定した (nb , Sb ) を用 い，シーケンスの予測を行う（赤線） ． 以上のような処理を用いることで，図 7 に示すとおり， 本手法は 2 つの新たなパターンを予測するとともに，ピー クの位置も正しく推定することに成功した．. 注目度等の直感的な意味を持つことである．この特長を利 用することで，観測される拡散パターンから，本来のデータ の振舞いを理解することができる．図 9 は，MemeTracker と Twitter の 2 つのデータセットから，SpikeM を用いて それぞれ 1,000 以上の拡散パターンを学習し，各パラメー タ（N ，β ∗ N ，Ps ）の分布を示したものである．以下では 得られた知見について議論する． 知見 1 あるイベントに興味を持つ潜在的なユーザ数 N は，両データにおいて主に N = 1, 000 − 2, 000 である． 知見 2 イベント生成直後の影響力の強さは両データに. 4.2 外れ値検出 3 章で示したように，SpikeM は実データのパターンを高 い精度で表現することができる．これを利用することで，外 れ値検出問題を容易に実現することができる．より具体的に は，時刻 n におけるデータと推定モデルの距離を対数スケー ルを用いて次式で計算する：δ(n) = log|X(n) − ΔB(n)|． この値 δ(n) が閾値を超える場合にその時刻 n を外れ値と する．図 8 は，図 5 (a) に示した津波のシーケンスを対数 スケールでプロットしたものである．ここで，黒点はオリ ジナルの値，赤線は SpikeM のフィッティング結果を表 す．図中において，いくつかの外れ値が確認できる．たと えば，(a) 3 月 29 日にこのイベントとは異なる別の地震が 発生している．さらに，(b) 12 月 26 日（n = 52）に非常 に大きなスパイクがあるが，これはこの大地震が発生した ちょうど 1 年後の地震の記念日にあたる．. おいて，およそ β ∗ N 1.0 に分布している． 上記の 2 つの知見は，MemeTracker と Twitter の両デー タにおいて情報拡散過程に共通の振舞いがあることを意味 する．つまり，Blog と Twitter が類似したソーシャルアク ティビティを持つことを示唆している． 知見 3 両データにおいて，24 時間単位の周期的な活動 が見られる．特に MemeTracker データの (a) 周期の位相 は Ps = 0 であり，早朝の活動が小さく，夕方に活動が増加 する一方で，Twitter データでは (b) 位相 Ps に幅がある． 実験では，両データセットにおいて 90%以上のシーケン スに，1 日単位の周期性が見つかった．周期性に関する特 徴として，Twitter データには様々な位相 Ps を持つシー ケンスが観測された．これは，MemeTracker データがア メリカ国内のユーザであるのに対し，Twitter のユーザが 様々なタイムゾーン（アメリカ，イギリス，オーストラリ ア，インド等）を使用しているためである．. 4.3 リバースエンジニアリング. 5. 関連研究. 提案モデルの最大の強みは，構成する各パラメータが， イベントに興味を持つユーザの潜在的な人数やニュースの. c 2013 Information Processing Society of Japan . 関連研究は以下の 3 つに分類される．. 19.
(10) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). 5.1 時系列データ解析 時系列データの解析に関する研究は様々な分野で進めら. や，より複雑なネットワーク構造を考慮したモデルについ て検討していく予定である．. れている [4]．自己回帰モデル（AR: autoregressive model） ， 線形動的システム（LDS: linear dynamical systems），カ. 参考文献. ルマンフィルタ（KF: Kalman filters）は代表的な技術で. [1]. あり，これらに基づく時系列の解析と予測手法が数多く提 案されている [12], [23], [24], [25]．しかしこれらの技術は すべて線形という特徴を持つ．非線形のモデルにおいて. [2] [3]. は最近傍探索（NNS: nearest neighbor search）[5] や人工 ニューラルネットワーク（ANN: artificial neural networks）. [4]. [41] を用いる手法が主流であり，予測モデルとしての表現 能力は不十分である．時系列シーケンスを対象とした類 似検索やパターン発見問題も様々な研究が行われている が [7], [8], [13], [15], [26], [28], [30], [31], [33], [36], [37], [40]，. [5] [6]. 時系列データのバースト性の発見とそのモデル化に着目し ていない．. [7]. 5.2 影響伝播. [8]. ソーシャルネットワーク上の情報伝播は，SI モデル （susceptible-infected model）に代表される感染症疫学モ デル [1] と深い関係性がある．文献 [29] において，情報の. [9]. 減衰パターンがパワー則の性質を持つことが報告されて いる．より具体的には，ブログにおける単位時間あたりの. [10]. 情報の影響力は −1.5 のベキ指数に基づき減衰する性質を 持つ．Barabasi は通信における応答時間の分布がベキ指. [11]. 数 −1 から −1.5 の間のパワー則に従うという性質を発見 している [2]．ブログ，ソーシャルメディアの解析および. [12]. 情報の伝播とカスケードに関する研究は様々なものがあ り [9], [10], [11], [14], [17], [19], [20], [34], [35], [39], [42]，. [13]. さらにその発展研究として，情報拡散の発起点を探す研 究 [18], [38] も進められている．. 5.3 バースト検知 時系列データを対象としたバースト検知は Kleinberg [16]，. [14]. [15]. Zhu ら [44]，Parikh ら [32] に代表される様々な手法が存在 するが，これらはすべてネットワーク上のバーストを表現. [16]. するモデルではない．. [17]. 6. むすび. [18]. 本論文では，オンラインメディア上の情報拡散過程を表 現するモデルとして，SpikeM について述べた．SpikeM. [19]. は既存の知見（K-SC，SI モデル）を一般化すると同時に， パワー則に基づく減衰パターンを含む，様々な実データ上. [20]. の情報拡散の振舞いを表現する．SpikeM は少ない数のパ ラメータで構成され，これらのパラメータの利用すること. [21]. により，‘what-if’ シナリオによる予測や，リバースエンジ ニアリング等の有用なアプリケーションを実現した．今後 の課題として，外部ショックが複数箇所から発生する状況. c 2013 Information Processing Society of Japan . [22]. Anderson, R.M. and May, R.M.: Infectious Diseases of Humans, Oxford University Press (1991). Barabasi, A.L.: The Origin of Bursts and Heavy Tails in Human Dynamics, Nature, Vol.435 (2005). Bass, F.M.: A New Product Growth for Model Consumer Durables, Management Science, Vol.15, No.5, pp.215–227 (1969). Box, G.E., Jenkins, G.M. and Reinsel, G.C.: Time Series Analysis: Forecasting and Control, 3rd edition, Prentice Hall, Englewood Cliffs, NJ (1994). Chakrabarti, D. and Faloutsos, C.: F4: Large-scale Automated Forecasting Using Fractals, CIKM (2002). Crane, R. and Sornette, D.: Robust Dynamic Classes Revealed by Measuring the Response Function of a Social System, PNAS (2008). Faloutsos, C., Ranganathan, M. and Manolopoulos, Y.: Fast Subsequence Matching in Time-series Databases, SIGMOD, pp.419–429 (1994). Gilbert, A.C., Kotidis, Y., Muthukrishnan, S. and Strauss, M.: Surfing Wavelets on Streams: One-pass Summaries for Approximate Aggregate Queries, VLDB, pp.79–88 (2001). Goetz, M., Leskovec, J., McGlohon, M. and Faloutsos, C.: Modeling Blog Dynamics, ICWSM (2009). Gruhl, D., Liben-Nowell, D., Guha, R. and Tomkins, A.: Information Diffusion through Blogspace, SIGKDD Explor. Newsl., Vol.6, No.2, pp.43–52 (2004). Guha, R., Kumar, R., Raghavan, P. and Tomkins, A.: Propagation of Trust and Distrust, WWW, pp.403–412 (2004). Jain, A., Chang, E.Y. and Wang, Y.-F.: Adaptive Stream Resource Management Using Kalman Filters, SIGMOD, pp.11–22 (2004). Kahveci, T. and Singh, A.K.: An Efficient Index Structure for String Databases, Proc. VLDB, pp.351–360 (Sep. 2001). Kempe, D., Kleinberg, J. and Tardos, E.: Maximizing the Spread of Influence through a Social Network, KDD (2003). Keogh, E.J., Palpanas, T., Zordan, V.B., Gunopulos, D. and Cardle, M.: Indexing Large Human-motion Databases, VLDB, pp.780–791 (2004). Kleinberg, J.M.: Bursty and Hierarchical Structure in Streams, KDD, pp.91–101 (2002). Kumar, R., Mahdian, M. and McGlohon, M.: Dynamics of Conversations, SIGKDD, pp.553–562 (2010). Lappas, T., Terzi, E., Gunopulos, D. and Mannila, H.: Finding Effectors in Social Networks, KDD, pp.1059– 1068 (2010). Leskovec, J., Adamic, L.A. and Huberman, B.A.: The Dynamics of Viral Marketing, TWEB, Vol.1, No.1 (2007). Leskovec, J., Backstrom, L. and Kleinberg, J.M.: Memetracking and the Dynamics of the News Cycle, KDD, pp.497–506 (2009). Leskovec, J., McGlohon, M., Faloutsos, C., Glance, N.S. and Hurst, M.: Patterns of Cascading Behavior in Large Blog Graphs, SDM (2007). Levenberg, K.: A Method for the Solution of Certain. 20.
(11) 情報処理学会論文誌. [23]. [24]. [25] [26]. [27]. [28]. [29]. [30]. [31]. [32]. [33]. [34]. [35]. [36]. [37]. [38]. [39]. [40] [41]. [42]. データベース. Vol.6 No.5 11–22 (Dec. 2013). Non-linear Problems in Least Squares, Quarterly Journal of Applied Mathmatics, Vol.II, No.2, pp.164–168 (1944). Li, L., Liang, C.-J.M., Liu, J., Nath, S., Terzis, A. and Faloutsos, C.: Thermocast: A Cyber-physical Forecasting Model for Data Centers, KDD (2011). Li, L., McCann, J., Pollard, N. and Faloutsos, C.: Dynammo: Mining and Summarization of Coevolving Sequences with Missing Values, KDD (2009). Li, L. and Prakash, B.A.: Time Series Clustering: Complex is Simpler!, ICML (2011). Lin, J., Keogh, E.J., Lonardi, S., Lankford, J.P. and Nystrom, D.M.: Visually Mining and Monitoring Massive Time Series, KDD, pp.460–469 (2004). Matsubara, Y., Sakurai, Y., Prakash, B.A., Li, L. and Faloutsos, C.: Rise and Fall Patterns of Information Diffusion: Model and Implications, KDD, pp.6–14 (2012). Matsubara, Y., Sakurai, Y. and Yoshikawa, M.: Scalable Algorithms for Distribution Search, ICDM, pp.347–356 (2009). McGlohon, M., Leskovec, J., Faloutsos, C., Hurst, M. and Glance, N.: Finding Patterns in Blog Shapes and Blog Evolution, International Conference on Weblogs and Social Media, Boulder, Colo. (March 2007). Papadimitriou, S. and Yu, P.S.: Optimal Multi-scale Patterns in Time Series Streams, SIGMOD Conference, pp.647–658 (2006). Papapetrou, P., Athitsos, V., Potamias, M., Kollios, G. and Gunopulos, D.: Embedding-based Subsequence Matching in Time-series Databases, ACM Trans. Database Syst., Vol.36, No.3, p.17 (2011). Parikh, N. and Sundaresan, N.: Scalable and Near Realtime Burst Detection from Ecommerce Queries, KDD, pp.972–980 (2008). Patel, P., Keogh, E.J., Lin, J. and Lonardi, S.: Mining Motifs in Massive Time Series Databases, Proc. ICDM, pp.370–377 (2002). Prakash, B.A., Beutel, A., Rosenfeld, R. and Faloutsos, C.: Winner Takes All: Competing Viruses or Ideas on Fair-play Networks, WWW, pp.1037–1046 (2012). Prakash, B.A., Chakrabarti, D., Faloutsos, M., Valler, N. and Faloutsos, C.: Threshold Conditions for Arbitrary Cascade Models on Arbitrary Networks, ICDM (2011). Sakurai, Y., Faloutsos, C. and Yamamuro, M.: Stream Monitoring under the Time Warping Distance, Proc. 23rd International Conference on Data Engineering, ICDE 2007, April 15-20, 2007, The Marmara Hotel, Istanbul, Turkey, pp.1046–1055 (2007). Sakurai, Y., Papadimitriou, S. and Faloutsos, C.: BRAID: Stream Mining through Group Lag Correlations, SIGMOD Conference, Baltimore, MD, USA, pp.599–610 (2005). Shah, D. and Zaman, T.: Rumors in a Network: Who’s the Culprit?, IEEE Trans. Information Theory, Vol.57, No.8, pp.5163–5181 (2011). Tong, H., Prakash, B.A., Tsourakakis, C.E., Eliassi-Rad, T., Faloutsos, C. and Chau, D.H.: On the Vulnerability of Large Graphs, ICDM (2010). Vlachos, M., Kozat, S.S. and Yu, P.S.: Optimal Distance Bounds on Time-series Data, SDM, pp.109–120 (2009). Weigend, A.S. and Gerschenfeld, N.A.: Time Series Prediction: Forecasting the Future and Understanding the Past, Addison Wesley (1994). Yang, J. and Leskovec, J.: Modeling Information Diffusion in Implicit Networks, ICDM, pp.599–608 (2010).. c 2013 Information Processing Society of Japan . [43] [44]. Yang, J. and Leskovec, J.: Patterns of Temporal Variation in Online Media, WSDM, pp.177–186 (2011). Zhu, Y. and Shasha, D.: Efficient Elastic Burst Detection in Data Streams, KDD, pp.336–345 (2003).. 松原 靖子 2006 年お茶の水女子大学理学部情報 科学科卒業．2009 年同大学大学院人 間文化創成科学研究科理学専攻博士前 期課程修了．2012 年京都大学大学院 情報学研究科社会情報学専攻博士後期 課程修了．博士（工学）．2011∼2012 年カーネギーメロン大学客員研究員．データストリーム 処理，大規模データマイニングに関する研究に従事．日本 データベース学会会員．. 櫻井 保志 （正会員） 1991 年同志社大学工学部電気工学科 卒業．1991 年日本電信電話（株）入 社．1999 年奈良先端科学技術大学院 大学情報科学研究科博士後期課程修 了．博士（工学） ．2004∼2005 年カー ネギーメロン大学客員研究員．2013 年熊本大学大学院自然科学研究科教授．本会平成 18 年度 長尾真記念特別賞，本会平成 16 年度および平成 19 年度 論文賞，電子情報通信学会平成 19 年度論文賞，日本デー タベース学会上林奨励賞，ACM KDD best paper awards （2008，2010）等受賞．データマイニング，データストリー ム処理，センサデータ処理，Web 情報解析技術の研究に従 事．ACM，電子情報通信学会，日本データベース学会各 会員．. 21.
(12) 情報処理学会論文誌. データベース. Vol.6 No.5 11–22 (Dec. 2013). B. Aditya Prakash. Christos Faloutsos. B. Aditya Prakash is an Assistant. Christos Faloutsos is a Professor at. Professor in the Computer Science. Carnegie Mellon University. He has. Department at Virginia Tech.. He. received the Presidential Young In-. graduated with a Ph.D. from the. vestigator Award by the National Sci-. Computer Science Department at. ence Foundation (1989), the Research. Carnegie Mellon University in 2012. Contributions Award in ICDM 2006,. and got his B.Tech. (in CS) from the Indian Institute of. the SIGKDD Innovations Award (2010), seventeen best. Technology (IIT)—Bombay in 2007. He has published. paper awards (including two ‘test of time’), and four. more than 25 refereed papers in major venues, holds two. teaching awards. He has served as a member of the ex-. U.S. patents, and has given two tutorials (VLDB 2012 and. ecutive committee of SIGKDD; he is an ACM Fellow; he. ECML/PKDD 2012). His work has received one best pa-. has published over 200 refereed articles, 11 book chapters,. per award and two best-of-conference selections (CIKM. and one monograph. He holds five patents and he has. 2012, ICDM 2012, ICDM 2011). His interests include. given over 30 tutorials and over 10 invited distinguished. Data Mining, Applied Machine Learning, and Databases,. lectures. His research interests include data mining for. with emphasis on large real-world networks and time se-. graphs and streams, fractals, database performance, and. ries.. indexing for multimedia and bioinformatics data.. Lei Li. （担当編集委員 比戸 将平）. Lei Li is a Post-Doctoral researcher at EECS department of UC Berkeley and visiting researcher at CMU. His research interest lies in the intersection of machine learning, statistical inference and database systems. Specifically, he has been working on Bayesian inference in open universe probabilistic models, probabilistic programming language, large-scale learning, time series, communication and social networks. He received his B.S. in Computer Science and Engineering from Shanghai Jiao Tong University in 2006 and Ph.D. in Computer Science from Carnegie Mellon University in 2011, respectively. His dissertation work on fast algorithms for mining coevolving time series was awarded ACM KDD best dissertation (runner up).. c 2013 Information Processing Society of Japan . 22.
(13)
図
![図 1 オンラインメディア上に現れる 6 つの代表的な情報拡散パター ン（ K-SC [43] ）と SpikeM の効果](https://thumb-ap.123doks.com/thumbv2/123deta/10093897.1494416/2.892.73.428.98.464/図1オンラインメディア上現れるつの代表情報拡散パターン効果.webp)
+3
関連したドキュメント
文献資料リポジトリとの連携および横断検索の 実現である．複数の機関に分散している多様な
ドリフト流がステップ上段方向のときは拡散係数の小さいＤ２構造がテラス上を
１）まず、最初に共通グリッドインフラを構築し、その上にバイオ情報基盤と
現在入手可能な情報から得られたソニーの経営者の判断にもとづいています。実
絡み目を平面に射影し，線が交差しているところに上下 の情報をつけたものを絡み目の 図式 という．.
当社は、お客様が本サイトを通じて取得された個人情報（個人情報とは、個人に関する情報
ストックモデルとは，現況地形を作成するのに用
・本書は、
