社会ネットワークにおける汚染拡散最小化のためのリンク封鎖

社会ネットワークにおける汚染拡散最小化のための

リンク封鎖

Blocking Links to Minimize Contamination Spread

in a Social Network

木村昌弘

1∗

斉藤和巳

2

元田浩

3

Masahiro Kimura

1

_{Kazumi Saito}

2

_{Hiroshi Motoda}

3

1

_{龍谷大学理工学部電子情報学科}

1

_{Department of Electronics and Informatics, Ryukoku University}

2

_{静岡県立大学経営情報学部}

2

_{School of Administration and Informatics, University of Shizuoka}

3

_{大阪大学産業科学研究所}

3

_{Institute of Scientific and Industrial Research, Osaka University}

Abstract: We consider the problem of minimizing the spread of undesirable things, such as computer viruses or malicious rumors, by blocking a limited number of links in a network, a converse problem to the influence maximization problem in which the most influential nodes for information diffusion are searched in a social network. This minimization problem is another approach to the problem of preventing the spread of contamination by removing nodes in a network. We propose a method for efficiently finding a good approximate solution to this problem based on a naturally greedy strategy. Using large real networks, we demonstrate experimentally that the proposed method significantly outperforms conventional link-removal methods. We also show that unlike the case of blocking a limited number of nodes, the strategy of removing nodes with high out-degrees is not necessarily effective for our problem.

1

はじめに

近年，現実世界の様々な複雑ネットワークの機能や 構造に関する研究が注目されている [9]．機能という観 点では，ネットワークはイノベーションやトピックス など様々な重要情報の拡散を媒介するということがあ げられる．しかしながら，好ましくない情報がネット ワークを通じて拡散することもしばしばある．例えば， コンピュータウィルスがコンピュータネットワークや 電子メールネットワークを通じて広がりうるし，悪意 のある噂が友人関係の社会ネットワークを通じて広が りうる．したがって，好ましくない情報がネットワー クを通じて広がることを防ぐ有効な戦略の開発は，重 要な研究課題と言える．これまで，ネットワークから 適切にノード群を除去することにより情報拡散の大き さを縮小させる戦略が研究されてきた．特に，出次数 ∗_{連絡先：龍谷大学理工学部電子情報学科}       〒 520-2194 大津市瀬田大江町横谷 1-5        E-mail: [email protected] の高いノードから順に除去する戦略が，しばしば有効 であるということが示されていた [1, 2, 10]．ところで， ノード除去は必然的にリンク除去を伴っている．すな わち，リンク除去タスクはノード除去タスクよりも基 本的であると言える．したがって，ネットワークから 適切にリンク群を除去することにより好ましくない情 報の拡散を防止することは，重要な問題である． 一方，社会ネットワーク内での情報拡散において影響 力が強いノード群を抽出することは，社会学やバイラル マーケティングの観点から重要である [3, 12, 4]．近年， 社会ネットワーク内の情報伝搬の基本確率モデルとし て広く用いられている “independent cascade (IC) モデ ル” に基づいて，“影響最大化問題” と呼ばれる組み合わ せ最適化問題を解くことが試みられている [5, 7]．ここ に，影響最大化問題とは，与えられた正整数 K に対し て，ある好ましい情報が伝わるノード数の期待値を最大 にするには，どの K 個のノード群にその情報を最初に 伝えるべきかという最適化問題である．IC モデルは，伝 染病蔓延に関する所謂 susceptible/infective/recovered 人工知能学会研究会資料 SIG-DMSM-A803-16 (3/4)

