| 講演名 | 2016-01-29 完全多部グラフの代数的連結度最大性と2-switchに基づく代数的連結度極大グラフ探索法 藤原 拓郎(岡山大), 高橋 規一(岡山大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | マルチエージェントネットワークにおける重要な課題の一つに合意形成がある．Olfati-SaberとMurrayによって提案された代表的な合意形成アルゴリズムでは，各エージェントの状態値は他のエージェントの状態値に依存して連続的に変化し，最終的に初期状態値の平均値に収束する．また，その収束の速さはエージェント間の相互作用を表すグラフの代数的連結度によって決まる．本研究では，与えられた次数列の下で代数的連結度が最大となるグラフの構造について考察する．はじめに，任意の完全多部グラフがそれと同一の次数列をもつグラフの中で，代数的連結度を最大にすることを証明する．次に，完全多部グラフに2-switchを適用して得られるグラフの代数的連結度の最小値を評価する．最後に，2-switchに基づく代数的連結度極大グラフの局所探索法を提案し，その有効性を実験的に検証する． |
| 抄録(英) | How to reach a consensus is an important problem for multiagent networks. In the most well-known consensus algorithm proposed by Olfati-Saber and Murray, the state value of each agent varies continuously depending on those of other agents and converges to the average of the initial state values of all agents. In addition, the convegence rate is determined by the algebraic connectivity of the grath representing the interaction between agents. In this study, we consider the problem of finding a graph that maximizes the algebraic connectivity under a given degree sequence. First, we prove that each complete multipartite graph has the highest algebraic connectivity among all graphs with the same degree sequence. Next, we derive a lower bound for the algebraic connectivities of graphs that are obtained from a complete multipartite graph by applying a 2-switch. Finally, we propose 2-switch-based local search algorithms for finding algebraic connectivity locally maximizing graphs and evaluate their effectiveness experimentally. |
| キーワード(和) | マルチエージェントネットワーク / 代数的連結度 / 完全多部グラフ / 2-switch |
| キーワード(英) | multiagent network / algebraic connectivity / complete multipartite graph / 2-switch |
| 資料番号 | RCC2015-92 |
| 発行日 | 2016-01-22 (RCC) |
| 研究会情報 | |
| 研究会 | RCC |
|---|---|
| 開催期間 | 2016/1/29(から1日開催) |
| 開催地（和） | 関西大学うめきたラボラトリ |
| 開催地（英） | Kansai University Umekita Laboratory |
| テーマ（和） | 制御通信に関するすべてのトピックス |
| テーマ（英） | Reliable Communication and Control |
| 委員長氏名（和） | 片山 正昭(名大) |
| 委員長氏名（英） | Masaaki Katayama(Nagoya Univ.) |
| 副委員長氏名（和） | 原 晋介(阪市大) / 三浦 龍(NICT) |
| 副委員長氏名（英） | Shinsuke Hara(Osaka City Univ.) / Ryu Miura(NICT) |
| 幹事氏名（和） | 林 和則(京大) / 小林 孝一(北大) |
| 幹事氏名（英） | Kazunori Hayashi(Kyoto Univ.) / Koichi Kobayashi(Hokkaido Univ.) |
| 幹事補佐氏名（和） | 石井 光治(香川大) / 小林 健太郎(名大) |
| 幹事補佐氏名（英） | Koji Ishii(Kagawa Univ.) / Kentaro Kobayashi(Nagoya Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Reliable Communication and Control |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 完全多部グラフの代数的連結度最大性と2-switchに基づく代数的連結度極大グラフ探索法 |
| サブタイトル（和） | |
| タイトル（英） | Maximality of the Algebraic Connectivity of Complete Multipartite Graphs and a 2-Switch-Based Method for Finding Algebraic Connectivity Locally Maximizing Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | マルチエージェントネットワーク / multiagent network |
| キーワード(2)（和/英） | 代数的連結度 / algebraic connectivity |
| キーワード(3)（和/英） | 完全多部グラフ / complete multipartite graph |
| キーワード(4)（和/英） | 2-switch / 2-switch |
| 第 1 著者 氏名（和/英） | 藤原 拓郎 / Takuro Fujihara |
| 第 1 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 第 2 著者 氏名（和/英） | 高橋 規一 / Norikazu Takahashi |
| 第 2 著者 所属（和/英） | 岡山大学(略称：岡山大) Okayama University(略称：Okayama Univ.) |
| 発表年月日 | 2016-01-29 |
| 資料番号 | RCC2015-92 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | RCC-442 |
| ページ範囲 | pp.31-36(RCC), |
| ページ数 | 6 |
| 発行日 | 2016-01-22 (RCC) |