| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-01-23 14:05 次数バイアス付きランダムウォークを用いた重要なグラフ固有値の推定方法の検討 ○尾崎遼介・作元雄輔・大崎博之（関西学院大）  IA2024-62 |
|
| 抄録 | （和） | ネットワークの隣接行列やラプラシアン行列，ウォーク行列など重要な固有値(グラフ固有値)は，様々なグラフアルゴリズムの設計や分析に役立てられている．一般に，グラフ固有値を計算するためには，ネットワーク全体の情報を収集し，行列を明示的に構築する必要がある．ソーシャルネットワークなどの大規模かつ秘匿性の高いネットワークにおいては全体の情報収集に膨大なコストを要してしまうため，一部のノードを観測することで重要なグラフ固有値を推定する方法が検討されている．従来の方法である cWalker は，単純ランダムウォークを用いたノードサンプリングによって，ネットワークの一部の情報から隣接行列の固有値を推定することに成功している．本稿では，cWalker を拡張し，隣接行列だけでなくウォーク行列の重要な固有値を推定できる方法 cWalker' を検討する．次数バイアス付きランダムウォークを用いて cWalker' を設計し，設計した cWalker' が実際のソーシャルネットワークに対する固有値推定に有効であることを確認する． |
| （英） | Important eigenvalues of network matrices such as adjacency matrices, Laplacian matrices, and walk matrices have been utilized in the design and analysis of various graph algorithms. Generally, in order to compute these eigenvalues, it is necessary to collect complete information from the entire network and explicitly construct the matrices. For large-scale networks with high confidentiality, such as social networks, collecting complete information is prohibitively costly. Therefore, some methods to estimate important eigenvalues by observing only a subset of nodes have been proposed. The existing method, cWalker, has been successful in estimating the eigenvalues of the adjacency matrix from partial information of the network using simple random node sampling. In this paper, we discuss an extension of cWalker, named cWalker', which can also estimate important eigenvalues of the walk matrix. We design cWalker' using a degree-biased random walk, and confirm the effectiveness of cWalker' in estimating eigenvalues for real social networks. | |
| キーワード | （和） | スペクトラルグラフ理論 / 隣接行列 / ウォーク行列 / 正規化ラプラシアン行列 / 固有値推定 / / / |
| （英） | Spectral Graph Theory / Adjacency Matrix / Walk Matrix / Normalized Laplacian Matrix / Eigenvalue Estimation / / / | |
| 文献情報 | 信学技報, vol. 124, no. 350, IA2024-62, pp. 3-9, 2025年1月. | |
| 資料番号 | IA2024-62 | |
| 発行日 | 2025-01-16 (IA) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IA2024-62 |
|
| 研究会情報 | |
| 研究会 | IA |
| 開催期間 | 2025-01-23 - 2025-01-23 |
| 開催地（和） | NICT イノベーションセンター |
| 開催地（英） | NICT Innovation Center |
| テーマ（和） | センサー ネットワーク, IoT, M2M, 一般 |
| テーマ（英） | Sensor Network, IoT, M2M, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IA |
| 会議コード | 2025-01-IA |
| 本文の言語 | 日本語 |
| タイトル（和） | 次数バイアス付きランダムウォークを用いた重要なグラフ固有値の推定方法の検討 |
| サブタイトル（和） | |
| タイトル（英） | Preliminary Study on Constructing a Method for Estimating Important Eigenvalues of Graph Matrices Using Degree-Biased Random Walk |
| サブタイトル（英） | |
| キーワード(1)（和/英） | スペクトラルグラフ理論 / Spectral Graph Theory |
| キーワード(2)（和/英） | 隣接行列 / Adjacency Matrix |
| キーワード(3)（和/英） | ウォーク行列 / Walk Matrix |
| キーワード(4)（和/英） | 正規化ラプラシアン行列 / Normalized Laplacian Matrix |
| キーワード(5)（和/英） | 固有値推定 / Eigenvalue Estimation |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 尾崎 遼介 / Ryosuke Ozaki / オザキ リョウスケ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 作元 雄輔 / Yusuke Sakumoto / サクモト ユウスケ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 大崎 博之 / Hiroyuki Ohsaki / オオサキ ヒロユキ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-01-23 14:05:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IA |
| 資料番号 | IA2024-62 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.350 |
| ページ範囲 | pp.3-9 |
| ページ数 | 7 |
| 発行日 | 2025-01-16 (IA) |
[研究会発表申込システムのトップページに戻る]