| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-06-26 09:50 スパースモデリングによる媒介中心性推定手法の提案 ○松尾涼太郎・中村 遼・大崎博之（関西学院大）  IA2018-10 ICSS2018-10 |
|
| 抄録 | （和） | 近年、スパースモデリングと呼ばれる、モデルの特徴量が有するスパース性を利用することで、少数の観測値からモデルの未知の特徴量を推定する統計的手法が注目を浴びている。信号処理や画像処理の分野を中心に研究が進んでいるスパースモデリングであるが、少数ながらも情報ネットワーク分野における応用の検討も始まっている。我々はこれまで、スパースモデリングにより、ネットワークフロー問題の一つである最小リンクフロー問題が効率的に解けることを示した。最小リンクフロー問題とは、各ノードに対するトラヒック流入/流出レートが与えられた時に、それらの条件を満たすフローの中で、ネットワーク全体で使用するリンク数を最小化するフローを求めるという問題である。本稿では、スパースモデリングによる最小リンクフロー問題の定式化を拡張することで、情報ネットワークにおけるより複雑な問題にスパースモデリングが応用できるかを検討する。本稿では、スパースモデリングを利用することにより、ネットワークにおけるノードの中心性指標の一つである媒介中心性を推定する。具体的には、最小リンクフロー問題を $l_1$ ノルム最小化問題として解くことにより得られる最短経路木から、各ノードの媒介中心性を推定する。さらに本稿では、いくつかの小規模なグラフに対して、提案した推定手法によりノードの媒介中心性がどの程度正確に推定できているかを調査する。その結果、提案した推定手法により、グラフにおける上位 10% の媒介中心性を有するノードを正確に推定できていることがわかった。 |
| （英） | In recent years, a statistical approach for estimating unobserved model parameters from a small number of observations utilizing the sparsity of model parameters called sparse modeling have been extensively studied. In the literature, many applications of sparse modeling have been proposed in several fields such as signal processing, image processing, and compressed sensing. However, to the best of our knowledge, in the field of the information networking, a few applications have been studied. In our previous work, we have shown the effectiveness of sparse modeling for a network flow problem called minimum link flow problem, which finds, for given incoming/outgoing rate requirements at nodes, a set of flows satisfying requirements with the least number of links. This paper extends our sparse-modeling based approach to a more complex problem --- estimation of betweenness centrality, which is one of the major graph indices. In this paper, we present a sparse-modeling based solution for betweenness centrality estimation. Betweenness centralities of all nodes in an undirected graph are estimated from shortest-path trees, each of which is obtained as the solution for the minimum link flow problem formulated as the $l_1$-norm minimization problem. Furthermore, we investigate how accurately betweenness centrality can be estimated with our proposed sparse-modeling based estimation method. Our findings include that our proposed estimation method can accurately estimate a set of nodes whose top 10% betweenness centralities in a graph. | |
| キーワード | （和） | スパースモデリング / 媒介中心性 / ネットワークフロー問題 / 最小リンクフロー問題 / 最短経路木 / / / |
| （英） | Sparse Modeling / Betweenness Centrality / Network Flow Problem / Minimum Link Flow Problem / Shortest-Path Tree / / / | |
| 文献情報 | 信学技報, vol. 118, no. 108, IA2018-10, pp. 61-66, 2018年6月. | |
| 資料番号 | IA2018-10 | |
| 発行日 | 2018-06-18 (IA, ICSS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IA2018-10 ICSS2018-10 |
|
| 研究会情報 | |
| 研究会 | ICSS IA |
| 開催期間 | 2018-06-25 - 2018-06-26 |
| 開催地（和） | 愛媛大学 南加記念ホール |
| 開催地（英） | Ehime University |
| テーマ（和） | インターネットセキュリティ、一般 |
| テーマ（英） | Internet Security, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IA |
| 会議コード | 2018-06-ICSS-IA |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | スパースモデリングによる媒介中心性推定手法の提案 |
| サブタイトル（和） | |
| タイトル（英） | Proposal of Sparse-Modeling based Approach for Betweenness Centrality Estimation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | スパースモデリング / Sparse Modeling |
| キーワード(2)（和/英） | 媒介中心性 / Betweenness Centrality |
| キーワード(3)（和/英） | ネットワークフロー問題 / Network Flow Problem |
| キーワード(4)（和/英） | 最小リンクフロー問題 / Minimum Link Flow Problem |
| キーワード(5)（和/英） | 最短経路木 / Shortest-Path Tree |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 松尾 涼太郎 / Ryotaro Matsuo / マツオ リョウタロウ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 中村 遼 / Ryo Nakamura / ナカムラ リョウ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2018-06-26 09:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IA |
| 資料番号 | IA2018-10, ICSS2018-10 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.108(IA), no.109(ICSS) |
| ページ範囲 | pp.61-66 |
| ページ数 | 6 |
| 発行日 | 2018-06-18 (IA, ICSS) |
[研究会発表申込システムのトップページに戻る]