Community Detection With Side Information: Exact Recovery Under the Stochastic Block Model
Community Detection With Side Information: Exact Recovery Under the Stochastic Block Model
复制标题
DOI：
10.1109/jstsp.2018.2834874
复制
发表时间：
2018-10-01
影响因子：
7.5
通讯作者：
Nosratinia, Aria
中科院分区：
文献类型：
--
作者：
Saad, Hussein;Nosratinia, Aria
社区检测问题涉及基于观察图的边来对图中的节点标签进行推断。本文研究了具有n个节点的二元随机块模型中附加的非图形边信息对精确恢复相变的影响。当边信息由具有错误概率α的噪声标签组成时，表明当且仅当log（1-alpha/alpha）= Omega（log（n））时，相变得到改善。当边信息包括揭示分数1 -是标签的元素时，表明当且仅当log（1/是的元素）= Omega（log（n））时，相变得到改善。对于由K个特征组成的更一般的边信息，研究了两种情况，第一，K是固定的，而每个特征相对于对应节点标签的似然随n而演变，以及，第二，特征的数量K随n而变化，但每个特征的似然是固定的。在每种情况下，我们都会发现辅助信息何时会改善确切的恢复相变以及改善程度。在推导内界的过程中，提出了一种有效的算法的变化与边信息的社区检测，使用局部改进过程相结合的部分恢复算法。
The community detection problem involves making inferences about node labels in a graph, based on observing the graph edges. This paper studies the effect of additional, non-graphical side information on the phase transition of exact recovery in the binary stochastic block model with n nodes. When side information consists of noisy labels with error probability alpha, it is shown that phase transition is improved if and only if log(1-alpha/alpha) = Omega(log(n)). When side information consists of revealing a fraction 1 - is an element of of the labels, it is shown that phase transition is improved if and only if log(1/is an element of) = Omega(log(n)). For a more general side information consisting of K features, two scenarios are studied, first, K is fixed while the likelihood of each feature with respect to corresponding node label evolves with n, and, second, the number of features K varies with n but the likelihood of each feature is fixed. In each case, we find when side information improves the exact recovery phase transition and by how much. In the process of deriving inner bounds, a variation of an efficient algorithm is proposed for community detection with side information that uses a partial recovery algorithm combined with a local improvement procedure.