关键词： 复杂网络   动态网络   社团结构   聚类算法  

摘要： 现实世界中大量复杂系统可以抽象为复杂网络模型，社团结构是复杂网络的关键结构特征，网络的整体功能是网络中各社团相互作用的结果。因此社团结构检测是复杂网络研究中的重要内容。 本文研究复杂网络社团检测算法及其在生物领域和社会领域的应用，主要包括以下几点： 1.在很多真实网络中，由于一个顶点需要行使不同的功能，该顶点可能同时属于多个社团，这导致社团间存在一定程度的重叠，为了检测重叠社团结构，对近邻传播算法(AP)进行改进，提出一个重叠社团检测算法OAP。AP算法检测社团结构时，先识别出所有社团的中心点，再为每个顶点唯一指派一个中心点，拥有相同中心点的顶点集合就构成了一个社团。在中心点指派时，有时会出现顶点在多个中心点间难以选择的情况，AP通过扰动网络避免这种情况发生，而该现象可以作为识别重叠点、设计OAP算法的重要依据。OAP先用AP对网络硬划分，再利用AP的上述特点识别重叠点的候选集，最后将候选集里那些会使社团变稀疏的顶点作为噪声过滤掉，即得到重叠社团结构。实验利用空手道网络验证了候选集选择策略的合理性，利用蛋白质相互作用网络验证了算法能够更准确的检测社团结构，并且检测到的社团更有意义。实验结果说明OAP算法是一个有效的重叠社团检测算法。 2.除了拓扑结构，网络中的顶点还具有属性信息，为了检测拓扑结构稠密且属性信息相似的社团，提出一个基于顶点特征的社团检测算法。首先定义顶点间基于特征子空间的特征相似性，然后结合顶点特征相似性和拓扑相似性，计算网络中边的相似性，接着利用单链接分层凝聚算法对边聚类，最后提取边上的公共特征作为社团特征。实验利用Facebook网络数据验证了算法能够快速准确的检测出社团结构，并能很好的解释社团含义。利用酵母PPI数据说明算法能够准确检测到具有生物意义的社团，并给出该社团可能行使功能的时间。实验结果说明算法具有普适性，能够在顶点具有属性信息的网络中识别有意义的社团结构。 3.分析动态网络不同时刻间社团结构的变化以研究网络演化规律与特点是动态网络研究的重点。由于动态网络相邻采样时刻网络结构一般变化不大，为避免对相似网络重复聚类，提出一个基于桥系数的静态局部社团检测算法和在此基础上的增量社团检测算法。首先利用静态算法提取每个社团的最小桥系数生成树，最小桥系数生成树的导出子图就是t1时刻的社团结构，然后通过桥系数的变化判断t时刻可能出现结构变化的社团，最后局部调整这些社团，以得到符合t时刻网络拓扑的社团结构。实验利用足球队网络数据验证了静态局部社团检测算法的精确性，利用构造数据验证了增量算法的精确性，利用DBLP数据验证了增量算法的高效性。实验结果说明算法能够利用前一时刻的社团结构和增量信息，快速准确的检测当前时刻的社团结构。 4.蛋白质复合体预测对理解生物体结构与功能之间的关系具有极其重要的意义。研究发现蛋白质复合体由一个核和一些附属蛋白质构成，对复合体的拓扑结构目前没有明确的定义，本文从边的角度刻画复合体的核结构，提出一个基于边的蛋白质复合体检测算法。算法首先识别出所有的核边，然后对核边聚类得到候选核，接下来过滤候选核以保证其中不存在重叠程度较高的核，最后检测每个核的附属蛋白质，得到蛋白质复合体。实验利用DIP数据库中的酵母PPI和文献中的Gavin PPI数据，验证了算法的精确性。实验结果说明算法能够更准确的检测蛋白质复合体，识别出位置一致性和语义相似性都更高的复合体。 5.作为沟通和分享信息的平台，在线社交网络已是人们生活中必不可少的一部分，为注册用户推荐朋友是社交网站必须提供的重要服务，为了解决这个问题，提出基于社交圈的朋友推荐算法。算法基于有相似社交圈的用户更易成为朋友的假设，定义了用户间的社交圈相似性，然后将社交圈相似程度大的间接邻居作为潜在好友推荐给用户。实验使用YouTube数据验证算法假设；使用Facebook数据验证朋友推荐算法的准确性。实验结果说明算法能够更准确的预测好友关系。

关键词： 复杂网络   社团检测   重叠社团   局部优先   标记传播  

