JST ERATO

河原林巨大グラフプロジェクト

Newsletter 2
Kawarabayashi Large Graph ProjectAugust2015vol.

Momentum

研究総括より− Real Madrid と Barcelona のフィナーレ ―研究総括

河原林 健一Momentumは日本語でも英語でも、スポーツの試合中によく使われる（日本語訳は「勢い」）。Momentumが試合の勝敗に直結した例を、我々は数多く目撃している。ただしMomentumだけでは長いシーズンを戦えないことも、我々は何 度も見てきた。Real MadridとBarcelona の世 界 2 大サッカークラブは、今シーズンMomentumであった時期を共に過ごした。しかし両チームが迎えたシーズンフィナーレは、あまりにも対照的なものになってしまった（注釈 1）。
情報分野も現在 Momentumである時期を過ごしているといえるだろう。
「Big Data」「人工知能」という社会にも浸透しているキャッチーなキーワードのもと、学術界、産業界それから政府が多額の投資を行い、産学官連携を促進し、世界をリードする研究開発を目指している（注釈 2）。したがって情報系の研究者、技術者は、現在 Momentumである時期を過ごし、比較的恵まれた研究環境にある。本プロジェクトもその一つであるといえるだろう。
本プロジェクトも、別の意味でMomentum の時期を過ごない時代でも生き残り、研究業績を挙げてきた。若手研究そうとしている。本プロジェクトの研究総括に決まった直後か者、技術者にはMomentumでない時期でも研究成果を挙げら、このプロジェクトの命運を若手研究者に託そうと考えた。

られる「基 礎 力」と「技 術」を、Momentum の 時 期である

したがって本プロジェクトでは、なるべく若手研究者に「投「今」、身につけてほしいと思う。Barcelonaは、シーズン当資」しようと決めた。そして発足 3 年目現在、20 代、30 代

初にはいくつか問題を抱えていたが、それを乗り越え3 冠を達前半の多くの若手研究者が、国際的に評価される研究成成した。情報分野全体も今後多くの困難が待ち受けている果を挙げてきている。本プロジェクトは、若手研究者がけんと思うが、「基礎力」と「技術」を身につけている研究者、技引する活気のある研究センターになりつつある。

術者が多ければ、いつの時代も乗り越えられるのではないか

しかしこの Momentumは永遠には続かない。本プロジェ
クトもあと3 年弱で終わりを迎える。現在の「Momentum」をどのように未来につなげるかが、本プロジェクトの今後の課題であろう。Barcelona のようなフィナーレを迎えればいいのだが。
情報分野全体のMomentumはどうかといえば、これも永遠には続かないだろう。現在の情報分野を作ってきた「大御所」たちは、確かな基礎研究能力と技術によって、Momentumでと思う。
注釈 1：Real Madridは、2014 年の 10月から年末にかけて、クラブ史上最多連勝記録である公式戦 22 連勝を達成。クラブ史上最強チームと評された時期もあった。しかし2015 年に入り失速。
2015 年 にはタイトルを一 つも 取 れずにシーズンを終えた。
Barcelonaは、クラブ史上 2 回目の「3 冠」を達成。2015 年のヨーロッパを席巻した。
注釈 2：このMomentumは、日本のみならず世界的な潮流である。
Google、Facebook等も人工知能研究に多額の投資を行っている。

研究紹介

最適なネットワークを求めてグラフ・ネットワークにおける理論と最適化グループ

福永 拓郎

Takuro Fukunaga

国立情報学研究所特任准教授

先日、ミュージカルを見に行ったときのことです。上演前の席に着いたときには使えていた携帯電話が、1 幕と2 幕の休憩中に圏外になっていることに気付きました。
後で調べてみると、その劇場では電波を妨害する装置で上演中は携帯電話がつながらないようにしているそうです。
私の研究テーマはネットワークの最適化です。特に、なるべくネットワークから切り離されてしまう人がいないように、ネットワークの形状を最適化する問題について取り組んでいます。私が体験した劇場での出来事のように、携帯電話の近くで妨害電波を出されてしまってはどうしようもないのですが、通信ネットワークのどこかのケーブルが不意に切断してしまってもなるべく通信が途切れないようにするにはどのようなネットワークがよいのかといった点について、数理最適化のアプローチから取り組んでいます。最近は無線ネットワークの研究にも取り組んでいて、通信機器が発信する信号の強さをどれぐらいにすれば良いネットワークになるかといった問題について、いくつかの成果を挙げています。右下の絵は、私が開発したアルゴリズムで構築した、故障に強い無線バックボーンネットワークを表しています。
これまでの私の研究では通信ネットワークを想定していることが多かったのですが、これからはソーシャルネットワークなど他のネットワークの最適化もやってみたいなと思っています。例えば、人 間 関 係が 円滑にいくようにネットワークを最適化するというのも、面白いかもしれません。

