| Presentation | 2014-05-26 A 2-switch-based Method for Searching Algebraic Connectivity Maximizing Graphs and its Applicaton to 3-Regular Graphs Takuro FUJIHARA, Norikazu TAKAHASHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | How to reach a consensus is an important problem in multiagent networks. In a representative consensus protocol proposed by Olfati-Saber and Murray, the state value of each agent in a network varies with time depending on those of other agents, and eventually converges to the average of the initial state values. The speed of convergence of this protocol is determined by the second smallest eigenvalue of the Laplacian matrix, also known as the algebraic connectivity, of the graph representing interactions between agents. In this report, we address the problem of finding a graph that has not only the same degree sequence as a given graph but also the maximum algebraic connectivity among all graphs with the same degree sequence. For this problem, we first propose a local search algorithm based on 2-switch. We then apply this algorithm to 3-regular graphs and investigate the structural characteristics of the obtained graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | multiagent network / algebraic connectivity / 2-switch / regular graph |
| Paper # | NLP2014-4 |
| Date of Issue |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2014/5/19(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Nonlinear Problems (NLP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A 2-switch-based Method for Searching Algebraic Connectivity Maximizing Graphs and its Applicaton to 3-Regular Graphs |
| Sub Title (in English) | |
| Keyword(1) | multiagent network |
| Keyword(2) | algebraic connectivity |
| Keyword(3) | 2-switch |
| Keyword(4) | regular graph |
| 1st Author's Name | Takuro FUJIHARA |
| 1st Author's Affiliation | Graduate School of Natural Science and Technology, Okayama University() |
| 2nd Author's Name | Norikazu TAKAHASHI |
| 2nd Author's Affiliation | Graduate School of Natural Science and Technology, Okayama University |
| Date | 2014-05-26 |
| Paper # | NLP2014-4 |
| Volume (vol) | vol.114 |
| Number (no) | 55 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |