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

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

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

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

关键词： 情报分析   属性网络   生成模型   社团检测   语义识别  

摘要： 利用复杂网络分析方法,对复杂系统中的关系结构及属性进行分析,识别网络中社团结构具有重要研究意义。课题组构建了基于复杂网络算法进行人、物、组织及相互关系的感知、理解、预测的情报分析框架IAF,从基于社会/物理/网络空间中人类电子足迹的大规模社交关联网络(复杂网络)中进行社团检测,是智能情报分析框架中理解模块中的关键功能。本文提出融合网络结构和节点属性的社团检测方法,并进行了实证。首先,提出了结合属性网络无标度特性的社团检测方法(PLAC)。该方法基于联合生成模型,通过编码所有节点变化的度分布,保持网络中节点度的异质性,同时融合网络的结构和属性信息进行社团检测和语义识别。其次,提出了属性网络中的广义社团检测和语义识别的方法(GSC)。该方法基于联合贝叶斯生成模型,同时建模了网络的结构和属性,采用有效的吉布斯采样进行求解。在网络拓扑结构部分利用贝叶斯混合模型来检测网络中的广义社团,采用一个概率转移矩阵揭示结构社团和属性主题的潜在联系,通过分析社团中节点的内容信息解释社团语义。最后,本文利用论文数据集进行实证分析。根据生物领域论文的引用关系构建属性复杂网络,然后划分社团。又围绕领域研究现状分析的情报任务展开实证,构建了物理学不同领域作者合作网络,解释社团语义,分析不同领域研究内容,为各领域以后开展研究活动做指导。本文基于情报分析框架IAF理解模块中社团检测的功能,提出了两个属性网络中的社团检测生成模型,并且在真实的数据集上完成了验证,利用节点的内容信息,分析社团与主题之间的关系,描述社团的语义。论文最后在Aminer数据集上进行实证分析,可以发现特定社团并且揭示社团的特征,分析得出有关各领域研究内容的情报,具有重要的研究价值。

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

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

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

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

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

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

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

摘要： 复杂网络是指具有复杂拓扑结构和复杂节点行为的网络系统,它是对现实世界中各种各样的大规模复杂系统的抽象。复杂网络的节点可以是任意具有特定动力和信息内涵的系统的基本实体,而边则表示这些基本实体之间的关系。复杂网络以展现出能够在节点和边的水平上被获取的丰富、低阶连接模式著称,社团结构是其中最重要的一种模式。当前,复杂网络中的社团结构研究已然成为了现代复杂网络科学中最热门的研究课题之一。研究复杂网络中社团结构能够帮助人们更加清晰的认识复杂网络中蕴含的拓扑结构,促进复杂网络科学研究从宏观到微观的高速发展,具有重要的理论意义和现实的应用价值。目前,随着真实网络规模的不断增大,大量的全局社团检测算法因过高的时间和空间复杂度已经无法满足时代的需求,如何设计针对大型复杂网络的全局社团检测算法是当前亟待解决的重要问题。另一方面,针对大型复杂网络,局部社团结构的挖掘显得尤为必要,如何设计快速的局部社团检测算法是近几年兴起的又一研究热点。针对以上问题,基于局部谱逼近设计了针对大型复杂网络的全局重叠社团检测算法和局部社团检测算法,主要工作及创新点如下:（1）针对大型复杂网络的全局重叠社团检测问题,提出了一种基于二次优化的团扩张（Quadratic Optimization-based Clique Expansion,QOCE）的全局重叠社团检测算法。QOCE算法包含四个关键步骤:极大团枚举、随机游走采样、二次优化和社团检测。首先,由于经典的Bron-Kerbosch（BK）极大团枚举算法对大型复杂网络的适用性,采用BK算法高效地找出复杂网络中至少包含3个节点的所有极大团。将所有极大团按其节点个数进行降序排列,然后依次删除与前一个极大团至少重叠75%节点数的所有极大团。其次,为了降低QOCE算法的计算复杂度,采用快速的随机游走策略以极大团为初始节点进行局部子图采样,使得该采样子图尽可能覆盖了极大团近邻的所有节点。然后,基于Cheeger割最小化,在采样子图上设计带l1正则项的二次目标函数并采用数值算法进行优化求解。最后,根据二次目标函数的优化解向量进行极大团所属社团的截断选取。由于不同的极大团扩张过程存在重叠现象,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)基于连接模式的相关分析的社团检测算法。该算法首先获得顶点间的连接模式,计算相关系数得到连接模式间的相关性,获得must-link与cannot-link成对约束,并根据must-link关系的传递性,对must-link及cannot-link关系集合进行扩展。然后将扩展后的cannot-link集合作为种子节点,结合must-link关系构造社团结构的框架。最后用最小生成树方法,将其余节点划分到相应社团,得到最终的社团结构。(2)基于带偏置的信号传播机制的随机游走算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑信号的衰减,为每条边增加了衰减因子,对信号传播过程进行限定。通过模拟信号的传播,将网络每个顶点均作为信号源重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证本文所提出方法的性能,本文在多个实际网络数据集以及人工合成网络数据集上进行了实验,并与相关算法的检测结果进行对比检测,实验结果表明,本文提出的算法能够从网络中提取出高质量的社团结构。

关键词： 复杂网络   社团检测   重叠社团   谱聚类   聚类集成   边划分  

