講演者：松田 哲直（東京工業大学）
題 目：ネットワークにおける噂の発信源推定法
日 時：2015年12月4日(金) 18:00-
場 所：早稲田大学西早稲田キャンパス63号館 数学応用数理会議室（102号室）
オープニング
司会：じゃあ、お願いします。
堀井：簡単に紹介をさせてもらって。松田哲直さんは2012年に学位を取得されて、それ以来、東工大で助教をされているということですね。1年に1回、我々の業界でSITA（情報理論とその応用シンポジウム）というのがあって、たぶん初めて会ったのがそのシンポジウムですね。
松田：そうですね。
堀井：たぶん鬼怒川の時に初めて会った……
松田：たぶんそうですね。初めて会ったのはそうですね。
堀井：だから2007年ぐらいのSITAで会って、それ以来、1年に数回、1年に1回は絶対会うというような。SITAシンポジウムって1年に1回あるんですけど、毎年、若手の研究者の優秀な論文を表彰するというSITA奨励賞というのを出していて、今年の受賞者です。
松田：ちょっと今回の内容とは関係ないので、なんか申し訳ないです。
堀井：実は去年のシンポジウムで2件発表されたんですよね。
松田：そうですね。
堀井：2件発表されていて、ご専門が多端子情報理論というネットワーク型の情報理論が専門で、そちらの発表が受賞の論文なんですけど、こっちは受賞しなかったほうの論文なんですけれど、去年、話を聴いてちょっと面白いなって、ぜひ聴かせていただきたいなとお願いしました。じゃあ、お願いします。
講演
松田：どうもありがとうございます。じゃあ、始めていきます。皆さん、このような場を与えてくださり本当にありがとうございます。堀井さんにはこの話を聴いていただいた際に興味を持っていただいてよかったと、こういう場を与えていただいてよかったなと思っています。
今日は、噂の発信源推定法というものをお話しますけど、分かんないこと、気になること、特に「なんか、これ、おかしいんじゃないのか？」ってことなんかをコメントしていただけると助かります。
タイトルは「ネットワークにおける噂の発信源推定法」です。1カ月前にタイトルだけポンと決めちゃったんで、ついタイトルに「推定法」って付けちゃったんですけど、実は推定法そのものにはあまりスポットを当ててなくて、どちらかというと「噂の発信源特定問題」というものにスポットを当てています。
最初に、「噂の発信源」というのを特定する問題を、その背景から問題設定まで説明していきます。次に、発信源と推定値との距離というのを見ていきます。これが、私がSITAで発表した内容になっています。あとはその他の話題を話して、最後にまとめようと思っています。
噂の発信源特定問題、何なのかよく分かんないですね。まずはこれについて話していきます。
「噂はネットワークを介してまるで伝染病のように広がっていく」と書いてありますけど、実際、くだらない噂でも人のネットワークを介して伝染病のように伝わっていきますよね。この前聞いた話で面白いのがあって、噂だけで銀行から大量の預金が無くなったという事件がありました。知っていますかね。すごい昔の話なんですけど、女子高生がある銀行が危ないという話を友達にしたら、それが伝染病のように町中に広がってしまって、その話を信じた人たちが次々と預金を引き下ろしたんです。1週間ほどで20億ぐらい引き落とされちゃったらしいです。
今だったらFacebookとかツイッターがあるんで、目に見える形で、フォローし合っている人のネットワークを通じて噂はどんどん広がっていきます。
噂の例というのをここで挙げています。今言ったようなゴシップ、これは人のネットワークを介して伝播していくような例ですけど、あとはトレンド、流行ですね。おしゃれな服があるとか靴があるというのも、これはツイッターなんかで広がりやすいかもしれません。あとはコンピューターウイルスっていうのも、伝播していくものの典型的な例ですね。ウイルスがネットワークを伝わって伝播していく。例えば、ワームがルータ間を伝わって脆弱なノードにどんどん飛び火していきますね。ワームが流行りだした時は、すごい未来感がしましたけどね、自己増殖するっていうあの感じは。という余談をしているとちょっと時間がなくなりますね。
噂って伝染病みたいと言えますけど、その逆も、伝染病っていうのは噂みたいなもんだと考えれば、これも伝播していくようなものの例でしょう。あと、企業の損益ですね。どこかの企業が損をすると関連会社にどんどん損が広がっていっちゃうというのを考えると、関連する会社同士のネットワークを介する噂の伝播と見なせるかなと思います。
こういうものがどんどん広がっていく様子を解析するというのが、よくあるネットワークの研究です。例えば伝染病の研究だと、伝染する確率がどういう値以上だと、その伝染病を止められず広がっていってしまうのかといったことが研究されます。その広がりにスポットを当てているわけです。
今回の話はある意味その逆で、広がってきた結果から、その発信源というのがどこにあるのかを探しましょうということです。発信源が分かると何ができるかというと、例えばゴシップだったら噂の真偽を確認しやすいですよね。一次情報にたどり着けるわけですから。例えば、明日、震度7の地震が東京で起きるかもしれないという噂をみんな知っているとして、その発信源が政府だったら、割と信用できそうです。でも私だったら、たぶんまったく信用してくれないですね。そういう真偽の確認には使えるかもしれない。
あとは、流行させた人のページランキング。流行したものをGoogleで検索したら、はやらせた人の、例えばブログがトップに来てほしいですね、そういうページランキングにも使えるかもしれない。
コンピューターウイルスだったら、発信源になったノードというのは脆弱でしょうと。そういう脆弱なノードを隔離するためには使えそうです。あるいは犯人そのものかもしれませんけど、そういう犯人を捕まえるのに使えるかもしれない。
そして、伝染病では感染源を隔離できると。
あとはこういう企業の損益の広がりで、ある原因となった企業に一時的な融資をしたり、投資をしてもっと利益を上げるようにしたりとか、そういうことができそうです。
という感じで、この辺が噂の発信源特定問題の背景です。この問題を最近、2011年ぐらいに真面目に理論的に取り組んだ人たちがいて、その人たちの論文で読んで興味を持ったのでこの研究を始めました。
過去にこういう研究をした人がまったくいなかったのかというと、そういうわけではなくて、今回の研究とはちょっと話が外れるんですけど、たぶん、このJohn Snowという人が初めて理論的に発信源というのを研究した人だと思います。
John Snowってご存じですか？ 私は知らなかったんですけど、この人は「疫学」っていわれている、伝染病とか集団の病気を理論立てて何が原因だったとか、どうやって広がっていくのかっていう研究をする学問がありますが、その始祖とされている人です。だから、情報理論でいうとShannonに当たる人ですね。
1854年にロンドンでコレラがものすごく流行して、616名の死者が出ました。これが、その死者が出た所のマップなんですけど。John Snowという人は医者で、この人はコレラの感染者の居住地、ここでマップで書いてあるこの黒い点々が感染死者の居住地になっているんですけど、これを調べて、あとは実際にこの地域に行ってインタビューなんかをして、手押し井戸が感染源だと推測しました。それで、井戸の使用を止めるとコレラは実際に終息したと。井戸が感染源となって、どんどんコレラを広げていったということが分かったわけです。
この彼の手法というのは、井戸からのボロノイ図みたいなものを作って、その井戸の範囲に入っている人たちが何人いるのかを数えることで、この部分が感染源だということを推測しました。こういう単純な平面であれば、そういう推定法が有効かもしれませんが、今回扱うのはネットワークです。
発信源特定問題というのは、ざっくり言うと、噂を知っている人、さっきの例だったら伝染病の死者が分かっていて、その人たちの間のネットワークも知っているとして、感染した時間は分かりませんが、とにかく死亡している人は分かっているとして、その発信源というのを探し当てることができるかという問題です。
コンピューターウイルスだったら、いつ感染したのか分からないけれどもウイルスに感染していることは分かっていると。で、社内のネットワークのトポロジーも分かっていますと。そのときに発信源がわかりますかという問題です。
そうすると、その推定方法、推定成功率とか、ネットワークの構造に依存するのかという疑問が湧いてきます。
ここまでが背景になります。ここからは数学的な定義に移っていきます。何か質問があれば止めていただいてかまいません。
ネットワークと今まで呼んでいたものは、数学的に言えばグラフです。
ネットワークを今、Gにしておきます。Gというのは無向で連結なグラフです。
V（G）って書いたら、Gの頂点の集合とします。ちょっと注意ですけど、伝播していったときに境界にたどり着くと感染する先がなくなっちゃうんで、そういう影響を今は避けるために、頂点数は無限にあるとします。あと、ここはどうでもいいんですけど、整数の集合としておいてください、分かりやすいので。
E（G）というのは、Gの辺の集合とします。
(i,j)は、iとjを結ぶ辺だとしておいてください。
噂が辺を伝わる確率というのを次に考えなきゃいけません。ここでは時刻tまでに噂が伝わる確率というのを定義します。時刻t、秒でも何でもいいですけど、t秒までに噂が伝わる確率というのをこのF（t）の確率で定義します。つまり、赤い頂点が噂を知っていたとすると、噂を知らない隣接頂点には時刻tまでにF（t）の確率で噂が伝わるということです。λって書いてあるこの値は噂の伝わりやすさを表していて、大きければ大きいほど速い時間で伝わりやすいということです。
このFという関数は、実は指数分布の累積分布関数になっています。なんで指数分布なのかっていうと、この噂の伝播モデルでは、時間が進むごとに感染力が変わらないことを仮定しているからです。感染力が時間ごとに変わったりする研究もあったりするんですけど、とりあえず簡単のためにここではこうしています。
なぜ指数なのかはちょっと説明しますけど、微小時間Δtの間に感染力が変わらないとすると、その時間の間に隣に伝わる確率はλ×Δtになる。そうすると時刻Δtまでに噂が伝わらない確率というのは、1-λΔtです。これは噂が伝わる確率を1から引けばいいわけですね。これをもとに、t秒までについてを考えると、tをΔtで割るとそのΔt秒の区間が何個あるかが分かるので、その区間分だけ積をとります。そうすると時刻tまでに噂が伝わらない確率になります。Δtは微小時間なので、0に近づけてあげると指数になります。これは感染力が変わらないということから導ける式です。
Ａ：さっきのグラフの定義だと、無向グラフだと。伝わるっていうとなんかどっちからどっちみたいなのがあるかと思うんで、それは何か矛盾なく定義できるのか。
松田：矛盾なく定義できて、噂を知っている人を親として、それが伝わるというかたちです。
Ａ：ここのF（t）の情報にはどっちからどっちとかいうのは無いけれど、それはいいの？
司会：知ってる・知ってるの場合に両方ってことですか。
松田：知ってる・知ってるの場合には……
司会：両方向伝える可能性があるってことなんですか。
松田：それはないです。
司会：それはないんですか。
松田：それはなくて、知っている人にはもう伝えなくて、知らない人に対して伝わっていくっていう意味では、そういう知っている人から知らない人に伝わるっていう方向性はあります。
堀井：その時刻っていうのは、誰か隣の人が噂を知ってからの時刻なんですか。
松田：知ってからの時刻です。だからそういう意味での因果関係みたいなのはありますね。それはこの後でも話していきますけど。
τ(i,j)っていうのを各辺に定義されている、指数分布に従う独立な確率変数とします。噂が伝播していくモデルってどうなっているかというと、まず時刻0で、一つの頂点v1が噂を知っているとします。頂点vが噂を知ったら、そこに隣接する頂点v'は単位秒後、τ(v,v')秒後に噂を知るということにします。
一度知った噂っていうのは忘れることはない。ウイルスに感染したら、それを駆除するまではずっとウイルスをまき散らすと。これは伝染病でも使われるモデルで、SIモデルというふうにも呼ばれています。
ちなみに、噂を忘れるようなモデルっていうのはSISモデルって呼ばれています。Sという噂に感染しやすい状態になって感染して、また感染しやすい状態に戻ると。こういう伝染病のモデルをこの問題でも借りているわけです。確率過程の分野ではコンタクト・プロセスと呼ばれているものです。
発信源特定問題をどうやって定義するかを説明します。S（G)というのは、Gの連結な誘導部分グラフ全ての集合です。Gの部分グラフなんですけど、G内の部分的な頂点とその頂点を結ぶ辺を全て含むグラフです。Gnというのが、観測されるグラフです。これはローマン体で書いているんで、要は確率的なものだというイメージです。噂のグラフってこれ以降呼びますけど、このGnというのを噂を知っているn個の頂点から誘導されるGの部分グラフとします。
これがGの一部だとすると、この赤いのが噂に感染してる、というか噂を知ってる頂点だとしましょう。そうすると、Gnっていうのはこの部分のグラフです。そこの頂点から誘導される全ての辺を持つグラフが噂のグラフです。
それで、特定問題っていうのはどういうものかというと、与えられたグラフGと噂のグラフGnから、噂の発信源だった頂点を特定するというものです。ただし、噂のモデルはSIモデルに従っていることを仮定します。これらの中のどれが噂の発信源になっているかを推定しなさいという問題です。
司会：これはどういう順番とか全くなくて、ある特定の点で0、1ということですね。感染しているか、感染していないか。
松田：感染しているか、感染していないか。そこから導き出したいということです。
Mathematicaを使った噂の発信源特定問題のデモ：
ちょっとデモを作ったんですけど、おもちゃみたいなデモを作ってきて。
あんまり複雑なネットワークにしてもしょうがなかったので、すごい簡単なこういうネットワークがあるとしましょう。頂点があって、辺があると。赤い所が噂を知っている人だったとします。
今、例えば20人の人が噂を知っているというネットワークをつくります。これで、どこが発信源でしょうという問題です、要は。
推定成功率を定義しておきます。φは推定器とします。これは要は噂のグラフから頂点への写像です。Cnというのが推定成功率で、v1から噂が始まったとしたときにφを使って推定が成功する確率としておきます。
これはこのように定義します。今、Pnっていうのをvから始まってGっていうグラフが得られる確率とします。なのでこの部分は、頂点v1から噂が始まって、Gnっていう噂のグラフが得られる確率になります。それで、Gnを推定器に入れてv1が出てくれば推定が成功するわけですけど、それを全てのGnについて足し合わせたものが推定成功率になります。
ここで、これが確率的に動いているのは、推定器としては確率的な推定器も許しているからです。
堀井：今のは、推定は一つの頂点だけ？
松田：そうです。それも仮定しています。一つの頂点から始まっている。ちなみに、複数の頂点から始まるというのも研究としてはあったりします。けど、そこまで話してると時間がなくなるので、今は噂は一つの頂点から始まっているとしています。
推定法としては何がいいかというと、最尤推定が一番いい。どの頂点が噂の発信源になるかという事前情報は一切持っていません。ということは、要はどの頂点も同様に確からしいわけです。どれも発信源になりやすいと。そうしたらやることは最尤推定しかないです。実際、これがさっきの推定成功率を最小にする方法だっていうことが証明できます。
最尤推定をどうするかというと、Gnっていうのが得られたとすると、頂点vから始まってこのGnっていうのを得られる確率を最大化する頂点を出力するわけです。つまり、最もGnになりやすい出発地というのを出力すると。ただしこれを最大化するような頂点がいっぱいあったら、どれかを等確率で選びます。
ただ、最尤推定って一般には困難ですね。こういう確率を計算するのってすごく困難で、だからそのあたりをどうやってうまく計算していくかっていうのが重要になってくるわけです。
ちなみに、この2人が最近、噂の発信源の特定問題というのを理論的に研究した人たちです。
最尤推定するにはPnの計算をどうするかというのが重要になってきます。これは一般には難しいんで、特別な場合を今度は見ていこうと。いろんなネットワークに対する推定法と推定成功率というのを見ていくことにします。
ちょっと定義が続きますけど、基本的な定義はここに書いておきました。NというのがvのNeighborで、vに隣接する頂点の集合。
Bというのが頂点集合のBoundaryなので、Vという頂点の集合に隣接する頂点の集合。
この後でまた例をお見せしますけど、Pn(v1)っていうのは、v1っていう噂の発信源から始まって、この伝播の順番にn個の頂点を並べた集合になっています。これは後の例を見たほうが早いので、ちょっと例をお見せします。
Pn(v1,Gn)って書いたら、Gnを構成するのと同じ頂点集合で構成される列の集合とします。
ちょっと例を見ていきます。
Nというのは隣接する頂点の集合なので、例えばN(1)というのは頂点1にすぐ隣接するような頂点の集合なので、N(1)というのは2、3、4、こことこことここの集合になります。B({1, 2})と書いたら、この1と2っていう2つの頂点の集合に隣接する頂点の集合なので、今、ここに隣接する頂点は3と4と5と6なので、3、4、5、6になります。
P2（2）というのがちょっと厄介で、これは2という頂点から噂の伝播が始まって、頂点数が2になるような伝播を表す列の集合です。だから2から始まって頂点数が2の伝播っていうのは、2から始まって1になるもの、2から始まって5になるもの、2から始まって6になるもの、この3つしかないです。2から3に飛ぶことはないですね。2から3に飛ぶと、2に行って1に行って3に行かなきゃいけないんで、頂点数は3つになります。それがこっちに入ってきます。
頂点数を今度3にすると、2から始まって1に行って4に行くパターンと、2から始まって1に行って3。で、2から始まって1に行って今度は5に行くパターンがある。2から始まって1に行って6。全部で8パターンあります。
ここにGnっていうのが付いたら、今言った8パターンの中でこのGnを構成するような頂点列の集合になります。だから、これを構成する頂点って2、5、6なので、この中で2、5、6だけで構成されるのはこれとこれだけなので、これがこういう2つの列の集合になります。ちょっと話が込み入ってきたので、分からなかったら聞いてください。
最初の特別なネットワークとして、レギュラーツリーっていうのを考えます。ちょっと説明しますけど、これ、連結で閉路を含まない、全ての頂点が同じ次数を持つネットワークになっています。次数が全部同じじゃなかったら、「木」って呼ばれているネットワークになります。
レギュラーツリーっていうやつが一番基本的なんですけど、一番重要です。何でかというと、今のところ、これに対してしか解析的な結果がほとんど出ていないからです。これぐらい構造を持っていないと、やっぱり難しいわけです。それ以外のネットワークは、何か推定法を作ってシミュレーションするっていうことぐらいしか今のところはできていないです。
レギュラーツリーに対する推定法を今度は見ていきます。構造があると、さっきの最尤推定ってそれなりに簡単にできます。そのためには、Pnとかいう確率を計算していかなきゃいけないんですけど。これ、何時まででしたっけ？
司会：19時15分とか、15分過ぎぐらいまでだよね。
松田：はい、分かりました。数式を載せすぎた感があるんで申し訳ないです。
Viっていうのをi番目に噂が伝播した頂点を表す確率変数としておきます。そうすると、V1がv1になる確率は1です。これは発信源になっているので。次に問題になるのは、V1っていうのが噂の発信源として、次に感染する頂点の確率、これがこの後の肝になっていくんですけど、これはどうなるのかというと、この感染の次に起こる伝播というのは、ここの青い3つの頂点のどれかに移るわけです。その2つ目に感染する頂点の確率っていうのは、例えばv2に感染する確率っていうのは、こういう確率で書けます。v1からv2に伝わるこの時刻τ(v1,v2)というのが他の2つの時刻よりも小っちゃければ、次に選ばれるのがv2になるわけです。だから、この3つの時刻の中での最小の値がτ(v1,v2)になっている確率を計算すればいいと。
これを計算するとこうなります。この場合、v1の隣接する頂点の個数で1を割ればいいわけです。つまりv1が発信源だとすると、次の瞬間にどれかの頂点に移る確率というのは全部一様に3分の1になります。これがレギュラーツリーにおいて計算を簡単にする要因になってきます。こういう確率が、簡単なこんな確率になると。レギュラーツリーだけでなくて一般の木においてもこれは成り立ちます、ループがないので。
一般に、次に伝播する確率というのはその境界の頂点数分の1になります。例えばv2が感染したとすると、次に感染する頂点がv5である確率というのは4分の1です。v6である確率も4分の1だし、これになる確率も4分の1と、全部等確率で次の瞬間に選ばれることになります。
司会：うん、そうだね。この状態から次の……
松田：v3として……
司会：v3に行くのが4分の1なんですか？
松田：そうですね。
司会：その前の状況で3分の1に近い所にいるけれども、4分の1なんですか。
松田：そうです。指数分布って無記憶性があって……
司会：そうか、そうか。前を引きずらないわけだ。
松田：そうなんです。だから、小っちゃい文字で申し訳ないですけど、τっていうのが指数分布に従う確率変数だったとすると、τがs秒より大きいという条件の下で、s+tよりも大きくなる確率というのは、tよりも大きい確率と同じになるという、前に感染していなかったっていう状況が関係なくなるという無記憶性があります。
司会：次っていうふうにおっしゃっているのは、よく分かんないけど、v1からv2に移った後、またっていう話になるんですよね。
松田：そうですね。
司会：なるほど。つまり、ちゃんと区切られてるわけですね。
松田：そうです。
司会：時間が区切られてる。
松田：時間がないんです、ここには。つまり、言ってしまえば時間全てで周辺化しているような感じなんですけど、何番目に感染したものがこれだという確率を出すときには時間は関係なくなっちゃいます。
司会：なるほど。
松田：時間っていうのは今回の問題では関係ないんです。感染している頂点がどれかというのだけしか分からなくて、噂が感染し始めて何秒後かっていうのは一切分からないわけです、こっちは。
司会：なるほど、そうか、そうか。移る可能性がある。
松田：移る可能性です。
司会：なんかv3の人は近くに感染している人がいて、「俺の確率は3分の1だったのに、1人に移ったら4分の1になったぜい」とか、そう聞こえますけど。そういうわけじゃないの？
松田：そういうわけ……
司会：そういうことですよね。
松田：そういうわけなんですけど、確かにそう聞こえちゃいますね。
堀井：長い目で見たらば確率でいったら3分の1足す4分の1になるだろうし、にはなってるんじゃない？
松田：そうです、そうです。だから条件付き確率になっちゃってるんで、1個前にv1とv2は感染しているという条件の下で4分の1になっているだけで、3分の1掛ける4分の1みたいになっていくと。
司会：分かりました。
松田：そんな感じでですね、この確率っていうのは要はBの頂点数を数え上げれば計算できることになります。
数式ばっかりで申し訳ないですけど、これを木だとして、δ(v)っていうのは、各頂点の次数だとします。最初の噂の発信源に隣り合っている頂点集合の個数っていうのは、次数そのものです。v1に隣り合っている頂点っていうのはこの3つなので、例えば今だったら次数3なのでここは3になると。
B({v1,v2})っていう2つの頂点集合の境界部分の個数というのは、こんな感じになります。例えば、この例だとv1とv2が感染していたとすると、この2つの頂点の境界っていうのはこの4つの頂点になります。実際、これを計算すると4になるんですけど、これはなんでこうなるかというと、この個数というのは1個前に噂に感染する可能性のある人たちの集合の個数です。そこからマイナス1しています。これは、噂に感染すると噂に感染する可能性がなくなって、感染しちゃったらその可能性がなくなるのでマイナス1。その代わりに、次に噂に感染する可能性のある人たちが（δ-1）個、付け加わります。なので、ここにプラスするわけです。
整理するとこういう値になります。一般には、最初に噂の発信源になる頂点の次数、足す、感染していく頂点の次数から2を引いた値になります。
それで、結局、Pnを計算したかったわけです。この確率というのは、要はGnを構成できる頂点列が得られる確率です。頂点列V^nの中にGnの頂点が含まれれば、最終的にはGnが観測されるわけです。なので、Gnを構成するような頂点列の確率を全部足し合わせればいいわけです。先ほどの結果から、これはこういう確率になりました。この個数はこうなります。なので、この確率というのは結局こういう確率になります。これは今、簡単のためにpと書いておきます。
そうやってようやく戻ってくるんですけど、レギュラーツリーの……
Ａ：今の置き換えたときのVのnって……
松田：ごめんなさい。V^ｎ、これは書いておきましょう。A^nって書いたら、こういう添字が付いた列A^n=(A1,A2,...,An)だと思ってください。
V^nは、V1から次々伝染していってる列になります。
松田：それで、結局やりたかったのは、これをどうやって計算すればいいのかという話でした。レギュラーツリーの場合は実は簡単に計算できて、これはこういう確率になったわけです。今、レギュラーツリーなので、次数は全部同じでδとしておきます。
そうすると、結局、この推定っていうのは、ここのvに依存するこの項P(v,Gn)の要素数が最大になるものを返しなさいという問題に変わります。これを今、Rとしておきます。このRというのはこの要素数そのままなんですけど、これを返すのがレギュラーツリーにおける最適な推定法です。
この頂点数Rというのはメッセージパッシングアルゴリズムで計算可能というのが分かっています。この辺をちょっと説明したかったんですけども、時間に限りがあるので説明しません。とにかくオーダーnで計算することが実はできます。というのを、彼らShahとZamanが示したわけです。これはこれで一つのインパクトがあったわけですね。
これを使えばシミュレーションできるわけです。ですけど、実は真の推定成功率っていうのが、このレギュラーツリーの場合は分かっています。
真の推定成功率は最近、Dongらが出したんですけど、最尤推定をφMLと今、書いておきましょう。そうすると、どんなv1に対しても推定成功率がこんな値になるっていうのが分かっています。
グラフを描いてみると、こういう感じになります。レギュラーツリーは次数が全部同じなんですけど、その全ての次数が2になるようなもの、つまり、直線ですけど、その場合の推定成功率が青い線です。この横軸のnというのが噂を知っている人の個数です。縦軸が推定成功率で、噂の発信源を特定できる確率。結構残念なんですけど、急峻に一気に下がります。nが10ぐらいで、例えばδ2だったら20パーセントぐらいです。発信源というのはだいたい20パーセントぐらいでしか、その場合は推定できない。δが3になるとグンと上がって、4、5というふうに上がっていきます。上にちょっとずつ上がっていきます。だけど、せいぜい30パーセントぐらいですね。
これ、収束しているように見えるんですけど、実際、収束します。
収束すると、こんな値になります。δ2の場合は実は0に収束します。だから、早めに発信源を推定し始めないといけないわけですけど、急峻に下がるのでそういうわけにもいかず、ちょっと厄介です。オーダーとしては√n分の1で下がることがわかっています。
δ3以上だと、0にはなりません。こんな値に収束します。だけど収束する速さがやっぱり速いので、ちょっと厄介です。
この辺の細かい数式はどうでもいいです。こういう式になると。
グラフにするとこんな感じになっていて、横軸が次数で、縦軸がさっきの推定成功率の極限です。そうすると、次数を上げると推定成功率は上がっていくんですけど、それも実は収束して30パーセントぐらいになります。だからどんなに頑張っても推定成功率は30パーセントぐらいにしかなりません。
次に、一般の場合を見ていきます。レギュラーツリーは簡単なのでいろいろ解析結果が出ているんですけど、一般の木の場合はレギュラーツリーほど簡単に計算できなくなります。なので、こういう推定を使います。
さっきのこのRという値に、前に定義したpっていうのを掛けたものを推定器として定義します。このvBFSっていうのは、vから始まって幅優先で広がっていって、最終的にGnになる頂点列です。
これはちょっと分かりにくいんですけど、こういう赤い点の集まりがGn、観測された噂のグラフだったとしましょう。今、3つ例を用意したんですけど、vというのを例えばこの1stと書いてある――見えないかもしれないですけど――1と書いてある所の頂点から噂が始まったと仮定しましょう。そうすると、そこから幅優先で広がってGnになる頂点の列なので、1stに行って2ndに行って3rdに、要は隣接する近場のノードに先に感染させて、その次の距離のノードに感染すると。
例えばここがvだったとすると、1stから2ndに行って、次にこっちに移って4thになる。こうやって幅優先で広がって、最終的にこういう頂点列が得られるような図です。
そういう列が得られる確率をここに掛けておきます。この推定の気持ちとしては、最尤推定できないので、あとは気持ちで勝負するしかないわけです。気持ちとしては、起こりやすい順序っていうのは幅優先であろうと。近場のやつからどんどん感染していきますと。
このRというのはこのP(v,Gn)の要素数そのものだったんですけど、このP(v,Gn)に入っている頂点列が起こる確率の主要な部分というのはほとんど同じ確率だろうと。対数の法則みたいな感じで、出てくる例というのは典型的なもので、それは全部、等確率で出てくるというような気持ちです。そうすると、こういう幅優先という一番起こりやすい列が出てくる確率がpになっていて、その起こりやすい確率というのが主要なので、それをR個足すと、この推定で使う値になります。ということで、この値が大きければ大きいほど、vっていうのが発信源の可能性が高いんだという気持ちがこもった推定法になっています。
一般のグラフだと、最尤推定ってほとんどの場合、無理なので、もっと簡単に計算する方法を使います。どうするかというと、一般でも木として見ましょうというわけです。
こういう推定をします。こういうTBFSっていうグラフに対するRを計算して、そこにさっきの幅優先の確率pを掛けます。これが何かというと、vから始まる幅優先の探索で得られるGn内の木です。
例えばこういうグラフが観測されたとします。これは木じゃなくて、ループが入ってるんですけど。例えば今ここから噂が始まったと仮定します。そうしたら、ここから幅優先で得られる木っていうのは、ここから始まって、次に幅優先でこれが選ばれて、こことここの間に辺が生まれると。この次にこれが選ばれて、この辺が次に生まれると。次にこれが選ばれるので、この辺が生まれる。そんな感じで、選ばれたものの間に辺を通していくと木ができます。
この推定の気持ちとしては、噂を素早く広げるのは木の構造であろうと。要は、噂をすでに知っている人にはループを経由して伝えるというロスはしませんという気持ちです。噂を知らない人に対してとにかく素早く噂を広げていく広がり方が最も起こりやすいだろうということです。あとは木の場合の気持ちと一緒です。
これでシミュレーションができます。彼らShahとZamanはいろんなネットワークでシミュレーションしていて、いわゆるスモールワールド・ネットワークとかスケールフリー・ネットワークとか、そういう現実世界によく似た人工的なネットワークに対してもシミュレーションしています。それがどうなるかというと、スモールワールド・ネットワークに対しては推定成功率というのは2パーセントです。
スモールワールド・ネットワークって、一応簡単に説明しますと、「六次の隔たり」というのがあって、知り合いを6人通じれば世界中の誰にでも会えると。そういうのを体現したネットワークです。つまり、頂点間の平均距離というのがすごく小っちゃくて、この頂点からこの頂点にたどり着くまでのステップ数、距離というのがすごい小っちゃいネットワークです。かつ、クラスタ性というのがあって、自分から出て誰かを通じて戻ってくるような三角形の関係っていうのがこの中にいっぱい含まれているようなネットワークです。平均距離が短くて三角形の関係がいっぱいあるようなネットワークというのを、スモールワールド・ネットワークというふうに呼んでいます。これは現実世界の人間関係を人工的につくり出したネットワークとして有名です。だから伝染病のネットワークモデルとして使われたりします。
それで、どういうシミュレーションを行ったかというと、5,000個の頂点で構成されるスモールワールド・ネットワークのうち、400個の頂点に感染させて発信源を特定できたかできなかったかを見ます。これを何回も行なって噂の発信源を特定できる頻度を計算するわけです。それでその頻度が2パーセントというわけです。
次の人工的なネットワークとしてスケールフリーというのがあります。これは、要するにインターネットです。インターネットのネットワークを人工的につくったネットワークになっていて、次数の分布が「ベキ乗則」に従っているという性質があります。こういうグラフの中に含まれている頂点の次数の割合を、次数が低いものから並べていくとベキ関数的に減少していくような、そういう規則が得られるネットワークです。これに対してはだいたい5パーセントぐらいになります。
素朴な感想としては、推定成功率が低いですよね。だから、この論文を最初読んだ時は、「何の役に立つのかさっぱり分からない」というのが感想でした。低いですからね。「2パーセントで推定が成功できます」と言われても、「そんなの、たぶん誰も使わない」というのが素朴な感想でした、最初は。
司会：すみません。確認なんですけど、2パーセントとか5パーセントっていうのは、要はいわゆる100回試して、2回しか当たらないっていう感覚ですよね。
松田：はい。ただ、あくまでシミュレーションです。最尤推定でもないので、もっと良くなるかもしれないんですけど、少なくとも木のグラフに関してはあれ以上改善できません。最尤推定していて、しかも急峻に下がっちゃうので、ほとんど30パーセントとかぐらいしか推定成功できないです。推定成功率が低いから、なんか意味がないような気がするわけです。
そういうわけで、私が行った研究につながっていきます。推定成功率が低いままだと、この分野、噂の発信源特定問題っていうのは無意味なものになってしまいます。別にそれはそれでいいんですけど、ただ、せっかく興味を持ったのでもうちょっと意味のあることができたらいいなと思ったわけです。ということで、ちょっと視点変えて、今度は距離というのを考えてみましょうという話に移ります。
実は推定値は、割と発信源に近いことが実験的には知られています。
ShahとZaman以降、発信源推定問題について色々と研究されているんですけど、推定成功率そのものを評価する人ってあまりいなくて、それはさっきも述べたように推定成功率が低いからでしょう。それで、こういう推定値と発信源との距離を相手にしている人が結構います。「私の考えた推定法だと発信源に近い所を選んでます」というふうに論文を構成するわけです。ただそれらは、実験的、シミュレーションによる成果がほとんどです。
距離というのは、2頂点を結ぶ最短経路の辺の数です。この図は推定器が発信源に近い頂点を選んでいることを示すイメージ図です。横軸は推定値から発信源までの距離です。縦軸はその距離の頂点を推定値として出力する確率です。距離0っていうのは発信源を特定できたことを意味しています。この距離0の所の確率が推定成功率で、これが低かったわけです。実験的には、シミュレーションの結果を見てみるとだいたいこういう山なりの確率になっていて、距離1とか2ぐらいの所が選ばれる確率が高いです。
さっきのイメージ図からもわかるように、発信源ってピンポイントで特定するのは難しいんですけど、推定器は発信源に近いところを選んでいるようなので、その事実を利用すれば高い確率で発信源を絞り込むことはできそうです。つまり、「推定器の選んだ頂点から距離いくつ以内に発信源があります」という絞り込みが可能なわけです。そういうことが高い確率で可能であれば、色々と利用価値がありそうです。だけど、その事実は実験的にしかわかっていないので、具体的にどの程度近くを選んでいるのかとか、どんな分布になっているのかというのはよく分かってませんでした。だから絞り込もうにも、推定した頂点からどの程度の距離まで絞り込めばいいのかよくわからないわけです。
この解析を一般のネットワークでやると、やっぱり難しいです。手を出せるのはレギュラーツリーぐらいしかない。じゃあ、レギュラーツリーで解析しましょうというのが去年の私の研究だったわけです。時間がなくなってきたので、たぶん結果だけを述べることになります。
噂の発信源と推定値との間の距離の分布関数をこういう記号Dnで書いておきます。さっきの山なりの関数を表すのがこのDnです。
Dnを定義するとこんな感じになっていて、Vハットは最尤推定で選ばれた頂点になっています。これは距離dの頂点の集合です。つまり、最尤推定で選ばれた頂点がこの頂点のいずれかである確率として、距離の確率が定義されます。これはちょっと言ってなかったんですけど、レギュラーツリーだと距離dの頂点というのは、「δ×（δ-1）のd-1乗」個、存在します。定義から、距離が0のときには最尤推定したときの推定成功率になります。
以下で、スターリングナンバー（Stirling number）というのを使います。スターリングナンバーってこういう定義なんですけど、「符号なし」だとこういう定義になっています。上昇階乗べきというのがあって、これを多項式に分解したときに出てくる係数の値、これがスターリングナンバーです。要は二項係数の親戚みたいなものです。この係数が符号なし第1種スターリングナンバーといわれています。
「符号あり」と書いてあるこれは、ここの値に-1の（k-l）乗したものです。これは、上昇階乗じゃなくて下降階乗べきの係数になります。
これを使うと、こういう結果が得られます。δが３の場合には距離分布はこういう形になります。もっと簡単に表せるかもしれないんですけど、とりあえずこんな式になります。
噂を知っている人の数nが奇数のときにはこう書けます。ここにスターリングナンバーが出てきますけど、こういう確率で書けます。噂を知っている人の数が偶数のときにはこんな感じになります。
グラフを描くと、こうなります。横軸が噂を知っている人たちの人数、縦が距離の確率になっています。dが０というのは推定成功率ですけど、これは急峻に下がって30パーセントぐらいになっています。その一方で、距離が1、つまり隣接するノードを選ぶ確率っていうのは割と高くて、40パーセント以上の確率でこの頂点を選ぶと。距離が2のノードを選ぶ確率はこうなる。距離3のノードを選ぶ確率はこうだと。4、5というふうにだんだん下がっていきます。
次に、極限を考えます。極限をとると、こういう式になります。今度は閉じた式になってくれます。
これを描くと、こういう山なりの分布になります。ちゃんとさっき述べたイメージ図のような形になりました。
累積分布を見ると、こんな感じになっていて、距離3ぐらいまで足すと、96パーセントぐらい。つまり、推定した頂点のだいたい距離3以内に高い確率で発信源があるといえるわけです。
堀井：だいたい22人ぐらいに絞り込めるの？
松田：そのぐらいになります。
Ａ：さっきの2個前のグラフは、これで縦に足せば1になるんですか。
松田：そうだと思います。これは1にならなかったら間違ってるんで、そうですね、足すと１になりそうです。ちょっと今は見ないことにしましょう。
δが3のときはこうですけど、δが４以上だと等式として書くことはできなくなってきます。極限を考えますけど、下界と上界しか出ていません。下界を今、fって書いておきます。距離分布の極限とこのfとの差っていうのが0以上で、この値以下になっています。なので、fは下界ですね。fはこんな値になります。その中でシフトされた多重ゼータ関数の部分和が出てきます。これ自身も結構面白くて、いろいろ調べてるうちに時間が過ぎていったんですけど。多重ゼータ関数、それ単独でも結構研究されていて、これの振る舞いとか収束する速さなんかが研究されています。
それで、このfというのは次数と距離と、あとmに依存して決まります。mっていうのは自然数なら何でもいいです。mを大きくすると、この下界がどんどんタイトになっていきます。mが35ぐらいで、下界は十分に厳密になります。
これは、δが6のときのfのグラフです。δ6のときにはこうなると。
累積分布を見るとこんな感じになっていて、距離3以内に入っている確率っていうのはやっぱり非常に高い。98パーセントぐらいになるということが分かります。どんな場合でも距離が3以内に発信源がある確率が非常に高いです。
定理の証明は飛ばします。ちょっと時間が無いので。
あとは関連するその他の話題というのがいくつかあります。それをざっと説明していきます。
まず、発信源となる頂点が絞られている場合の解析っていうのがやられています。この講演では、最初のほうで説明したように、感染している人は全員、等しく発信源になりやすいという立場に立っていました。ここでは発信源になり得る人が絞られているという仮定をおいていて、例えば、噂がある2人の内のどちらかから始まるということは事前に知っているとして、推定成功率ってどうなるのかというのを検討しています。発信源になる人たちの頂点が隣り合っているか隣り合っていないかでちょっと解析が変わるんで、その辺の場合分けをして解析しています。彼らもやっぱりレギュラーツリーを中心に解析しています。それで、「Polyaの壺」を使って解析を行なっています。
今回の伝播のモデルは、噂を知ったら二度と忘れることはなくて、ずっと噂をまき散らすというモデルだったんですけど、そうじゃなくてSIRというモデルを考えたときの解析っていうのもやられています。SIRって何かというと、これがおそらく一番、伝染病のモデルで使われやすいと思うんですけど、さっきのSIにRecoveredという状態をプラスしたものです。つまり、噂を知っているノードというのが、ある一定の確率で噂を口にすることをやめて、もう二度とその噂には興味を示さないという状態を加えます。伝染病の文脈で言うと、回復して抗体ができたという状況です。そういう場合の推定成功率というのを解析しています。
「観測したネットワーク」っていうのは、要するに噂のグラフのことですけど、これは噂を知っているか知っていないかという0、1の2状態のグラフと考えることができます。その2状態のグラフになるような状態遷移っていうのを考えてみましょうと。最初に噂の発信源があって、次に今までやってきたように隣の頂点が1になってというふうに。ただし、これまでと違って、リカバーするという状態が加わっています。そういう遷移をいろいろと辿った結果、観測したグラフになる一番起こりやすい状態遷移を持ってきたときの始点を発信源とする推定法というのがあります。それをSample-path-based detectionと彼ら、ZhuとYingは呼んでるんですけど、そういうのがあって。レギュラーツリーを始めとして、スモールワールドとかスケールフリーとか、いくつかのネットワークに対するシミュレーションを彼らは行なっています。
噂の発信源が複数ある場合ってさっき言いましたけど、その場合の解析もされています。この講演では噂の発信源が1個だったんですけど、もっといっぱい、2個とか3個あるときに、何個発信源があるのかと、それらがどこにあるのか、その2つを推定する問題が研究されています。
この問題に対しては、MDL原理に基づいた推定法というのが提案されています。MDL原理は情報理論の人たちにとっては割とメジャーなんですけど、ざっくり言うと、ある観測された噂のグラフを記述するために必要なビット数を最小にする頂点数が最も良いという原理です。それを線形オーダーで計算する推定法が提案されている。シミュレーションによると、噂の発信源の個数は正確に当てることができるらしいです。ただ、やっぱり、発信源がどこにあるのかを当てることは難しいようです。
噂のグラフは今回１回しか得られなかったんですけど、それが何回も得られる場合というのも解析されています。犯人が何回も噂を流すんです。その結果が何回も得られると。レギュラーツリーの場合は、実は噂のグラフが得られる回数が増えていくと推定成功率が1に収束していきます。Lが2以上なら、噂のグラフが２回得られるんだったら、次数を無限大すれば推定成功率は1に漸近します。
あとは、部分的にしか噂を知っている頂点が報告されない場合の解析があります。噂を知っていても噂を知っていると報告しない人がいる場合にどうなるのかというわけです。これはさっきのSIRのモデルとほとんど一緒で、要は感染したけど回復しちゃって感染していないと報告することと、感染してるけど感染していないと報告することっていうのはほとんど一緒なので、この場合にも Sample-path-based detection を使います。それを使って、レギュラーツリーの場合には線形オーダーの計算量で推定できることを示しています。
ということでまとめます。
噂の発信源が特定できると、駆除とか隔離とか除去というのが可能です。一般には最尤推定することが難しいんですけど、レギュラーツリーに対しては簡単に計算できました。一般のグラフでも木のように伝播したと見れば、簡単に推定できます。発信源と推定値って実は近くて、だいたい推定値から距離3以内の所に高い確率で発信源があります。これをレギュラーツリーの場合には解析的に特徴づけましたと。その他いろいろな問題がありますということです。以上です。
質疑
司会：どうもありがとうございました。何か最初のほうから質問とかご意見あればお願いします。
堀井：これって、従来研究は業界としてはどの辺が知られてるんですか。
松田：多岐にわたっていて、医学系の人たちは伝染病という形でやっていますし、計算機の人たちはコンピューターウイルスという形でやってたりして、どこかって言われるとちょっと難しいです。複雑ネットワークの人たちもこういうことをやっていますし、あとはプロトコルを研究する人たちも似たようなことをやってたり。もちろん情報理論の人たちも研究しています。ただ、情報の伝播モデルを扱う人が多いのは、複雑ネットワークの分野かなと思います。それでも、発信源を特定するという研究は私自身は見たことが無いです。
司会：お願いします。
Ａ：噂があって、それが広がっていくモデルじゃないですか。それの発信源だから、どっちかというと逆問題の立場から見ないといけないかなと思っていて。逆問題だと、しかも離散的なんで、NP-hardな話になっちゃうんじゃないかなってちょっと思って。素人考えですけど。でもツリーの形を仮定しさえすれば、うまいこといけるときがあるという理解でよろしいですか。
松田：そうです、そうですね。ただ、NP-hardかどうかはちょっと分からないです。少なくともレギュラーツリーのときには簡単に最尤推定ができるということしか今は知られていないです。他のネットワークでうまくいくのかはちょっとよく分かんない。
Ａ：そっちの構造が結構限定されてきちゃうところが結構つらいところですね。
松田：そうですね。つらいですね。レギュラーツリーって現実的にはたぶんほとんどないんですけど、噂の発信源特定問題に限れば、レギュラーツリーで見られるような現象が他のスモールワールドとかそういうネットワークでも見られるので、レギュラーツリーを相手にしたらだいたい他のネットワークでも同じようなことがいえるんじゃないかという感じですね。
Ａ：確率2パーセントは、やっぱりそれなりに……
松田：きついです。推定成功率そのものには手を着けてはだめだと思います。相手にするのは距離だと思うんです。発信源を特定するのはたぶん無理だと思います。ネットワークの構造にもよるので絶対とはいいませんが。
Ａ：ありがとうございます。
司会：距離だとすると、さっきのスモールワールドみたいなやつはやっぱり情報がゴチャゴチャしちゃうっていうか……
松田：シミュレーションしてみると、あれもレギュラーツリーの場合と同じような分布になります。
司会：なることはなるんですか。
松田：シミュレーションではだいたい距離としては4以内に収まることが分かっています。近くを選んでるっちゃあ選んでます。
司会：他にございますか。
Ａ：こういう研究を実用に応用するような発表なんかは、もっとやっている人はいないですか。
松田：そうですね。私が知らないだけの可能性は高いですが、あまり見かけないですね。ただ、感染源を見つけたいとか、ニーズはいくらでも作れると思います。さっき言ったページランクを付けるのに使ったりとか、どのノードが脆弱かっていうのを調べたりとか。金融関係だったら、投資に使えるのかなという気はしますけど、具体的にアプリケーションがあるかというのはちょっと分かんないですね。いろいろ考えられると思いますけど。そもそも今まで発信源というのがあまり注目されてこなかった気がします。
司会：論文が割と最近のがパンパンパンと出てる感じでしたけど。
松田：割と最近になって多く出始めたみたいです。昔からちょくちょくあったようですけど。
Ｂ：すみません。松田さんがこの辺の分野で今後やっていきたいなって考えていることはございますか。
松田：この辺の分野だと、あとはもうちょっと、レギュラーツリーじゃない別の構造のあるネットワークに対して、何か解析的な結果が出ればなあというふうに考えていますね。あまりシミュレーションに対する素養がないので、興味あるのが解析的な手法になっちゃって……。
堀井：シミュレーションとその解析の間で数値計算で求められるようなものはあるような気がするんですけど。
松田：そうですね。その辺もいい気がしますね、確かに。人間では無理だけど、ある程度高い精度で近似できてとか、そういうのはできる可能性はありますね。
今回のこの問題はどちらかというと組み合わせ論的な話がいっぱい出てきたんで、スターリングナンバーとか、あとは多重ゼータ関数とか。こういうのが出てきた時はすごい面白かったですね。噂の発信源を探るとかいう目的は置いといて、数式自身が面白くなってきて、興味としてはこういう組み合わせ的な解析にあります。そういう話が他のネットワークでもできればいいなという気はしますね。
司会：解析的に出るのは面白いですよね、やっぱり。
松田：そうなんですよね。ただ、現実的なネットワークになると、シミュレーションでやるしかないのかなという気はしますね。
司会：そうかもしれないですね。
松田：ちょっとやってみないと分かんないですけど。
司会：他にございますか。
Ａ：シミュレーション結果のいろんな蓄積を生かして、何かの事件で捜査を撹乱できるようなプロファイルみたいなのができるかもと……
司会：できるかもしれない。
Ａ：そういう手法は完成されていない？ こういうふうに伝えていくと発見しづらいとか。
司会：確かにそうかもしれない。
松田：そうですね。発信源を特定しようとする人が、さっきのSIモデルとかそういう正しい感染源のモデルに従っていると仮定して発信源を推定しようとしていたとすると、噂を知っている人のネットワークの端っこにいるときが一番捕まりにくいですね。だから、なるべく周りに噂を知っている人を増やさないこと。いたとしても1人しか自分の周りにはいないときには、たぶん一番見つかりにくいと思います。
Ａ：街中で、そういうことがそもそもできるかは、ちょっと……
松田：そうですね。
司会：確かに。
松田：秘密を教えるのは1人だけ。それ以外には言っちゃダメっていうのが一番分かりにくいです。
堀井：おしゃべりな友達1人だけに言ってバイバイって。
松田：それがたぶん一番いいかもしれないですね。そうですね。ただ、その人が怪しいとなると自分も疑われるので。距離として4つ以上離れた人がおしゃべりだったら、たぶん一番いいかなと。
司会：だけど、ウイルスとかは、そういう意味じゃあ分かんないけど、「踏んで、踏んで」っていうじゃないですか。どこかの国のコンピューターを踏んで、そこからまたこっちのコンピューターを踏んでって。
松田：最初に4つウイルスに感染させておいてから広げる。
司会：なるほど。「なるほど」とか言っちゃいけないですね。そうですか、面白いですね。
では、そろそろ時間になりましたので、もしこの後お時間があれば、何か質問していただければと思います。どうもありがとうございました。
松田：ありがとうございました。（拍手）