基于图嵌入和多标签传播的重叠社区检测算法

为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA)。该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。在真实数据集和人工合成数据集上对该算法进行实验验证。实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。

基于KC-SLPA算法的重叠社区检测算法研究

针对标签传播的思想在复杂网络上进行重叠社区发现,提出一种优化的重叠社区检测算法KC-SLPA。综合考虑网络结构的局部以及全局属性指标,融合K-shell与集聚系数的节点重要性来度量节点的影响力分数,节点影响力排序固定访问顺序,减少算法的随机性;提出改进的Speaker-Listener规则,根据标签出现频率的平均值进行标签传播,避免标签选择的随机性问题;引入改进的节点相似度对出现多个Speaker标签做进一步处理,提高社区的检测质量。分别在合成网络与真实数据集上进行验证,实验结果表明,该算法能够在不同规模的网络中具有较高的稳定性且检测重叠社区的质量较好。

基于标签传播与多指标的重叠社区检测算法

为解决标签传播的社区检测算法容易产生怪物社区和不稳定社区划分的问题,以标签熵为基础,提出一种重叠社区检测算法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%,具有较高的准确性和稳定性,更适合挖掘网络中的重叠社区结构。

复杂网络大数据中重叠社区检测算法

提出一种新的面向复杂网络大数据的重叠社区检测算法DOC(detecting overlapping communities over complex network big data),时间复杂度为O(nlog2(n)),算法基于模块度聚类和图计算思想,应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法.相对于传统的重叠节点检测算法,对每个节点分析的频率大为降低,可以在较低的算法运行时间下获得较高的识别准确率.复杂网络大数据集上的算法测试结果表明:DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法.

基于节点尺度特征的重叠社区检测算法

针对社会网络中重叠社区检测问题,在节点尺度特征下量化社区结构,用这些特性更易界定社区划分。利用合理假设来量化节点尺度的期望值,基于节点描述符集和谱算法建立算法模型,从而提出一种重叠社区检测算法。该方法允许节点同时属于多个社区,在社区重叠时同样可行。通过计算验证,算法对于整体边缘密度都有效。在2类网络中实验的结果表明,该算法在重叠社区检测中性能稳定、准确性高,能适用于目标特定的社区概念。

采用模糊层次聚类的社会网络重叠社区检测算法

为了能够发现社会网络中的重叠社区以及解决重叠社区之间关系的模糊性和层次性,提出了一种基于模糊层次聚类的重叠社区检测算法(CDHC)。算法中引入了距离加权因子来计算社区间的相似度,通过模糊层次聚类来合并相似度高的社区;针对合并生成的原始社区计算社区中节点的隶属度,再将隶属度小于阈值的节点从社区中移除,从而形成最终的网络重叠社区结构。该算法不仅可以发现重叠的社区结构,还可以处理孤立节点。在Lancichinetti基准网络和真实网络上将CDHC算法与具有代表性的重叠社区发现算法CMP和LFM进行了比较,结果表明:影响社区检测精度的主要因素是社区间的混合程度,而网络规模和网络中社区的规模的影响并不显著;CDHC算法在小社区网络上的社区检测精度优于LFM,在大社区网络上的社区检测精度优于CMP。CDHC算法在保持社区检测质量的同时,还具有较好的稳定性,是一种有效的社会网络重叠社区检测算法。

基于中心团的重叠社区检测算法

社区检测已经成为了了解复杂网络结构和网络动态的一个重要途径。针对传统的节点聚类和链接聚类在发现重叠社区方面存在的两种固有缺陷,即参数依赖和结果不稳定,文中提出了一种基于中心团的局部扩展改进算法CLEM,用于检测重叠社区。该算法通过选取中心团为核心种子,并在种子扩展过程中惩罚被多次删除的节点,改善所得结果的稳定性;通过选取不依赖参数的适应度函数,改进其迭代计算过程,避免了适应度函数的参数限制,并降低了计算复杂度。在合成网络和现实网络上测试的结果表明,与已有算法相比,所提算法在计算时间和准确度上均有很好的表现。

