コミュニティ抽出とは簡単に言えばグラフにおけるノードのクラスタリング手法です。具体的なアルゴリズムとしてはGirvan–Newman法をはじめ様々なアルゴリズムが存在しますが、この記事では去年(2019年)提案された新しい手法について解説したいと思います[1]。 [1907.03993] Community Detection on Networks with Ricci Flow 話の元になっているのはこちらの論文で、グラフをリッチフローによって変形し、伸びたエッジを切断していくことでクラスタを求めるというアルゴリズムです。リッチフローという聞き慣れない言葉が出てきましたが、ちゃんと後で説明するので気にせず進めましょう。 まずは実際にグラフのクラスタリングを行う様子をアニメーションで見てみてください。 アルゴリズム自体はそれほど難しくありませんが、背景を含めて理解するためには2つの理論
![グラフからコミュニティ構造を抽出する 〜リッチフローによるグラフの時間発展〜](https://cdn-ak-scissors.b.st-hatena.com/image/square/1a5177b36fc73b905890f4ec4452d77a35966652/height=288;version=1;width=512/https%3A%2F%2Fres.cloudinary.com%2Fzenn%2Fimage%2Fupload%2Fs--4NL4gTOx--%2Fc_fit%252Cg_north_west%252Cl_text%3Anotosansjp-medium.otf_55%3A%2525E3%252582%2525B0%2525E3%252583%2525A9%2525E3%252583%252595%2525E3%252581%25258B%2525E3%252582%252589%2525E3%252582%2525B3%2525E3%252583%25259F%2525E3%252583%2525A5%2525E3%252583%25258B%2525E3%252583%252586%2525E3%252582%2525A3%2525E6%2525A7%25258B%2525E9%252580%2525A0%2525E3%252582%252592%2525E6%25258A%2525BD%2525E5%252587%2525BA%2525E3%252581%252599%2525E3%252582%25258B%252520%2525E3%252580%25259C%2525E3%252583%2525AA%2525E3%252583%252583%2525E3%252583%252581%2525E3%252583%252595%2525E3%252583%2525AD%2525E3%252583%2525BC%2525E3%252581%2525AB%2525E3%252582%252588%2525E3%252582%25258B%2525E3%252582%2525B0%2525E3%252583%2525A9%2525E3%252583%252595%2525E3%252581%2525AE%2525E6%252599%252582%2525E9%252596%252593%2525E7%252599%2525BA%2525E5%2525B1%252595%2525E3%252580%25259C%252Cw_1010%252Cx_90%252Cy_100%2Fg_south_west%252Cl_text%3Anotosansjp-medium.otf_37%3Alotz%252Cx_203%252Cy_121%2Fg_south_west%252Ch_90%252Cl_fetch%3AaHR0cHM6Ly9saDMuZ29vZ2xldXNlcmNvbnRlbnQuY29tL2EtL0FPaDE0R2hJWXEzTUc1M3M1M2MzUXo1bjNzcVNoTlFWTThKQkZnNU1GT0FyUnc9czI1MC1j%252Cr_max%252Cw_90%252Cx_87%252Cy_95%2Fv1627283836%2Fdefault%2Fog-base-w1200-v2.png)