(SIR) モデル [4] と同一視されることに注意しておく． 本論文では，影響最大化問題と反対の問題を論じる． それは，ネットワークにおいて指定された数のリンク 群を封鎖することにより，好ましくない情報の広がり を最小化するという問題である．より具体的には，あ る好ましくない情報が任意のノードから始まり，IC モ デルに基づいてネットワークを通じて拡散していくと き，与えられた正整数 K に対して，次のような条件を 満たす K 本のリンク群を抽出する問題を考える．その 条件とは，それらリンク群を封鎖することにより得ら れるネットワークが，その情報による “汚染度” を最小 にするというものである．我々はこの組み合わせ最適 化問題を “汚染最小化問題” と呼ぶ．ネットワークの汚 染度として “平均汚染度” と “最悪汚染度” の 2 つの定 義を導入し，それらの定義に従って “平均汚染最小化 問題” と “最悪汚染最小化問題” の 2 つの汚染最小化問 題を定式化する．前者は汚染ノード数の期待値（平均 ケース）を最小化することを目的とし，後者は汚染ノー ド数の最大値（最悪ケース）を最小化することを目的 としている． 我々は，これら汚染最小化問題の近似解を，自然な 貪欲戦略に基づいて効率よく求める新たな手法を提案 する．また，提案法とナイーブ貪欲戦略の計算量を比 較し，提案法は計算効率を大幅に改善できることを示 す．さらに，実際問題において提案法の計算効率をよ り向上させる実装戦略も与える．最後に，社会ネット ワークの顕著な特徴を多くもつ大規模な実世界ネット ワークを用いた実験により，複雑ネットワーク科学の 分野でよく用いられている，betweenness や出次数に 基づいたリンク除去ヒューリスティクスよりも，提案 法が高性能であることを実証する．特に，指定された 数のノード群を封鎖する場合と異なり，高出次数ノー ド群を除去する戦略は我々の問題では必ずしも有効で ないことを示す．

2

情報拡散モデルと汚染最小化

ある好ましくない情報がネットワークを通じて拡散 する過程の数理モデルとして IC モデルを仮定する．そ の情報によって汚染されたノードを，“アクティブノー ド” と呼ぶ． G = (V, E) を有向ネットワークとする．ここに，V はノード全体の集合を，E (⊂ V × V ) は（有向）リン ク全体の集合を，それぞれ表わす．本論文では，ネッ トワークは有向ネットワークを，リンクは有向リンク をそれぞれ意味し，ネットワークはグラフとも呼ばれ る．以下では，まず Kempe ら [5] の研究にしたがって グラフ G 上の IC モデルを定義し，そして G 上の汚染 最小化問題を定式化する．

2.1

IC モデル

IC モデルを定義する．本モデルでは，拡散過程は離 散時間 t ≥ 0 で展開していく．ノードはその状態が非 アクティブからアクティブに変化するが，その逆には 変化しないと仮定される．また，0 < p < 1 なる実数 p が前もって指定される．ここに，p はリンクを通じて の “伝播確率” と呼ばれる． 初期アクティブノード v が与えられたとき，ノード v は時刻 t = 0 で初めてアクティブになり，その他のノー ドは時刻 t = 0 では非アクティブであると仮定される． IC モデルの拡散過程は次のように進んでいく．ノード u が，時刻 t で初めてアクティブになったとする．この とき，u は，非アクティブであるその各子ノード w を アクティブにする試行を時刻 t で行い，その試行は確 率 p で成功する．もし，w の複数の親ノードが時刻 t で 初めてアクティブになった場合は，それら親ノードが w をアクティブにする試行は任意の順序で独立に順々 に行われることになるが，これらの試行はすべて時刻 t で行われる．そして，w をアクティブにする試行のう ち，少なくとも一つの試行が成功したとき，w は時刻 t + 1 においてアクティブとなる．ところで，u が時刻 t で w をアクティブにするのに成功したか失敗したか にかかわらず，時刻 t + 1 以降では，u はもはや w を アクティブにする試行を行うことはできない．すなわ ち，初めてアクティブになったノードのみが，その非 アクティブ子ノードをアクティブにする試行を行うこ とができる．新たにアクティブとなるノードが存在し なくなったとき，IC モデルの拡散過程は終了する． 初期アクティブノード v からの G 上の IC モデルに 基づいた確率過程に対して，その終了後のアクティブ ノード数の期待値を σ(v; G) とする．σ(v; G) はグラフ G におけるノード v の “影響度” と呼ばれる．

2.2

汚染最小化問題

