| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2024-12-20 10:30 ランダムウォークのエッジ還流度に基づく小規模コミュニティ抽出手法 ○山内隆史・山下剛志（慶大）・松本直己（琉球大）・金子晋丈（慶大）  IN2024-68 |
|
| 抄録 | （和） | コミュニティ抽出は，SNSなどのグラフを用いたサービスのレコメンデーションにおいて注目されている． 特に，小規模コミュニティ抽出は，利用者の注目頂点を内包する最小単位の情報グループを探索する点において重要である．しかしながら，代表的なコミュニティ抽出手法であるLouvain法が用いるモジュラリティは，ランダムグラフと比較した密度度合いを定量化しており，その解像度限界が小規模コミュニティ抽出を困難にしている．そこで，本研究ではランダムウォークのエッジ再訪率を定量化したエッジ還流度に基づいた手法を提案する．具体的にはエッジの双方向性と還流のマクロ性を考慮し，エッジ還流度を無向化し頂点の次数で重みづけした重み付け無向エッジ還流度の極小値を用いてオーバラップのないコミュニティ境界を特定する．この手法をFacebook のデータセットに適用し，$alpha$が0.05 のときに，Louvain 法とほぼ同規模で同一の頂点群が全て含まれたコミュニティが抽出できることを確認した．加えて，$alpha$を0.05よりも大きくすることでより小規模な連結したコミュニティを抽出できることを確認した． |
| （英） | Community detection has garnered attention in recommendation systems based on graph-based services such as social networking services (SNS). In particular, the extraction of small-scale communities is crucial for identifying the smallest information groups that encapsulate a user's point of interest. However, modularity, a measure widely used in the Louvain method, quantifies the density of a graph relative to a random graph. While effective in identifying broader structures, its inherent resolution limit makes it difficult to detect smaller-scale communities. In this study, we propose a novel method based on edge recirculation, which quantifies the rate of edge revisitation in random walks. Specifically, we consider the bidirectionality of edges and the macroscopic properties of recirculation, utilizing a degree-weighted undirected edge recirculation measure to identify community boundaries without overlaps. We applied this method to Facebook datasets and confirmed that when $alpha=0.05$, the method successfully extracts communities of comparable scale to those identified by the Louvain method, while including all vertex groups identified by Louvain. Furthermore, by increasing $alpha$ beyond 0.05, the method demonstrated its ability to extract smaller, tightly connected communities. | |
| キーワード | （和） | ランダムウォーク / コミュニティ抽出 / 小規模コミュニティ / エッジ還流度 / / / / |
| （英） | Random Walk / Community Detection / Small-Scale Community / Edge Recirculation / / / / | |
| 文献情報 | 信学技報, vol. 124, no. 312, IN2024-68, pp. 73-80, 2024年12月. | |
| 資料番号 | IN2024-68 | |
| 発行日 | 2024-12-12 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2024-68 |
|
| 研究会情報 | |
| 研究会 | IN IA |
| 開催期間 | 2024-12-19 - 2024-12-20 |
| 開催地（和） | デザイン・クリエイティブセンター神戸 (KIITO) |
| 開催地（英） | KIITO |
| テーマ（和） | 性能評価とシミュレーション、信頼性技術、スループットやトラヒックの計測、品質(QoS)制御、輻輳制御、トラヒック・フロー制御、オーバーレイネットワーク・P2P、CCN・ICN、マルチキャスト、ルーティング、セキュリティ及び一般 |
| テーマ（英） | Performance Analysis and Simulation, Robustness, Traffic and Throughput Measurement, Quality of Service (QoS) Control, Congestion Control, Overlay Network/P2P, CCN, ICN, Multicast, Routing, Security, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2024-12-IN-IA |
| 本文の言語 | 日本語 |
| タイトル（和） | ランダムウォークのエッジ還流度に基づく小規模コミュニティ抽出手法 |
| サブタイトル（和） | |
| タイトル（英） | The Small-Scale Community Detection Method Based on Edge Recirculation of Random Walk |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | コミュニティ抽出 / Community Detection |
| キーワード(3)（和/英） | 小規模コミュニティ / Small-Scale Community |
| キーワード(4)（和/英） | エッジ還流度 / Edge Recirculation |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 山内 隆史 / Takashi Yamauchi / ヤマウチ タカシ |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山下 剛志 / Tsuyoshi Yamashita / ヤマシタ ツヨシ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 松本 直己 / Naoki Matsumoto / マツモト ナオキ |
| 第3著者 所属（和/英） | 琉球大学 (略称： 琉球大) Ryukyus University (略称： Ryukyus Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第4著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2024-12-20 10:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IN |
| 資料番号 | IN2024-68 |
| 巻番号（vol） | vol.124 |
| 号番号（no） | no.312 |
| ページ範囲 | pp.73-80 |
| ページ数 | 8 |
| 発行日 | 2024-12-12 (IN) |
[研究会発表申込システムのトップページに戻る]