# Son et al. FRFIM method Son, S.-W. らが提案したスピン模型に基づくコミュニティ検出手法。強磁性ランダム場イジングモデル(Ferromagnetic Random Field Ising Model, FRFIM、式56)を用い、2頂点 s, t の spin を無限大の逆符号磁場で固定することで、最大流最小カット問題として解く。全ての基底状態で同一クラスタに属す頂点集合は coterie(コテリー)と呼ばれ、クラスタの核とみなされる([[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] p.44)。 計算量は O(n^{2+θ})(θ≈1.2)で低速なため、数千頂点規模までしか実用的でない。重要頂点が事前にわかれば s, t を制約でき、O(n^θ) まで高速化できる(同 p.44)。Ispolatov は反強磁性項を含む類似ハミルトニアンを提案した(同 p.44)。 > "The vertices that end up in the same cluster in all ground states represent the cores of the clusters, which are called coteries." (同 p.44) ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] — 本手法を扱う章。 ## 出典 - [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] — Son et al. による提案として言及される(原論文の書誌情報は本章の extract に含まれないため未記載)。