摘要： 信息技术的迅猛发展，特别是互联网的发展，使人们已迈入了“网络时代”。复杂网络的研究已成为当前炙手可热的研究领域之一。作为复杂网络研究的重要课题之一，社团检测得到的极大的研究与发展。传统的社团检测方法大多集中在检测非重叠社团上，然而真实网络的一个重要的特性是网络中存在大量的重叠节点。因此，高效准确地检测出复杂网络中的重叠社团结构能够更准确真实地揭示复杂网络的拓扑结构。 针对复杂网络中普遍存在重叠节点这一特性，本文提出了两种社团检测算法：局部优先的重叠社团检测算法和增强的多标记传播社团检测算法。局部优先的重叠社团检测算法针对每个节点生成其邻居网络，通过构造节点邻居网络的一棵最大生成树，从中提取该节点的所有局部圈子，以局部圈子为最小单元，通过定义局部融合策略，实现全局重叠社团检测；增强的多标记传播算法是一种基于标记传播的社团检测算法，但是该算法能同时检测出复杂网络中的重叠社团结构和非重叠社团结构。算法首先扩展了传统标记传播算法节点只能存储单一标记的能力，通过设置从属因子使节点能够同时保存多个标记。同时，通过模拟一种特殊的投票过程设计了新的标记更新策略——增强的标记更新策略。 通过对比分析大量真实网络和生成网络上的实验表明：本文提出的两种社团检测算法能够高效、准确地检测出复杂网络中潜在的社团结构。

关键词： 流数据聚类   模糊聚类   手写数字图像   量子聚类   社团检测  

摘要： 随着现代科技的发展,人类迈入了信息社会,各行各业的信息数据呈现爆发式的增长。如何从这些海量数据中找到真正有用的信息成为人们关注的热点。数据挖掘（Data mining）技术是信息决策和数据库知识发现的重要工具,聚类技术便是数据挖掘技术中一个非常重要的手段。聚类技术目的是将大量样本或抽象的数据按照相互之间的相似性分成若干个子集合,从而发现数据的结构,帮助人们更好的了解数据之间隐藏的信息。信息科技的进步,导致信息规模增长越来越快,样本包含的特征也越来越复杂,很多传统聚类算法都已无法应对如此大规模的数据,研究人员将注意力转移到能够适应复杂海量数据的新型算法上。本文将结合传统模糊聚类算法并引入流数据聚类的概念,提出了针对海量数据的流数据聚类模型,使算法能够适应大规模数据集。本文主要工作如下:（1）提出了一种基于传统点密度加权FCM聚类算法的适应较大规模手写数字图片识别的方法。本方法根据现有流数据聚类方法,每次读取一个数据点,每次循环只对一个点和现有聚类中心计算隶属度,根据隶属度的最大值来决定是否令该点直接参与聚类模型的更新。本算法的关键步骤就是设计了一个基于流数据的聚类框架,结合在线k-means算法模型更新方法和点密度加权的FCM算法,实现了one-by-one的在线聚类来进行无监督方式的手写数字识别。本算法避免了同时处理所有数字图像数据,极大地减轻了大规模数据处理时对计算机硬件的要求,同时与现有的分块的WFCM算法相比,由于大部分点直接参与了聚类模型的更新,减少了调用WFCM算子的次数,从而节省了计算时间,降低了时间的复杂度,更适合处理规模较大的手写数字图片数据。（2）基于上一部分提出的流数据处理框架,提出了一种改进的流数据处理方法,由于之前提出的算法是基于点密度加权的FCM算法,虽然该算法根据数据样本周围的密度来给每一个数据点加权值以突显出周围密度较大的特点,一定程度上提高了算法的收敛速度,但这种算法需要给数据池中的每一个点都计算权值,这在一定程度上增加了算法的计算复杂度。为了避免这种现象,本章我们提出了一种在SPFCM基础上改进的流数据聚类算法,这个算法在上一章中已经使用过。这个算法的基本原理也是给每个样本点进行加权,但每个样本点的权值都初始化为1,只有聚类中心的权值会不断增加,每多一个点对应的聚类中心的权值就会增加。这样在对后来进入的数据块进行聚类时,这些权值较大的点就更容易成为聚类中心。（3）对现有的社区检测算法做了深入研究发现,社区检测问题和数据聚类问题有很多相似的地方,且目前已有很多用聚类手段来做社区检测的方法。由于对复杂网络的特征矩阵结构较为复杂,现有聚类方法方法效果不是很理想。于是我们引入量子聚类方法对网络的特征矩阵进行聚类来划分社区。首先用结构相似度矩阵来度量网络节点关系的强弱,对由该矩阵提取出的特征矩阵进行聚类,将社区检测问题转化为聚类问题。并在聚类阶段引入节点邻接信息,提高了算法的处理效率并提高了算法性能,并在人工生成网络和真实世界网络上和其他算法做了对比。