ある好ましくない情報が任意のノードから始まり，IC モデルに基づいてネットワークを通じて拡散していく と仮定する．このとき，その広がりを防止するために， 指定された数のリンク群を適切に除去することにより， その情報による “汚染度” を最小化すること目指す．こ こに，ネットワークの汚染度とは，その情報がネット ワークをどのくらい汚染しうるかの尺度である．我々 は，2 つの汚染度の定義を導入し，2 つの汚染最小化問 題を定式化する． まず，グラフ G の “平均汚染度”c0(G) を，G 内の ノードの影響度の平均値として次のように定義する． c0(G) = 1 |V | X v∈V σ(v; G). (1)

次に，グラフ G の “最悪汚染度”c+(G) を，G 内のノー ドの影響度の最大値として次のように定義する． c+(G) = max v∈V σ(v; G). (2) 上記の汚染度の定義にしたがって，ネットワーク上 の汚染最小化問題を，影響最大化問題と反対の問題と して数学的に定義する．まず，いくつかの記号法を準 備する．任意のリンク e ∈ E に対して，グラフ (V , E \

{e}) を G(e) と記述する．グラフ G(e) を，G において e を封鎖することにより構成されるグラフと呼ぶ．同 様に，任意のリンク集合 D ⊂ E に対して，グラフ (V , E \ D) を G(D) と記述する．グラフ G(D) を，G に おいて D を封鎖することにより構成されるグラフと呼 ぶ．さて，グラフ G 上の “汚染最小化問題” を，組み 合わせ最適化問題として次のように定義する．「正整数 K (K < |E|) 与えられたとき，任意のリンク集合 D ⊂ E (|D| = K) に対して， c(G(D∗_{)) ≤ c(G(D))} となるようなリンク集合 D∗ ⊂ E (|D∗_{| = K) を求め} よ．」ここに，c = c0の場合の汚染最小化問題を “平均 汚染最小化問題” と呼び，c = c+の場合の汚染最小化 問題を “最悪汚染最小化問題” と呼ぶ．

3

提案法

大規模ネットワークにおいて汚染最小化問題を厳密 に解くとき，組み合わせ爆発が問題となる．我々は，品 質の良い近似解を効率よく求める手法を提案する．汚 染最小化問題において封鎖するリンク群の数を K と する．

3.1

貪欲アルゴリズム

我々は，グラフ G0 = (V0, E0) 上の汚染最小化問題 を，次の貪欲アルゴリズムにより近似的に解く． A1 Initialize a subset D of E0 as D ← ∅.

A2 Initialize a graph G = (V, E) as V ← V0 and

E ← E0.

A3 Choose a link e∗∈ E minimizing c(G(e)),

(e ∈ E). A4 Update D as D ← D ∪ {e∗}. A5 Update G = (V, E) as E ← E \ {e∗}. A6 Return to Step A3 if |D| < K. A7 Set DK← D. A8 Set GK ← G. ここに，DKは封鎖リンク集合であり，本アルゴリズ ムにより求められる近似解を表している．GKは G0か ら DKを封鎖することにより構成されるグラフであり， すなわち，GK = G0(DK) である． この貪欲アルゴリズムでは，ステップ A3 において 与えられたグラフ G = (V, E) に対し， e∗= arg min e∈Ec(G(e)) (3) を計算する手法が必要である．しかしながら，IC モデル は確率過程モデルであり，影響度を厳密に求める効率的 手法は知られていない [5]．すなわち，{c(G(e)); e ∈ E} を効率よく推定する手法の開発が必要である．ところ で Kimura ら [7] は，任意のグラフ ˜G = ( ˜V , ˜E) に対し 影響度 {σ(v; ˜G); v ∈ ˜V } を効率よく推定する手法とし て “ボンドパーコレーション (BP) 法” を与えた．BP 法を用いることにより，各 e ∈ E に対して，式 (1), (2) から c(G(e)) を推定することができる．よって，ステッ プ A3 を単純に次の手法で実現することにより，近似 解 DKを求めることができる．

1. Estimate {c(G(e)); e ∈ E} by straightforwardly performing the BP method |E| times.

2. Find e∗ ∈ E such that c(G(e∗)) ≤ c(G(e)) for

any e ∈ E. 我々はこの戦略を “ナイーブ貪欲戦略” と呼ぶ．しかし ながら，大規模ネットワークでは，K があまり大きく ないとき |E| は非常に大きくなってしまう．すなわち， ナイーブ貪欲戦略は大規模ネットワークにおいては実 用的ではない．したがって，我々は，BP 法に基づいて 式 (3) を満たす e∗∈ E を推定する，より効率のよい手 法を提案する．

