Signed Modularity Density 最大化問題に対する半正定値計画緩和の実験的評価

カテゴリ: 全国大会

論文No: 3-029

グループ名: 【全国大会】令和3年電気学会全国大会論文集

発行日: 2021/03/01

タイトル(英語): A computational study of semidefinite programming relaxations for maximizing modularity density on signed networks

著者名: 工藤蓮（神奈川大学）,伊豆永洋一（神奈川大学）

著者名(英語): Ren Kudo (Kagawa University),Yoichi Izunaga (Kagawa University)

キーワード: コミュニティ抽出|符号付きネットワーク|signed modularity density|半正定値計画緩和|射影行列|community detection|signed network|signed modularity density|semidefinite programming relaxation|projection matrix

要約(日本語): 与えられたネットワークを密な部分ネットワークに分割するタスクはコミュニティ抽出と呼ばれ，工学や社会科学において幅広い応用を持つ. ネットワークの各枝が正負の符号情報を持つとき，それを符号付きネットワークと呼び，正の符号を持つ枝は友好関係を，負の符号を持つ枝は敵対関係を表す.本研究では，符号付きネットワーク上のコミュニティ抽出における signed modularity density の最大化問題が，非負対称な射影行列を変数とする最適化問題に定式化できることを示す．さらに，この問題の半正定値計画緩和を解く

原稿種別: 日本語

PDFファイルサイズ: 691 Kバイト