基于深度强化学习的复杂网络可扩展社区检测

针对复杂网络社区检测可扩展性不足与准确性不高的问题,提出一种复杂网络可扩展社区检测算法。该算法由两个阶段构成,第一阶段根据邻域度数方差检测网络中的候选社区中心,基于网络拓扑结构评估节点的相似性,基于相似性进行标签传播,建立网络的初始化社区;第二阶段基于深度强化学习对网络社区结构进行微调与优化,利用深度强化学习强大的感知能力与决策能力提高社区结构的准确性。实验结果表明,由该算法发现的网络社区获得了较高的准确性。

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

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

模体感知的自适应跨层游走社区检测

近年来,利用高阶交互信息进行多层网络社区检测已成为复杂网络分析领域的研究热点。尽管多层网络社区检测的研究已取得了一些进展,但大多数方法忽略了网络各层之间的联系。为了解决这一问题,提出了一种模体(motif)感知的自适应跨层游走社区检测算法(Motif-aware Adaptive Cross-Layer random walk Community Detection,MACLCD)。该算法充分考虑了多层网络各层内的高阶交互特性以及层间的相关性,有效整合了多层网络的结构信息,提高了社区检测结果的准确性。具体地,首先从网络和节点的角度进行综合度量,揭示网络层间相关性;其次,考虑了各层网络可能具有不同的局部和全局结构特征,利用motif识别各层网络特有的高阶交互结构,构建多层加权混合阶网络;进一步,设计了多层网络跨层游走模型,并引入跳转因子,以确保随机游走能够自适应地遍历多层网络,从而捕获更丰富的网络结构信息。在4个真实的网络数据集上进行实验比较分析,结果表明MACLCD算法在社区检测方面性能较优,相比目前表现最佳的对比算法在ACC和NMI上分别提高了10%和8.9%。

基于协变量的一类贝叶斯社区检测算法

在复杂网络系统研究中,社区检测是挖掘网络数据内部结构信息的重要方法之一。提出了一个含有节点协变量信息的度修正随机块模型的贝叶斯社区检测算法,通过基于随机森林的算法选择重要的节点协变量,应用与协变量相关的随机划分模型划分社区隶属度,应用DCSBM模型,通过Gibbs采样方法进行社区检测并推断社区数量。数值模拟结果表明含有节点协变量信息的度修正随机块模型的贝叶斯社区检测算法可以显著提高社区检测的性能。最后将含有节点协变量信息的度修正随机块模型的贝叶斯社区检测算法方法应用到Weddell Sea营养网络的实际数据进行实证分析。

基于引力作用的重叠社区检测算法

社区结构是复杂网络的一个重要特征,通过社区检测来分析和理解复杂网络的结构和功能具有重要意义。基于局部社区检测的算法因其高效性和有效性而被广泛应用于解决这一问题。然而,大多数算法对局部信息的利用率较低、扩展过程中的适应度函数无法动态度量节点间的连接方式,使得社区检测结果存在质量和稳定性方面的不足。基于此,提出一种基于引力作用的重叠社区检测算法,将网络中的拓扑信息带入万有引力公式,来衡量两个节点间的相互作用力;并应用引力作用公式改进局部扩展过程中的适应度函数,来获取高质量的可重叠的社区。通过真实网络和合成网络中的实验表明,该算法具有良好的性能。

自编码模块化增强非负矩阵分解社区检测算法

社区检测一直是网络分析中的重点研究方向之一。目前大多数网络社区检测算法主要利用网络的结构信息采用贪心算法使某一指标最大化,无法充分考虑节点特征信息、边权重以及网络社区间关系不对称性等问题。针对这一情况,提出一种自编码模块化增强非负矩阵分解(autoencoder-like modularity nonnegative matrix factorization,AMNMF)社区检测算法。该算法通过采用类编码器结构拓展非负矩阵分解的深度,将模块度和图正则化器引入到非负矩阵分解的目标函数优化过程中以充分挖掘网络中的节点和社区结构信息,通过在编码器中间层添加正交约束解决了社区间关系不平衡的问题。在多个真实网络上的实验表明:AMNMF是一种有效地利用节点特征信息和网络结构信息的NMF拓展算法,与基线算法的最佳结果相比实现了约15%至122%的提升,能够准确有效完成社区检测任务。

基于非负矩阵分解的有向网络半监督社区检测

