マルチエージェントネットワークにおける代数的連結度計算のための新しい連続時間ァルゴリズム

摘要

モバイルエージェントネットワークにおいて連結性保持は基本的かつ重要な課題である.そのためのーつのアプローチとして,ネットワークが連結であることとエージェント間の相互作用を表すグラフの代数的連結度が正であることが同値であるという事実に着目し,代数的連結度が正の値をとり続けるように各エージェントの動きを制御する方法がある.したがって,この方法においては,代数的連結度をいかに高速かつ効率的に計算するかが重要である.本稿では,代数的連結度を計算するための新しい連続時間アルゴリズムを提案する.これは乗算回数が少ないという意味で既存のアルゴリズムよりも簡潔なものになっている.我々は,提案アルゴリズムの動的挙動を解析し,ほとんどすベての初期状態に対して代数的連結度に収束することを証明する.%How to maintain connectivity is an important issue in mobile agent networks. An approach is to control movement of agents so that the algebraic connectivity of the graph representing the interaction between agents is kept positive. This is based on the fact that the network is connected if and only if the algebraic connectivity is positive. Therefore, it is important in this approach to calculate the algebraic connectivity fast and efficiently. In this report, we propose a new continuous-time algorithm for calculating the algebraic connectivity of the graph. The proposed algorithm is simpler than the conventional one in the sense that less multiplications are needed. We study the dynamical behavior of the proposed algorithm and prove that it can find the algebraic connectivity of the graph for almost all initial conditions.