提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对...
详细信息
提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.
为解决标签传播的社区检测算法容易产生怪物社区和不稳定社区划分的问题,以标签熵为基础,提出一种重叠社区检测算法LEKA(Label Entropy and K-shell Algorithm in overlapping community),综合考虑了标签初始化、标签更新和标签传播的...
详细信息
为解决标签传播的社区检测算法容易产生怪物社区和不稳定社区划分的问题,以标签熵为基础,提出一种重叠社区检测算法LEKA(Label Entropy and K-shell Algorithm in overlapping community),综合考虑了标签初始化、标签更新和标签传播的各个阶段。首先,利用K-shell算法对节点进行初始化以获取节点的层次信息;其次,依据标签熵升序依次更新节点标签,在选择标签时综合节点间的层次信息和节点间的影响,在存在多个候选标签的情况下基于节点标签权重进行选取。在真实网络数据集上的实验结果表明,LEKA在运行时间较短的情况下,重叠模块度EQ(ExtendQ)相较于OCKELP(Overlapping Community detection algorithm based on K-shell and label Entropy in Label Propagation)提高了2.3%~13.2%,具有较高的准确性和稳定性,更适合挖掘网络中的重叠社区结构。
为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA)。该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。在真实数据集和人工合成数据集上对该算法进行实验验证。实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。
暂无评论