有向网络上的社区检测是网络科学领域一个重要的课题.针对这一问题,本文提出了一种基于非负矩阵分解的有向网络半监督社区检测算法,首先利用先验信息重构邻接矩阵,然后使用先验信息对节点的社区隶属度进行惩罚,并通过行归一化消除节点度异质性的影响,最后运用交替迭代更新给出了目标函数的求解方法.在真实网络数据上的对比实验验证了算法的有效性,相对于基于非负矩阵分解的现有方法,本文方法能显著提高社区发现的准确性.

基于邻居相似性的图嵌入社区检测算法

社区检测是复杂网络中的研究热点,理解和发现网络的社区结构对于探索网络的行为和功能具有重要意义。提出了一种新颖的基于邻居相似性的图嵌入方法进行社区检测。基于节点的邻居相似性和接受度聚合邻居的属性信息表达,得到网络中每个节点的向量表达后,直接进行K-均值聚类得到最终的社区划分结果。实验结果表明:提出的算法具有更好的社团划分结果,其模块性和标准归一化指标都有明显的提升。

基于优化蚁群和标签传播的复杂网络社区检测

标签传播算法被广泛应用于复杂网络中社区检测及其它工程领域,但由于其标签更新的随机性,降低了社区检测的稳定性,为此提出一种LPA-5SA(LPA-five step Ant)算法。使用蚁群优化算法的概率转移公式将标签传播算法的随机选择变为目标函数高概率选择,通过5步更新法提高信息素选择权重,提高社区检测的稳定性和准确率。该算法在真实的网络和人工合成的网络中进行实验,结果用模块度和NMI指标进行评价,验证了该方法的准确率和稳定性。

基于相似度加强Louvain方法的复杂网络社区检测

在针对复杂网络的社区检测问题中,基于模块度的社区划分方法Louvain Method(LM)迭代算法被广泛的应用,但是考虑到该算法在第一次迭代过程中的时间复杂度非常大,为了解决这个问题,文中引入了OLM方法,对复杂网络中的节点利用相似性的度量方法进行处理,从而优化整个网络结构,来更高效地使用该算法识别社区。实验结果表明,提出的OLM方法具有更高的效率和稳定性。

基于多属性决策的社区检测算法研究

针对社交网络中的社区检测问题,课题组提出了基于多属性决策的社区检测算法。该算法根据用户偏好来找到与查询用户高度相关且在多个属性中综合得分最高的社区。首先将网络建模为多属性社交道路网络,每个用户都与位置信息和多维属性相关联,然后定义了一种适用于多属性决策的社区模型,称为多属性社区,接着分别设计了全局和局部搜索算法来进行社区检测。最后,使用真实的社交网络数据集来验证算法的有效性。

两阶段量子行走算法在社区检测中的应用

已有基于量子行走的社区检测算法存在计算开销过大或对时间参数过于敏感的问题。针对此问题,提出两阶段量子行走(two-stage quantum walk,TSQW)算法。TSQW算法第一阶段为无测量量子行走,此阶段融合节点的邻域拓扑信息将节点表达为向量,第二阶段利用K-means方法聚类上一阶段得到的节点向量以划分网络社区。通过仿真网络和空手道俱乐部网络的验证,该算法能够准确地检测网络社区结构。进一步,提出TSQW的扩展(TSQW-E)算法,该算法依据节点的社区信息增加或删除原始网络的连边并实现社区隐藏。根据互信息指标和调整兰德系数下的实验表现,TSQW-E算法使已有社区检测算法的平均识别精度分别下降0.491和0.58,对网络社区结构的破坏效果最好。

基于多目标粒子群优化的属性网络局部社区检测算法

社区结构是复杂网络中的重要特征,局部社区检测的目标是查询出包含一组种子节点的社区子图。传统的局部社区检测算法通常利用网络的拓扑结构进行社区查询,而忽略了网络中丰富的节点属性信息。针对现实中广泛存在的属性网络,提出了一种基于多目标粒子群优化的属性网络局部社区检测算法。首先根据节点与其多阶邻居之间的属性相似度构造属性关系边,并根据模体结构获取网络中的高阶信息得到拓扑关系边,然后基于种子节点使用随机游走算法对两种关系边采样得到备选节点集。在此基础上,通过多目标粒子群优化算法对备选节点集进行迭代筛选,得到拓扑结构紧密和节点属性同质的社区结构。在真实数据集上的实验结果表明,所提方法有效提升了局部社区检测的质量。

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

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

复杂脑网络社区检测算法综述