基于重叠社区检测的跟踪区列表管理方法

跟踪区列表(TAL)由多个跟踪区(TA)灵活配置组成,在3GPP R8中引入TAL可减少位置管理信令开销。目前基于TAL的位置管理方法大多针对不同用户产生不同的TAL,在海量蜂窝部署环境下的计算效率急剧降低。针对该问题,在TA规划的基础上,提出一种基于重叠社区检测的TAL管理方法。通过统计用户在跟踪区内产生的位置更新和寻呼数据,将TAL管理建模为图形分割问题,给出线性规划模型,并应用基于博弈论的重叠社区检测算法得到TAL结构。实验结果表明,该方法能够有效降低蜂窝网络中的位置管理信令开销,提高TAL分配效率。

基于模块化多尺度算法的通信重叠社区检测

针对常规的社区检测方法未能量化社区特征这一问题,通过考察社区结构的多尺度特征,提出一种基于模块化多尺度的重叠社区检测算法。从节点、社区和网络三个尺度分别量化社区结构,并建立高度模块化的社区检测模型。首先提取节点集,扩展社区形成社区初始集,最后通过算法迭代聚类特定节点。在人工网络和现实网络中对算法进行了大量测试,几种质量评价指标以及实验结果均表明该算法计算成本低,且准确高效。

重叠社区检测及其果蝇视觉进化神经网络

针对社区发现中,部分节点划分难的问题,探讨重叠社区检测的优化模型和求解的视觉进化神经网络。模型通过设计节点隶属度矩阵和节点分割规则,建立以模糊分割阈值为变量,且能评估社区划分效果的改进型模块度函数;算法设计中,以候选解构成的状态矩阵对应函数值矩阵作为输入,依据果蝇视觉系统的信息处理机制,建立以输出作为状态学习率的果蝇视觉前馈神经网络,进而借助灰狼优化的位置更新规则,设计状态更新策略,获得基于重叠社区检测的果蝇视觉进化神经网络及其算法。该神经网络的计算复杂度,由状态矩阵的大小及社区网络的节点数确定。比较性的数值实验显示,该求解重叠社区检测问题具有明显优势,有较好的应用潜力。

面向延迟容忍移动传感器网络的重叠社区节点检测方法

延迟容忍移动传感器网络(DTMSN)呈现重叠社区结构特征,对重叠社区节点进行准确检测可有效提高网络运行效率。提出了适用于DTMSN的重叠社区节点检测方法。依据节点相遇信息挖掘节点移动轨迹规律,从而对其所属初始社区进行判定;进而,设计了节点社区隶属度估计方法,据此进行重叠社区节点的准确检测。仿真结果表明,相比已有方法,所提方法可分别提高平均检出率、平均负载率14%、15%以上。

基于梯度的重叠式层次社区检测

社区检测(community detection)任务一直是数据挖掘领域的一个研究热点,近年来,深度学习和图链接数据呈现出多样化和复杂化的发展趋势,层次(Hierarchical)社区检测逐渐成为研究的焦点.层次社区检测任务的目标是,在将同质图中相似的节点聚集到社区中的同时,学习社区之间的层次结构关系,以更好的理解图数据结构.社区间层次关系的引入给社区检测算法带来了更复杂的建模挑战.针对该任务,已经有一些有效的启发式的方法被提出,但是受限于社区分布形态的简单假设和离散的优化学习方式,它们无法描述更复杂的图链路数据,也无法和其它有效的连续优化算法组合获得更好的结果.为了解决这个问题,本文首次尝试建模复杂的重叠式(overlapping)层次社区结构,提出简洁的节点嵌入和社区检测双任务优化模型,通过梯度更新的方式来灵活地探索节点和重叠式层次社区的隶属关系.在学习过程中,我们可以分别获得节点和社区的嵌入表示,以应用于丰富的下游任务.