关键词： 复杂网络   社团结构   亲密度   二分网络  

摘要： 社团结构指的是复杂网络内部聚合的情况。复杂网络的聚类情况对研究复杂网络的网络行为、拓扑结构和信息传播与挖掘都有十分重要的意义。所以,近几年,越来越多的学者投身到复杂网络的社团结构检测中,同时,大量的算法也被提出。而不同的网络,由于其网络特性的差异,其社团结构的检测方法也存在不同,且存在一定的问题。如在重叠社团检测上重叠界限要求过于严格,而对于有向加权网络和二分网络的社团检测,研究过程中则可能存在信息丢失等问题,需进一步的探究。为此,本文针对不同的网络提出了三种不同的基于相似度的社团结构检测算法,主要工作和创新点如下:(1)提出了一个基于关键节点的重叠社团划分算法。算法通过对复杂网络的节点进行预处理,筛选出其中的关键节点,并形成以关键节点为中心的核心区域,随后吸收与该核心区域关系紧密的节点以形成初始社团,再根据吸收度扩大社团。算法利用了一种初始网络筛选方法和最新的吸收度函数对重叠社团进行检测。实验结果表明了该算法能有效地检测出网络的社团结构,且算法时间复杂度相对较低。(2)提出了一种基于非对称亲密度的有向加权网络的社团检测算法。通过对有向加权网络节点间的关系特点的研究,给出了一种既能体现节点对间直接关系又能体现其间接关系的亲密度参数,并将其设计和引申至社团间的亲密关系。利用节点间的关系对网络进行聚类分析,最终根据最优模块度选择出最终的划分结果。通过对比试验发现了该算法的优越性和亲密度参数设计的合理性。(3)提出了一种二分网络社团结构检测算法。通过分析二分网络中节点间的互连特点,设计出分别体现二分网络中同种类型节点间与异种类型节点间的亲密度关系。利用该亲密度关系分析和聚类节点,形成多个子社团,再通过社团间的关系参数,进一步合并子社团,以形成最终的社团结构。实验结果很好的反映了算法和参数设计的优越性,并能有效地检测出网络的二分社团结构。本文设计和实现了针对不同网络所提出的三种不同的基于网络中节点间的亲密关系的社团检测算法,研究不断地深入、递进。其中基于关键节点的重叠社团划分方法和非对称亲密度的算法针对的是单分网络,而第三种算法则应用于二分网络。针对不同的网络,本文使用不同的评价参数进行分析,最终实验结果也表明算法设计的有效性和优越性。

关键词： 社团检测   谱聚类   演化聚类   动态协同训练  

摘要： 社团结构作为复杂网络的普遍特征对分析复杂系统具有重要意义。由于真实网络是动态变化的,动态社团检测方法近年来获得广泛关注。本文提出一种多相似性协同训练谱聚类方法用于动态网络社团检测,该方法首先协同训练多种相似矩阵构造新的相似矩阵,然后通过演化聚类思想融合历史信息。最后,将提出的动态社团检测方法应用到人工生成数据集和真实网络中验证方法的有效性和准确性。本文的主要研究工作如下:(1)提出一种多相似性谱聚类方法用于静态网络社区结构检测。目前存在多种度量节点间相似性的方法,不同的度量方法可能会导致聚类结果有较大差异。本文借助协同训练思想融合已有的多种相似性度量方法,构造出新的相似性矩阵。(2)在实际复杂网络中,网络节点及节点间关系具有时变性,现存的动态社团检测算法多采用两步策略或演化聚类。本文基于演化聚类框架,提出了一种动态协同训练方法以融合动态网络中的多种相似性度量。(3)为了更好运用到真实网络中,提出了一种直观的方法自适应选择演化聚类中的平滑参数。并将提出的动态协同训练方法扩展到结点和社区个数可以随时间变化的情景中。(4)将上述方法应用到人工生成数据集和真实数据集中,对比了经典的基准模型,实验结果表明提出的方法大多情况下都可以得到较好的实验结果。

关键词： 社团检测   链路预测   标签传播   节点相似性  

摘要： 随着复杂网络的不断深入发展,对网络结构的探知要求也越来越严格,人们由此提出了社团检测算法并不断地进行深化改进。在现实网络中,节点与边的分布并不均匀,总是有着稠密或稀疏的地方,稠密的局部网络以社团的结构出现,而稀疏的连边则是整个网络中社团与社团的边界。链路预测理论对网络的研究是通过网络的内部结构、节点与连边等信息,来预测网络中未连接的节点之间产生连接的可能性。节点间的相似性是度量两个节点之间关系的重要指标,两个节点之间相似性越大,说明两个节点之间越可能有边相连。本文基于节点相似性的链路预测理论,提出了一类针对非重叠网络的社团检测算法。该类算法对网络丢失信息通过链路预测进行补全,对网络冗余信息通过删除链路进行分裂,由此自动获取社团数目以及核心节点集,并针对孤立节点进行标签传播处理,最终实现网络聚类。本文首先提出了两种基于节点相似性的社团检测算法,分别是基于共同邻居数指标(CN指标)的ADL-CN算法和基于共同邻居的度的倒数和指标(RA指标)的ADL-RA算法,并对算法进行了详细的阐述。然后,根据上述两个算法存在的缺陷和不足,提出了基于两种指标(CN指标和RA指标)相结合的ADL-CNRA算法。最后,将本文所提出的三个算法在数据集上与两个经典算法进行实验对比,验证了本文所提算法有较好的社团划分效果,并且优于对比算法。

关键词： 社团结构   标签传播   随机游走   模块度   信息熵  

摘要： 网络科学为解决现实生活中各种各样的复杂问题带来了新的视角。真实网络系统通常具有一些非平凡的拓扑特性,如重尾度分布、高聚集系数、同配异配性、社团结构和层级组织等。其中,社团结构是复杂网络最突出的特性之一,即网络中存在一些内部连接紧密的群组,而群组与群组之间的连接较为稀疏。社团结构的检测在物理学、生物学、社会学和计算机科学等领域具有重要的理论意义和广阔的应用前景,近年来吸引了很多不同领域研究者的关注。本文介绍了社团检测的基本概念和方法,探讨了聚类意义以及如何测试和比较各种方法,讨论了社团检测在真实网络中的应用,并深入研究了三种基于传播动力学的社团检测方法。具有创新性的研究成果有以下三个方面:1.基于网络随机游走动力学特征和信息熵最小化,提出了一种新的社团检测方法-LPAf。它基于以下思想:如果按照网络的社团结构对其节点进行二级编码,则网络上随机游走的平均描述长度(加权信息熵)将会显著减小。平均描述长度是网络划分的函数,对于同一个网络,较好的划分对应较短的平均描述长度。通过改进原始标签算法的多数投票规则,使平均描述长度在标签扩散过程中逐渐减小,可以精确且有效地检测社团结构。在合成网络和真实网络上的测试结果表明,LPAf具有较强的鲁棒性、较高的精确度,以及较低的时间复杂度。2.基于社团内节点互相相似且连接紧密的特征,提出了一种高效的多分辨率社团检测方法-MLPA。在MLPA中,相似的节点首先聚集到一起形成许多元社团。然后,这些元社团通过比较其内部凝聚力与外部吸引力,决定是否与其它元社团进行合并,这个过程一直进行直到所有元社团都满足定义。MLPA既不需要知道社团结构的任何先验信息,也不需要优化任何目标函数。在合成网络和真实网络上的测试结果表明,与其它几种流行的算法相比,MLPA具有较高的准确度和极低的时间复杂度。通过调节分辨率参数,可以观察不同尺度的社团,进而揭示网络的层级结构。为了进一步验证MLPA的有效性,利用它对大肠杆菌的转录调控网络进行了详细的分析,结果表明检测到的模块具有很强的结构和功能的一致性。3.基于局域标签传播过程,提出了一种高效的动态社团检测方法-ALPA。许多真实网络是随时间演化的,而传统方法将它们视为静态的,即通过聚合一段时间内的数据而构建的,这种处理方式会丢失网络及社团的演化信息。如果希望实时跟踪网络的社团,静态方法通常非常耗时,因为即使网络的结构发生极小的改变,它们也必须重新计算整个社团结构。网络演化愈快,静态方法的耗时缺陷愈发明显。与传统方法不同,ALPA通过一个局域的标签传播过程来更新当前的社团结构。局域的标签传播过程有效利用了社团结构的历史信息,因此通常只会影响网络中很小一部分节点,这使得ALPA能够快速地响应网络结构的变化。在合成网络和真实网络上的测试结果表明,ALPA能够成功地识别并且追踪动态网络中的社团。此外,和其它常用方法相比,ALPA拥有更高的准确度和更低的时间复杂度。

关键词： 复杂网络   社团检测   多尺度社团   谱图理论   谱聚类  

摘要： 现实生活中存在着各种各样的复杂网络,这些复杂网络可以看作复杂系统的高度抽象。随着对复杂网络的深入研究,研究人员发现许多实际网络都存在一些共同的拓扑特性,如小世界特性、幂律度分布以及社团结构等。其中,社团结构描述的是复杂网络中各群组内部节点间的连接较为紧密,群组之间节点的连接相对稀疏的特性,是复杂网络最重要的拓扑性质之一。因此,复杂网络中的社团检测问题受到了许多学者的广泛研究,针对该问题,本文主要做了以下工作:1.首先介绍了复杂网络中社团结构检测问题的研究背景与意义,对经典社团检测算法进行了分类,并系统介绍了各算法对应的算法原理与思想基础。重点分析了谱聚类算法的优缺点,以及该算法在网络社团检测中的应用。2.针对谱聚类算法在复杂网络社团检测中存在的两个问题:(1)仅选择网络矩阵的部分特征向量对网络节点聚类,没有充分考虑到网络的全局拓扑结构;(2)矩阵特征向量的计算复杂度高,谱聚类算法无法适用于具有海量节点的网络。本文对谱聚类算法进行了大幅改进,改进后的算法称为全息谱聚类算法。全息谱聚类算法采用网络矩阵的所有特征向量聚类,并利用谱图理论中的Parseval公式,将网络节点对应向量的余弦相似性进行了转化,避免了对网络矩阵特征向量的计算,降低了算法的计算复杂度。3.针对网络矩阵的特征向量在网络节点聚类中的重要性不同,引入了加权函数,通过对网络矩阵的所有特征向量加权,既充分考虑到了网络的全局拓扑结构,又考虑到了不同的特征向量对网络节点聚类的重要性问题。另外,为了使全息谱聚类算法可反映出网络中社团结构的多尺度性,引入了尺度参数,通过调节尺度参数,控制加权函数对特征向量的加权,该算法可将网络划分为不同尺度的社团。实验结果表明:相对谱聚类算法,全息谱聚类算法将计算复杂度和存储复杂度降低到了线性级,使得该算法可应用于含有大量节点的网络。另外,通过调节尺度参数,全息谱聚类算法既能有效地检测复杂网络中的社团结构,又可反映出网络中社团结构的多尺度特性。

关键词： 社团检测   相似性规则   谱二分法   模块度   函数依赖   闭包  

摘要： 社团结构是复杂网络的一个重要特性,网络中的社团通常对应于具有独特功能或属性的模块,将这些模块从网络中提取出来,有利于对网络功能作进一步分析。例如,在生物学领域,蛋白质相互作用网络中的社团对应于具有相同结构或功能的蛋白质组织;在社会学领域,社交网络中的社团对应于具有共同点的个体的集合。因此,社团检测研究具有重要的理论研究意义和实际应用价值,受到不同领的研究人员的广泛关注,并提出了大量的社团检测算法。在对这些算法进行深入研究的基础上,本文充分利用相似性规则,提出了一种基于最优特征向量的谱二分社团检测算法和一种基于相似性闭包的社团检测方法。基于谱二分法,并针对谱二分法固定地根据某一特定的特征向量对网络进行分裂这一特征,本文提出了BSOE算法。该算法是一种使用最优特征向量的社团检测方法,从网络转移矩阵中选择能够使网络分裂时模块度增量最大的特征向量,直到网络的分裂无法增大模块度为止。BSOE算法能够充分利用矩阵的特征谱信息。为了能够更充分地利用网络的邻接信息,本文对有边相连的顶点对进行相似性计算,将其作为该边的权值,并应用于BSOE算法,使其能适用于有权网络,能够从网络中提取模块度更大的社团结构,形成WBSOE算法。本文提出的第二种算社团检测方法CDCS算法是基于相似性度量,并将相似性度量作为判断顶点之间的函数依赖关系的规则,以判断两个顶点是否属于同一社团。在此基础上,CDCS算法定义了顶点的函数依赖闭包,该闭包中的顶点都可能属于同一个社团。然后从所有顶点的函数依赖闭包中寻找最大闭包,也就是闭包出发顶点不被任何其他闭包含有的函数依赖闭包,作为网络的社团。在解决最大闭包之间的重叠问题后,最后得到具有明确边界的社团结构。为了验证提出的社团检测方法的有效性,本文在多个网络数据集与多个算法的运行结果进行了深入的比较。实验结果证实,本文提出的算法能有效地从网络中提取出高质量的社团结构。

关键词： 深度学习   数据预测   数据特征   社团检测   社团演化  

摘要： 大数据时代的降临,使得数据成为一种珍贵的资源。数据中蕴藏着许多有用信息,例如疾病传播规律、人类行为倾向、市场营销等等。数据预测作为数据挖掘的核心应用之一,是开发利用这种资源的重要手段。数据特征常常被用来描述数据性质和关系,好的数据特征意味着好的预测结果。因此,针对具有非线性、不平稳和高度不确定性等特点的数据,如何提取得到更好的数据特征成为一项十分重要且有意义的工作。当前存在的特征提取和预测模型大都是基于浅层学习开发的,这些模型转化的数据特征都是基于统计学方法计算得到的,这样得到的特征不能准确、有效的表达样本数据之间的内部关系。深度学习理论的发展离不开大脑视觉系统的仿生学成果,它采用了深层次的架构模型,可以对数据样本进行逐层的抽象转化,得到深层次的数据特征。由于在数据特征的提取和转化上具有强大的优势,它已经被广泛应用到图像识别、语音处理、自然语言表征等领域。因此,本论文从深度学习在数据特征的提取和预测方面展开研究,所做的具体工作如下:(1)对时间序列数据进行预测。结合递归神经网络和受限玻尔兹曼机网络对时序数据处理的优势,构建了一个基于递归神经网络-受限玻尔兹曼机深层结构的深度学习预测模型,模型的深层结构可以优化门诊量数据的原始特征,通过对比仿真实验证明了预测模型的有效性。(2)复杂网络的社团划分算法。基于网络模块度的社团检测算法中提取到的数据特征未包含非线性关系的问题,为解决该问题,建立了一个基于深度自编码网络的深度模型,该模型可以通过逐层学习转化得到蕴含网络拓扑结构中的非线性关系的数据特征。在人造网络和真实网络上的仿真实验说明了该模型提取转化的数据特征可以有效的提高社团检测效果。(3)复杂网络的社团演化预测。动态社团演化包含了静态网络的社团拓扑结构信息和社团演化的时间序列信息,所以本文从社团内部和外部的角度综合考虑网络演化过程中的社团的变化,选择并优化了社团演化中社团合并的影响因素,然后构建了一个基于深度信念网络的社团合并预测模型,该预测模型可以在通过对所提取的影响因素进行学习得到具有代表能力的数据特征,以此提高预测的精度。

关键词： 复杂网络   社团检测   统计推理   广义社团  

摘要： 复杂系统是系统科学与控制理论在新时代的基础研究中所面临的一个重大挑战,其中一个重要课题是对复杂网络中潜在的定性特征和定量规律的深入探索、科学理解以及可能的应用。而在复杂网络研究中,一项关键步骤是确定网络中的社团结构。社团,对应于复杂系统的单元结构,其研究对于复杂系统的功能和行为的科学理解以及结构和动力学特性的进一步研究具有重要意义。研究发现网络中除了内紧外松的传统社团以外,还存在多种类型的潜在结构,称为广义社团。本文主要基于统计推理方法,对复杂网络的广义社团检测算法展开研究。针对现实复杂系统中社团会出现重叠的问题,基于度修正随机分块模型对复杂网络的重叠社团结构检测算法进行研究。通过引入似然度得分参数和阈值参数,并结合谱算法提出了一种网络中重叠社团的检测算法。分别在人工基准网络和现实验证网络上进行实验,结果表明,算法在速度和检测效果上均表现良好。不过,算法也存在检测极限问题,本文认为是网络中存在不同类型的社团结构导致的,应对更广义的社团结构进行研究。针对网络中存在多种类型潜在结构的情况,对复杂网络的广义社团结构检测算法进行研究。针对现有网络模型设计过度,现有算法有时收敛时间较长等问题,基于随机图模型构建了一种连续空间的网络模型,并引入广义伯恩斯坦多项式逼近网络模型的概率测度,提出了一种广义社团结构检测的改进算法。在人工网络和现实验证网络上进行了实验,结果表明,算法收敛速度快,能够发现网络中潜在的连续结构,并能扩展到网络的层次结构检测。不过,复杂网络中可能存在的环路有时会对算法性能产生影响,这将留待以后研究。针对现实复杂系统中的关系具有不同层次,不宜用无权网络表示的问题,对加权网络上的广义社团检测算法进行研究。在无权网络的广义社团检测算法基础上,修改网络模型概率测度以考虑加权网络的权重强度分布,并在消息传播中引入连边权重以衡量节点间的相容性,提出了一种加权网络上的广义社团结构检测算法。对现实验证网络做权重变换,以无权网络广义社团检测算法和一种考虑权重的传统社团检测算法作为对比,进行了实验。结果表明,加权网络上的广义社团检测算法检测到的结构更加合理。关于该算法的更具体的应用有待进一步研究。最后对本文的研究工作进行了总结,并且对未来的研究进行了展望。

关键词： 中心性   LPA算法   复杂网络   社团结构   社团检测  

摘要： 随着复杂网络不断涌现及其实际应用领域不断拓宽,复杂网络的理论研究受到广泛关注。社团结构和中心性特性是复杂网络中典型的结构特征,其中社团结构是指网络中的顶点可自然地形成不同的组,每个组即为一个社团。社团表现出高密度聚拢状态,即社团内部的节点之间联系较为紧密,位于不同社团的节点之间联系则相对稀疏得多。社团结构作为复杂网络的重要结构特征,包含的社团往往对应于网络的功能模块。通过检测网络的社团结构,可以发现网络的功能单元,研究结构与功能的对应关系,通过结构预测网络的功能。此外,已有研究表明,从社团层面往往可以发现单个顶点或整个网络层面未曾表现出来的一些特性。因此,社团检测方法的研究不论是在理论方面还是在实际应用方面都具有重要意义。研究人员已经提出了大量的社团检测算法,但很多算法的时间复杂度较高,无法有效地应用于规模较大的网络。针对这一问题,本文首先将频繁项集挖掘技术与LPA算法相结合,提出了改进算法LPAFI;其次基于局部中心性,提出了CG和CD两个社团检测算法。(1)LPAFI:该算法是基于LPA和频繁项集提出的确定性的社团检测算法。LPAFI算法首先通过多次运行LPA算法,将每次运行检测到的社团结构作为一条事务,从而构造出事务数据库,然后通过挖掘频繁项集的方法挖掘出满足条件的频繁项集,其次合并频繁项集,得到社团的大致结构,即“核心社团”。最后将不在核心社团的顶点作为“单点社团”,与核心社团进行社团合并,得到最终的社团结构。(2)基于中心性特性的社团检测算法:该算法根据社团结构的定义提出了新的局部中心性,即顶点与其邻居构成的社团,其内部边的数目占该社团总边数的比。局部中心性有一个重要的性质:中心性值较小的顶点往往处于社团的“边缘”。中心性增益算法又简称为CG算法,该算法首先通过重复的移除连接到顶点的边使得每个顶点的中心性值达到最大,从而将网络划分成小的社团,然后从得到的小社团中找出不稳定的小社团,将其划分成更小的社团,最后将得到的小社团进行合并,得到最终的社团结构;中心性扰动算法又简称为CD算法,该算法首先通过重复的移除对当前顶点中心性“贡献”较小的顶点之间的边,从而将网络划分成小的社团,然后从得到的小社团中找出不稳定的小社团,将其划分成更小的社团,最后将得到的小社团进行合并,得到最终的社团结构。为了验证本文提出的社团检测方法的性能,本文在7个网络数据集上进行了实验。实验结果表明,本文提出的方法能够快速地从网络中检测出高质量的社团结构。

关键词： 推特   社团检测   事件检测   情感分析   大选预测  

摘要： 随着互联网的发展,社交媒体在人们生活中的应用越来越多样化。而推特(Twitter)作为社交媒体中的佼佼者,已经成为近年来最流行的社交媒体应用之一。而社交媒体在政治事件中的影响也在与日俱增。2012美国总统奥巴马连任、英国脱欧公投等一系列政治事件的背景中都出现了推特的身影。推特在事件传播、反映民众的政治倾向上有逐步取代传统民意调查的趋势。目前在社交媒体上的政治倾向研究主要针对文本中的特定信息来进行分析,例如推文中的标签(hashtag)、提到(@)等。由于社交媒体数据不具有正式性,所以政治倾向分析的结果不够精确。同时对于社交媒体中的大选选情预测并没有特别完善的流程和方案。所以,本文通过图挖掘的方法,对社交媒体中的政治类事件进行分析研究。针对2016美国总统大选选情预测的问题,提出并设计了大选选情预测模型。本文的主要工作和创新点概括如下:(1)在推特数据上进行政治倾向情感分析和大选相关事件检测。在情感分析上,针对推特信息简短、非正式、缺乏补充信息的特点,本文采用了基于字典的情感分析方法,对推文的政治倾向性进行判断。同时对于情感分析中的反语鉴别难点,通过推文的表情符以及用户的历史推文来提升情感分析的结果。在事件检测中,针对美国总统大选的背景,本文采用了多次聚类、同义词拓展,关键词权重提升等方法,来对碎片事件进行整合。该方法提升了大选相关事件检测的性能。(2)利用图挖掘的方法来对推特数据进行研究分析。由于推特数据源上有多种多样的信息,例如用户,推文,图片,视频等等。而用户的点赞,转发和评论行为,往往也会表露出用户的政治倾向。所以,本文采用复杂网络分析方法,将不同类型的社交媒体数据投影到复杂网络中,再根据实际需求,对社交媒体复杂网络进行分析。在大选预测结果中发现支持总统候选人的用户社团。这种分析方法不仅仅适用于大选选情预测,还可以应用于社交媒体的舆论导向分析、用户影响力等方面。本文使用了真实社交媒体数据,分别对情感分析方法,事件检测模型和大选预测模型进行实验。实验结果显示,本文提出的大选预测模型可以对大选选情进行正确预测。