重複構造を有するコミュニティ抽出の統計力学的解析

摘要

従来のコミュニティ抽出手法の多くは，リンク密度に基づいてネットワークを静的に分割する．しかしながら，ネットワーク内には，様々なコミュニティが存在し，ある-つのノードは，複数のコミュニティに属することが一般的であると考えられる．本研究では，事前に用意した重複を許した複数のコミュニティ（パターン）に従って確率的にスパースなネットワークを生成させる．そして，コミュニティ抽出問題を，ネットワークリンクを強磁性相互作用としたエネルギー関数の最小化問題であるとみなし，ネットワークから埋め込まれたコミュニティを表わすパターンが分離できる条件を，統計力学的な手法の一つであるレプリカ法を用いて解析した．%In most of proposed conventional community extraction methods, a network is divided based on the density of the links of it. It is however common that there are various communities in a networks and one node usually belongs to a number of communities. In the present study, a network is therefore stochastically produced based on a number of communities (patterns) that are allowed to contain overlapping nodes, and the community extraction problem is regarded as a minimization problem with respect to an energy function in the case that network links are used as ferromagnetic interaction strength. The conditions that the embedded community (pattern) can be extracted from the network are theoretically examined with the replica method, which is one of the most powerful tools of a mathematical mechanics.