摘要： 在许多现实世界系统中,对象与对象之间的关系都能够建模成复杂网络进行分析。其中社团结构是复杂网络的重要属性,通常能够解释复杂网络系统的拓扑结构与功能模块。复杂网络社团检测旨在挖掘这种具有复杂网络结构的系统中的模块化结构,研究这种模块化结构有助于更好了解并挖掘网络系统的潜藏功能。近年来,多个领域的研究者们提出了众多社团挖掘算法,在不同学科领域上对复杂网络社团检测进行了深入研究,随着重叠社团结构这一概念提出,这些算法在重叠社团检测领域值得进一步研究。因此,针对传统的基于谱聚类的社团检测算法无法很好地挖掘重叠社团结构的问题,本文提出了一种基于边划分的谱聚类重叠社团检测算法。此外,复杂网络的社团结构不尽相同,为了使算法在不同结构的网络上都有着较好的鲁棒性,本文进一步提出了一种基于谱聚类思想的集成重叠社团检测算法。这两种算法均是以谱聚类算法思想为基础对重叠社团检测算法进行研究的。本文的主要研究工作如下:(1)提出了一种基于边划分的谱聚类重叠社团检测算法。当前基于谱聚类思想的社团检测算法在检测非重叠社团结构时,能够很好地处理复杂的网络结构,得到较为精确的划分结果,但却无法很好地解决重叠社团检测问题。主要原因在于谱聚类方法通过矩阵谱分析理论得出网络节点的新特征,利用新的数据特征将原网络切成相互没有连接的k个子图,故无法检测重叠社团结构。因此,本文提出了一种基于边划分的谱聚类重叠社团检测算法,其主要思想是将谱聚类算法思想与边划分思想结合,通过构造边与边之间的相似矩阵挖掘网络中边社团的结构,从而挖掘每个社团中的非重叠节点以及候选重叠节点,之后通过分析每个社团候选重叠节点的邻居节点信息逐步挖掘重叠节点,得到最终的重叠社团划分结果。在人工合成的LFR网络上与现有的多个算法的对比实验表明,该方法能够有效地挖掘网络中复杂的重叠社团结构,并且能够有效地解决边划分的过度重叠问题。(2)提出了一种基于谱聚类的复杂网络集成重叠社团检测算法。当前基于谱聚类思想的复杂网络社团检测算法实现简单,不易陷入局部最优,但该类方法计算复杂度相对较高,并且依赖于社团尺度参数的选择,主要原因在于随着网络规模的增大,特征向量计算复杂度过高而无法达到足够的精确度。为了解决该问题,并且提高算法的鲁棒性,本文提出了一种基于谱聚类的复杂网络集成重叠社团检测算法。该方法的主要思想是通过设计一种新的抽样方法尽可能的从每个社团中抽取多个代表点,根据矩阵的摄动理论对抽样点进行多样性的谱聚类划分,从而挖掘网络中节点间的社团信息,然后根据网络的拓扑结构以及多个划分的质量进行加权集成得到权重网络,从而加强并挖掘网络社团结构,获得最终的重叠社团划分。通过在多组不同复杂结构的合成网络以及真实网络上,与现有的几种重叠社团挖掘算法实验对比表明,本算法在不同复杂结构的多组网络中均能得到稳定且良好鲁棒性的重叠社团划分结果。并且通过进一步的模拟实验验证,本算法可以很好地从各社团中抽样得到代表节点,且加权集成网络中社团的结构获得了一定的加强。

关键词： 位置社交网络   社团检测   分辨率极限   网络嵌入   模块度优化  

摘要： 移动互联网络和定位技术的广泛普及给人们的生产和生活带来极大便利,同时也促进了位置社交网络的发展,和传统社交网络只包含用户拓扑信息不同,位置社交网络是一种既有用户信息又有位置信息的复杂异构网络,检测出其中的社团结构对于深入分析位置社交网络具有重要意义。模块度优化是传统社交网络的社团检测方法,由于其时间性能和检测效果俱佳,因此考虑将其推广到位置社交网络。而分辨率极限却是模块度定义中固有的一个问题,因此避免分辨率极限问题的产生并将模块度优化方法与位置信息相结合,是研究位置社交网络中社团检测的基础。针对上述问题,本文在分析了位置社交网络的特点和分辨率极限问题产生原因的基础上,提出一种网络权重预处理方案,该方案可以使预处理后的网络使用模块度优化方法进行社团划分时既避免分辨率极限问题,又适用于位置社交网络。本文研究工作主要分为两方面:一方面,由于网络嵌入在节点特征学习方面表现出的优异性能,本文在分析了一种针对位置社交网络的网络嵌入方法walk2friends的过程和优势后,将其节点相似度生成过程的工作与一种利用随机游走挖掘网络结构的方法相结合,进而提出本文的预处理方案。预处理方案将无向无权图转换成无向有权图来完成社团检测,该方案利用walk2friends结合位置社交网络特征得到的学习相似度使节点更内聚,利用随机游走方法得到的结构相似度可以探测网络结构,区分出不同社团的节点,最后利用K近邻算法使关联度低的节点间边权值趋于0,从而破坏分辨率极限的产生条件。相比于现有的一些位置社交网络社团检测方法只以用户签到信息作为输入,该方案还考虑了用户的社交关系。实验结果表明,本文预处理方案可有效解决模块度优化方法的分辨率极限问题,walk2friends考虑位置信息的特性使得该方案适用于位置社交网络。另一方面,由于目前walk2friends方案缺乏对用户社交关系的考虑,本文提出一种基于社交关系的协同过滤方法进行改进。该方法不仅给walk2friends过程加入用户社交关系,还可以避免协同过滤中的数据稀疏问题,并将改进后的walk2friends用于网络预处理方案的改进。最后实验结果表明,改进后的walk2friends在链路预测性能方面较之前有了很大的提升,应用于预处理方案的改进后,不仅可以有效解决分辨率极限问题,而且从模块度密度、收缩率和社团间连边等评价指标来看改进后方案比未改进方案得到的社团结构更合理,且和其他典型的社团检测方法对比结果显示,改进后的网络预处理方案更适用于位置社交网络。