WEKO3
アイテム
Estimating High Betweenness Centrality Nodes via Random walk in Social Networks
https://ipsj.ixsq.nii.ac.jp/records/206250
https://ipsj.ixsq.nii.ac.jp/records/206250c00e9422-ddf7-4095-9dff-f3cf66e463e0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOD1303003.pdf (4.1 MB)
|
Copyright (c) 2020 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2020-07-16 | |||||||||
| タイトル | ||||||||||
| タイトル | Estimating High Betweenness Centrality Nodes via Random walk in Social Networks | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Estimating High Betweenness Centrality Nodes via Random walk in Social Networks | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [研究論文] social networks, betweenness centrality, ego betweenness centrality, sampling, estimation, random walk | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| Tokyo Institute of Technology | ||||||||||
| 著者所属 | ||||||||||
| Tokyo Institute of Technology | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Tokyo Institute of Technology | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Tokyo Institute of Technology | ||||||||||
| 著者名 |
Kazuki, Nakajima
× Kazuki, Nakajima
× Kazuyuki, Shudo
|
|||||||||
| 著者名(英) |
Kazuki, Nakajima
× Kazuki, Nakajima
× Kazuyuki, Shudo
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The betweenness centrality is a widely used property to identify important nodes in social networks. Several algorithms have been studied to efficiently compute the top-k nodes with the highest betweenness centrality on a graph where all the data is available. However, all the graph data of real social networks are not typically available to third parties such as researchers or marketers, and hence, an estimation algorithm based on sampling the graph data is required. Accurately estimating the top-k nodes with the highest betweenness centrality from a small sample of a graph is a challenging task. First, the top-k nodes need to be included in the small sample. Second, nodes with the high betweenness centrality that is defined on the whole graph need to be accurately identified from the small sample. We propose a random walk-based algorithm to estimate the top-k nodes with the highest betweenness centrality by utilizing the ego betweenness centrality that has a high correlation with the betweenness centrality in social networks. The proposed algorithm firstly obtains a small sample that includes many of top-k nodes with the highest betweenness centrality via a random walk on a social network. Then, we obtain unbiased estimates of the ego betweenness centrality of sampled nodes and approximate the top-k nodes with the highest betweenness centrality as the top-k nodes with the highest estimated ego betweenness centrality. The proposed estimator efficiently estimates the ego betweenness centrality of each sample without additionally sampling the graph data by utilizing the neighbor data of the previous and the next samples. The experiments using real social network datasets show that the proposed algorithm estimates more accurately the top-k nodes with the highest betweenness centrality than existing algorithms when the sample size is small. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.28(2020) (online) ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The betweenness centrality is a widely used property to identify important nodes in social networks. Several algorithms have been studied to efficiently compute the top-k nodes with the highest betweenness centrality on a graph where all the data is available. However, all the graph data of real social networks are not typically available to third parties such as researchers or marketers, and hence, an estimation algorithm based on sampling the graph data is required. Accurately estimating the top-k nodes with the highest betweenness centrality from a small sample of a graph is a challenging task. First, the top-k nodes need to be included in the small sample. Second, nodes with the high betweenness centrality that is defined on the whole graph need to be accurately identified from the small sample. We propose a random walk-based algorithm to estimate the top-k nodes with the highest betweenness centrality by utilizing the ego betweenness centrality that has a high correlation with the betweenness centrality in social networks. The proposed algorithm firstly obtains a small sample that includes many of top-k nodes with the highest betweenness centrality via a random walk on a social network. Then, we obtain unbiased estimates of the ego betweenness centrality of sampled nodes and approximate the top-k nodes with the highest betweenness centrality as the top-k nodes with the highest estimated ego betweenness centrality. The proposed estimator efficiently estimates the ego betweenness centrality of each sample without additionally sampling the graph data by utilizing the neighbor data of the previous and the next samples. The experiments using real social network datasets show that the proposed algorithm estimates more accurately the top-k nodes with the highest betweenness centrality than existing algorithms when the sample size is small. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.28(2020) (online) ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA11464847 | |||||||||
| 書誌情報 |
情報処理学会論文誌データベース（TOD） 巻 13, 号 3, 発行日 2020-07-16 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7799 | |||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
