Algorithmic infeasibility of community detection in higher-order networks
This addresses a fundamental limitation in network analysis for researchers, revealing that more complex data can hinder rather than help community detection, which is incremental as it builds on existing detectability analysis methods.
The paper tackles the problem of community detection in higher-order networks, showing that excessive information can make extraction algorithmically infeasible, with results indicating a phase where lower-order networks outperform higher-order ones in detectability.
In principle, higher-order networks that have multiple edge types are more informative than their lower-order counterparts. In practice, however, excessively rich information may be algorithmically infeasible to extract. It requires an algorithm that assumes a high-dimensional model and such an algorithm may perform poorly or be extremely sensitive to the initial estimate of the model parameters. Herein, we address this problem of community detection through a detectability analysis. We focus on the expectation-maximization (EM) algorithm with belief propagation (BP), and analytically derive its algorithmic detectability threshold, i.e., the limit of the modular structure strength below which the algorithm can no longer detect any modular structures. The results indicate the existence of a phase in which the community detection of a lower-order network outperforms its higher-order counterpart.