关键词： 社团检测   社会网络   邻居相似性   半监督   数据挖掘  

摘要： 社团检测分析作为社会网络领域中一个重要的研究领域,在国内外都受到学者们的广泛关注。随着数据挖掘技术的普及和互联网的发展,社团检测的地位也越来突出。其中标签传播算法(LPA:Label Propagation Algorithm)因其具有线性的时间复杂度受到学者们大力推崇,基于层次凝聚和层次分裂的社团检测算法(代表算法如FastQ和GN算法)为社团检测领域也做出了巨大贡献。然而,标签传播算法具有不稳定性,对标签更新顺序比较敏感,而基于层次凝聚和层次分裂的社团检测算法由于时间性能过低,在一定程度上限制了它们应用的广泛性。 本文设计了两个社团检测算法： (1).基于邻居相似性的社团检测算法(NSA:Neighbor Similarity Based Algorithm):NSA算法分为两大步,第一步是根据相似性阈值对网络图进行初步的划分,得到社团结构的轮廓;第二步是对第一步得到的社团结构进行优化,得到更加清晰的社团结构。NSA算法在社团检测过程中只考虑每个节点和它的邻居节点之间的相似性关系,而不考虑和其它节点之间的相似性关系,这点和LPA算法有一定的相似性,只不过LPA算法考虑的是每个节点和其邻居节点的标签关系。所以NSA算法的时间性能和LPA算法相比不会相差甚远,NSA算法也具有接近线性的时间复杂度。同时NSA算法在多个数据集上的实验证明,用NSA算法可以得到高质量的社团划分结构。 (2).基于选点的半监督社团检测算法(SSCDAWSP:Semi-Supervised Community Detection Algorithm With Selected-Point):SSCDAWSP算法在研究社团检测特点和半监督学习理论过程中,发现了社团检测和半监督的结合点,将半监督思想应用到社团检测中。在SSCDAWSP算法设计过程中设计了节点的边界值和核心度定义,以此为选点提供规则基础,另外设计了节点之间的归属度定义,以此来判断相邻节点之间的社团划分关系。SSCDAWSP算法在选点过程中需要用到节点边界值信息和核心度信息,因此计算节点的边界值和核心度会消耗一定的时间性能。但相比其他大多数社团检测算法,SSCDAWSP算法的时间性能还是有一定优势,同时通过多个数据集上的实验证明,SSCDAWSP算法的社团划分精度可达到非常理想的期望。

关键词： 复杂网络   社团结构   邻居   依赖度  

摘要： 社团结构是复杂网络的一个重要属性,在生物学、社会学等众多学科领域有着广泛的应用,越来越受到人们的关注。近年来有很多的社团结构探测算法被提出来,但是这些算法在计算复杂度和准确度上仍然存在着一些不足。本文从节点间的邻居关系出发,提出了两种检测社团结构的算法,主要工作如下： (1)给出了某种社团结构划分下单个节点划分效果的评价：强社团结构节点、弱社团结构节点、二义性社团结构节点和非社团结构节点。这种评价方法的理论基础是强社团结构和弱社团结构的定义,对于分析和判断一种社团结构的划分效果具有一定借鉴意义。 (2)提出了一种改进的派系查找算法,从当前网络中度最小的节点开始,每找到一个派系就删除只存在于这个派系中的边；从大到小选取派系来组成社团或者将派系中的节点吸收进社团。在几个实际网络上对算法进行了测试,并对结果进行分析,结果显示该算法在派系查找上相对现存的其它算法有更高的时间效率和更低的空间资源需求,并且对网络的社团结构划分效果较好。 (3)提出了基于节点间依赖度的社团结构检测算法,这种算法只需考虑一个节点的邻居节点,即可将该节点划分到社团。给出节点对节点、节点对社团的依赖度以及节点对社团的条件依赖度,详细介绍了算法的实现过程,在几个实际网络上对算法进行了测试,并对结果进行分析,该算法有较低的计算时间复杂度,对社团结构的划分结果也比较理想。 本文得到国家自然科学基金(61370145,61173183,60973152),高等学校博士点专项科研基金(20070141014),辽宁省高等学校优秀人才支持计划资助(LR2012003),辽宁省自然科学基金(20082165),中央高校基本科研基金(DUT12JB06)的联合资助。

