关键词： 复杂网络   神经网络   模块度函数   社团结构   特征向量  

摘要： 针对复杂网络的社团结构提取问题提出了两种新的复杂网络社团结构提取算法:连续神经网络(CNN)算法和离散Hopfield神经网络(DHNN)算法,对提出的两种社团结构提取算法在8个实际网络上进行了仿真实验,结果表明,DHNN社团结构提取算法比CNN算法及Newman的特征值特征向量算法得到的Q大.同时DHNN算法不需要进行求特征值特征向量之类的计算,只需要进行简单的加法乘法运算便能提取到网络中的社团结构.即所提算法特别是DHNN算法具有强大的计算能力,可以提取出规模更大的复杂网络中的社团结构.

关键词： 农产品供应链网络   社团结构检测   重叠社团   风险级联失效   鲁棒性  

摘要： 农产品在其生产、加工、销售等流通过程中,其质量的安全与稳定引起了广大人民群众的关注。随着5G时代的到来,信息的网络化与全球化使得农产品供应链的结构和风险传播方式变得更加复杂,所以供应链网络区域协同化管理与风险级联传播问题成为了亟待解决的问题。复杂网络理论具有解决大型真实网络问题的能力,为开展农产品供应链网络相关的研究给予了新的方法。本文利用复杂网络中社团检测与级联失效理论,通过建模及其仿真,对农产品供应链网络进行社团结构检测,提出了一种控制风险级联传播的方法。力图为农产品供应链网络区域化协同管理提供理论参考,为具有社团特性的农产品供应链网络流通风险防控与网络鲁棒性的提升提供新的技术指导及理论参考。本文具体研究内容如下:(1)研究农产品供应链网络局部社团与重叠行检测方法,针对供应链网络规模大、全局信息获取难等特点,提出一种基于强度优化的局部社团结构检测方法,对社团进行社团划分;并在此基础上,提出了一种基于强度优化的局部社团重叠性检测方法,分析了不同社团中的重叠节点在社团内隶属度,仿真实验表明该方法具有较高的社团划分准确性和检测速度。(2)对农产品供应链网络风险级联失效进行建模仿真分析,基于“负载-容量”(ML)模型和节点本身及其邻居的节点重要性信息,提出一种双参数下可调权重的初始风险负载定义方法,并运用风险负载重分配的方式,对农产品供应链网络进行完整性和鲁棒性的研究,得出了既能够保证其最大完整性,又能提高网络鲁棒性的初始负载定义最优参数。(3)对河南省焦作市辖区蔬果供应链网络进行建模与仿真,将两种农产品供应链网络进行局部社团与重叠性检测,对其进行社团紧密程度划分,获得了较高的划分准确性。建立相应的供应链网络风险级联失效模型,分析其级联失效的过程,得到了能使果蔬供应链网络具有高完整性和高鲁棒性的负载最优参数。

关键词： 社团检测   鲁棒性   攻击方法   增强方法   开源软件  

