CAJ | 학술논문

多标签传播算法具有接近线性的时间复杂度，但用于重叠社区发现时存在精度低、稳定性差的问题。文中基于重叠节点更可能出现在社区边缘的思想，提出基于节点层级与标签传播增益的重叠社区发现算法。该算法首先利用改进的基于节点中心度与社区分布约束的单标签传播方法发现非重叠社区，并在标签传播过程中利用局部信息同步计算节点中心度。然后根据节点中心度定义节点层级函数，标记节点在所属社区中的层级。最后基于节点间的标签传播增益，利用新的多标签更新规则，获得重叠社区结构。实验表明该算法能有效提高精度和稳定性。
다표첨전파산법구유접근선성적시간복잡도，단용우중첩사구발현시존재정도저、은정성차적문제。문중기우중첩절점경가능출현재사구변연적사상，제출기우절점층급여표첨전파증익적중첩사구발현산법。해산법수선이용개진적기우절점중심도여사구분포약속적단표첨전파방법발현비중첩사구，병재표첨전파과정중이용국부신식동보계산절점중심도。연후근거절점중심도정의절점층급함수，표기절점재소속사구중적층급。최후기우절점간적표첨전파증익，이용신적다표첨경신규칙，획득중첩사구결구。실험표명해산법능유효제고정도화은정성。
The time complexity of multi-label propagation algorithm ( MLPA) is nearly linear. However, when it is applied to overlapping community discovery, the accuracy and the stability of MLPA are poor. Inspired by the idea that overlapping nodes are more probable to appear in the boundary regions of different communities, an overlapping community discovery algorithm based on node hierarchy and label propagation gain is proposed in this paper. Firstly, the improved single label propagation with node centrality and community distribution constraints is utilized to unfold preliminary non-overlapping communities and centrality values of nodes are calculated by local information in the propagation process simultaneously. Furthermore, node hierarchy partition function is defined according to centrality values of nodes and employed to mark the hierarchy of each node in its respective community. Finally, based on the label propagation gain among nodes, a new multi-label updating rule is designed to obtain the final overlapping communities. Extensive experimental results on synthetic and real-world networks validate that the proposed algorithm effectively improves the accuracy and stability.