Detectability of hierarchical communities in networks
We study the problem of recovering a planted hierarchy of partitions in a network. The detectability of a single planted partition has previously been analysed in detail and a phase transition has been identified below which the partition cannot be detected. Here we show that, in the hierarchical setting, there exist additional phases in which the presence of multiple consistent partitions can either help or hinder detection. Accordingly, the detectability limit for non-hierarchical partitions typically provides insufficient information about the detectability of the complete hierarchical structure, as we highlight with several constructive examples.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
Modularity is a popular measure of community structure. However, maximizing the modularity can lead to many competing partitions, with almost the same modularity, that are poorly correlated with each other. It can also p…
Stochastic Block ModelCommunity Detection and Improved Detectability in Multiplex Networks
We investigate the widely encountered problem of detecting communities in multiplex networks, such as social networks, with an unknown arbitrary heterogeneous structure. To improve detectability, we propose a generative …
Community DetectionStochastic Block ModelGraph energy as a measure of community detectability in networks
A key challenge in network science is the detection of communities, which are sets of nodes in a network that are densely connected internally but sparsely connected to the rest of the network. A fundamental result in co…
Community DetectionDisentangling group and link persistence in Dynamic Stochastic Block models
We study the inference of a model of dynamic networks in which both communities and links keep memory of previous network states. By considering maximum likelihood inference from single snapshot observations of the netwo…
Community DetectionPhase Transitions in Spectral Community Detection of Large Noisy Networks
In this paper, we study the sensitivity of the spectral clustering based community detection algorithm subject to a Erdos-Renyi type random noise model. We prove phase transitions in community detectability as a function…
ClusteringCommunity Detection