| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-11-09 09:25 最適解テーブル法による最大重み2-plex抽出問題の厳密解法に関する研究 ○柏原優稀・山口一章・中村匡秀（神戸大）  KBSE2024-32 SC2024-35 |
|
| 抄録 | （和） | 本研究では，頂点に重みが割り当てられたグラフにおける最大重み2-plex問題に対する厳密解法を提案する．2-plexは頂点の次数に着目したグラフの密な部分集合の構造のひとつであり，ネットワーク解析におけるコミュニティ抽出などで応用される．本稿では，最大重みクリーク問題に対する効率的な解法であるRussian Doll Search (RDS) 及び最適解テーブル法を最大重み 2-plex 問題に対し拡張し，手法を構築する．提案手法の有効性を評価するため，数理最適化ソルバーを用いた従来法と比較する計算機実験を行った．ランダムグラフの入力に対し，提案法は辺密度の低いケースを中心とした多くの場合において従来法より高速に動作することがわかった． |
| （英） | In this study, we propose an exact algorithm for the maximum weight 2-plex problem in graphs where vertices are assigned weights. A 2-plex is one of the dense substructures in graphs, focusing on vertex degrees, and is applied in tasks such as community detection in network analysis. In this paper, we extend the Russian Doll Search (RDS), an efficient solution method for the maximum weight clique problem, as well as the optimal solution table method, to address the maximum weight 2-plex problem and construct a new approach. To evaluate the effectiveness of the proposed method, we conducted computational experiments comparing it with conventional methods using a mathematical optimization solver. The results showed that the proposed method performed faster than conventional methods in many cases, especially in inputs with lower edge densities. | |
| キーワード | （和） | 分枝限定法 / 2-plex / NP困難 / ,最大クリーク / / / / |
| （英） | Branch and Bound / 2-plex / NP Hard / Maximum Clique / / / / | |
| 文献情報 | 信学技報, vol. 124, no. 245, SC2024-35, pp. 77-82, 2024年11月. | |
| 資料番号 | SC2024-35 | |
| 発行日 | 2024-11-01 (KBSE, SC) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | KBSE2024-32 SC2024-35 |
|
| 研究会情報 | |
| 研究会 | SC KBSE |
| 開催期間 | 2024-11-08 - 2024-11-09 |
| 開催地（和） | 高知市文化プラザかるぽーと（9F特別学習室） |
| 開催地（英） | Kochi-City Culture Plaza CUL-PORT |
| テーマ（和） | 一般 |
| テーマ（英） | General |
| 講演論文情報の詳細 | |
| 申込み研究会 | SC |
| 会議コード | 2024-11-SC-KBSE |
| 本文の言語 | 日本語 |
| タイトル（和） | 最適解テーブル法による最大重み2-plex抽出問題の厳密解法に関する研究 |
| サブタイトル（和） | |
| タイトル（英） | An Exact Algorithm for the Maximum Weighted 2-Plex Problem Using the Optimal Table |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 分枝限定法 / Branch and Bound |
| キーワード(2)（和/英） | 2-plex / 2-plex |
| キーワード(3)（和/英） | NP困難 / NP Hard |
| キーワード(4)（和/英） | ,最大クリーク / Maximum Clique |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 柏原 優稀 / Yuki Kashihara / カシハラ ユウキ |
| 第1著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kove Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山口 一章 / Kazuaki Yamaguchi / ヤマグチ カズアキ |
| 第2著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kove Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 中村 匡秀 / Masahide Nakamura / ナカムラ マサヒデ |
| 第3著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kove Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-11-09 09:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | SC |
| 資料番号 | KBSE2024-32, SC2024-35 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.244(KBSE), no.245(SC) |
| ページ範囲 | pp.77-82 |
| ページ数 | 6 |
| 発行日 | 2024-11-01 (KBSE, SC) |
[研究会発表申込システムのトップページに戻る]