| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-07-30 10:15 第三者グラフ利用のためのエッジ遷移確率に基づく重み付きグラフ要約 ○岡松紀伸・山下剛志・金子晋丈（慶大）  IN2024-24 |
|
| 抄録 | （和） | グラフ利用者である第三者にグラフを提供する際には，分析コストの低減と情報の秘匿化の側面から，グラフ要約手法が有用である． グラフ要約とは，構造的に類似する複数のノード集合を集約して一つのノードとみなすことで，特徴を維持しながらグラフを縮小する手法である． 既存のグラフ要約手法では，要約後のグラフにおいて，グラフ解析の基盤技術であるランダムウォーク演算の誤差が大きくなる． その理由は，要約時に元グラフのランダムウォークの遷移情報を維持していないからである． そこで本研究では，元グラフのランダムウォークの遷移情報を要約グラフにおけるエッジの重みに反映する手法を提案し，要約グラフ上でのランダムウォーク演算の誤差を削減する． 具体的には，元グラフにおけるランダムウォークの滞在確率や遷移確率を用いて，要約グラフの エッジの重みを決定する． 実世界のグラフデータを用いた評価では，要約グラフに対してランダムウォーク演算の一種である PageRank 演算を実行し，提案手法は既存手法により生じた誤差率を最大で約92% 削減した． |
| （英） | When providing graphs to third party graph users, graph summarization methods are useful for reducing the cost of analysis and protecting privacy. Graph summarization is a method of reducing the size of a graph while preserving its features by aggregating multiple structurally similar nodes into one node. In existing graph summarization methods, the error in random walks, which is a fundamental technology for graph analysis, becomes significant on summary graphs. This is because the transition information of random walks on the original graph is not preserved during summarization. Therefore, we propose a method to reflect the transition information of random walks on the original graph into the edge weights of the summary graph and reduce the error of random walks on the summary graph. Specifically, the edge weights in the summary graph are determined using the expected number of stays and transition probabilities of random walks on the original graph. In an evaluation using real-world graph data, the PageRank computation, which is a type of random walk computation, was executed on summary graphs. As a result, our method reduced the error rate caused by existing methods by up to approximately 92%. |
|
| キーワード | （和） | グラフ / グラフ要約 / ランダムウォーク / / / / / |
| （英） | Graph / Graph Summarization / Random Walks / / / / / | |
| 文献情報 | 信学技報, vol. 124, no. 139, IN2024-24, pp. 83-88, 2024年7月. | |
| 資料番号 | IN2024-24 | |
| 発行日 | 2024-07-22 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2024-24 |
|
| 研究会情報 | |
| 研究会 | IN CCS |
| 開催期間 | 2024-07-29 - 2024-07-30 |
| 開催地（和） | モエレ沼公園 ガラスのピラミッド（北海道札幌市） |
| 開催地（英） | Moerenuma Park Glass Pyramid |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2024-07-IN-CCS |
| 本文の言語 | 日本語 |
| タイトル（和） | 第三者グラフ利用のためのエッジ遷移確率に基づく重み付きグラフ要約 |
| サブタイトル（和） | |
| タイトル（英） | Weighted Graph Summarization Based on Edge Transition Probabilities for Third-Party Graph Utilization |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ / Graph |
| キーワード(2)（和/英） | グラフ要約 / Graph Summarization |
| キーワード(3)（和/英） | ランダムウォーク / Random Walks |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岡松 紀伸 / Kishin Okamatsu / オカマツ キシン |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-07-30 10:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2024-24 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.139 |
| ページ範囲 | pp.83-88 |
| ページ数 | 6 |
| 発行日 | 2024-07-22 (IN) |
[研究会発表申込システムのトップページに戻る]