2007 年 1月、京都大学大学院情報学研究科博士後期課程修了。
京都大学助教を経て2013 年 2月より現職。
ネットワーク最適化をはじめとした組合せ最適化問題の研究に従事｡

マルチエージェントと最適化

皆さんは普段、自分で考えて行動をしていますでしょうか。かくいう私は指示待ち人間です。さて、私はマルチエージェントの研究に従事しています。エージェントは一般的に「主体的、自律的に行動するもの」などと訳されます。直観的には我々人間のようなものです。マルチエージェントでは、複数のエージェントが互いに協調し合うことで、一つの問題を解きます。ではマルチエージェントの何が嬉しいのでしょうか。
今、あるプロジェクトを進めており、どのように運営するかを考えているとします。簡
単な方法はリーダーを決定し、他のメンバーの状態を管理、指示を出す方法（図(a)）です。しかし、この方法ではメンバーが増加すると、指示が複雑化し状態の管理も困難となります。その結果、リーダーの負担が増大し過労で倒れます。これを解決するのがマルチエージェントです。ここではリーダーは存在せず、各メンバーが周りと情報交換しながら自律的、協調的に行動する（図 (b)）ことでプロジェクトを達成します。
私はこのマルチエージェントを最適化の文脈で主に研究しています。例えば、複数の計算機が問題を解く分散最適化の研究や、ゲーム理論のような異なる性質をもつエージェントが存在する状況下で、最適化する研究を行っています。特に分散グラフマイニング&WEB&AIグループ

波多野 大督Daisuke Hatano

国立情報学研究所特任研究員

2013 年 3月、神戸大学大学院海事科学研究科博士課程修了。
同年 4月から5月まで神戸大学大学院海事科学研究科研究員。同年 6月より現職。
制約充足問題、組み合わせ最適化問題を分散最適化とゲーム理論の観点からモデル化し解くことに興味を持つ。

最適化の研究は、本プロジェクトで扱うような一 つの 計算機では処理が不可能な巨大グラフを、複数の計算機を用いて処理することを可能とするでしょう。

感染症の広がる過程にネットワーク構造がどう関わるかを研究しています。感染症とは、インフルエンザやデング熱などのように病原体を介して広まる病気のことです。
感染症の広がる経路はまさにネットワークです。たとえば関係の深い人どうしを線で結ぶとソーシャルネットワークが描けます。あるいは、世界各地の空港は航空路線を介してネットワークを構成しています。このようなネットワークの構造を調べて感染症拡大感染症と戦う
ネットワーク研究の要因を探ることについて、特に近年では物理学者による研究がさかんです。自然現象を数式に表して分析することはまさに物理学の得意とするところだからです。ネットワークの分析や物理学的な方法では、どこにいつ感染が起こるかを特定することは困難です。その代わりに、どんなネットワークだと感染が広がりやすいかという傾向については理論的な回答を与えることができます。
感染症の広がり方を知るだけでなく、拡大を抑えることにもネットワークの知識は活用できます。たとえば羽田空港のように多くのつながりをもつ地点に集中的に対策を講じることが思い付きます。それ以上に効果の高い方法はないのでしょうか？この問
題に計算機科学との接点があります。現実のネットワークは含まれる地点の個数が膨大で複雑な構造をしているので、その構造を素早く正確に調べてより効果の高い対策を検討するためには高速な計算アルゴリズムが欠かせません。ネットワークを合言葉として計算の理論と実社会の現象を結び付けることが、２つの異なる学問分野の研 究 者が一 緒に研究することの醍醐味だと思います。

