Detectability Limit of Graph Partitioning

DOI Web Site

Bibliographic Information

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

Search this article

Abstract

<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

Details 詳細情報について

Report a problem

Back to top