講演抄録/キーワード |
講演名 |
2016-01-29 15:05
完全多部グラフの代数的連結度最大性と2-switchに基づく代数的連結度極大グラフ探索法 ○藤原拓郎・高橋規一(岡山大) RCC2015-92 |
抄録 |
(和) |
マルチエージェントネットワークにおける重要な課題の一つに合意形成がある.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 / / / / |
文献情報 |
信学技報, vol. 115, no. 442, RCC2015-92, pp. 31-36, 2016年1月. |
資料番号 |
RCC2015-92 |
発行日 |
2016-01-22 (RCC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
RCC2015-92 |
研究会情報 |
研究会 |
RCC |
開催期間 |
2016-01-29 - 2016-01-29 |
開催地(和) |
関西大学うめきたラボラトリ |
開催地(英) |
Kansai University Umekita Laboratory |
テーマ(和) |
制御通信に関するすべてのトピックス |
テーマ(英) |
Reliable Communication and Control |
講演論文情報の詳細 |
申込み研究会 |
RCC |
会議コード |
2016-01-RCC |
本文の言語 |
日本語 |
タイトル(和) |
完全多部グラフの代数的連結度最大性と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 |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
藤原 拓郎 / Takuro Fujihara / フジハラ タクロウ |
第1著者 所属(和/英) |
岡山大学 (略称: 岡山大)
Okayama University (略称: Okayama Univ.) |
第2著者 氏名(和/英/ヨミ) |
高橋 規一 / Norikazu Takahashi / タカハシ ノリカズ |
第2著者 所属(和/英) |
岡山大学 (略称: 岡山大)
Okayama University (略称: Okayama Univ.) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2016-01-29 15:05:00 |
発表時間 |
25分 |
申込先研究会 |
RCC |
資料番号 |
RCC2015-92 |
巻番号(vol) |
vol.115 |
号番号(no) |
no.442 |
ページ範囲 |
pp.31-36 |
ページ数 |
6 |
発行日 |
2016-01-22 (RCC) |