脑网络社区检测算法是近年来脑科学和网络科学领域备受关注的重要课题,被广泛用于揭示大脑结构和功能连接模式。由于大脑网络的复杂性以及需要处理多个被试、多种场景任务等因素,极大地增加了该领域社区检测的难度。聚焦功能磁共振成像技术,全面综述了面向脑功能网络社区检测算法的研究进展。首先,描述了脑网络社区检测算法的基本流程、任务类别和方法种类。然后,分类介绍了不同任务场景下的脑网络社区检测算法,包括分离社区、重叠社区、多层次社区和动态社区检测算法,深入分析了不同方法的优缺点,并给出了适用范围。最后,展望了未来脑网络社区检测算法的主要发展方向,包括多被试网络社区检测问题、脑网络社区检测的鲁棒性问题以及面向多模态影像数据的脑网络社区检测算法研究等。可为今后脑网络社区结构研究提供方法学指导。

一种基于高阶组织的学习者潜在重叠社区检测算法

学习者网络拓扑结构稀疏,且传统的社区检测算法无法为惰性/冷启动学习者检测其潜在的社区。针对该类问题,提出了一种基于高阶组织的学习者潜在重叠社区检测算法(POCDL)。POCDL算法是一种局部图聚类算法,首先利用社交化在线课程平台中的好友关系、同学关系和师生关系解决学习者网络数据稀疏问题;然后挖掘学习者网络中的高阶组织并重构学习者网络;最后,根据学习者的度中心性选取初始种子集,根据社区归属度和社区亲密度进行局部社区检测。在人工网络和学者网真实网络数据集上的实验结果表明:POCDL算法能够较好地为惰性/冷启动学习者检测社区;对其他类型的复杂网络也具有一定的普适性。

基于社区密度的重叠社区检测算法

社区检测是研究复杂网络的热点话题之一,其目的是找到具有共同性质的社区成员。随着网络复杂性的增强,传统算法在时间和精度上都受到了一定的限制。基于此,本文提出一种基于社区密度的重叠社区检测方法。在该方法中,我们首先对顶点的邻居集做交集运算,在确定初始候选社区的基础上过滤掉社区密度低于阈值的社区。其次,以社区间相似性这一概念作为社区合并的判断条件,生成重叠社区。最后,我们在两类合成网络上与现有的经典算法作比较,实验结果表明本文所建立的算法是有效的。

基于时间序列相似性的网络社区检测方法

社区检测作为目前复杂网络的研究热点之一,其检测结果能帮助人们深入理解复杂网络的网络结构和内在运行机制,并具有非常高的应用价值。随着数据采集等技术的不断发展,复杂系统中的个体所具有的海量时间序列数据得以保存。本文针对一些具有时间序列数据的复杂系统,提出根据时间序列之间的相似性重构出其对应的复杂网络,并利用阈值法将网络进行了相应的简化,最后利用社区检测算法将网络划分为不同的社区,从而对复杂网络的网络拓扑结构和社区结构进行理解和分析。利用上证180指数成分股票的收盘价时间序列数据对该方法进行了实验分析验证,结果表明了该方法能够有效地检测出网络中的社区结构。

基于高阶信息局部策略的符号网络社区检测

现有符号网络社区检测方法中,局部搜索策略作为符号网络社区检测算法的重要组成部分,可加速算法收敛速度,但符号网络局部搜索策略大多仅利用连边及节点等低阶结构信息,忽略了可挖掘符号网络更深层、更丰富信息的高阶结构.为提升现有符号网络社区检测的局部搜索策略性能,提出了一种基于符号模体的局部搜索策略,设计了一种基于符号模体进行社区迁移的新方法,将传统社区编号在二元组之间的迁移扩展到了三元组,综合利用符号网络低阶和高阶拓扑结构信息来优化节点的结构平衡性,提升算法收敛速度和检测性能.在模型网络和实证网络上的实验表明,设计的局部搜索策略相对于现有算法表现出更高的精度和质量.

基于模体的模块度优化高阶社区检测算法

为提升现有高阶社区检测算法的性能,提出一种基于模体的模块度优化高阶社区检测算法。通过量化网络模体数量为节点间权重,将高阶基于模体的社区检测转化为低阶基于边的加权网络社区检测,并构造为加权模块度优化问题求解。为保证加权模块度优化性能以获得逼近全局最优的高阶社区划分,一方面优化策略采用典型的生物启发式算法;另一方面综合利用网络低阶和高阶拓扑结构信息,通过节点邻域社区修正操作和局部搜索操作,进一步提升社区划分质量并防止算法陷入局部最优。在人工合成和真实世界网络上的实验表明,利用模体高阶结构信息有助于提升复杂网络社区的检测性能,尤其是在社区结构较为模糊的情况下。该算法能够有效实现基于模体的高阶社区检测,与现有基于模体的典型方法相比在精确性和质量性上表现出一定优势,有助于加深对网络高阶结构及功能特性的理解。