关键词： 复杂网络   社团检测   密母算法   紧密度   模拟退火  

摘要： 现实世界中的很多复杂系统可以由网络表示出来,如技术网络、社交网络、交通运输网络及生物网络等。这些网络经过建模以后可抽象化为图,其中节点表示对象,节点之间的连接可以表示对象之间具有某种关系。社团结构是复杂网络的一个重要特性,它可以定义为网络中的一个由若干节点构成的子集,其内部节点之间连接紧密,而与网络中其他节点之间的连接较为稀疏。研究社团结构对于分析复杂网络的拓扑结构、理解复杂网络的功能、预测复杂网络的行为具有重要的意义。近年来,社团检测问题受到了各个领域的学者的广泛关注,许多算法也相继被提出来,如图划分方法、层次聚类法、谱聚类法、基于相似度的方法以及基于进化的优化算法等。密母算法是计算机科学和社会生物学的交叉产物,它建立在模拟文化进化基础之上,实质是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。经过多年发展,密母算法已被越来越多的研究人员接受并广泛应用到组合优化、模式识别、图像处理等领域中。本文针对复杂网络社团检测进行了系统地研究,所取得的主要研究成果为:1.研究进化算法的基本理论,并深入理解密母算法及其改进算法在复杂网络社团检测问题中的应用。在此基础上,提出了一种利用局部结构信息的密母算法(Memetic algorithm using local structural information,MA-LSI)用于解决复杂网络的社团检测问题。在该算法中,利用模块度函数Q作为适应度函数,并利用一个局部社团的质量评价函数来定义局部搜索算子,此外还采用了一种节点移动策略来改善划分结果。与经典的快速纽曼(Fast Newman,FN)聚类算法和其他密母算法相比,实验结果表明该算法可以产生更为精确的划分结果。2.研究了传统的模块度优化所具有的分辨率限制问题,采用另外一个可以克服分辨率限制问题的目标函数:扩展模块度密度函数。该函数中含有一个可调参数,通过改变参数的取值可以实现以不同分辨率分析网络,从而检测出网络的多分辨结构。基于扩展模块度密度函数的优化,提出另外一种密母算法(Memetic algorithm with simulated annealing strategy and tightness greedy optimization,MA-SAT)用于复杂网络社团检测。该算法中有两个局部搜索算子,一个采用了模拟退火策略,另一个采用了局部社团紧密度函数的贪心优化。模拟退火策略可以加速算法的收敛且有助于算法跳出局部最优,紧密度贪心优化充分利用了网络的结构信息来产生邻居划分,计算代价小并且有助于提高种群的多样性。与几种经典算法对比的实验结果表明该算法是非常有效的。本文工作得到如下基金资助:国家自然科学基金(No.61003199),中央高校基本科研业务费专项资金资助(***140216和K5051202019)。

关键词： 聚类分析   量子聚类   核熵主成分分析   结构相似度   社团检测  

摘要： 数据挖掘技术是近年来在人工智能、信息决策及数据库领域研究的热点之一。在众多数据挖掘分析工具中，聚类分析是一种最常用、最有力的工具。聚类分析的目的是将抽象出来的对象或样本集合根据相似度划分成若干具有特殊意义的团或者类，从而更好地理解和分析数据，发现样本的潜在分布结构。迄今为止，人们提出了大量聚类算法。但随着数据规模（包括样本个数及数据维度）越来越大，而先验知识相对匮乏，传统的聚类算法效果并不尽如人意。受量子力学启发，量子聚类（Quantum Clustering, QC）将聚类问题作为一个物理系统，在波函数已知的情况下，通过求解薛定谔方程式（Schr dinger equation）导出势能函数，从势能能量点的角度来确定聚类中心。作为一种基于划分的无监督聚类算法，量子聚类能够克服传统方法的一些缺陷，如对初始值和噪声敏感，聚类类别数需要事先给定等。为了进一步提高数据的聚类精度和运算效率，本文在传统量子聚类基础上做了相关的改进工作。由于复杂网络的社团检测与数据的聚类分析具有一定的相似性，量子聚类同样可以应用于社团检测问题研究。本文所做的主要工作如下： （1）通过研究了量子聚类的基本理论及特点，提出了一种利用核熵主成分分析的量子聚类算法。为了获取数据的潜在结构，采用核方法将原始数据映射至高维特征空间，并用熵值为评价标准筛选特征向量，以获得核熵主成分。为了增强算法的局部特性，同时提高算法的运行效率，在量子聚类算法中引入K近邻策略，并通过梯度迭代获得最终的聚类结果。通过实验分析，不论是聚类效果还是鲁棒性，该算法远优于其他对比算法，尤其是对线性不可分数据集。 （2）在对已有的复杂网络社团检测算法进行深入研究的基础上，将量子聚类应用于复杂网络的社团检测问题研究中。首先为把网络转化为适合聚类分析的数据结构，构建了结构相似度矩阵，度量网络中节点之间连接关系的强弱。同时，在量子聚类过程中，引入节点的邻接信息，在提高算法局部分析能力的同时，降低算法的时间复杂度。 （3）针对大规模复杂网络的社团检测问题，借鉴小规模社团检测解决方式，综合考虑检测精度和运算效率两方面的因素，提出了两点改进策略以增强量子聚类算法对大规模网络社团检测的处理能力。该算法采用网络层次划分方法，将原始大规模网络划分成若干个较小的子网络，并在子网络中构建相似度矩阵。此外，采用Nystr m方法逼近结构相似度矩阵的特征向量，进一步提高算法的运行效率。仿真结果表明，该算法能够取得较好的检测效果，且运算时间较之于原来的算法大大降低。

