Community Detection With Known, Unknown, or Partially Known Auxiliary Latent Variables
Community Detection With Known, Unknown, or Partially Known Auxiliary Latent Variables
复制标题
DOI：
10.1109/tnse.2022.3207413
复制
发表时间：
2023-01
影响因子：
6.6
通讯作者：
Mohammadjafar Esmaeili;Aria Nosratinia
中科院分区：
文献类型：
--
作者：
Mohammadjafar Esmaeili;Aria Nosratinia
经验观察表明，在实践中，社区成员资格并不能完全解释观察图边缘之间的依赖性。图表的剩余依赖性是在本文中建模的，一阶，辅助节点潜在变量，这些变量会影响图形边缘的统计数据，但没有有关感兴趣社区的信息。然后，我们在图形中研究了遵守随机块模型的群落检测，并使用辅助潜在变量审查了块模型。当这些辅助潜在变量未知时，我们分析了精确恢复的条件，代表未知的滋扰参数或模型不匹配。当这些次级潜在变量完全或部分揭示时，我们还分析了精确的恢复。最后，我们提出了一种半决赛编程算法，用于恢复所需标签时，当辅助标签是已知或未知的标签时。我们表明，通过半决赛编程可以直至相应的最大似然精确恢复阈值，这是可能的。
Empirical observations suggest that in practice, community membership does not completely explain the dependency between the edges of an observation graph. The residual dependence of the graph edges are modeled in this paper, to first order, by auxiliary node latent variables that affect the statistics of the graph edges but carry no information about the communities of interest. We then study community detection in graphs obeying the stochastic block model and censored block model with auxiliary latent variables. We analyze the conditions for exact recovery when these auxiliary latent variables are unknown, representing unknown nuisance parameters or model mismatch. We also analyze exact recovery when these secondary latent variables have been either fully or partially revealed. Finally, we propose a semidefinite programming algorithm for recovering the desired labels when the secondary labels are either known or unknown. We show that exact recovery is possible by semidefinite programming down to the respective maximum likelihood exact recovery threshold.