近線形ネットワーク最適化技術の提案

Tiffany Trader

マサチューセッツ工科大学の研究者チームは、困難なネットワーク最適化問題を解決するための新たな枠組みを考案した。数学者とコンピュータ科学者は、ネットワーク上のポイント間の最も効率的なパスを決定するために、長い間、最大流量問題、または「max flow」を使用してきたが、ネットワークはこれまで以上に複雑になるように、一連の方程式を解くことは法外な時間消費をすることになる。しかし最近では、MITのコンピュータ科学・人工知能研究所(CSAIL)の科学者が、最大規模のネットワークの効率を高めることができる「最大フロー」を計算するためのほぼ線形時間アルゴリズムを開発した。

最大フロー問題は、一連のノードと接続線(知っての通り頂点とエッジ)を持つグラフとしてネットワークを表す。各エッジが最大容量を有することを考慮すると、「最大フロー」の目標は、どのくらい多くの何かのユニットをネットワークの一端から他端に移動させることができるかを計算することである。「最大フロー」の伝統的なバージョンが小規模なネットワークでうまく機能する一方、ネットワークは指数関数的に大きくなるように、問題があまりにも多くの時間とオーバーヘッドを必要とし手に負えなくなる。

「研究されているグラフサイズでの爆発が最近ありました。」と主導的な執筆者のひとりでMITで応用数学の助教授とCSAILのメンバーでもあるJonathan Kelnerは言う。「たとえば、インターネット上のトラフィックを辿りたい場合は、Facebook上のすべての接続を研究し、もしくはゲノムデータを分析すると、簡単に、何百万、何十億、または何兆ですらエッジを持つグラフになってしまう可能性があります。」

CSAILの研究者は、最大フロー問題を解くために必要な操作の数を劇的に減少させる可能性を有する新たな理論的アルゴリズムを開発した。この近直線解法で、それはインターネットまたはヒトゲノムのような巨大なネットワークを横断するトラフィックを最適化することが可能かも知れない。

以前のアルゴリズムは等しいとしてグラフ内のすべての経路を扱っていたところ、新しい技術は、ネットワーク内のボトルネックを作った経路を正確に特定する。チームのアルゴリズムは、適切に接続されたノードのクラスター内での各グラフと、ボトルネックを作ったそれらの間の経路とを分離する。

「私たちのアルゴリズムは、どのグラフの部分で彼らがする必要があることを簡単送ることができるのか、そしてどの部分にボトルネックがあるのか分かります。これは、あなたが重要でない決断に多くの時間を費やす代わりに、多くの時間をより効率的に使うことができることを意味し、問題領域と高レベル構造について焦点を当てることが可能となります。」とKelnerは言う。

拡張は、結果的に近線形アルゴリズム、すなわち、問題を解決するのに必要な時間の量はネットワークの大きさにほぼ正比例する。ノード数が10倍に拡大した場合は、解決までの時間は、以前の技術の下での経験では100倍または1,000倍だっただろう代わりに、10倍まで上がる(またはそれに近い)。

「これは、入力サイズを望むことができることと同様に本質的に比例することを意味します。」とKelnerは言う。

Kelnerの他に、研究チームはMITの応用数学の講師、Lorenzo Orecchia、同学科の大学院生、Yin Tat LeeとAaron Sidfordが含まれてる。

著者は、オレゴン州ポートランドで開かれる離散アルゴリズムに関するACM-SIAMシンポジウムで彼らの論文を発表する。今年のACM-SIAM会議で最優秀論文賞を受賞した彼らの作品はまた、離散アルゴリズムジャーナルのACM-SIAMシンポジウム欄で見られる。