关键词： 社会网络   社团检测   层次凝聚   主动学习   半监督  

摘要： 近年来,复杂网络研究作为一个新兴的研究方向,已经成为了计算机科学、统计物理学、社会学、生物信息学等领域的一个热点问题。复杂网络具有小世界性、无尺度性、模块性等特性。通常,一个复杂网络包含有若干个社团,同一个社团内的节点联系紧密,不同社团间的节点联系疏松。发现复杂网络的社团结构是理解和分析复杂网络的一种重要工具和手段。有效的社团检测算法,可以划分出清晰的社团结构,降低复杂网络的研究难度。发现复杂网络的社团结构是复杂网络研究中的一个重要课题,具有重要的应用价值。 本文通过对现有社团检测方法的研究分析,提出了两个新的社团检测算法CDACSM和ASCD。CDACSM算法是基于相似度度量的层次凝聚社团检测算法,该算法主要解决层次凝聚社团检测算法存在的两个问题：1)容易产生极小和极大社团；2)一旦节点的标签被划分错误,直到社团检测结束都是错误状态,无法更正。CDACSM算法通过定义单点社团间的相似度、社团间的相似度等度量标准和单点社团和社团间的合并规则等,在一定程度上有效地避免了以上两个问题。ASCD算法是基于主动学习的半监督社团检测算法,该算法的设计主要针对以下三种社团划分结果不清晰的情况：1)半监督学习的标签数据质量不理想时；2)网络结构比较复杂和模糊时；3)社团规模大小相当时。ASCD算法定义了相关度、最相关节点、凝聚力等度量标准,提出了标签数据的主动选取方法和利用这些标签数据进行半监督学习的策略,在以上三种情况下获得了较好的社团检测效果。 本文利用多个真实的复杂网络数据集和评判基准图数据集对CDACSM算法和ASCD算法进行了实验验证。通过模块度、准确率、运行时间效率等多项指标对CDACSM算法和ASCD算法进行评价,实验结果表明本文提出的两种社团检测算法具有较好的社团检测效果且运行效率较高。

关键词： 复杂网络   社团结构   边模式   网络检测  

摘要： 为了检测网络的社团结构,提出基于统计推理的边模式社团检测方法,在计算机生成的网络中和实际网络检测了算法的可行性和准确性,并与现有的两种基于边模式的社团检测方法做了比较。实验表明,所提出的方法可以快速有效地检测出重叠社团,在性能上优于后两种方法。

关键词： 用户社团   社团变化   异常检测   复杂网络  

摘要： 为准确刻画Internet上的用户群体行为,发现网络中潜在的协同攻击。首先从采集的流中提取用户的社会行为特征,构建用户交互网络(HIN)。然后,基于HIN的用户社会行为的相似性,定义用户社团,并定义5个指标对用户社团的变化进行定量描述,采用基线法设置每个指标的检测区间。期间,为了适应网络环境的动态性,引入了固定时间宽度的滑动窗口机制实现自适应网络异常群体行为检测。提出了一种通过对用户社团变化的监测实现网络异常群体行为检测的方法。通过在两个实际网络流数据集上进行试验验证了基于用户社团变化的方法可以检测大型网络的异常群体行为。