| Presentation | 2018-06-26 Proposal of Sparse-Modeling based Approach for Betweenness Centrality Estimation Ryotaro Matsuo, Ryo Nakamura, Hiroyuki Ohsaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Sparse Modeling / Betweenness Centrality / Network Flow Problem / Minimum Link Flow Problem / Shortest-Path Tree |
| Paper # | IA2018-10,ICSS2018-10 |
| Date of Issue | 2018-06-18 (IA, ICSS) |
| Conference Information | |
| Committee | ICSS / IA |
|---|---|
| Conference Date | 2018/6/25(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Ehime University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Internet Security, etc. |
| Chair | Yoshiaki Shiraishi(Kobe Univ.) / Katsuyoshi Iida(Hokkaido Univ.) |
| Vice Chair | Hiroki Takakura(NII) / Katsunari Yoshioka(Yokohama National Univ.) / Rei Atarashi(IIJ) / Hiroyuki Osaki(Kwansei Gakuin Univ.) / Toru Kondo(Hiroshima Univ.) |
| Secretary | Hiroki Takakura(NTT) / Katsunari Yoshioka(NICT) / Rei Atarashi(Tokyo Metropolitan Univ.) / Hiroyuki Osaki(TOYOTA-IT) / Toru Kondo(NEC) |
| Assistant | Akira Yamada(KDDI labs.) / Keisuke Kito(Mitsubishi Electric) / Kenji Ohira(Tokushima Univ.) / Ryohei Banno(Tokyo Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Information and Communication System Security / Technical Committee on Internet Architecture |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Proposal of Sparse-Modeling based Approach for Betweenness Centrality Estimation |
| Sub Title (in English) | |
| Keyword(1) | Sparse Modeling |
| Keyword(2) | Betweenness Centrality |
| Keyword(3) | Network Flow Problem |
| Keyword(4) | Minimum Link Flow Problem |
| Keyword(5) | Shortest-Path Tree |
| 1st Author's Name | Ryotaro Matsuo |
| 1st Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 2nd Author's Name | Ryo Nakamura |
| 2nd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| 3rd Author's Name | Hiroyuki Ohsaki |
| 3rd Author's Affiliation | Kwansei Gakuin University(Kwansei Gakuin Univ.) |
| Date | 2018-06-26 |
| Paper # | IA2018-10,ICSS2018-10 |
| Volume (vol) | vol.118 |
| Number (no) | IA-108,ICSS-109 |
| Page | pp.pp.61-66(IA), pp.61-66(ICSS), |
| #Pages | 6 |
| Date of Issue | 2018-06-18 (IA, ICSS) |