| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-12-20 13:30 サンプリングとクローリングを組み合わせた高い連結性を有するグラフ縮小手法 ○佐藤 空・山下剛志・金子晋丈（慶大）  IN2024-72 |
|
| 抄録 | （和） | 近年，セキュリティ等で全グラフの利用が困難なため，縮小グラフによるデータ間の関係理解が重要となっている． 特に，ユーザの興味ノード近傍と様々なコミュニティのノードを隣接情報として辿れるような縮小グラフは有用である．しかし既存の縮小手法は特定コミュニティへの偏りが大きく，前述のような縮小は困難である．そこで本研究では，Random Walk（RW）ベースのサンプリングと，コミュニティの境界ノードに遷移しやすくしたクローリングを用いることで，そのようなグラフを提供可能とする．具体的には，ある１ノードとその隣接からなる部分グラフ密度を示すエゴネットワーク密度を用い，境界ノードにたどり着きやすくしたクローリングと，その手法と高次数ノード程高確率となる遷移確率を切り替えることで，クローリンググラフと連結しやすくしたサンプリング手法を提案した．実験では元グラフをコミュニティ分割した後，元グラフと縮小グラフにおいて各コミュニティへの到達しやすさをRWer流量を用いて評価した．その結果，類似度指標であるコサイン類似度が既存手法に比べて約0.2高い値を示し，各コミュニティへの到達しやすさが縮小グラフと元グラフで類似することが分かった． |
| （英） | In recent years, the use of entire graphs has become increasingly challenging due to security concerns, highlighting the importance of understanding relationships between data through reduced graphs.Reduced graphs that allow traversal of adjacency information, including nodes near a user’s nodes of interest and nodes from various communities, are particularly valuable.However, existing reduction methods often exhibit significant bias toward specific communities, making such reductions difficult to achieve.To address this issue, this study proposes a method that leverages Random Walk (RW)-based sampling and crawling enhanced to facilitate transitions to community boundary nodes, enabling the creation of such reduced graphs.Specifically, the proposed approach employs ego network density—a measure of the density of a subgraph composed of a node and its neighbors—to perform crawling that more effectively reaches boundary nodes.Additionally, by switching between this crawling method and a transition probability that favors high-degree nodes, the sampling method ensures better connectivity with the crawling graph.In experiments, we partitioned the original graph into communities and evaluated the ease of reaching each community in both the original and reduced graphs using RW flow.The results showed that the cosine similarity, a measure of resemblance, was approximately 0.2 higher than existing methods, demonstrating that the reduced graph maintains accessibility to communities similar to the original graph. | |
| キーワード | （和） | サンプリング / クローリング / エゴネットワーク / コミュニティ / ランダムウォーク / / / |
| （英） | sampling / crawling / ego network / community / random walk / / / | |
| 文献情報 | 信学技報, vol. 124, no. 312, IN2024-72, pp. 99-106, 2024年12月. | |
| 資料番号 | IN2024-72 | |
| 発行日 | 2024-12-12 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2024-72 |
|
| 研究会情報 | |
| 研究会 | IN IA |
| 開催期間 | 2024-12-19 - 2024-12-20 |
| 開催地（和） | デザイン・クリエイティブセンター神戸 (KIITO) |
| 開催地（英） | KIITO |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、CCN・ICN、マルチキャスト、ルーティング、セキュリティ及び一般 |
| テーマ（英） | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, CCN, ICN, Multicast, Routing, Security, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2024-12-IN-IA |
| 本文の言語 | 日本語 |
| タイトル（和） | サンプリングとクローリングを組み合わせた高い連結性を有するグラフ縮小手法 |
| サブタイトル（和） | |
| タイトル（英） | Graph Reduction Method Combining Sampling and Crawling with High Connectivity |
| サブタイトル（英） | |
| キーワード(1)（和/英） | サンプリング / sampling |
| キーワード(2)（和/英） | クローリング / crawling |
| キーワード(3)（和/英） | エゴネットワーク / ego network |
| キーワード(4)（和/英） | コミュニティ / community |
| キーワード(5)（和/英） | ランダムウォーク / random walk |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 佐藤 空 / Sora Satoh / サトウ ソラ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-12-20 13:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2024-72 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.312 |
| ページ範囲 | pp.99-106 |
| ページ数 | 8 |
| 発行日 | 2024-12-12 (IN) |
[研究会発表申込システムのトップページに戻る]