EXIT Analysis for Community Detection
This paper employs the extrinsic information transfer (EXIT) method, a technique imported from the analysis of the iterative decoding of error control codes, to study the performance of belief propagation in community detection in the presence of side information. We consider both the detection of a single (hidden) community, as well as the problem of identifying two symmetric communities. For single community detection, this paper demonstrates the suitability of EXIT to predict the asymptotic phase transition for weak recovery. More importantly, EXIT analysis is leveraged to produce useful insights such as the performance of belief propagation near the threshold. For two symmetric communities, the asymptotic residual error for belief propagation is calculated under finite-alphabet side information, generalizing a previous result with noisy labels. EXIT analysis is used to illuminate the effect of side information on community detection, its relative importance depending on the correlation of the graphical information with node labels, as well as the effect of side information on residual errors.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Active Community Detection with Maximal Expected Model Change
We present a novel active learning algorithm for community detection on networks. Our proposed algorithm uses a Maximal Expected Model Change (MEMC) criterion for querying network nodes label assignments. MEMC detects no…
Active LearningCommunity DetectionmodelStochastic Block ModelEnhancing Community Detection in Networks: A Comparative Analysis of Local Metrics and Hierarchical Algorithms
The analysis and detection of communities in network structures are becoming increasingly relevant for understanding social behavior. One of the principal challenges in this field is the complexity of existing algorithms…
Community DetectionCommunity Detection in Networks: A Rough Sets and Consensus Clustering Approach
The objective of this paper is to propose a framework, called Rough Clustering-based Consensus Community Detection (RC-CCD), to effectively address the challenge of identifying community structures in complex networks fr…
ClusteringCommunity DetectionSimplify to Amplify: Achieving Information-Theoretic Bounds with Fewer Steps in Spectral Community Detection
We propose a streamlined spectral algorithm for community detection in the two-community stochastic block model (SBM) under constant edge density assumptions. By reducing algorithmic complexity through the elimination of…
Computational EfficiencyCommunity DetectionCommunity detection and Social Network analysis based on the Italian wars of the 15th century
In this contribution we study social network modelling by using human interaction as a basis. To do so, we propose a new set of functions, affinities, designed to capture the nature of the local interactions among each p…
ClusteringCommunity Detection