摘要： 社团结构是存在于许多复杂网络中的一个重要性质。检测网络中的社团结构可以揭示其功能与特点，在社会学、生物学等多个领域有着很大的研究价值。研究社团检测算法的鲁棒性及增强方法，有助于科研工作者对算法进行更加全面的评估，进一步提升社团检测结果的准确性。目前已有的关于社团检测鲁棒性的研究更多关注于恶意攻击对局部检测结果的影响，即目标社团划分错误，较少的研究从全局角度出发，观察遭受攻击后社团检测算法整体的性能下降情况。而在增强方法的相关研究中，已有工作多是通过链路预测相似性指标对网络结构进行调整。如何选取关键节点进行更有效的连边扩充、如何更好地捕获节点间的结构相似性等问题都值得更多的探索。针对上述问题，本文进行了攻击方法和增强方法的研究，并在Apache开源软件数据集上加以应用，具体包括以下三个部分：　　(1)本文从攻击方法的研究入手，观察社团检测算法在遭受恶意攻击时的性能变化，进而评估算法的鲁棒性。特别地，本文从全局角度出发，提出了一种基于遗传算法的Q值攻击方法Q-Attack，针对网络结构特性及攻击目标进行了编码方式和适应度函数的设计。比较Q-Attack与三种启发式攻击方法的攻击效果，实验结果表明Q-Attack能使社团检测算法的性能下降更为明显，同时该方法具有较好的迁移性。观察各社团检测算法在遭受攻击后的性能变化，可以得出，Louvain算法及Infomap算法较实验中其它几种社团检测算法具有更好的鲁棒性。　　(2)不同于研究性能更佳的某种社团检测算法，对增强方法的研究可以通过改善网络结构来提升多种社团检测算法的性能。具体地，本文提出了一种基于关键节点连边扩充的网络增强方法NE-EABC，创新地利用连边的介数中心性进行关键节点的选择，将基于Jaccard相似系数的连边扩充方式和基于重启随机游走采样的连边扩充方式结合，进行网络增强，提升社团检测算法性能。实验结果表明多数情况下NE-EABC较对比方法能表现出更好的增强效果。此外，本文还检验了对抗网络经NE-EABC增强后的社团划分结果质量，结果表明NE-EABC可以改善对抗网络结构，具有一定的防御能力。　　(3)将所提方法应用到Apache开源软件数据集上。本文主要从Apache数据中提取信息构建邮件通讯网络，特别地，考虑到原始数据中不存在开发者标签信息，本文提出了一种开发者邮件通讯网络构建方式，根据开发者所参与的项目补充标签信息，便于使用NMI、ARI指标评估社团检测结果。实验中将攻击方法Q-Attack和增强方法NE-EABC应用于新构建的网络上，进一步验证方法的效果，探究开源软件数据的安全性问题。

关键词： 复杂网络   节点中心性   精准k核   库仑力中心性   标签传播算法  

摘要： 复杂网络是现实世界中复杂系统的抽象模型,它将复杂系统中的实体对象抽象为节点,将实体对象之间的显性或隐性关系抽象为边。节点重要性评估和社团检测作为复杂网络中最热门的两个课题,在计算机、通信、刑侦、社会、金融、交通、生物等诸多领域中得到了广泛的研究与应用。关键节点是构成一个网络并实现其信息传递功能的核心要素,识别关键节点并对其着手保护能够有效提升网络的抗毁性,也能够从关键节点入手提出更高效的网络攻击策略。此外,复杂网络中存在一种特殊的特征结构,社团结构。具体体现在社团内部节点的联系较为紧密,而社团之间的节点联系则相对稀疏,而发现网络中社团结构的过程则称为社团检测。利用社团检测能够轻易地揭示网络中的隐藏结构、反映节点之间的相互关系、分析复杂网络的潜在信息以及预测网络的局部功能特性。本文着手研究了复杂网络中节点重要性评估方法和社团结构检测方法,其主要成果如下:k核是一种常见的节点重要性评估指标,但由于其存在破坏网络整体结构信息、忽略邻居节点影响力等缺点导致每个节点难以量化区分。为了提高关键节点的识别精度,本文首先改进了k核的分解过程,提出了精准k核Ak(Accurate k-shell)。考虑到网络中局部特征信息和全局结构信息对节点的影响,本文随后将精准k核应用到重力中心性GC(Gravity Centrality)中并提出了库仑力中心性CFC(Coulomb Force Centrality)。信息学中的香农熵在网络关键节点识上具有良好的扩展性,通过结合邻域度中心性、邻域精准k核以及库仑力中心性三者的香农熵,最终本文提出了混合中心MC(Mixed Centrality)。该指标能将节点的拓扑结构信息、位置信息、局部特征信息和网络整体拓扑结构信息充分融合,消除单一指标评估节点时产生的片面性,从而达到对节点多元化评估的目的。在7种真实网络下,对MC和其它节点评估指标分别从单调性和准确性上进行了一系列实验,实验结果表明MC具有更好的关键节点识别性能。标签传播算法(LPA)是一种高效快速的社团检测算法,能够适用于不同规模大小的网络。然而,由于标签的随机传播和收敛条件的不明确致使实验结果非常不稳定。为了进一步识别出网络中的关键节点,本文首先在CFC的基础上提出了联合中心性UC(Union Centrality)。随后,针对LPA中节点随机选择标签这一缺陷,本文利用UC设计出了用于量化评估节点标签传播能力的标签选择性LS(Label Selectivity)。通过将UC和LS这两种指标应用到LPA中,本文最终提出了基于库仑力中心性的标签传播算法CFCLPA。该算法消除了原始LPA中的随机性并且明确了算法的结束条件,从而使其具备了高效精确的社团结构识别能力。在真实网络和LFR基准网络下进行了一系列测试和比较,实验结果表明CFCLPA具有更优秀的社团检测性能。

