关键词： 数据挖掘   社团检测   复杂网络   种子扩展算法  

摘要： 现实生活中存在着形形色色的网络,如社交网络、论文引用网络和蛋白质相互作用网络等,人们将这些网络统称为“复杂网络”。复杂网络具有社团结构的特性。社团检测算法旨在高效、准确地从复杂网络中划分出社团结构。社团检测算法有很多类,基于种子扩展社团检测算法就是其中之一。一些基于种子扩展的算法在社团扩展时未考虑社团的聚类特征,其次在社团优化时存在筛选稀疏社团不准确的问题,这两个问题的存在降低了种子扩展算法社团检测的准确性。通过分析现有的种子扩展社团检测算法,本文提出基于社团聚类特征的种子扩展社团检测算法。本文的主要工作如下:（1）针对种子扩展社团检测算法在种子扩展阶段未考虑社团的聚类特征以及在社团优化阶段筛选稀疏社团不准确的问题,本文提出基于社团聚类特征的种子扩展社团检测算法SEA。SEA算法,在种子扩展阶段,用CEA算法完成社团的初步划分;在社团优化阶段,用MOA算法在CEA算法输出结果的基础上完成社团优化。在种子扩展阶段,本文定义了评估社团聚类能力的社团聚类系数,并以社团聚类系数定义了节点对于社团的聚类增量。CEA算法在种子扩展时,根据社团的聚类特征从尚未被划分社团的节点中选择局部聚类系数最大且度相对较小的节点作为种子节点,然后把社团的邻节点按局部聚类系数排序,最后把聚类增量大于0的节点扩展至社团;在社团优化阶段,本文引入了模块度增量,并以模块度最大化来优化社团,避免了筛选稀疏社团不准确的问题。MOA算法在社团优化时引入模块度增量矩阵,在每次迭代时选择把模块度增量最大的两个社团合并。（2）针对种子扩展算法在社团优化阶段筛选稀疏社团不准确的问题,本文重新定义了评估社团稀疏性的社团密度,并提出基于社团密度优化的种子扩社团检测算法D＿SEA。D＿SEA算法在CEA算法的社团检测的基础上,每次迭代时筛选择最稀疏的社团,并与其最相似的社团合并,直至社团划分结果中社团的稀疏性都大于阈值!时,算法执行结束。在真实网络和人工网络上,将本文提出的算法与具有代表性的算法进行对比实验。实验结果表明,本文提出的算法可以更准确地检测出复杂网络中的社团。

关键词： 社团检测   k核   加权图   紧密子图   贪婪策略  

摘要： 紧密子图查询作为图查询的研究热点之一,在很多领域都有着重要的应用。现有的研究中已有许多紧密子图查询方法,如基于模块度优化的算法、谱方法、非负矩阵分解等。对于紧密子图的定义也有多种,常见的有k架(k-truss)、k团(k-clique)、k核(k-core)等。其中k核的定义要求图中每个节点至少有k个邻接节点,即每个节点的度至少为k。根据该定义,k核可以在线性时间复杂度内计算得到,具有较好的应用基础,已在许多方面有所研究与应用。由于k核只考虑图中节点和边的关系,据此得到的仅是一个边稠密的子图。但在很多场景下的图数据还会包括更多其它属性,若在查询紧密子图时不考虑这些属性则所得到的结果缺乏实际意义。在现有的k核研究中,已有部分文献开始结合图中的其它属性,如:图的关键词属性、图的空间位置属性、图的节点影响力属性等。但目前对于k核紧密子图的查询中,结合图中边权值的研究还较少,而在很多场景下,图中边的权值往往具有很强的语义关系。考虑到这一点,本文提出了一个新的紧密k核子图查询问题。目前对于紧密子图的查询,主要有两个研究方向:社团搜索和社团检测。本文所提出的问题属于紧密子图查询中的社团检测问题,其查询得到所有符合要求的连通子图。并且,本文考虑到查询最紧密子图往往会消耗较多的时间,在一些应用场景下也并不需要查询子图权重的最值。为此,本文所提的问题不局限于社团检测中最值的查询,子图只需满足给定的节点平均权值即可,而该值可以根据实际应用需求给出,具有更高的灵活性,能适应更多的查询场景。本文主要完成的工作如下:(1)提出了在加权图中查询联系紧密的连通k核子图问题,简记为紧密k核子图查询(Query Closely Relatedk-Core Subgraph,QCRKS)问题,其描述如下:给定核值k、节点平均权值,在加权图中查询紧密连通k核子图,该子图节点平均权值大于等于。随后通过多项式规约的方法,证明了QCRKS问题是一个NP-难问题。(2)由于无法为QCRKS问题找到一个在多项式时间复杂度内的最优算法,故本文为该问题设计了启发式算法CRK-G,其先在原图中查询一个最大连通k核作为候选子图,然后采用贪心策略通过在候选子图中不断迭代删除权值最小的节点,从而得到满足条件的紧密k核子图。(3)为提高CRK-G算法的效率,本文在其基础上进行改进,设计了CRK-C和CRK-F算法。CRK-C算法使用图压缩策略,在迭代之前先将权值相近节点进行合并,从而降低候选子图的规模。CRK-F算法使用单次多节点删除策略,每次迭代从候选子图中删除多个节点,从而减少迭代次数。两个算法分别从降低图规模和减少迭代次数两个方面出发,提高了查询效率,其查询速度明显高于CRK-G算法。(4)通过在真实数据集上的实验,对比了3种算法在不同查询场景下的查询效率,验证了算法的误差,分析了图压缩算法的有效性,以及最后通过与传统k核方法的对比和一个实例分析验证了本文所提模型的有效性。

关键词： 复杂网络   社团检测   标签传播   节点重要性   公共安全数据分析  

摘要： 复杂网络是由真实世界里对应复杂系统经过建模得到的一种网络结构,常见的复杂网络有金融交易网络、蛋白质网络、人际关系网络等,在数字化的时代背景下,这类网络已经成为了研究信息传播的重要工具。社团检测是研究复杂网络结构的一种常用技术,研究人员通过社团检测可以揭示复杂网络的拓扑信息,探究各群体之间以及个体之间的潜在关系,因此社团检测及其相关课题具有重要的研究价值和意义。原始的标签传播算法LPA具有简单高效的特点,在社团检测领域具有较高的热度,但其存在稳定性较差且不能适用于重叠社团的检测等问题。本文在深入研究了LPA算法的思想和运行原理后,提出了三种基于LPA改进的算法。论文的主要研究内容如下:（1）针对原始LPA算法的高随机性而导致检测结果不稳定的问题,本文提出一种基于节点重要性的标签传播算法LPANI。首先本文基于k-shell算法和节点活跃度定义了一种节点重要性指标KSNI,并按该重要性递减的顺序对节点进行排序从而确定标签初始化以及标签更新的序列;然后提出一种基于节点影响力的标签初始化方法,运用该方法进行标签初始化可以减少网络中冗余标签的出现,从而有效减少标签迭代的次数;接着本文基于Salton指标定义了标签影响力并利用节点邻接信息定义了新的网络约束系数,用于解决标签更新冲突的问题;最后本文基于模块度增量提出一种社团后处理方法,进一步提高了算法的准确度。（2）为了弥补LPANI算法的不足,让算法的检测结果更贴近真实社团结构。本文提出了一种基于马尔可夫聚类的标签传播算法LPAMC。算法主要做出两点改进:首先,为了更加全面的定义节点重要性,本文利用MCL算法构建节点重要性矩阵,并将其与KSNI指标相结合提出新的节点重要性指标;然后,本文提出了一种基于社团相似度的社团合并策略,避免了模块度增量的分辨率限制问题带来的影响,使社团合并结果更接近真实结构。（3）为了完成重叠社团的检测,本文将LPAMC算进行拓展,提出了SLPAMC算法。主要有以下三个改进点:算法为每个节点设置标签存储列表,允许节点同时携带多个标签;在标签传播阶段筛选出对待更新节点网络约束最大的邻居节点作为标签传播节点,减少了标签传播过程中冗余标签带来的干扰;最后利用预设阈值对节点标签存储列表中的标签进行筛选,去除出现频率低于阈值的标签,剩下的标签则为节点所归属的社团。（4）本文将LPAMC算法和SLPAMC算法应用于某市“公共安全大数据分析”项目。将真实案件中的资金交易信息构建成人员关系网络,利用社团检测技术挖掘网络中的团伙结构,刻画网络中的核心成员,为刑侦工作寻找出更多潜在线索,最后通过案件的侦破验证了算法的在公共安全领域内的可行性。

