| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-01-18 10:30 ランダムウォークを用いたハイパーグラフにおけるローカルコミュニティと弱い紐帯の抽出 ○岡 亮（慶大）・高井勇輝（理研）・松本直己（慶大）・池田正弘（理研）・金子晋丈（慶大）  IN2020-41 |
|
| 抄録 | （和） | コンテンツを頂点，その関係性を枝とするグラフを活用したサービスが多く普及している．コミュニティ抽出あるいはグラフクラスタリングは，グラフの特徴を把握するための基本的な問題である．ここでの「コミュニティ」とは，グラフ内で相対的に高密度な頂点集合と定義される．しかし，既存の多くのコミュニティ抽出アルゴリズムは全体グラフを対象とした解析が多く，全体グラフを入手できない場合には解析不可能である．また既存手法の多くはハイパーグラフを対象としていない．そこで本研究では，Personalized PageRankに基づいたランダムウォークによってハイパーグラフの解析範囲を始点周辺に限定しながら，始点を含むコミュニティ(ローカルコミュニティ)とローカルコミュニティの外に出る枝(弱い紐帯)を抽出するためのアルゴリズムとその評価方法を提案する．そしてground-truthコミュニティを持つ，ハイパーグラフのStochastic Block Modelによって作成した合成ネットワークと既存の評価指標を用いて，ランダムウォークの試行回数とその精度の関係を明らかにした．結果として，頂点数1000，弱い紐帯の割合が$mu=0.1-0.9$であるハイパーグラフを用いて，2000ステップのランダムウォークが訪問した頂点をpower methodをベースに並び替えた時，$mu=0.1-0.5$でコミュニティの$F_1$値が0.8以上を維持できることが明らかになった． |
| （英） | There are many services that use a graph with a content as a vertex and their relationship as a edge. Community detection or graph clustering is one of the fundamental problems in graph characterization. The word "community" here is defined as a relatively dense set of vertices in a graph. Many existing community detection algorithms often assume the analysis of the global graph, but it is difficult to analyze the global graph as they would like. Also, many existing methods do not assume hypergraphs. We propose an algorithm for extracting the local community that include the starting vertex and the weak ties connected to it, while limiting range of the analysis of the graph to the surrounding of the starting vertex by random walk based on Personalized PageRank. We then reveal the relationship between the number of random walk trials and their accuracy using existing metrics and a synthetic network with ground-truth community. As a result, using hypergraphs which has 1000 vertices created by Stochastic Block Model, we found that the $F_1$ value of the community can remain above about 0.8 for $mu =0.1-0.5$ during a random walk of 2000 steps. | |
| キーワード | （和） | コミュニティ抽出 / 弱い紐帯 / ランダムウォーク / ハイパーグラフ / personalized pagerank / / / |
| （英） | community detection / weak ties / random walk / hypergraph / personalized pagerank / / / | |
| 文献情報 | 信学技報, vol. 120, no. 311, IN2020-41, pp. 1-6, 2021年1月. | |
| 資料番号 | IN2020-41 | |
| 発行日 | 2021-01-11 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2020-41 |
|
| 研究会情報 | |
| 研究会 | IN |
| 開催期間 | 2021-01-18 - 2021-01-19 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | コンテンツ配信/流通、ソーシャルネットワーク(SNS)、データ分析・処理基盤、ビッグデータ及び一般 |
| テーマ（英） | Contents Distribution, Social Networking Services, Data Analytics and Processing Platform, Big data, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2021-01-IN |
| 本文の言語 | 日本語 |
| タイトル（和） | ランダムウォークを用いたハイパーグラフにおけるローカルコミュニティと弱い紐帯の抽出 |
| サブタイトル（和） | |
| タイトル（英） | Local community and weak ties detection using random walk on hypergraph. |
| サブタイトル（英） | |
| キーワード(1)（和/英） | コミュニティ抽出 / community detection |
| キーワード(2)（和/英） | 弱い紐帯 / weak ties |
| キーワード(3)（和/英） | ランダムウォーク / random walk |
| キーワード(4)（和/英） | ハイパーグラフ / hypergraph |
| キーワード(5)（和/英） | personalized pagerank / personalized pagerank |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 岡 亮 / Ryo Oka / オカ リョウ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 高井 勇輝 / Yuuki Takai / マツモト ナオキ |
| 第2著者 所属（和/英） | 理化学研究所 革新知能統合研究センター (略称： 理研) RIKEN Center for Advanced Intelligence Project (略称： RIKEN) |
| 第3著者 氏名（和/英/ヨミ） | 松本 直己 / Naoki Matsumoto / タカイ ユウキ |
| 第3著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 池田 正弘 / Masahiro Ikeda / イケダ マサヒロ |
| 第4著者 所属（和/英） | 理化学研究所 革新知能統合研究センター (略称： 理研) RIKEN Center for Advanced Intelligence Project (略称： RIKEN) |
| 第5著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第5著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-01-18 10:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2020-41 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.311 |
| ページ範囲 | pp.1-6 |
| ページ数 | 6 |
| 発行日 | 2021-01-11 (IN) |
[研究会発表申込システムのトップページに戻る]