| 講演名 | 2022-05-27 グラフ接続によって変化する経路に注目した媒介中心性の推測 宮越 桂仁(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 媒介中心性は，グラフ内の最短経路に対象となる頂点が含まれる回数を表す重要性指標であり，グラフを用いたコンテンツ探索において有用である．将来的に重要なコンテンツを探索することにおいて，これからグラフに起こる枝追加や頂点追加などにより，変化する頂点の媒介中心性を推測することは重要である．しかし，一般に非連結なグラフAとグラフBに枝を追加して，接続後のグラフAの媒介中心性を推測する場合，グラフをまたぐグラフ間経路が発生し，グラフAの2頂点を端点とするグラフA内の経路が更新されるため，接続後の媒介中心性は推測不可能なほど大きく変化する．そこで本研究では，グラフAとグラフBの接続を2枝に限定し，接続頂点間の距離$l_A,l_B$が$l_A > l_B$のとき，グラフ間経路とグラフA内の経路による媒介中心性変化量をグラフAのトポロジと$l_A,l_B$，グラフBの頂点数$n_B$のみで近似することで，接続後のグラフAの媒介中心性をグラフBのトポロジに依存せずに推測することを目的とする．500頂点，1500枝数のグラフで，誤差率0.01未満を満たす頂点の割合によって評価したところ，グラフ間経路のみによる媒介中心性変化量の近似で60％以上，グラフA内の経路のみによる近似で60％以上を達成した．また，グラフ間経路とグラフA内の経路両方による近似では，誤差率0.1未満を満たす頂点の割合が70％以上を達成した． |
| 抄録(英) | Betweenness Centrality(BC) is an importance measure that expresses the number of times a target vertex is included in the shortest path in the graph. Apporoximation BC is in useful in Content Search. However, after connecting graphs A and B, BC of graph A changes so significantly that it is impossible to Apporoximate. This is because the path between graphs A and B opens and the path in graph A is updated. In this study, we approximate BC change due to paths between graphs and paths in graph A using only the topology of graph A, $l_A,l_B$ and the number of vertices $n_B$ in graph B. We allow only connections with two edges, $l_A,l_B$ represent the distance between connected vertices. Our aim is to approximate BC of graph A after the connection, without the topology of graph B. As a result of the evaluation, the approximation of the paths between graphs and the paths in graph A respectively achieved a percentage of vertices with an error rate of less than 0.01 of more than 60％. And, the approximation both paths achieved a percentage of vertices with an error rate of less than 0.1 of more than 70％. |
| キーワード(和) | 媒介中心性 / 動的な媒介中心性計算 / グラフ接続 / 媒介中心性指標の推測 |
| キーワード(英) | Betweenness Centrality / Dynamic Betweenness Centrality calculations / Graph Connections / Apporoximation Betweenness Centrality |
| 資料番号 | IN2022-11 |
| 発行日 | 2022-05-19 (IN) |
| 研究会情報 | |
| 研究会 | IN / RCS |
|---|---|
| 開催期間 | 2022/5/26(から2日開催) |
| 開催地（和） | 慶應大学 日吉キャンパス |
| 開催地（英） | Keio University (Hiyoshi Campus) |
| テーマ（和） | アドホック・センサネットワーク・MANET，モバイルネットワーク，M2M・IoT通信制御，無線LAN(Wi-Fi)，IEEE802.15(ZigBee)及び一般 |
| テーマ（英） | Ad-Hoc/Sensor Networks/MANET, Mobile Networks, M2M/IoT Communications, Wi-Fi, IEEE802.15(ZigBee) and others |
| 委員長氏名（和） | 石田 賢治(広島市大) / 岡本 英二(名工大) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) / Eiji Okamoto(Nagoya Inst. of Tech.) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 西村 寿彦(北大) / 旦代 智哉(東芝) / 児島 史秀(NICT) |
| 副委員長氏名（英） | Kunio Hato(Internet Multifeed) / Toshihiko Nishimura(Hokkaido Univ.) / Tomoya Tandai(Toshiba) / Fumihide Kojima(NICT) |
| 幹事氏名（和） | 谷口 展郎(NTT) / 星野 文学(長崎県立大) / 渡部 康平(長岡技科大) / 城 哲(KDDI総合研究所) / 村岡 一志(NEC) / 山本 哲矢(パナソニック) |
| 幹事氏名（英） | Noburo Taniguchi(NTT) / Fumitaka Hoshino(Univ. of Nagasaki) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Tetsu Jyo(KDDI Research) / Kazushi Muraoka(NEC) / Tetsuya Yamamoto(Panasonic) |
| 幹事補佐氏名（和） | / 安達 宏一(電通大) / 中村 理(シャープ) / 酒井 学(三菱電機) / 岩渕 匡史(NTT) / 奥山 達樹(NTTドコモ) |
| 幹事補佐氏名（英） | / Koichi Adachi(Univ. of Electro-Comm.) / Osamu Nakamura(Sharp) / Manabu Sakai(Mitsubishi Electric) / Masashi Iwabuchi(NTT) / Tatsuki Okuyama(NTT DOCOMO) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Radio Communication Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | グラフ接続によって変化する経路に注目した媒介中心性の推測 |
| サブタイトル（和） | |
| タイトル（英） | Apporoximation Betweenness Centrality focusing on paths affected by the connection of two graph |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 媒介中心性 / Betweenness Centrality |
| キーワード(2)（和/英） | 動的な媒介中心性計算 / Dynamic Betweenness Centrality calculations |
| キーワード(3)（和/英） | グラフ接続 / Graph Connections |
| キーワード(4)（和/英） | 媒介中心性指標の推測 / Apporoximation Betweenness Centrality |
| 第 1 著者 氏名（和/英） | 宮越 桂仁 / Kaito Miyakoshi |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2022-05-27 |
| 資料番号 | IN2022-11 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | IN-48 |
| ページ範囲 | pp.50-55(IN), |
| ページ数 | 6 |
| 発行日 | 2022-05-19 (IN) |