关键词： 社团检测   邻接矩阵   标签传播   非负矩阵分解  

摘要： 在互联网飞速发展的背景下,复杂网络研究已经成为一项热门研究方向。复杂网络中往往存在属性相似或者关系紧密的结点,社团检测方法通过分析复杂网络中结点之间的联系,将结点划分到不同社团,从而得到社团网络结构。社团检测算法分为两类,即非重叠和重叠社团检测算法。传统的非负矩阵分解（Non-negative Matrix Factorization,NMF）算法将网络的邻接矩阵分解,从而得到非重叠社团结构,但邻接矩阵体现的是每个结点与其直接邻居之间的关系,位于同一社团的结点往往并不只是直接邻居关系。本文在NMF研究的基础上,提出了两种算法,非重叠社团检测算法LPNMF（Label Propagation on Non-negative Matrix Factorization）,重叠社团检测算法Link NMF（Non-negative Matrix Factorization on Link-graph）。（1）社团检测算法LPNMF:使用标签传播算法对网络进行社团划分,并得到社团的模块度,在标签传播算法得到的社团结构中,如果两个结点属于同一社团,为其在邻接矩阵中的元素值附加模块度的值,来增强这些结点间的关系。因为标签传播算法有着高效率、不稳定的特性,因此通过多次标签传播,快速得到多个社团,加强每次在同一个社团中的结点之间的关系,然后对新的矩阵进行非负矩阵分解,得到网络的最终社团结构。（2）重叠社团检测算法Link NMF:先将网络转化为边图,获得边图的邻接矩阵,与LPNMF算法的思想类似,通过标签传播算法来增加边图的邻接矩阵中属于同一个社团的元素值,再对由边图的邻接矩阵和标签传播算法获得的新矩阵进行非负矩阵分解,得到边的划分结果,最后将边图还原为原始图。在LPNMF检测到的隶属矩阵上,设置阈值参数来过滤掉多余的重叠结点,获得网络的最终重叠社团结构。在多个数据集上与多个算法进行对比实验,结果证明,本文提出的两个算法在非重叠网络和重叠网络上都能得到高质量的社团划分结果。

关键词： 复杂疾病   多组学数据   遗传网络   模式挖掘   社团检测  

摘要： 复杂疾病往往是由遗传、环境等多种因素共同作用导致的。挖掘复杂疾病的潜在遗传模式是揭示复杂疾病遗传机理的重要方法,其中基于多组学数据的复杂疾病网络模式挖掘方法为识别复杂疾病的遗传因子提供了新思路。本文以仿真数据和真实的复杂疾病多组学数据(基因表达数据、甲基化数据、拷贝数变异数据、单核苷酸多态性数据等)为基础,以遗传交互网络的构建与网络模式挖掘方法为手段,致力于发现复杂疾病的潜在遗传模式。具体研究内容如下:(1)针对复杂疾病多组学数据的网络构建问题,提出交互部分互信息测度,有效量化基因之间的依赖关系,从而构建基因之间的交互作用网络。将该方法应用到复杂疾病的基因表达数据上,进而从该基因网络中提取了与复杂疾病相关的特征基因以及重要通路。(2)针对复杂疾病遗传因子间的高阶交互作用检测问题,引入了两种节点用于构建高阶网络:真实节点表示遗传因子,虚拟节点表示遗传因子之间的交互作用。对构建的高阶交互网络进一步挖掘得到高密度子图,并对其进行了相关生物意义的验证。(3)针对复杂疾病遗传网络的节点检测问题,提出了基于归一化中心性测度的网络节点挖掘与分析方法。首先,识别复杂疾病的差异表达基因,并构建差异表达基因之间的遗传交互网络。然后,提出归一化中心性测度,全面分析该遗传网络中基因的局部特征和全局特征,从而充分挖掘网络中蕴含的特征基因以及重要生物通路。(4)针对复杂疾病多组学整合数据的社团挖掘问题,提出基于鲁棒主成分分析方法的社团挖掘与分析方法。首先,对多个复杂疾病的基因表达数据进行整合,引入鲁棒主成分分析方法从整合数据中筛选差异表达基因,并构建差异表达基因之间的交互作用网络,进而从网络中提取重要的社团。(5)针对复杂疾病多组学数据的网络构建以及网络整合问题,提出基于非负矩阵分解的网络整合与分析方法。首先,基于皮尔森相关系数构建复杂疾病多组学数据的异质性网络。然后,利用该整合方法对多个异质性网络进行整合,充分考虑不同的遗传因子之间的交互作用机制。最后,从网络中挖掘到与疾病相关的核心社团,并进一步检测出重要的生物通路。各项实验表明,本文提出的方法比同类方法在网络模式挖掘中更具优势,且可以检测到更多与复杂疾病相关的潜在遗传模式。

