| 講演名 | 2016-01-18 メッセージ伝搬にもとづく疎な2部グラフ上のショートサイクル数え上げ法に関する研究 中原 悠太(早大), 齋藤 翔太(早大), 松嶋 敏泰(早大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本研究では，疎な2部グラフ上のショートサイクルをメッセージ伝搬によって数え上げるアルゴリズムの改良を提案する．従来研究では，2部グラフのガースを$g$，エッジ数を$|E|$とおいたとき，長さ$g, g+2, dots , 2g-2$のサイクルを，$O(g|E|^2)$の計算量で数え上げている．本研究では，従来のアルゴリズムのメッセージ更新処理を行うノードを制限することによって，従来研究と同じ長さのサイクルをより少ない計算量で数え上げることができることを示す．提案アルゴリズムの計算量は，ノード次数が一定の値$d_u, d_w$をとる2部グラフに対しては$O(|E|d_u^{frac{g}{2}}d_w^{frac{g}{2}-1})$となる．サイクル数の知られている2部グラフとして，いくつかのLDPC符号に対し提案アルゴリズムを用いてショートサイクルを数え上げ，従来アルゴリズムと比較する． |
| 抄録(英) | In this paper, we propose an improvement of message passing algorithm for counting short cycles in sparse bipartite graphs. Let $g$ and $|E|$ denote the girth of the graph and number of edges respectively. In previous studies, algorithms are proposed for counting cycles of length $g, g+2,dots , 2g-2$ with complexity of $O(g|E|^2)$. Our proposed algorithm is able to count cycles of the same length of previous algorithm with lower complexity by limiting the nodes to process. Proposed algorithm have the complexity of $O(|E|d_u^{frac{g}{2}}d_w^{frac{g}{2}-1})$, where the node degrees of bipartite graph is constant $d_u, d_w$. Then computer simulation is provided to count the cycles of famous LDPC codes. |
| キーワード(和) | 2部グラフ / サイクル / メッセージ伝搬 / LDPC符号 |
| キーワード(英) | Bipartite graph / cycle / LDPC code / message passing |
| 資料番号 | IT2015-50,SIP2015-64,RCS2015-282 |
| 発行日 | 2016-01-11 (IT, SIP, RCS) |
| 研究会情報 | |
| 研究会 | RCS / IT / SIP |
|---|---|
| 開催期間 | 2016/1/18(から2日開催) |
| 開催地（和） | 関西学院大学(大阪梅田) |
| 開催地（英） | Kwansei Gakuin Univ. Osaka Umeda Campus |
| テーマ（和） | 無線通信のための信号処理，学習，数理，情報理論および一般 |
| テーマ（英） | Signal Processing for Wireless Communications, Learning, Mathematical Science, Communication Theory, etc. |
| 委員長氏名（和） | 太郎丸 真(福岡大) / 大濱 靖匡(電通大) / 宝珠山 治(NEC) |
| 委員長氏名（英） | Makoto Taromaru(Fukuoka Univ.) / Yasutada Oohama(Univ. of Electro-Comm.) / Osamu Houshuyama(NEC) |
| 副委員長氏名（和） | 村田 英一(京大) / 田野 哲(岡山大) / 眞田 幸俊(慶大) / 和田山 正(名工大) / 中静 真(千葉工大) / 奥田 正浩(北九州市大) |
| 副委員長氏名（英） | Hidekazu Murata(Kyoto Univ.) / Satoshi Denno(Okayama Univ.) / Yukitoshi Sanada(Keio Univ.) / Tadashi Wadayama(Nagoya Inst. of Tech.) / Makoto Nakashizuka(Chiba Inst. of Tech.) / Masahiro Okuda(Univ. of Kitakyushu) |
| 幹事氏名（和） | 岡崎 彰浩(三菱電機) / 須山 聡(NTTドコモ) / 岩本 貢(電通大) / 葛岡 成晃(和歌山大) / 辻川 剛範(NEC) / 平林 晃(立命館大) |
| 幹事氏名（英） | Akihiro Okazaki(Mitsubishi Electric) / Satoshi Suyama(NTT DoCoMo) / Mitsugu Iwamoto(Univ. of Electro-Comm.) / Nariaki Kuzuoka(Wakayama Univ.) / Masanori Tsujikawa(NEC) / Akira Hirabayashi(Ritsumeikan Univ.) |
| 幹事補佐氏名（和） | 増野 淳(NTT) / 山本 哲矢(パナソニック) / 井上 高道(NEC) / 旦代 智哉(東芝) / 西村 寿彦(北大) / 日下 卓也(岡山大) / 宮田 高道(千葉工大) |
| 幹事補佐氏名（英） | Jun Mashino(NTT) / Tetsuya Yamamoto(Panasonic) / Takamichi Inoue(NEC) / Tomoya Tandai(Toshiba) / Toshihiko Nishimura(Hokkaido Univ.) / Takuya Kusaka(Okayama Univ.) / Takamichi Miyata(Chiba Inst. of Tech.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Radio Communication Systems / Technical Committee on Information Theory / Technical Committee on Signal Processing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | メッセージ伝搬にもとづく疎な2部グラフ上のショートサイクル数え上げ法に関する研究 |
| サブタイトル（和） | |
| タイトル（英） | A Study on Message Passing Algorithm for Counting Short Cycles in Sparse Bipartite Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 2部グラフ / Bipartite graph |
| キーワード(2)（和/英） | サイクル / cycle |
| キーワード(3)（和/英） | メッセージ伝搬 / LDPC code |
| キーワード(4)（和/英） | LDPC符号 / message passing |
| 第 1 著者 氏名（和/英） | 中原 悠太 / Yuta Nakahara |
| 第 1 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 2 著者 氏名（和/英） | 齋藤 翔太 / Shota Saito |
| 第 2 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 第 3 著者 氏名（和/英） | 松嶋 敏泰 / Toshiyasu Matsushima |
| 第 3 著者 所属（和/英） | 早稲田大学(略称：早大) Waseda University(略称：Waseda Univ.) |
| 発表年月日 | 2016-01-18 |
| 資料番号 | IT2015-50,SIP2015-64,RCS2015-282 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | IT-394,SIP-395,RCS-396 |
| ページ範囲 | pp.13-18(IT), pp.13-18(SIP), pp.13-18(RCS), |
| ページ数 | 6 |
| 発行日 | 2016-01-11 (IT, SIP, RCS) |