| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-07-31 15:05 ランダムウォークに基づく興味ノード群を媒介する部分グラフの選択 ○岡田和真・山下剛志・金子晋丈（慶大）  IN2025-15 |
|
| 抄録 | （和） | グラフにおいて，ユーザが興味をもつ2 つのコミュニティ同士を媒介する部分グラフを挿入することで，ユーザの興味の連続的な拡張が実現する．その際，双方のコミュニティからのランダムウォーク（RW）が均等に到達するように挿入される部分グラフが選ばれることが望ましい．しかし，挿入候補が多数存在する場合，すべての候補グラフに対して挿入時のコミュニティ間のRW の到達量を演算することは困難である．そこで本研究では，挿入グラフごとに事前演算したRW の到達量を活用することで，挿入時のRW 到達量を軽量に評価し，挿入候補を絞り込むためのスコアを提案する．具体的には，挿入グラフのみに着目して，コミュニティと挿入グラフとの共通ノード群から RW の到達量を事前演算する．実世界のグラフを用いた評価では，提案手法の精度および計算時間を測定した．その結果，スコアの上位1% の候補グラフは最大25% の確率で有効な部分グラフであり，計算時間は1 つずつ挿入しながら演算する手法より最大139 倍の高速化を達成することが明らかになった． |
| （英） | In graph-based systems, inserting a subgraph that bridges two communities of user interests enables continuous expansion of user interests. For optimal bridging, the inserted subgraph should be equally accessible to random walks (RW) originating from both communities. However, when numerous candidate subgraphs exist, computing RW reachability from both communities for each insertion becomes computationally prohibitive. To address this challenge, we propose a scoring method that leverages precomputed RW arrival rates for each candidate subgraph to efficiently evaluate their impact on RW reachability at the time of insertion. Our approach focuses exclusively on the insertion subgraph itself, precomputing RW arrival rates from nodes shared between the candidate subgraph and each community. We evaluate our method on real-world graphs in terms of both accuracy and computational efficiency. Results demonstrate that the top 10% of subgraphs ranked by our scoring method achieve up to 83% accuracy in identifying valid bridging subgraphs, while reducing computation time by up to 69 times compared to conventional methods that evaluate each insertion individually. | |
| キーワード | （和） | グラフ / ランダムウォーク / グラフ挿入 / / / / / |
| （英） | graph / random walk / graph insertion / / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 137, IN2025-15, pp. 25-30, 2025年7月. | |
| 資料番号 | IN2025-15 | |
| 発行日 | 2025-07-24 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2025-15 |
|
| 研究会情報 | |
| 研究会 | CCS IN |
| 開催期間 | 2025-07-31 - 2025-08-01 |
| 開催地（和） | 北海道大学 FMI フード＆メディカルイノベーション国際拠点 |
| 開催地（英） | Global Research Center for Food & Medical Innovation, Hokkaido Univ |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2025-07-CCS-IN |
| 本文の言語 | 日本語 |
| タイトル（和） | ランダムウォークに基づく興味ノード群を媒介する部分グラフの選択 |
| サブタイトル（和） | |
| タイトル（英） | Selecting Subgraphs for Bridging Interest Nodes Based on Random Walks |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | ランダムウォーク / random walk |
| キーワード(3)（和/英） | グラフ挿入 / graph insertion |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岡田 和真 / Kazuma Okada / オカダ カズマ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-07-31 15:05:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2025-15 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.137 |
| ページ範囲 | pp.25-30 |
| ページ数 | 6 |
| 発行日 | 2025-07-24 (IN) |
[研究会発表申込システムのトップページに戻る]