关键词： 社团检测   近邻   影响力   模体   图绘制  

摘要： 生活中存在着大量的复杂系统,这些复杂系统可被抽象表示为复杂网络,例如传染病网络、生物网络、人际网络等。社团结构可以揭示复杂网络的结构和功能特性,是复杂网络最基本的特征。发现社团结构的过程就是社团检测。随着复杂网络的种类愈来愈多,社团检测算法面临新的挑战,这就需要研究人员考虑不同的情况,提出高效,准确的社团检测算法。本文针对目前社团检测中两种不同的问题,提出了两个社团检测算法:DCDC和Vortex。DCDC算法以互k近邻连接的方式发现社团核心,克服了该类算法难以出检测任意结构,任意规模社团的局限性。Vortex算法是Black Hole算法的改进算法,Vortex算法以基于高阶结构motif的引力模式发现社团核心来进行社团检测,克服了Black Hole算法在节点度差别很大网络上表现较差的缺点。DCDC算法和Vortex算法的基本原理及优势如下:（1）DCDC如何检测任意结构,任意规模的社团是社团检测领域的一个难点。为解决该问题,提出了一种可以通过k最近邻发现社团核心的社团检测算法DCDC。该算法首先遍历所有节点,将两个互为近邻的相似节点及它们的共同邻居聚集到一个社团核心中;然后,在遍历过程中,若不在核心中的节点与某个社团核心内任何节点存在互近邻关系,那么该节点也会被吸引到这个社团核心中;接着,该算法检测出社团核心中的异常节点,并将其标记为无类标节点;最终,该算法利用影响力分配无类标节点,得到最终的社团结构。该算法简单且时间复杂度较低。此外,该算法不需要社团个数作为先验参数。通过在4个真实网络以及3个不同规模的LFR人工合成网络的综合测试表明:DCDC算法能检测出任意结构与任意规模的社团,且发现的社团质量高于所用的5个基准算法。（2）Vortex大部分社团检测算法在节点的度差别较大的网络上都很难检测出高质量的社团结构。Black Hole算法是一个鲁棒性较强的图嵌入算法,该算法通过graph drawing中的图嵌入方法得到网络在二维平面上合力最小的分布,再通过DBSCAN聚类算法得到最终的社团结构。由于仅考虑到节点之间的低阶联系,即节点间的边,该算法在节点的度差别较大的网络上表现不佳。为了解决这个不足,引入了高阶结构motif,提出了基于motif引力模式发现社团核心的社团检测算法Vortex。引入高阶结构motif进行图嵌入时,可从全局角度考虑两个节点的相似性,这使得Vortex算法能不受网络间节点联系稀疏影响并发现节点间隐含的联系。此外,Vortex算法还提出了基于motif来分配无类标节点的方法。实验结果表明:无论对度差别较大的人工网络,还是对6个有真实类标签的小网络及8个无真实类标签的较大的网络,Vortex算法检测到的社团结构在大多数情况下不但较Black Hole算法质量高,而且较其它6个对比算法更高。

关键词： 复杂网络   节点中心性   社团结构检测   电阻距离   节点相似度   星型邻域子图  

