文件名称:论文研究-基于连边相似度的重叠社区发现算法研究.pdf
文件大小:1.12MB
文件格式:PDF
更新时间:2022-08-11 13:20:51
社区发现, 重叠社区, 相似度, 划分密度
针对GN算法在发现重叠社区时存在的不足, 以及为了降低算法时间复杂度, 提出一种基于网络图中连边相似度划分连边集的重叠社区发现算法EGN。算法依据网络图的连边集进行划分, 每一条边被划分到某个特定的社区, 而一个节点可以关联多条连边, 因此节点可以被划分到不同的社区, 从而发现重叠社区。EGN算法首先需要构造网络节点之间连边关系的边图; 然后根据边图中节点的关系计算网络图中连边的相似度, 在节点之间相似度的基础上提出了连边之间相似度的计算方法; 再按照相似度由小到大对边图删除边, 构建出边图的树状图。树状图的每一层对应网络的一个划分, 采用划分密度函数来衡量划分的质量, 以此寻找最优的划分。最后将算法应用到Zachary空手道俱乐部网络中, 并与GN算法进行对比, 实验结果表明EGN算法能够很好地发现重叠社区。