关键词： 社团检测   图神经网络   图嵌入   聚类   标签传播  

摘要： 图神经网络与图嵌入是近年来兴起的深度学习模型,凭借自身强大的归纳能力在复杂网络的各种任务中展现出巨大优势。图神经网络能够归纳网络内容,发掘网络结构中的隐藏信息。图嵌入方法将网络中的节点转化为具有节点信息的表示向量,方便一些深度学习模型处理图数据。为了更好地解决社团检测问题,本文提出了两种基于图嵌入与深度学习的社团检测算法,用以在无属性或有属性信息的网络上分别解决非重叠与重叠社团检测问题。本文的主要内容如下:(1)基于空域卷积网络的社团检测算法CDSCN。算法首先利用图嵌入方法得到网络中节点的向量表示,再利用空域图卷积网络GraphSAGE调整节点表示向量,以局部模块度为依据重新定义了GraphSAGE的二次采样过程,使分属不同社团的节点的表示向量相互区分,同时保证了相邻节点表示向量的相似性,最后使用Birch聚类算法对节点进行聚类,聚类结果即为社团划分结果。(2)基于直推式传播网络的重叠社团检测算法OCDTPN。算法采用了小样本学习的思想,利用图嵌入结果或网络自带的属性信息建立传播模型,解决重叠社团检测问题。算法首先选择一些在原始网络当中具有局部最大度的节点作为社团核心,在传播网络中作为传播源头。随后分批次建立以节点向量高斯相似性为传播依据的标签传播网络。接着通过社团核心节点的原始标签与预测标签的误差修正传播模型,算法通过分批传播预测归属概率的方法找到网络中所有节点的重叠社团归属。与对比算法在真实网络和人工网络上进行实验,结果表明了本文提出的算法具有良好的社团划分性能。本文还将两种算法应用于世界中亚研究英文文献的信息发掘任务中,在文献分类和学术社群划分任务中取得不错效果,为课题研究提供了重要参考。

关键词： 动态加权国际贸易网络   动态社团检测   时序链路预测   节点重要性识别  

摘要： 国际贸易网络可以用来衡量国家的经济实力,具有复杂性和动态性的特点。准确地对动态加权国际贸易网络进行社团检测能够找到更为紧密的区域性贸易合作组织,对于各国制定相应的贸易政策和未来的发展计划具有指导意义。目前,如何提高动态加权国际贸易网络社团检测的精度有待进一步研究。本学位论文研究动态加权国际贸易网络的节点重要性排序和有向边权重预测,进而对动态加权国际贸易网络的社团检测进行研究。主要研究内容和成果如下:为了提高动态加权国际贸易网络中节点重要性识别精度,建立了加权国际贸易网络,提出了基于指数时序聚合模型的加权主分量中心性算法(WPCC-ETSAM)。选定UNCTAD数据库,将国家之间的贸易额作为加权国际贸易网络中连边的权重。在加权主分量中心性算法的基础上,WPCC-ETSAM算法通过引入指数时序聚合模型对动态加权国际贸易网络的节点重要性进行识别。经过实验对比,WPCCETSAM算法相比于三种经典算法在动态加权国际贸易网络节点重要性识别的准确性方面表现出很大的优越性。为了提高动态加权国际贸易网络中有向边权重预测精度,构建了基于图神经网络的时序链路预测模型,并基于该模型提出了有向边权重预测算法(DEWPATLPM)。通过在以生成对抗网络、长短期记忆网络和图卷积网络为基础的时序链路预测模型中引入矩阵分解变换模块对动态加权国际贸易网络中有向边进行权重预测。DEWPA-TLPM算法通过引入重构损失函数提高动态加权国际贸易网络中有向边的权重预测精度。实验结果表明,DEWPA-TLPM算法对动态加权国际贸易网络有向边权重的预测准确度比四种经典算法表现的更佳。为了提高动态加权国际贸易网络中社团结构的检测精度,提出了基于节点重要性和链路预测的多目标动态社团检测算法(MDCDA-NILP)。MDCDA-NILP算法采用基于节点重要性的标签传播策略对动态加权国际贸易网络的社团结构进行初始化,进而采用多目标动态社团检测策略对动态加权国际贸易网络的社团结构进行检测。经过实验对比,MDCDA-NILP算法对动态加权国际贸易网络中社团结构的检测精度比三种经典算法表现的更优。