ERATO 河原林巨大グラフプロジェクトで私が進めている研究は、計算幾何学、グラフ理論、データ構造、そしてアルゴリズムを組み合わせた研究です。
グラフとネットワークは幅広く利用されており、経済学、遺伝学、社会科学、数学、コンピュータサイエンスなどさまざまな分野の情報構造のモデル化で役立てられています。
私の研究の目標は、これらのグラフに潜む様々な性質を見つけだし、これらの性質を利用して、ネットワークが各ノード間に短い経路を有することを示すだけでなく、これらの経路をたどる効率的なアルゴリズムを探しだすことにあります。このようなアルゴリズムは、ルーティングアルゴリズムと呼ばれます。
このルーティングアルゴリズムが役立つ例の一つとして、ワイヤレスネットワークが挙げられます。ワイヤレスネットワークは広く知られており、通常はノートパソコンやスマートフォンなどの携帯機器を互いに接続したり、インターネットに接続したりするために使用されます。
あるデバイスを他のすべてのデバイスに接続するには、（使用帯域幅、ハードウェア要件、消費電力の観点からみて）資源量を多く消費するので、それぞれのデバイスを少数のデバイスにのみ接続するのが一般的です。その結果、メッセージが目的のデバイスにたどり着くまで、デバイスは互いにメッセージを転送していかなければなりません。
しかしながら、どのデバイスもネットワーク全体の構造を知らないので、この転送プロセスの最適化は挑戦的な問題となります。
この分野で行われる研究のほとんどは、任意の2つのデバイス間で常に経路を見つけることのできるルーティングアルゴリズムの設計に焦点を当て、経路の長さを二の次と考えています。
私の研究では、これらのネットワークの幾何学的性質を把握し、これを利用して、２つのデバイス間においてその最短距離の高々定数倍の長さの経路を必ず見つけるような、ルーティングアルゴリズムを設計することです。

複雑ネットワーク・地図グラフグループ

高口 太朗

Taro Takaguchi

国立情報学研究所特任研究員

2013 年 3月、東京大学大学院情報理工学系研究科博士課程修了。同年 4月より現職。
実世界ネットワークに見られる構造の統計物理学的モデルと、感染症拡大や情報伝播などのダイナミクスに関心をもつ。

未知のネットワークにおけるルーティングの研究

ネットワーク・アルゴリズムグループ

André van Renssen
アンドレ ヴァン レンセン

国立情報学研究所

特任研究員

2014 年 8月、カールトン大学大学院コンピュータサイエンス博士課程修了。同年 9月より現職。
計算幾何学やアルゴリズム、データ構造やその他、難問であれば何であれ、手当り次第に研究対象となる。

近江高等学校での出張講義レポート

アウトリーチ

グラフマイニング &WEB&AI グループ
特任研究員

大輪 拓也

場 所：学校法人 近江育英会 近江高等学校（滋賀県彦根市松原町大黒前 3511-1）
日 時：2015 年 3月31日 14:10-15:30
聴講者：アカデミーコース1 年生、2 年生（約 80 名）講演タイトル：最先端数理科学の研究とビジネス

2015 年 3月31日、滋賀県の近江高等学校で「最先端数ように見受けられた。

理科学の研究とビジネス」というタイトルの講演を行った。聴講

講演後の感想の一つに、「女性としての今後の不安」を挙げ者は、近江高校の中でも大学進学を主な目標とするアカデミーた生徒がいた。講演を聞いて研究という仕事にも興味を持ったコースの生徒である。講演の内容は「自己紹介（研究職の紹一方、結婚や出産を考慮するとどれくらい自分の道を進むことが介）」、「数学や情報科学の研究」、「データを活用したビジネス可能であるのかを懸念しており、「女性のほうが自由は少なそう」と研究」等である。という言葉が印象的だった。私見だが、昨今の女性は、選択「自己紹介」では、何故研究職に就こうと考えたかを、私の肢は少しずつ広がってきたが、何をどう選択をすれば良いかにつ「高校→大学→企業→研究員」という経歴を踏まえて紹介した

いて悩んでいる方が多いように感じている。良い答えは私にもり、我々研究者が普段どんな生活をしているかについて紹介しわからないが、自身の経験から、研究職は比較的女性が働きやたりした。自身の高校生からの体験を踏まえた話しをした事で、すい職種ではないかと思っている。恐らく一般的な企業に比べ研究をより身近なものとして捉える事ができたように感じると、聴ると評価軸は明確であり、就労時間が自分で調整し易い点がそ講していた教員からコメントを頂いた。の理由である。もしくは、スライドを紹介する講演よりはもう少し「数学や情報科学の研究」では、ある暗号を確率的なアルゴ対話型の講演形式にして、個別の意見や悩みなどを聞きながらリズムで解く方法を紹介した。単純な方法による探索では天文話を進めるほうが良かったのではと感じた。

学的な年数が必要なのに対し、確率的なアルゴリズムを用いると一瞬で解が求められる事を、シミュレーションによる実演を交えて説明した。講演後の生徒から「文系の私でも興味のもてる内容だった、数学を使って研究できるのが面白かった」という声があった。
「データを活用したビジネスと研究」では、現在様々な企業で展開されているデータを中心としたサービスや製品の紹介と、それらを支える研究や学問についての紹介を行った。また、最近は高校生も参加できるデータ解析系のコンテストが開催されている事を紹介した。あるコンテストでは大学研究室や社会人をおさえて高校生が優勝した事を告げると、良い刺激になっていた