摘要： 在现实生活中,有很多网络都是以复杂网络的形式存在,例如社交网络、交通网络、电网、生命科学领域的各种网络等。在复杂网络中度量节点中心性和检测社团结构对于流行病传播与控制、信息扩散、社交网络分析等都具有非常重要的意义。近年来,研究人员提出了许多在复杂网络中度量节点中心性和检测社团结构的算法。这些算法为各个领域的研究人员理解复杂网络结构、功能及动态演化进程提供了强有力的工具。然而,一些传统的节点中心性度量方法虽然能够在一定程度上度量网络节点中心性,但是也存在一定的局限性,此外将社团结构检测问题与节点相似度结合分析研究还有潜在空间。因此,如何度量网络中节点中心性及检测与评估网络中社团结构,提出更加准确的度量节点中心性与检测社团结构算法仍然是当前重要的研究课题。针对复杂网络节点中心性度量策略,本文基于复杂网络理论及图谱理论,综合考虑了网络节点的局部信息,并在传统算法的基础上提出新的节点中心性度量方法。对于社团结构检测,使用网络中节点间电阻距离的特有性质,将电阻距离用于计算网络中节点相似度,并将聚类作为辅助手段用于检测社团结构,提出基于电阻距离与节点相似度的社团结构检测算法。本文的主要内容及创新性研究如下:(1)提出基于度与H指数扩展的中心性度量算法(DH)。度中心性是目前最简单的一种节点中心性度量方法,该方法通过计算邻居节点的数量来度量节点中心性,即节点的邻居节点越多,节点中心性越大,其影响力越大。但度中心性只考虑了节点的邻居节点的数量而忽略了邻居节点的影响力,这使得度中心性存在一定的局限性。H指数中心性虽然考虑了邻居节点的影响力,但却忽略了节点自身的度以及网络上部分结构信息。将基于度与H指数度量算法同时考虑,结合节点自身的度、H指数、和邻居节点的H指数三个因素,提出基于度与H指数扩展的中心性度量算法,弥补了原始度中心和H指数的不足,使其更准确地度量网络节点中心性。从真实网络和BA无标度网络的仿真结果可以看出,本文算法可以准确、有效地度量网络节点中心性。(2)提出了基于电阻距离和节点相似度的社团结构检测算法(CDRS)。社团结构检测对于理解网络的结构和功能都具有重要意义。电阻距离是网络本身固有的一种距离函数,在许多领域都有重要的应用。节点间的电阻距离越小,节点间的路径越多,连接越紧密,节点也越有可能在一个社团中,反之亦然。节点相似度通常用于度量网络中两个节点的连接紧密程度,两节点相似度越大,两节点连接越紧密。节点的星型邻域子图包含了节点自身和其所有邻居节点,充分体现了节点的局部拓扑连接关系。本文结合节点电阻距离和节点星型邻域子图的公共节点提出新的节点相似度计算指标,较好地考虑了节点的局部拓扑连接关系,提高了度量节点相似度的准确性。根据最邻近节点应该处于同一个社团的思想,沿着使得模块度增大的方向进行聚类,使得本文算法在网络中检测出社团结构的结果具有较大的模块度,从而获得了社团结构比较明显的社团结构集合。从真实网络仿真结果可以看出,本文算法可以有效地检测出网络中的社团结构。

关键词： 复杂网络   重叠社团检测   多目标优化   双编码   网络归减  

摘要： 现实世界中的复杂系统与人们的生活密切相关,这些复杂系统都可以表示为复杂网络,其中社团结构作为复杂网络的重要特性之一,对于分析复杂网络的结构属性和潜在功能具有重要作用。复杂网络中的社团结构主要分为两类:一类是非重叠社团,即网络中节点只能属于一个社团;另一类是重叠社团,即网络中节点可以属于多个社团。由于现实世界中大部分复杂网络都具有重叠社团结构,所以本文关注重叠社团检测问题。为了解决这个问题,基于多目标进化优化的重叠社团检测方法近年来引起研究人员越来越多的关注,该类方法可以同时优化多个互相牵制且充分利用网络结构信息的目标函数,最终得到一组不同层次的网络划分,决策者可以根据自己的要求来选择满足条件的社团划分。将多目标进化优化方法应用于重叠社团检测的一个主要挑战就是设计合适个体编码和相应的进化策略,为此,本文从编码的角度出发设计一种双编码表示策略,可以有效对种群中个体进行编码,并解码获得重叠社团结构。在双编码的基础上,本文提出一种基于双编码的重叠社团检测多目标优化方法。为了解决大规模复杂网络中的重叠社团检测问题,本文利用网络归减策略来减小网络规模,并在双编码的基础上又提出一种基于归减的双编码大规模重叠社团检测多目标优化方法。本文的主要研究工作如下:(1)本文设计了一种双编码表示方法,用于分别对社团结构和重叠点进行编码,并提出一种基于双编码的重叠社团检测多目标优化方法(DRMOEA)。在重叠社团检测多目标优化算法中,如何设计合适的编码使得编码能够全面检测重叠点是当前存在的挑战之一。为此本文将复杂网络重叠社团检测问题转化为一个多目标优化问题,同时考虑社团内部联系比例和社团外部联系比例,并提出基于双编码的重叠社团检测多目标优化方法,简称为DRMOEA。在DRMOEA算法中,提出基于社团边界点的初始化策略来获得好的初始个体,从而提高算法检测性能。在进化过程中,针对重叠点编码提出基于精英个体边界点的交叉策略,该策略利用社团边界信息以及种群中精英个体局部信息指导个体进化,从而进一步提高算法检测性能。最后通过实验验证DRMOEA能够有效处理重叠社团检测问题。(2)本文提出一种基于归减的双编码大规模重叠社团检测多目标优化方法(RDRMOEA)。随着网络中节点数目增加,种群中个体的编码长度会随之增大,同时种群的搜索空间也会指数级增大,为此本文提出一种基于归减的双编码大规模重叠社团检测多目标优化方法,来解决大规模复杂网络中的重叠社团检测问题。在RDRMOEA算法中,首先将网络中连接紧密的节点进行归减并重构网络,在进化过程中利用种群间个体的局部相同特性进一步对网络进行归减,并提出个体局部修复策略,用来修复网络中被错误归减的节点。最后在真实网络和LFR合成网络中的实验结果表明,RDRMOEA算法能够有效处理大规模复杂网络重叠社团检测问题。

关键词： 复杂网络理论   超像素分割   社团检测   图像分割   度分布   目标检测  

摘要： 图像分割和目标检测一直是图像分析与计算机视觉领域的重点研究课题。随着近几十年来复杂网络理论的快速发展,将复杂网络理论应用到图像分析与计算机视觉领域成为研究人员关注的问题之一。本文以复杂网络理论中的社团检测和节点度分布理论为中心,对图像网络的构建、图像分割和视频中运动目标检测算法进行了研究。具体研究内容如下。(1)提出了一种基于局部网络模块度增量的超像素分割算法(LocalNet)。以像素点颜色相似性建立图像的邻接加权网络,以模块度增量作为判断准则,对邻接网络进行社团划分,完成图像的超像素分割。该算法克服了经典的SLIC超像素分割算法分割精度不足,易出现欠分割的缺点。同时应用超像素分割算法对图像进行分割,以超像素区域为单位作为网络节点,构建图像网络结构。与以像素点为节点构建图像网络相比,可以提高图像处理的效率。实验结果表明LocalNet算法与SLIC及其改进算法VASLIC和MMTDSLIC相比,具有更高的分割精度。(2)提出了一种结合局部度中心性的图像分割算法(LDCS)。对图像应用LocalNet算法进行超像素分割,以超像素区域为单位作为网络节点,区域间的颜色、纹理相似性作为连边权值,构建图像邻接加权网络结构,结合局部度中心性,计算图像网络的局部度中心节点作为图像网络社团的中心,进行网络的社团划分,完成图像分割。实验表明该算法的图像分割精度高于应用复杂网络理论进行图像分割的框架算法GFCNIS。(3)提出了一种基于图像网络节点度变化量的运动目标检测算法(IN-MOD)。对视频中每帧图像应用LocalNet算法进行超像素分割,以区域颜色、纹理相似性建立图像的邻接加权网络结构,按照时间顺序建立视频网络节点的时间序列,寻找每帧图像网络节点度变化节点作为候选运动目标,应用本文LDCS图像分割算法以及K-means聚类算法对检测出的运动目标候选区域进行修正。实验结果表明,本文IN-MOD算法在检测运动目标发生镜头抖动、光照变化等特殊情况时,具有较好的检测效果。