关键词： 社团检测   量子进化   密度峰值   进化聚类   投资组合  

摘要： 复杂网络是复杂系统的抽象表示,是分析复杂系统中个体间联系以及系统整体结构的强有力工具。从小型图的分析,到大规模网络的处理,复杂网络作为新兴的跨学科研究,已经引起了诸多领域学者们的关注。社团结构普遍存在于各类复杂网络,探究复杂网络的社团结构有助于我们理解网络中的各种现象,有效的社团结构分析能够显著提高复杂系统的性能。在分析相关工作的基础上,本文从网络拓扑结构的角度出发,围绕静态网络社团检测、动态网络社团检测,以及社团检测在股票网络上的应用展开研究,主要研究内容及贡献如下:(1)提出了两种基于量子进化的静态网络社团检测算法模块度是目前广泛使用的衡量社团划分质量的度量标准,在此前提下,社团检测问题可以转化为以模块度为目标函数的寻优问题。本文将量子进化算法引入到社团检测,使用量子比特的概率幅编码方式,用量子染色体代表静态网络可能存在的社团划分,通过对量子比特的概率幅测量和坍缩的方法产生新的社团划分,在进化过程中搜索最优模块度对应的社团结构。为解决随网络规模增大产生的算法收敛速度减慢的问题,本文在前一个基于量子进化的检测算法基础上,创新性地引入一个向导量子染色体,在迭代过程中指导整个种群进化,达到快速收敛的同时,搜索更优的社团划分。两个基于量子进化的静态网络社团检测算法都能在寻优过程中自动确定社团数量,并有效发现社团结构。(2)提出一种基于扩展密度峰值聚类的静态网络社团检测算法真实的复杂网络结构中,往往存在社团尺度的显著差异,这种差异会带来社团划分中的分辨率限制问题。因此,本文定义了节点间连接强度和节点的相对连接系数,连接强度用来描述节点间的紧密度,相对连接系数用来描述节点的局部密度,连接强度和相对连接系数的定义,充分考虑节点相似度、节点间的连边、节点的度以及节点与其邻居节点各自连接强度的对比,使结构紧密的小型社团中的中心节点也能具有比较突出的相对连接系数,在社团检测的过程中更容易被发现。在基于密度峰值聚类思想选取候选中心节点的基础上,分析候选中心节点间的连接强度,剔除部分连接强度过高的候选中心节点,非中心节点则根据与已知划分的近邻节点的连接强度判断社团归属。基准网络和真实网络的实验证明,这种方法探测到的社团数目和社团结构更接近真实划分。(3)提出了一种基于连接强度和进化聚类框架的动态网络社团检测算法在动态网络中,许多基于进化聚类框架的社团检测算法都面临着平衡因子的选择问题,平衡因子的合理取值能体现出在满足时间平滑性的前提下,当前时间片与前一个时间片的社团划分存在多大程度上的关联。但目前大多数的检测算法是根据经验或者实验结果来确定这个参数,这忽略了网络拓扑结构变化所隐含的有效信息。为此,本文创新性的将节点间连接强度引入到进化聚类框架,把成本函数从社团结构的视角下推到节点间连接强度矩阵的变化,表示为相邻时间片连接强度矩阵的线性组合,并根据相邻时间片连接强度矩阵的变化幅度,动态确定平衡因子,修正当前时间片的连接强度矩阵,在此基础上使用谱方法进行划分。(4)将提出的社团检测方法应用于股票网络划分及投资组合分析金融领域中,投资的分散化可以减小投资风险,但如何选择合理的投资组合是投资者面临的重要问题。为此,本文将提出的社团检测算法应用到股票网络分析,用Pearson相关系数表示股票间的相关性,分别从中长期和短期两个角度,构建股票网络。在中长期股票网络中,通过社团划分结果和网络的拓扑结构确定投资组合,从整体上把握投资组合的方向。在短期股票网络中,对各周期的网络进行分析,及时探测网络的波动,并对投资组合方案做短期灵活调整。基于上证50指数股票网络分别进行了实证分析,证明提出的社团检测方法对投资策略及股市行业监管的有效性。

