Detectability Limit of Graph Partitioning

Kawamoto Tatsuro

doi:10.11316/butsuri.75.11_696

Bibliographic Information

Other Title

グラフ分割の検出限界
グラフブンカツノケンシュツゲンカイ

Search this article

Description

<p>Graph partitioning as an inference problem has been an important topic in multiple fields of science. In this article, we derive a performance limit called the algorithmic detectability limit on graph partitioning using a technique developed in statistical physics. This limit is a phase transition point beyond which an algorithm completely loses the ability to identify the group structure that is assumed in a random graph model.</p>

Journal

Butsuri

Butsuri 75 (11), 696-700, 2020-11-05

The Physical Society of Japan