文献

J-GLOBAL ID：202102280517300559   整理番号：21A1497008

遺伝的アルゴリズムを用いたグラフの構造最適化

Graph Structure Optimization Using Genetic Algorithms

著者 (3件)： 田尻紘生 (岡山大 大学院自然科学研究科) ,  右田剛史 (岡山大 大学院自然科学研究科) ,  高橋規一 (岡山大 大学院自然科学研究科)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 120  号： 430(NLP2020 55-65)  ページ： 23-28 (WEB ONLY)  発行年： 2021年03月08日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 現実社会には,複雑ネットワークとよばれる大規模で複雑なネットワークが数多く存在する.それらのネットワークはグラフとしてモデル化され,様々な特徴量を用いて分析される.代数的連結度はグラフの結びつきの強さを測る特徴量のひとつであり,ラプラシアン行列の2番目に小さな固有値で定義される.本報告では,グラフに指定本数の辺を追加して代数的連結度を最大化する問題について考察し,遺伝的アルゴリズムを用いた近似解法を提案するとともに,その有効性を実験的に示す.また,各頂点の近傍の頂点がどの程度強く結びついているかを表すクラスター係数を最大化する問題についても提案手法を適用し,その有効性を検証する.(著者抄録)

シソーラス用語： 遺伝的アルゴリズム ,  近似法 ,  *構造最適化 ,  最大化問題 ,  係数 ,  *無向グラフ ,  強度 ,  クラスタ化 ,  ネットワーク ,  *グラフ理論 ,  結合度 ,  進化的計算 ,  *改変
準シソーラス用語： クラスタ係数

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (12件)：

• M. Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Mathematical Journal, vol.23, no.98, pp.298-305, 1973.
• R. Olfati-Saber, J. A. Fax and R. M. Murray, “Consensus and cooperation in networked multiagent systems,” Proceeding of the IEEE, vol.95, no.1, pp.215-233, 2007.
• P. Wei, G. Spiers and D. Sun, “Algebraic conectivity maximization for air transportation networks,” IEEE Transcations on Intelligent Transportation Systems, vol.15, no.2, pp.685-698, 2013.
• D. E. Goldberg, Genetic Algorithm in Search, Optimization, and Machine Learning, Addison Wesley, 1989.
• C. Maas, “Transportation in graphs and the admittance spectrum,” Discrete Applied Mathematics, vol.16, no.1, pp.31-49, 1987.

タイトルに関連する用語 (3件)： 遺伝的アルゴリズム ,  グラフ ,  構造最適化