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
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)