关键词： 复杂网络   社团检测   重叠社团   标签传播   K-shell分解  

摘要： 复杂网络是由真实世界中的复杂系统抽象而成的,挖掘复杂网络的特征对理解复杂系统有重要意义。重叠社团普遍存在于复杂网络中,检测重叠社团对分析网络的特征和发掘节点的隐藏属性有很大帮助。近年来,多种检测重叠社团的算法被提出,其中基于多标签传播方法的算法因其原理简单、易于实现以及其近似线性的时间复杂度受到广泛关注,但是这种算法存在稳定性差和精度不足的问题。因此,本文对节点的拓扑结构以及多标签传播算法的标签传播过程进行研究,提出了两方面的改进措施,以进一步提高多标签传播算法的精度和稳定性:（1）提出一种基于双层过滤策略的节点标签更新算法。本文对多标签传播算法中节点更新标签这一行为进行分析,设计了一种双层过滤策略,该策略的第一层用于帮助节点过滤接收标签,第二层用于帮助节点选择传播标签。然后基于双层过滤策略提出一种节点标签更新算法,以提高多标签传播算法的精度。（2）生成两种不同的节点更新顺序。本文对K-shell分解算法进行研究,提出了改进的K-shell分解算法。然后基于节点邻居关系和改进的K-shell分解算法提出两种节点社团中心性NC和NCK,并根据NC和NCK分别生成两种不同的节点更新顺序,以提高多标签传播算法的稳定性和精度。基于上述的两项措施,本文提出MLPA-DF和DFKS这两种改进的多标签传播算法。使用人造网络数据集和真实世界网络数据集对这两种算法进行实验,并用NMI指标和Q指标对实验结果进行评估。实验结果表明,MLPA-DF算法和DFKS算法有良好的稳定性。并且MLPA-DF算法在部分人造网络上的NMI指标比经典的多标签传播算法（COPRA算法、SLPA算法和LPANNI算法）提升5%到10%,在部分真实世界网络上的Q指标比经典算法提升1%到3%。而DFKS算法的NMI指标和Q指标比MLPA-DF算法有进一步提升,但是需要更长的运行时间。

关键词： 重叠社团   模块化密度   社团领导度   节点领导度   加权网络   从属度树  

摘要： 随着对复杂网络的物理结构和功能特征的深入研究,研究者们发现许多复杂网络都具有社团结构的特征。通过检测社团结构,有助于发现复杂网络中一些潜藏的规则和定律,对解决现实生活中的问题具有较强的应用价值。基于优化模块度函数的社团检测算法无需事先输入社团数目,但其本身存在分辨极限问题。另外核心节点选择的随机性以及社团的边缘节点难以划分影响了社团检测的准确性。对此本文提出了基于社团领导度和模块化密度的重叠社团检测CL-MD(Community Leading And Modularity Density)算法。该算法一方面根据社团领导度以及节点中心度选取核心节点进行划分,解决了节点的随机性选取问题。另一方面模块化密度函数能够克服分辨极限问题,并通过矫正因子实现边缘节点的划分,从而提高社团划分的准确性。相比较于无权网络,加权网络更贴近现实世界。针对加权网络所提出的社团检测算法普遍存在关键节点的随机性所导致社团划分的准确性较低的问题。为此,本文构建了一种基于加权领导度和从属度树的复杂网络重叠社团检测方法模型。该模型中首先依据共同邻居节点的权重和,定义了加权领导度,其次根据影响力较大的节点作为关键节点建立从属度树,依据树的层次结构,对从属度树进行划分,提高其社团检测准确性。在计算机人工网络和真实网络上与其他四个加权网络社团检测算法进行对比,实验表明加权领导度和从属度树的算法模型检测社团结构的准确性更好。

关键词： 图像分割   运动目标检测   复杂网络   社团检测   标签传播   背景差分  