3.2

ボンドパーコレーション法

まず，BP 法について簡単に述べる（詳細は [7] を参 照）．グラフ G = (V, E) において伝搬確率 p の IC モ デルに対し，影響度 {σ(v; G); v ∈ V } を推定すること を考える． IC モデルはボンドパーコレーション (BP) 過程と同 値である [9]．ここに，BP 過程とは，G の各リンクを 独立に確率 p で “占領” と宣言していく過程である．与 えられた正整数 M に対して，BP 過程を M 回実行し， 占領リンクから構成される M 個のグラフ {Gm_{= (V, E}m_{); m = 1, · · · , M } (4)}

を生成する．任意の v ∈ V に対して s(v; G, M ) を， s(v; G, M ) = 1 M M X m=1 |F (v; Gm)| (5) で定義する．ここに，F (v; Gm) は，グラフ Gmにお いてノード v から到達可能なノード全体の集合である． M が十分大きいならば， σ(v; G) ' s(v; G, M ), (v ∈ V ) (6) が成り立つ [9]．各グラフ Gmを次のように強連結成分 (SCC) に分解する． V = Jm [ j=1 SCC(um j ; Gm). (7) ここに，Jmは Gmの SCC 数であり，SCC(um_j ; Gm₎ はノード umj を含む Gmの SCC である．このとき， |F (v; Gm)| = |F (umj ; Gm)|, (v ∈ SCC(umj ; Gm)) (8) が成り立つ．したがって，{|F (umj ; Gm)|; j = 1, · · · , Jm} を事前に計算し，式 (8) を用いることにより，すべての v ∈ V に対して |F (v; Gm_{)| を効率よく計算できる．さ} らに式 (5) より，すべての v ∈ V に対して s(v; G, M ) を求めることができる． すなわち BP 法は，まず BP 過程の実行回数 M を 指定し，上記の手続きに従ってすべての v ∈ V に対し s(v; G, M ) を求め，そして式 (6) を用いることにより， すべての v ∈ V に対し影響度 σ(v; G) を推定する．

3.3

推定法

我々は，式 (3) を満たす e∗∈ E を効率よく推定する 手法を提案する． まず，指定された正整数 M に対して，BP 過程を M 回実行し，式 (4) のように占領リンクからなる M 個の グラフを生成する．次に， BM(e) = {m ∈ {1, · · · , M }; e /∈ Em} , (e ∈ E) (9) を計算する． さて，任意のリンク e ∈ E に対して，BP 過程を

G(e) = (V, E \ {e}) 上で |BM(e)| 回試行し，占領リン

クからなる |BM(e)| 個のグラフ

{G(e)m; m = 1, · · · , |BM(e)|}

を生成しよう．ここで，M は |BM(e)| も十分に大きく

なるくらいに大きいと仮定する．このとき，式 (6) より，

σ(v; G(e)) ' s (v; G(e), |BM(e)|) , (v ∈ V ) (10)

が成り立つ．また，式 (5) から， s (v; G(e), |BM(e)|) (11) = 1 |BM(e)| |B_XM(e)| m=1 |F (v; G(e)m)| , (v ∈ V ) が成り立つ． 我々は，{c(G(e)); e ∈ E} を効率よく推定するため に，すべての e ∈ E に対してグラフ G(e) 上で BP 法 を適用する代わりに，BP 法に基づいてグラフ G 上で， sM(v, e) (12) = 1 |BM(e)| X m∈BM(e) |F (v; Gm_{)|, (v ∈ V, e ∈ E)} を計算することを考える．実際，式 (9), (10), (11), (12)， および BP 過程におけるリンク占領宣言の独立性より， 次の定理が成り立つ． 定理 3.1 G = (V, E) をグラフとする．すべての v ∈ V , e ∈ E に対して， sM(v, e) → σ(v; G(e)) as M → ∞ が成り立つ． 定理 3.1 より，M が十分大ならば，

