| 講演名 | 2021-01-18 ランダムウォークを用いたハイパーグラフにおけるローカルコミュニティと弱い紐帯の抽出 岡 亮(慶大), 高井 勇輝(理研), 松本 直己(慶大), 池田 正弘(理研), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | コンテンツを頂点，その関係性を枝とするグラフを活用したサービスが多く普及している．コミュニティ抽出あるいはグラフクラスタリングは，グラフの特徴を把握するための基本的な問題である．ここでの「コミュニティ」とは，グラフ内で相対的に高密度な頂点集合と定義される．しかし，既存の多くのコミュニティ抽出アルゴリズムは全体グラフを対象とした解析が多く，全体グラフを入手できない場合には解析不可能である．また既存手法の多くはハイパーグラフを対象としていない．そこで本研究では，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 |
| 資料番号 | IN2020-41 |
| 発行日 | 2021-01-11 (IN) |
| 研究会情報 | |
| 研究会 | IN |
|---|---|
| 開催期間 | 2021/1/18(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | コンテンツ配信/流通、ソーシャルネットワーク(SNS)、データ分析・処理基盤、ビッグデータ及び一般 |
| テーマ（英） | Contents Distribution, Social Networking Services, Data Analytics and Processing Platform, Big data, etc. |
| 委員長氏名（和） | 石田 賢治(広島市大) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) |
| 副委員長氏名（英） | Kunio Hato(Internet Multifeed) |
| 幹事氏名（和） | 小畑 博靖(広島市大) / 樫原 俊太郎(KDDI総合研究所) / 谷口 展郎(NTT) / 星野 文学(NTT) |
| 幹事氏名（英） | Hiroyasu Obata(Hiroshima City Univ.) / Shuntaro Kashihara(KDDI Research) / Noburo Taniguchi(NTT) / Fumitaka Hoshino(NTT) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ランダムウォークを用いたハイパーグラフにおけるローカルコミュニティと弱い紐帯の抽出 |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| 第 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.) |
| 発表年月日 | 2021-01-18 |
| 資料番号 | IN2020-41 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | IN-311 |
| ページ範囲 | pp.1-6(IN), |
| ページ数 | 6 |
| 発行日 | 2021-01-11 (IN) |