摘要： 图像分割与运动目标检测一直是图像分析与计算机视觉领域中的重要研究内容,在生物医学、自动驾驶、智能监控等领域应用广泛。近年来,随着复杂网络的蓬勃发展,复杂网络中的社团结构逐渐受到研究人员的密切关注。目前,许多优秀的社团检测算法被提出,其中标签传播算法因其近似线性的时间复杂度被许多学者使用与研究。本文对标签传播算法进行改进,并使用改进后的标签传播算法对图像分割及运动目标检测进行研究,主要研究内容如下。(1)标签传播算法在节点排序和节点更新阶段存在多个随机选择的过程,导致划分的社团结构不稳定,且算法不适用于图像网络。为此本文提出一种基于颜色特征的标签传播算法—CFLPA算法,以超像素区域为节点,构建无权图像网络,根据图像网络节点的颜色特征对节点进行排序,将节点之间的颜色特征相似性作为节点标签更新的依据,实现对图像网络的社团划分。CFLPA算法不仅能划分出稳定的社团结构,而且也能有效地处理图像网络。(2)提出了一种基于网络标签传播的图像分割算法—NLPAIS算法。应用CFLPA算法对图像网络进行社团划分,在划分的基础上建立加权图像网络,采用所提出的基于权重与节点度的标签传播算法获得加权图像网络的社团结构,达到图像分割的目的。NLPAIS算法与其他应用复杂网络理论对图像分割的算法相比,分割精度有较大的提升,分割轮廓也更加完整。(3)提出了一种结合复杂网络与背景差分的运动目标检测算法—CNBS算法。以像素点或同像素的连通区域为节点,对视频帧的R、G、B通道分别构建图像网络。使用CFLPA算法对图像网络进行社团划分,利用或操作将划分的社团融合,得到视频帧的预分割结果。将预分割结果作用于视频帧及其相邻两帧,构建三个帧内属性网络,通过节点的属性变化确定候选运动目标区域,对候选运动目标区域进行局部背景差分确定运动目标。实验结果表明CNBS算法可以有效地消除鬼影及噪声现象,和8个优秀的运动目标检测算法相比,评价指标也有明显优势。

关键词： 复杂网络   社团检测   图像预分割   运动目标检测   多目标跟踪  

摘要： 近年来,计算机视觉研究蓬勃发展,在视频监控、无人驾驶、虚拟现实等领域带给人们新的体验。图像分割、目标检测和跟踪是计算机视觉领域内的重要任务,是一系列高级任务的基石。本文将复杂网络社团检测方法应用于图像分割、运动目标检测和多目标跟踪,具体工作内容如下:(1)提出了一种基于图像轮廓信息的网络构建和图像预分割算法。首先利用MS算法检测图像中的轮廓,将轮廓划分的区域作为网络中的节点,区域间的颜色相似性作为相应节点连边的权值,构建了图像的加权区域邻接网络;然后结合社团检测算法构建了图像的预分割算法。实验表明,本文的图像网络结构优于基于像素和超像素的图像网络,本文的图像预分割算法相比其他算法也有优势。(2)提出了一种基于图像预分割和背景建模的运动目标检测算法。将首帧视频利用本文算法进行预分割,并将分割结果应用到后续视频帧,通过计算连续帧间不同分割区域颜色的绝对差和,建立背景模型;根据区域的熵值更新背景模型,与当前帧做背景差分,得到差分图像,对其再次用本文方法做预分割,分析差分图像不同区域的亮度平均值,得到自适应的前景阈值,从而检测出运动目标。实验结果表明,本文算法的检测结果令人满意,并且在前景目标短暂停止时的检测结果优于其他算法。(3)提出了一种基于目标检测的视频帧间网络构建和多目标跟踪算法。首先将视频各帧的目标作为网络节点;然后综合目标的外观特征、HOG特征和位置特征计算相邻两帧中目标的相似性,为对应节点的边赋予权值;最后分组检测视频帧间网络的社团结构,得到该组视频中目标的轨迹片段,合并轨迹片段得到目标的最终轨迹。实验结果表明了本文算法跟踪目标的有效性,同时在MOT17数据集上的测试结果也表明,本文算法有着较高的跟踪准确度,并且对无严重遮挡的检测目标能够稳定跟踪。