σ(v; G(e)) ' s_M(v, e), (v ∈ V, e ∈ E), (13) という近似を行うことができる．したがって，式 (1), (2) より，我々は，式 (3) を満たす e∗∈ E を，平均汚 染最小化問題 (i.e., c = c0) では， e∗= arg min e∈E Ã 1 |V | X v∈V sM(v, e) ! (14) と推定し，最悪汚染最小化問題 (i.e., c = c+) では， e∗= arg min e∈E µ max v∈V sM(v, e) ¶ (15) と推定することを提案する．

3.4

計算量と実装戦略

提案法とナイーブ貪欲戦略の計算量を比較する．貪欲 アルゴリズムのステップ A3 において，{c(G(e); e ∈ E} を推定する計算量に焦点をあてる．グラフ G = (V, E) 上で BP 法に基づいて {s(v; G, 1); v ∈ V } を計算する 計算量の期待値を Q とする．|E| は十分大きいので，任 意の v ∈ V , e ∈ E に対し s(v; G, 1) と s(v; G(e), 1) の 計算量は等しいと仮定する．このとき，提案法の計算

量の期待値は M Q であり，ナイーブ貪欲戦略の計算量 の期待値は M Q|E|(1 − p) であると考えられる（詳細 は [6] を参照）．すなわち，提案法はナイーブ貪欲戦略 よりも平均的に |E|(1 − p) 倍高速でありうることがわ かる．例えば，|E| = 10, 000, p = 0.2 ならば，提案法 は 8, 000 倍も高速になると期待できる． 我々はさらに，グラフ G = (V, E) に対し式 (14) ま たは式 (15) を満たす e∗∈ E を実際問題でより効率よ く求めることを目指し，以下のような実装戦略を導入 する．まず，最悪汚染最小化問題では，Leskovec ら [8] による劣モジュラー関数の周辺ゲインに対する lazy 評 価の考え方を応用する．すなわち，{sM(v, e); v ∈ V , e ∈ E} の計算を，s_M(v, e) の上限， M |BM(e)|s(v; G, M ) ≥ sM(v, e) を用いたプルーニングにより効率化し，式 (15) を効率 よく計算するという戦略をとる（詳細は [6] を参照）． 次に，平均汚染最小化問題では， 1 |V | X v∈V s_M(v, e) = 1 |BM(e)| X m∈BM(e) 1 |V | X v∈V |F (v; Gm_{)|, (e ∈ E)} を用いて，ノード v とリンク e のすべての組に対し s_M(v, e) を計算することなく，式 (14) を効率よく計算 するという戦略をとる（詳細は [6] を参照）．

4

実験評価

本研究では，社会ネットワークの顕著な特徴を多く もつ大規模な実ネットワークであるブログネットワー クや Wikipedia ネットワークを用いて，提案法の有効 性を実証した [6]．ここでは，ブログネットワークにお ける実験結果についてのみ述べる（実験の詳細は [6] を 参照）．ブログネットワークは，ノード数が 12, 047 で リンク数が 79, 920 の双方向ネットワークである．伝搬 確率 p として p = 0.2，BP 法における BP 過程の実行 回数 M として M = 10, 000 を用いた．

4.1

比較法

提案法を 3 つのヒューリスティクス法と比較した．そ の 2 つは複雑ネットワーク科学の分野でよく用いられる betweenness および出次数に基づいたものであり，あと の 1 つはランダムにリンクを封鎖するというベースラ インである．これらの手法をそれぞれ，“betweenness 法”，“出次数法” および “ランダム法” と呼ぶ． 4.1.1 Betweenness 法 グラフ G = (V, E) において，リンク e の “between-ness スコア”bG(e) を次で定義する． bG(e) = X u,v∈V nG(e; u, v) NG(u, v) . ここに，NG(u, v) はグラフ G 上でのノード u からノー ド v への最短パスの数であり，nG(e; u, v) はそれら最 短パスのうちリンク e を通るものの数である．ただし，

NG(u, v) = 0 の場合は，nG(e; u, v)/NG(u, v) = 0 と

定義する．“betweenness 法” とは，次のアルゴリズム [11] によるリンク除去法である．

B1 Calculate betweenness scores for all links in the network.

B2 Find the link with the highest score and remove it from the network.

B3 Recalculate betweenness scores for all remaining links.

B4 Repeat from Step B2.

4.1.2 出次数法 これまで，たいていの実ネットワークにおいては，出 次数の高いノードから順に除去する戦略が，汚染防止 に対してしばしば有効であるということが示されてい た [1, 2, 10]．ここに，ノード v の “出次数”d(v) とは， v からの出リンクの数のことである．そこで，リンク 除去法に関する比較法として，出次数の高い順にノー ドを選択し，選択されたノードに付着しているすべて のリンクを同時に削除するという手法を考える．我々 は本手法を “ノード出次数法” と呼ぶ． また，リンク除去法に関する別の比較法として，高 出次数ノード間のリンクを削除する手法を考える．す なわち，ノード u からノード v へのリンク e = (u, v) の “リンク出次数”d(e) を， d(e) = d(u) d(v) で定義し，リンク出次数の高いリンクから順に除去す るという戦略を考える．我々は本手法を “リンク出次 数法” と呼ぶ．

4.2

実験結果

提案法の性能を評価し，それを，betweenness 法，ノー ド次数法，リンク次数法およびランダム法の性能と比 較した．明らかに，性能は平均汚染度 c0および最悪汚

染度 c+により評価されうる．これらの値はボンドパー コレーション法を用いて， c0(GK) = 1 |V | X v∈V s(v; GK, M ), c+(GK) = max v∈V s(v; GK, M ), により推定した．ただし，M = 300, 000 を用いた． 0 100 200 300 400 500 0 100 200 300 400 500 600 700 800 900 1000

number of links blocked

average contamination degree

proposed betweenness 図 1: 平均汚染最小化問題における提案法と between-ness 法の性能比較． 101 102 103 104 105 0 100 200 300 400 500 600 700 800 900 1000

number of links blocked

average contamination degree

proposed (k = 500) random link out−degree node out−degree 図 2: 平均汚染最小化問題における提案法 (K = 500) とノード次数法，リンク次数法およびランダム法の性 能比較． 図 1,2 は平均汚染度 c0を封鎖リンク数 K の関数と して表示しており，図 3,4 は最悪汚染度 c+を封鎖リン ク数 K の関数として表示している．これらの図では， 丸印，四角印，ダイヤモンド印，三角印，およびクロ ス印は，それぞれ，提案法，betweenness 法，ノード次 数法，リンク次数法，およびランダム法の結果を示し ている．図 1,3 では提案法と betweenness 法を比較し 0 100 200 300 400 500 0 500 1000 1500 2000 2500 3000 3500

number of links blocked

worst contamination degree

proposed betweenness 図 3: 最悪汚染最小化問題における提案法と between-ness 法の性能比較． 101 102 103 104 105 0 500 1000 1500 2000 2500 3000 3500

number of links blocked

worst contamination degree

proposed (k = 500) random link out−degree node out−degree 図 4: 最悪汚染最小化問題における提案法 (K = 500) とノード次数法，リンク次数法およびランダム法の性 能比較． ており，図 2,4 では固定値 K = 500 での提案法とノー ド次数法，リンク次数法，およびランダム法を比較し ている．平均汚染最小化問題でも最悪汚染最小化問題 でも，提案法が最も高性能であり，betweenness 法が次 に性能がよく，他の 3 手法はこれら 2 つの手法よりも 性能が非常に悪いということが見て取れる．特に，提 案法により 500 本のリンク群を削除することは，ノー ド次数法により 10, 000 本以上のリンク群を削除する ことと同等であることが見て取れる．ところで，リン ク封鎖数 K = 500 とは，リンク全体の約 0.63% のリ ンク群を封鎖することを意味している．提案法は，約 0.63% のリンク群を封鎖することにより，平均汚染度 を約 976 から約 267 まで，すなわち，約 73% 削減して おり，最悪汚染度を約 3, 218 から約 1, 045 まで，すな わち，約 78% 削減している．

上記の結果より，提案法は期待どおり有効であると 考えられる．ところで，従来のリンク除去ヒューリス ティクスがどのような性能となるかは，もちろんネッ トワークの構造的特徴に依存する．我々が分析したネッ トワークは明確なコミュニティー（クラスター）構造を もっていたため，コミュニティ間をつなぐ少数のパス を削除するような betweenness 法が有効であったので はないかと考えられる．例えば，もしネットワークが 階層的な構造をしていたならば，その上部階層に属す るノードを削除するようなノード次数法が有効になっ たと推測される．また，我々が分析したネットワーク に対してリンク出次数法の性能が悪かったのは，コミュ ニティー内のリンクを主に削除していたためではない かと推測される．一方，提案法には，情報拡散過程の ダイナミクスを考慮して汚染度を陽に最小化している という強みがある．したがって，提案法はネットワー ク構造によらず性能が良かったと考えられる．

5

おわりに

ネットワークにおいて指定された数のリンク群を封 鎖することにより好ましくない情報の広がりを最小化 するという，影響最大化問題とは反対の問題である，汚 染最小化問題を論じた．特に，平均汚染最小化問題と 最悪汚染最小化問題という 2 つの汚染最小化問題を考 察した． 我々は，これら汚染最小化問題の近似解を，自然な 貪欲戦略とボンドパーコレーション法に基づいて効率 よく求める新たな手法を提案した．大規模なブログネッ トワークおよび Wikipedia ネットワークを用いた実験 により，提案法は有効であり，従来のリンク除去ヒュー リスティクスよりも高性能であることを実証した．特 に実験では，betweenness 法はある程度良い性能を示 していたが，出次数法はランダム法と同程度の悪い性 能しか示していなかった．出次数神話は我々が分析し たネットワークでは観察されなかった．すなわち，リ ンク除去ヒューリスティクスはネットワーク構造に性 能が大きく影響されるが，提案法はネットワーク構造 によらず性能が良いことが確認された．これは，情報 拡散過程のダイナミクスを考慮して汚染度を陽に最小 化することが，重要であるということを実証している．

謝辞

本研究は，科学研究費補助金基盤研究 (C)(No. 20500147) の補助を受けた．

参考文献

[1] Albert, R., Jeong, H., and Barab´asi, A. -L.: Error and attack tolerance of complex networks, Nature, Vol. 406, pp. 378–382 (2000).

[2] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J.: Graph structure in the web,

Proceed-ings of the 9th International World Wide Web Con-ference, pp. 309–320 (2000).

[3] Domingos, P. and Richardson, M.: Mining the net-work value of customers, Proceedings of the 7th ACM SIGKDD International Conference on Knowl-edge Discovery and Data Mining, pp. 57–66 (2001).

[4] Gruhl, D., Guha, R., Liben-Nowell, D., and Tomkins, A.: Information diffusion through blogspace. Proceedings of the 13th International World Wide Web Conference, pp. 107–117 (2004).

[5] Kempe, D., Kleinberg, J., and Tardos, E.: Maximiz-ing the spread of influence through a social network.

Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Min-ing, pp. 137–146 (2003).

[6] Kimura, M., Saito, K., and Motoda, H.: Blocking links to minimize contamination spread in a social network, to appear in ACM Transactions on

Knowl-edge Discovery from Data.

[7] Kimura, M., Saito, K., and Nakano, R.: Extracting influential nodes for information diffusion on a social network, Proceedings of the 22nd AAAI Conference

on Artificial Intelligence, pp. 1371–1376 (2007).

[8] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., and Glance, N.: Cost-effective out-break detection in networks, Proceedings of the 13th

ACM SIGKDD International Conference on Knowl-edge Discovery and Data Mining, pp. 420–429 (2007).

[9] Newman, M. E. J.: The structure and function of complex networks, SIAM Review, Vol. 45, pp. 167– 256 (2003).

[10] Newman, M. E. J., Forrest, S., and Balthrop, J.: Email networks and the spread of computer viruses,

Physical Review E, Vol. 66, 035101 (2002).

[11] Newman, M. E. J. and Girvan, M.: Finding and evaluating community structure in networks,

Physi-cal Review E, Vol. 69, 026113 (2004).

[12] Richardson, M. and Domingos, P.: Mining knowledge-sharing sites for viral marketing,

Proceed-ings of the 8th ACM SIGKDD International Con-ference on Knowledge Discovery and Data Mining,