Algorithmic infeasibility of community detection in higher-order networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Structure and inference in hypergraphs with node attributes
Many networked datasets with units interacting in groups of two or more, encoded with hypergraphs, are accompanied by extra information about nodes, such as the role of an individual in a workplace. Here we show how thes…
Community DetectionHyperedge PredictionHigher-order Knowledge Transfer for Dynamic Community Detection with Great Changes
Network structure evolves with time in the real world, and the discovery of changing communities in dynamic networks is an important research topic that poses challenging tasks. Most existing methods assume that no signi…
Community DetectionDynamic Community DetectionTransfer LearningBoosting Multitask Learning on Graphs through Higher-Order Task Affinities
Predicting node labels on a given graph is a widely studied problem with many applications, including community detection and molecular graph prediction. This paper considers predicting multiple node labeling functions o…
Community DetectionNode ClassificationSimplex2Vec embeddings for community detection in simplicial complexes
Topological representations are rapidly becoming a popular way to capture and encode higher-order interactions in complex systems. They have found applications in disciplines as different as cancer genomics, brain functi…
ClusteringCommunity DetectionDescriptiveInfeasibility Aware Large Language Models for Combinatorial Optimization
Large language models (LLMs) are increasingly explored for NP-hard combinatorial optimization problems, but most existing methods emphasize feasible-instance solution generation and do not explicitly address infeasibilit…