文献

J-GLOBAL ID：201802241618499293   整理番号：18A1064902

動的グラフ上の酔歩の被覆時間と混合時間【JST・京大機械翻訳】

Cover time and mixing time of random walks on dynamic graphs

著者 (3件)： Avin Chen (Department of Communication Systems Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel) ,  Koucky Michal (Computer Science Institute, Charles University, Prague, Czech Republic) ,  Lotker Zvi (Department of Communication Systems Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel)
資料名： Random Structures & Algorithms  (Random Structures & Algorithms)
巻： 52  号： 4  ページ： 576-596  発行年： 2018年 
JST資料番号： W0149A  ISSN： 1042-9832  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフ上の簡単なランダムウォークの応用は,ネットワーク探索,サンプリング,情報拡散,分散コンピューティングなどの多くのアルゴリズム設定において有用な強力なツールである。これは,局所データのみに対する簡単なランダムウォークの信頼性,その無視できるメモリ要件,およびその分散性による。静的グラフに対しては,グラフの各ノードを訪問する期待時間,および混合時間,すなわち,定常分布に従ってノードをサンプリングする時間はグラフのサイズに対してほとんど多項式であることが良く知られている。ピアツーピアと無線ネットワークのような実世界ネットワークに動機付けられて,本論文の会議バージョンは,任意の動的ネットワーク上でランダムウォークを研究する最初のものであった。ランダム歩行の各ステップ後にグラフを変化させることができる最も一般的なモデルを研究した。静的グラフとは対照的に,動的グラフ上で期待されるカバー時間と簡単なランダムウォークの混合時間を指数関数的に長くすることができることを示し,ネットワークが良く接続され,急速に混合されている場合でも,動的グラフ上の簡単なランダムウォークの混合時間が指数的に長くなることを示した。これを解決するために,著者らは簡単な戦略を提案する。それは,小さな条件の下で,多項式カバー時間と多項式混合時間を,敵によって作られた変化にかかわらず,保証する。Copyright 2018 Wiley Publishing Japan K.K. All Rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 分散処理 ,  *混合時間 ,  記憶装置 ,  高速度 ,  ネットワーク ,  モデル ,  モデリング ,  *グラフ ,  アルゴリズム ,  *被覆 ,  多項式 ,  *酔歩
準シソーラス用語： 動的ネットワーク ,  無線ネットワーク ,  ピアツーピア ,  定常分布 , 【Automatic Indexing@JST】

著者キーワード (5件)： 被覆時間 ,  動的グラフ ,  混合時間 ,  酔歩 ,  定常分布

分類 (3件)： 計算機網  (JC03000K) ,  移動通信  (ND08030H) ,  システム・制御理論一般  (IA02010H)

タイトルに関連する用語 (3件)： グラフ ,  酔歩 ,  混合時間