| 講演名 | 2011-01-26 グラフラプラシアンの第2固有値を最大にする無向グラフ : 平均次数が2以下の場合 荻原 幸之助, 高橋 規一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 与えられた頂点数nと辺数mの下でグラフラプラシアンの第2固有値を最大にする無向グラフを求める問題について考察する.グラフラプラシアンの第2固有値はネットワークマルチエージェントシステムの合意形成における収束の速さを決定する重要な指標である.本報告では,n= mかつn≦6のとき閉路グラフが第2固有値を最大にすること.n=mかつn≧6のとき星グラフに辺を一つ加えたグラフが第2固有値を最大にすること,閉路グラフが第2固有値を局所的に最大にすることを証明する. |
| 抄録(英) | We consider the problem of finding undirected graphs maximizing the second smallest eigenvalue of the graph Laplacian. The second smallest eigenvalue of the graph Laplacian is an important criterion which determines the speed of convergence of a consensus algorithm for networked multi-agent systems. Let n and m denote the numbers of nodes and edges, respectively. We prove in this report that 1) the cycle graph maximizes the second smallest eigenvalue when n = m and n ≦ 6, 2) a graph obtained by adding an edge to the star graph maximizes the second smallest eigenvalue when n = m and n ≧ 6, and 3) the cycle graph locally maximizes the second smallest eigenvalue for any n ≧ 3. |
| キーワード(和) | 合意問題 / グラフラプラシアン / 第2固有値 / 代数的連結度 |
| キーワード(英) | consensus problem / graph Laplacian / the second smallest eigenvalue / algebraic connectivity |
| 資料番号 | CAS2010-98 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2011/1/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフラプラシアンの第2固有値を最大にする無向グラフ : 平均次数が2以下の場合 |
| サブタイトル（和） | |
| タイトル（英） | Undirected Graphs Maximizing the Second Smallest Eigenvalue of the Graph Laplacian : Case where the Average Degree is Less than or Equal to 2 |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 合意問題 / consensus problem |
| キーワード(2)（和/英） | グラフラプラシアン / graph Laplacian |
| キーワード(3)（和/英） | 第2固有値 / the second smallest eigenvalue |
| キーワード(4)（和/英） | 代数的連結度 / algebraic connectivity |
| 第 1 著者 氏名（和/英） | 荻原 幸之助 / Kohnosuke OGIWARA |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学府 Graduate School of Information Science and Electrical Engineering, Kyushu University |
| 第 2 著者 氏名（和/英） | 高橋 規一 / Norikazu TAKAHASHI |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学研究院 Faculty of Information Science and Electrical Engineering, Kyushu University |
| 発表年月日 | 2011-01-26 |
| 資料番号 | CAS2010-98 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | 389 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |