关键词： 符号网络   社团检测   非负矩阵分解  

摘要： 现实情况中的许多系统都可以用复杂网络来表示,例如电力网络、社交网络、交通网络等。其社团结构属性作为复杂网络中最重要的属性之一已经引起了广泛的关注和发展。符号网络作为复杂网络的重要分支,因为其中负关系的存在使得它比普通的复杂网路可以表示更多的信息。但是目前基于符号网络的社团检测发展还很有限。利用非负矩阵分解的思想来进行符号网路的社团检测,并在人工生成的数据集进行实验,验证所提出的算法的有效性和准确性。

关键词： 重叠社团结构   社团检测   社团结构分析   复杂网络   群体智能  

摘要： 社团结构分析是复杂网络研究的一项重要内容,基于群体智能思想提出了一种自组织的重叠社团结构分析算法SO^2CSA^2。把网络视为一个群体,网络节点是其中的一个个具有简单智能的个体,每个个体依据定义的社团连接分数自主决定要加入的社团(可同时加入多个社团)。在网络中寻找一组K-派系作为初始社团结构,所有个体迭代地选择其社团归属,最终整个网络的社团结构将逐渐生长出来。最后对获得的社团结构进行后处理,即调整少量节点的社团归属,以提高其质量。在一组合成网络和现实世界网络上的实验表明,SO^2CSA^2发现的社团结构的质量比两种对比算法(SLPA和OSLOM)更好,尤其是在网络中重叠节点较多或节点重叠度较大的情况下,社团结构质量的提升更为明显。

关键词： 社会网络   个人意愿   社团检测   重叠社团   信息传播  

摘要： 个人意愿对于形成网络社团和传播信息有着重要的影响力,因此本文提出一种基于个人意愿的社团结构与信息检测方案.该方案中的社团检测算法初次检测以融入节点属性的模块度,再次检测以兴趣度并能发现重叠社团,最后精细检测以个人意愿,本文社团检测算法(ε_CSDA)较之前的算法更有效的是可以发现重叠社团;同时,该方案建立的信息传播模型在指数模型基础上构建边特征向量(边属性)、节点特征向量(节点属性)和意愿向量(用户意愿、社团意愿和节点意愿),并以传播概率和传播延迟构建模型基本关系,从而使得该模型实现了基于个人意愿的信息传播.实验结果表明,加入个人意愿的社团检测和信息传播方案,能够保证社团检测的有效性和实用性,能够实现用户间信息传播的主动性和可靠性.

关键词： 复杂网络   机器学习   社团检测   链路预测  

摘要： 近年来,随着大数据技术的进步,复杂网络与机器学习的交叉研究越来越受到众多学者的关注。复杂网络是自然界中众多复杂系统的抽象描述,主要以统计物理的角度研究系统的演化;机器学习又称为统计学习方法,主要研究从大量数据样本提取特征并建立模型。简要综述复杂网络领域主要的网络演化模型、常用统计度量方法以及网络上的动力学过程和机器学习领域内三种基本的学习技术;从交叉应用的两个角度,即基于复杂网络的机器学习方法和基于机器学习的复杂网络信息挖掘,详细对比了各种方法的计算思路。在此基础上,提出目前学界重点关注的两类问题,并展望了若干开放性挑战。

关键词： 加权复杂网络   重叠社团检测   节点重要度   Jaccard系数   模块密度  

摘要： 针对加权复杂网络中的重叠社团检测问题,提出了一种面向加权网络的基于Jaccard系数的BGLL模块密度优化算法(Modularity Density and Jaccard Based BGLL, DBGLLJ).利用节点重要度重构网络,根据模块度增益作为阶段函数和模块密度增益作为目标函数进行网络硬划分,并提出了结合改进的Jaccard系数的重叠检测方法.为验证算法,选择了3种算法在LFR网络和真实网络中进行测试,结果表明:在标准LFR网络和真实网络中,DBGLLJ算法检测效果较优,具有较高的重叠模块度以及重叠检测准确性,且运算效率较好.将所提算法应用于现实复杂机电系统因效性网络,重叠检测结果较好,具有较高的参考价值.

关键词： 复杂网络   社团检测   节点角色   动态网络   社团演化预测  

摘要： 现实世界中存在大量复杂系统可以抽象为网络形式,例如,疾病传播网络、科学家合作网络、能源传输网络、细胞代谢网络等。网络由节点和连接节点的边构成,其中节点表示系统中的主体,边表示网络主体间的关系或交互。社团结构作为复杂网络的重要特征,指的是网络中的节点聚集成簇,簇内连接紧密,簇间连接稀疏。社团检测旨在揭示网络中所蕴含的社团结构,有助于对网络结构的分析、对网络功能的推断、对网络拓扑的优化,并指导现实网络结构的识别、构建和预测,因而是理解和探索网络结构与功能的关键问题。高效准确地检测出网络中的社团结构、以及利用检测结果进行分析挖掘是复杂网络理论与实践研究中的重要课题。本文围绕社团检测和社团演化预测相关问题开展研究,主要工作和创新点如下:(1)针对标签扩散社团检测算法(LPA,Label Propogation Algorithm)存在的鲁棒性和稳定性较差等问题,提出一种LPA的改进算法基于角色的标签扩散算法(RLPA,Role-based Label Propogation Algorithm)。在已有社团检测算法中,标签扩散算法具有时间复杂度低、准确率较高、便于并行化等优点,然而,所引入的随机性使得算法具有较差的鲁棒性和稳定性,并且当网络社团结构较弱时,扩散机制可能导致网络中的大部分节点隶属于同一社团,从而得到无意义结果。为此,在深入分析社团角色对标签扩散过程的影响的基础上,基于标签扩散算法,通过引入一种与社团角色相关的度量作为节点偏好,利用局部指标调整节点更新策略,以提高鲁棒性和稳定性,及在社团结构较弱网络中的检测能力。在多个人工网络、实际网络上的实验结果表明,RLPA有效提高了检测的准确性,同时继承了原算法的速度优势。(2)针对基于角色的标签扩散算法在面向动态网络社团检测时,因采用静态检测方式导致结果不具有时序平滑性的问题,提出一种基于角色的标签扩散算法的动态网络扩展算法提出一种基于角色的标签扩散演化社团检测算法(RELPA,Role-based Evolutionary LPA)。由于实际动态网络中社团演化具有连续性的特点,即相邻网络快照中检测出的社团结构不会有过大差异,因此,面向动态网络的社团检测算法需要将社团结构的时序平滑性作为参照。为此,在静态社团检测算法RLPA的基础上,结合前一时刻社团结构信息以提高时序平滑性,并根据时序结构差异性调整前序信息对当前社团结构的贡献权重,以提高结果的准确性。实验结果表明RELPA能够快速准确地检测出动态网络中的演化社团。(3)提出一种基于多元结构特征的社团演化预测方法(MECE,Multi-length Evolution Chains Ensemble)。特征构造是社团演化预测任务中的难点和核心。已有社团演化预测方法所构造的特征难以有效描述多种尺度下(微观、介观、宏观)的社团拓扑结构信息,并且在构造分类器时采用固定长度的演化链数据作为输入,无法利用不同长度演化链中蕴含的时序信息。为此,该算法通过从社团演化数据中提取社团的多尺度结构特征、时序特征、行为特征,并针对多重长度演化链构造集成分类器,以提高预测准确性。实验结果表明了MECE算法能够更加准确地预测动态网络中的社团演化趋势。

关键词： 复杂网络   社团检测   多目标优化   并行计算  

摘要： 在现实生活中,存在着各种各样的复杂系统,这些复杂系统通常可以抽象地表示为复杂网络。利用社团检测算法对复杂网络进行社团检测,能更好地理解系统结构,挖掘系统潜在的信息,还可以对一些未知的功能和属性进行预测。多目标进化算法具有良好的并行性、全局搜索能力以及对多种函数类可用等优良特性,成为解决复杂网络社团检测问题的重要方法之一。但目前大多数基于进化的社团检测算法都无法很好地处理大规模网络,为了进一步提升社团检测算法在大规模复杂网络上的性能,本文分别提出了基于并行多目标进化的大规模复杂网络非重叠和重叠社团检测算法。本文的主要研究工作如下:(1)提出了基于并行多目标进化的大规模复杂网络非重叠社团检测算法(PMOEA)。为了解决大规模复杂网络的社团检测问题,本文避免直接检测整个网络的社团划分,而是采用多个多目标进化算法并行检测网络中与对应关键点相关的社团。算法主要思想是首先检测出整个网络的关键点,然后运用多个多目标进化算法并行检测网络中与对应关键点相关的社团集合,最后使用单目标进化算法,从与每个关键节点相关的社团集合中来获得整个网络的社团划分。本文采用了与传统多目标社团检测算法不同的优化目标,设计了特别的交叉变异策略,同时缩短了个体编码长度,减小进化过程中种群的搜索空间,有助于发掘出更好的社团结构。配合多线程和分布式计算资源,多个多目标进化算法并行检测,缩短了多目标进化算法检测大规模复杂网络社团的时间。本文验证了PMOEA算法在真实网络和LFR基准网络上的有效性,尤其在大规模复杂网络上,实验结果表明本文提出的PMOEA算法与六个现有的社团检测算法相比具有一定的优势。(2)提出了基于并行多目标进化的大规模复杂网络重叠社团检测算法(PMOEAO)。现实生活中很多复杂网络都是重叠结构的,但在(1)的工作中没有对重叠结构进行特殊考察,无法检测出重叠的社团结构。因此本文在(1)算法的基础上进行进一步改进,提出PMOEAO算法,该算法继承了(1)算法并行处理的机制,同时具有解决重叠社团检测问题的能力。本文算法在(1)算法的MOEA进化过程中加入了候选重叠节点策略来调整社团边界,让改进的MOEA发掘的与单个关键节点相关的社团结构具有更合理的社团边界。之后再选用评价重叠社团划分的扩展模块度作为目标函数,通过单目标进化算法来确定整个网络的重叠社团划分。通过与六个具有代表性的重叠社团检测算法的实验结果的对比表明,PMOEAO算法在解决大规模复杂网络的重叠社团检测问题上具有一定的优势。

关键词： 社团检测   团扩张   二次优化   Krylov子空间   Lanczos迭代  

摘要： 复杂网络是指具有复杂拓扑结构和复杂节点行为的网络系统,它是对现实世界中各种各样的大规模复杂系统的抽象。复杂网络的节点可以是任意具有特定动力和信息内涵的系统的基本实体,而边则表示这些基本实体之间的关系。复杂网络以展现出能够在节点和边的水平上被获取的丰富、低阶连接模式著称,社团结构是其中最重要的一种模式。当前,复杂网络中的社团结构研究已然成为了现代复杂网络科学中最热门的研究课题之一。研究复杂网络中社团结构能够帮助人们更加清晰的认识复杂网络中蕴含的拓扑结构,促进复杂网络科学研究从宏观到微观的高速发展,具有重要的理论意义和现实的应用价值。目前,随着真实网络规模的不断增大,大量的全局社团检测算法因过高的时间和空间复杂度已经无法满足时代的需求,如何设计针对大型复杂网络的全局社团检测算法是当前亟待解决的重要问题。另一方面,针对大型复杂网络,局部社团结构的挖掘显得尤为必要,如何设计快速的局部社团检测算法是近几年兴起的又一研究热点。针对以上问题,基于局部谱逼近设计了针对大型复杂网络的全局重叠社团检测算法和局部社团检测算法,主要工作及创新点如下:(1)针对大型复杂网络的全局重叠社团检测问题,提出了一种基于二次优化的团扩张(Quadratic Optimization-based Clique Expansion,QOCE)的全局重叠社团检测算法。QOCE算法包含四个关键步骤:极大团枚举、随机游走采样、二次优化和社团检测。首先,由于经典的Bron-Kerbosch(BK)极大团枚举算法对大型复杂网络的适用性,采用BK算法高效地找出复杂网络中至少包含3个节点的所有极大团。将所有极大团按其节点个数进行降序排列,然后依次删除与前一个极大团至少重叠75%节点数的所有极大团。其次,为了降低QOCE算法的计算复杂度,采用快速的随机游走策略以极大团为初始节点进行局部子图采样,使得该采样子图尽可能覆盖了极大团近邻的所有节点。然后,基于Cheeger割最小化,在采样子图上设计带l正则项的二次目标函数并采用数值算法进行优化求解。最后,根据二次目标函数的优化解向量进行极大团所属社团的截断选取。由于不同的极大团扩张过程存在重叠现象,QOCE算法不仅适用于大型复杂网络还能检测重叠社团结构。大量的实验结果表明,QOCE算法在合成数据和真实网络上的社团检测准确度高于作为对比的几种基准算法。(2)针对大型复杂网络的局部社团检测问题,提出了一种基于Krylov子空间谱逼近(Krylov Subspace Spectral Approximation,KSSA)的局部社团检测算法。KSSA算法包含三个关键步骤:宽度优先搜索(Breadth First Search,BFS)采样、Krylov子空间谱逼近和局部社团检测。首先,为了降低KSSA算法的计算复杂度,从极少量带标签的种子集出发,通过BFS扩张技术获取包含种子集的局部采样子图,使得该采样子图尽可能覆盖了种子集所在目标社团的所有节点。其次,基于谱图理论,在采样子图上利用Krylov子空间局部逼近特征子空间,通过最小化一范式求解Krylov子空间中以种子集为支撑的稀疏标识向量。该稀疏标识向量中的元素值表示对应节点属于目标社团的概率。最后,对稀疏标识向量中元素值对应的节点进行局部社团截断。由于不同种子集的扩张过程存在重叠现象,KSSA算法可用来检测重叠社团结构。大量的实验结果表明,KSSA算法在合成数据和大型真实网络上的社团检测准确度高于当前流行的几种基准算法。(3)针对大型复杂网络的局部社团检测问题,提出了一种基于Lanczos迭代谱逼近(Lanczos Iteration Spectral Approximation,LISA)的局部社团检测算法。LISA算法包含三个关键步骤:热核(Heat Kernel)采样、Lanczos迭代谱逼近和局部社团边界截断。首先,为了降低LISA算法的计算复杂度,从极少量带标签的种子集出发,首次采用快速的热核扩散技术进行种子集的局部子图采样,使得该采样子图尽可能覆盖了种子集所在目标社团的所有节点。其次,基于Rayleigh熵最小化,在采样子图上设计快速的Lanczos迭代方法局部逼近转移矩阵最大特征值所对应的特征向量,并给出了Lanczos迭代方法的收敛性分析。最后,对Lanczos迭代逼近获得的局部特征向量中的元素对应的节点进行截断,从而获得具有局部最小电导(Conductance)的社团。由于不同种子集的扩张过程存在重叠现象,LISA算法可用来检测重叠社团结构。大量的实验结果表明,LISA算法在合成数据和大型真实网络上的社团检测准确度高于对比的几种基准算法。综上所述,针对大型复杂网络分别设计了全局重叠社团检测算法QOCE与局部社团检测算法KSSA和LISA。大量的实验结果表明,三种算法在合成数据

关键词： 复杂网络   社团检测   多目标优化   密母算法   模拟退火算法  

摘要： 随着科技的迅速发展,复杂网络已不知不觉地影响着人们的生活。例如,从有形的交通网络、通信网络、电力网络到无形的经济网络、信息网络、社交网络等。这些网络都可以抽象为图的形式表示,用节点表示对象,节点与节点的连接表示对象之间存在的某种关系。社团结构是复杂网络的一个重要属性,它具有社团内部连接紧密,外部连接稀疏的特点。发现复杂网络社团结构的特征,有助于分析网络行为、揭示网络中潜在规律。近年来,研究者提出了一系列的算法来发现复杂网络的社团结构。社团检测中常用的是优化方法,就是将社团检测问题转化成目标优化问题。由于现实生活中网络复杂,结构繁多,在社团检测中优化多个目标函数的方式,能更好的发现网络社团结构。因此本文采用多目标优化方式,结合局部搜索算子,构造出一种新的多目标密母算法。本文主要工作和创新如下:1、研究了复杂网络社团结构及多目标优化算法。对于社团结构紧密和稀疏的判定,研究者根据不同的准则对社团定义了同的衡量标准,如模块度、模块密度、社团分数等。结合了不同目标同时优化,有助于综合考虑社团的多个特征,本文重点研究了多目标算法,并分析了不同算法的特点。2、提出了一个基于多目标密母算法的社团检测算法。算法采用社团分数和模块度作为优化目标函数,利用均匀交叉和点变异操作进行进化,编码方案采用基于邻接点的编码方式,该编码方式不需要提前知道社团数目,方便用来处理实际中大多数不知道社团数目的网络。3、采用随机游走的种群初始化策略。随机游走的初始化方式,与传统的随机初始化相比,它能保证产生的每个个体都是安全个体。以马尔科夫转移概率为节点游走标准,不仅保证了个体的有效性,而且维护了种群的多样性。4、引入模拟退火操作算子作为局部搜索策略。模拟退火算法是一种启发式算法,其本身有较好的搜索能力。本文对模拟退火算法做了一些改进,用支配关系作为评判个体优劣的唯一标准,这样的调整有利于搜索优秀个体。在人工合成网络平台生成的网络和现实世界的实际网络中进行仿真实验,并与其他算法进行了对比分析,实验结果验证了本文算对社团检测的有效性。

关键词： 复杂网络   社团检测   共同邻居   层次聚类   标签传播  

摘要： 随着信息技术的发展,现实世界中的许多复杂系统能够以网络的形式呈现。网络中的节点表示系统中的实体,而节点之间的连接表示实体之间的联系。由于现实世界网络的统计特征不同于规则网络和随机网络,因而将描述它们的理论模型称为复杂网络。复杂网络的社团结构表现为:紧密联系的局部节点属于同一社团,属于不同社团的节点之间联系较少。研究网络的社团结构有助于分析网络的结构特点、功能模块、信息传递、演化过程等,以及解决工程应用中的相关问题。因此,有关复杂网络社团检测的研究一直是热点问题。层次聚类方法能够实现多粒度的社团检测,揭示网络内部的层次化结构。但是,在部分应用中,非层次聚类方法给出的一种特定的社团划分方案就足以解决问题。社团划分的质量和速度一直是评价社团检测方法的关键。为了从复杂网络中挖掘出高质量的社团结构,同时保证较快的执行速度,本文提出了两个社团检测算法,分别是基于共同邻居的层次化社团结构检测算法和基于共同邻居约束标签传播的社团检测算法。本文的创新点如下:1)根据均值聚类的思想,从简单的邻接关系中提取关于共同邻居的信息,定义了节点亲密度以衡量相邻节点的相似性。基于节点亲密度,本文提出了一种分裂算法以层次化的方式分析网络的社团结构。该算法采用堆存储数据及索引,能够快速实现搜索最小亲密度、更新局部亲密度。实验结果表明该算法在层次化社团结构检测方面的良好效果,以及在节点度分布较为均匀的网络中执行速度较快。2)将社团检测问题用两个优化目标来描述:社团内的联系尽可能多,以及同一社团内的节点尽量共享邻居。在此基础上,本文提出了采用标签传播策略优化两个目标的算法。为了减弱过多节点标签趋于一致的倾向,引入了已有的关于社团内边数的约束和提出的关于社团内共同邻居数的约束。结合实验对比结果和理论分析,选择合适的约束强度和加权系数。实验结果验证了该算法在社团划分质量和速度方面的优势,特别是在社团结构模糊的情况下。