主要な研究成果

2015 年 1月〜 8月 国際学会発表論文
論文名

著

者

学会名

Eﬃcient Top-k Shortest-path Distance Queries on Large Takuya Akiba, Takanori Hayashi, Nozomi Nori,
Networks by Pruned Landmark
Yoichi Iwata, Yuichi Yoshida

AAAI2015 Austin, Texas USA, Jan 25-30

Learning Word Representations from Relational Graphs

Danushka Bollegala, Takanori Maehara, Yuichi
Yoshida, Ken-ichi Kawarabayashi

AAAI2015 Austin, Texas USA, Jan 25-30

Lagrangian Decomposition Algorithm for Allocating Daisuke Hatano, Takuro Fukunaga, Takanori
Marketing Channels
Maehara, Ken-ichi Kawarabayashi

AAAI2015 Austin, Texas USA, Jan 25-30

Deterministic Global Minimum Cut of a Simple Graph in Ken-ichi Kawarabayashi, Mikkel Thorup
Near-Linear Time

STOC2015 Portland, USA, June 15-17

The Directed Grid Theorem

Ken-ichi Kawarabayashi, Stephan Kreutzer

STOC2015 Portland, USA, June 15-17

Identifying an Honest EXPNP Oracle Among Many

Shuichi Hirahara

CCC2015 Portland, USA, June17-19

Correlation Bounds against Monotone NC¹

Benjamin Rossman

CCC2015 Portland, USA, June17-19

A Linear-time Algorithm for the Geodesic Center of a Simple Luis Barba, Prosenjit Bose, Matias Korman,Polygon
Jean-Lou De Carufel, Hee-Kap Ahn, Eunjin Oh

SoCG2015, Eindhoven,
the Netherlands, June 22-25

Budget Allocation Problem with Multiple Advertisers: A Takanori Maehara, Akihiro Yabe,
Game Theoretic View
Ken-ichi Kawarabayashi

ICML2015, Lille, France, July 6-11

Threshold Inﬂuence Model for Allocating Advertising Bud- Atsushi Miyauchi, Yuni Iwamasa,gets
Takuro Fukunaga, Naonori Kakimura

ICML2015, Lille, France, July 6-11

Real-time Top-R Topic Detection on Twitter with Topic Hijack Kohei Hayashi, Takanori Maehara, Masashi
Filtering
Toyoda, Ken-Ichi Kawarabayashi

KDD2015, Sydney, August 10-13

主要受賞
受賞年月

受賞者

2015 年 3月

河原林 健一2015 年度 日本数学会賞春季賞

受賞名

一般社団法人 日本数学会

主催

2015 年 3月

小関 健太

2014 年度 応用数学研究奨励賞

一般社団法人 日本数学会

2015 年 4月

林 浩平

平成 26 年度 船井研究奨励賞

公益財団法人 船井情報科学振興財団

お知らせ 当プロジェクトより以下の方々が転出されました。
氏

名前原 貴憲

特任研究員

馬場 雪乃

特任助教

Vorapong Suppakitpaisarn
特任助教

Matias Korman

転出時期

特任研究員

転出先

2015 年 2月

静岡大学学術院 工学領域数理システム工学専攻

助教

2015 年 4月

京都大学大学院 情報学研究科

2015 年 5月

東京大学大学院 情報理工学系研究科コンピュータ科学専攻

2015 年 6月

東北大学大学院 情報科学研究科

特定助教
助教

助教

イベントの様子2015.1.23 〜 24 河原林／湊プロジェクト合同ワークショップ予餞会 WINTER2015（日本科学未来館）

2015.2.26 日英 BigDataWorkshop（学術総合センター）

2015.2.28ERATO 成果報告会（学術総合センター）

2015.2.28ERATO 成果報告会（懇親会）

2015.6.12〜13 国立情報学研究所オープンハウス2015（学術総合センター）

発行：大学共同利用機関法人 情報・システム研究機構 国立情報学研究所 ビッグデータ数理国際研究センター〒101-8430 東京都千代田区一ツ橋2-1-2
Mail：kk-erato-jimu@nii.ac.jp

TEL：03-4212-2664

ホームページ：http://bigdata.nii.ac.jp/

facebook：https://www.facebook.com/erato.kawarabayashi