文献

J-GLOBAL ID：202002219493543742   整理番号：20A2093105

相互作用する酔歩によるFedlerベクトル近似【JST・京大機械翻訳】

Fiedler Vector Approximation via Interacting RandomWalks

著者 (2件)： Doshi Vishwaraj (North Carolina State University, NC, USA) ,  Young Eun Do (North Carolina State University, NC, USA)
資料名： ACM SIGMETRICS Performance Evaluation Review  (ACM SIGMETRICS Performance Evaluation Review)
巻： 48  号： 1  ページ： 101-102  発行年： 2020年 
JST資料番号： W5730A  ISSN： 0163-5999  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフのFiedlerベクトル,すなわちグラフラプラシアン行列の第2最小固有値に対応する固有ベクトルは,グラフ双分割とエンベロープ低減のような問題における応用を伴うスペクトルグラフ理論において重要な役割を演じる。この量を推定するように設計されたアルゴリズムは,通常全グラフの先験的知識に依存し,グラフが未知であるか,あるいは動的に変化する場合において明らかな欠点を持つグラフスパース化や電力反復のような技術を採用する。本論文では,グラフ上で相互作用するランダムウォークの集合に基づく確率的プロセスを構築するフレームワークを開発し,確率的プロセスの適切にスケーリングされたバージョンが,十分に大きな数の歩道に対してFiedlerベクトルに収束することを示した。また,異なるグラフに関する理論的発見を確認するために数値結果を提供し,提案アルゴリズムが広範囲のパラメータおよびランダムウォークの数に対して良好に機能することを示した。時間変動動的グラフに関するシミュレーション結果も,そのような設定におけるランダムウォークベース技術の有効性を示すために提供した。重要な貢献として,著者らの結果を拡張し,著者らのフレームワークがグラフラプラシアンのFiedlerベクトルを近似するだけでなく,相互作用ランダムウォークを介して任意の時間可逆Markov連鎖カーネルの2番目の固有ベクトルにも適用可能であることを示した。著者らの知る限り,ランダムウォークを用いた任意の時間可逆Markov連鎖の2次固有ベクトルを近似する試みは,グラフ上のランダムウォークを用いた高レベル固有ベクトルの近似を達成する可能性を開く。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  確率過程 ,  固有値 ,  シミュレーション ,  *相互作用 ,  *ベクトル ,  電力 ,  歩道 ,  経時変化 ,  Markov連鎖 ,  *近似法 ,  *酔歩 ,  エンベロープ ,  有効性 ,  固有ベクトル

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 相互作用 ,  酔歩 ,  ベクトル ,  近似