| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-03-13 14:30 サンプリンググラフに対するグラフ要約の有効性評価に関する検討 ○松尾涼太郎・中村 遼（福岡大）  CQ2023-75 |
|
| 抄録 | （和） | 近年、「要約グラフ (summary graph) 」と呼ばれる、与えられたグラフから、そのグラフが有する構造的特徴を可能な限り保持したまま、多数のノード (頂点) やエッジ (辺) を集約させた、コンパクトなグラフ表現が注目を浴びている。著者らが知る限り、これまでに検討されているグラフ要約の研究では、大規模グラフ「全体」のトポロジ (構造) が明示的に与えられることを仮定している。しかしながら、現実世界の大規模ネットワークを対象とする時、一般に、そのトポロジ全体を取得することは困難であるため、その「一部」しか与えられない場合も考慮する必要がある。そこで我々は、大規模グラフの一部のトポロジが明示的に与えられた場合におけるグラフ要約に着目し、その要約グラフから、元のグラフの構造的特徴を、どの程度表現できるか、つまり、部分グラフの要約グラフから元の要約グラフ (グラフ全体のトポロジから求められるグラフ) をどの程度表現できるか、を調査する。本稿では、大規模グラフの部分グラフに対するグラフ要約の初期検討として、部分グラフの要約グラフが、元の要約グラフと比較して、どの程度異なるかを、実験を通して、調査する。具体的には、人工ネットワークおよび現実ネットワークにおいて、グラフサンプリング方式により抽出される部分グラフから、グラフ要約アルゴリズムを用いて求められる、要約グラフと、元の要約グラフとの、構造上の違いを、スペクトル構造の距離およびグラフの直径という観点で、評価する。その結果として、コミュニティ構造を有するグラフでは、その部分グラフから、元の要約グラフを表現しやすいことなどを示す。 |
| （英） | In recent years, a compact graph representation called {em summary graph} has been extensively studied. This representation aims to aggregate a large number of nodes (vertices) and edges from a given graph while retaining as much of the structural features of the graph as possible. To the best of our knowledge, previous works on graph summarization assume that the "entire" topology (structure) of large-scale graphs is explicitly given. However, when dealing with real-world large-scale networks, it is often challenging to acquire the entire topology, so it is necessary to consider the case where only a "part" of the topology is given. Therefore, we focus on graph summarization in the case where the topology of a part of a large graph is explicitly given. We investigate to what extent the summary graph can represent the structural features of the original graph (i.e., how well a summary graph from a subgraph can represent the original summary graph derived from the entire graph's topology). In this paper, as an initial work of graph summarization for subgraphs of large graphs, we investigate how different the summary graph of a subgraph is compared to the original summary graph through experiments. Specifically, on both synthetic and real networks, we evaluate the structural differences between the summary graph obtained using a graph summarization algorithm from subgraphs extracted by graph sampling techniques, and the original summary graph, in terms of the distance of the spectral structure and the graph's diameter. As a consequence, we show, for instance, that it is easier to represent the original summary graph from subgraphs in graphs with community structures. | |
| キーワード | （和） | 要約グラフ / 大規模グラフ / グラフサンプリング / / / / / |
| （英） | Summary Graph / Large-Scale Graph / Graph Sampling / / / / / | |
| 文献情報 | 信学技報, vol. 123, no. 431, CQ2023-75, pp. 26-31, 2024年3月. | |
| 資料番号 | CQ2023-75 | |
| 発行日 | 2024-03-06 (CQ) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CQ2023-75 |
|
| 研究会情報 | |
| 研究会 | IE MVE CQ IMQ |
| 開催期間 | 2024-03-13 - 2024-03-15 |
| 開催地（和） | 沖縄産業支援センター |
| 開催地（英） | Okinawa Sangyo Shien Center |
| テーマ（和） | 五感に訴えるオンラインメディアとその評価，および一般（魅力工学研究会協賛） |
| テーマ（英） | Media of five senses, Multimedia, Media experience, Picture codinge, Image media quality, Network,quality and reliability, etc（AC） |
| 講演論文情報の詳細 | |
| 申込み研究会 | CQ |
| 会議コード | 2024-03-IE-MVE-CQ-IMQ |
| 本文の言語 | 日本語 |
| タイトル（和） | サンプリンググラフに対するグラフ要約の有効性評価に関する検討 |
| サブタイトル（和） | |
| タイトル（英） | Study on Evaluating the Effectiveness of Graph Summarization for Sampling Graphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 要約グラフ / Summary Graph |
| キーワード(2)（和/英） | 大規模グラフ / Large-Scale Graph |
| キーワード(3)（和/英） | グラフサンプリング / Graph Sampling |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 松尾 涼太郎 / Ryotaro Matsuo / マツオ リョウタロウ |
| 第1著者 所属（和/英） | 福岡大学 (略称： 福岡大) Fukuoka University (略称： Fukuoka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 中村 遼 / Ryo Nakamura / ナカムラ リョウ |
| 第2著者 所属（和/英） | 福岡大学 (略称： 福岡大) Fukuoka University (略称： Fukuoka Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-03-13 14:30:00 |
| 発表時間 | 20分 |
| 申込先研究会 | CQ |
| 資料番号 | CQ2023-75 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | no.431 |
| ページ範囲 | pp.26-31 |
| ページ数 | 6 |
| 発行日 | 2024-03-06 (CQ) |
[研究会発表申込システムのトップページに戻る]