G-007
遺伝アルゴリズムによる代数的連結度最大化

◎田尻紘生・右田剛史・高橋規一（岡山大）

ネットワークの結びつきの強さを表す指標の一つに代数的連結度がある．これはラプラシアン行列の2番目に小さい固有値で定義され，代数的グラフ理論の分野で古くから研究されている．代数的連結度は工学的にも重要であり，マルチエージェントネットワークの合意，結合振動子の同期，グラフ上のランダムウォークなど，ネットワーク上のダイナミクスを特徴づける．本発表では，与えられたグラフに指定本数の辺を追加して代数的連結度を最大化する問題について考察し，遺伝アルゴリズムを用いた解法を提案する．また，提案法と従来法の一つである最小次数最大距離アルゴリズムを同じグラフに適用する実験を行い，提案法の有効性を検証する．