摘要： In a very general context, communities in networks are defined as groups of nodes that have some common properties such that connections are stronger between the nodes in a community than with the nodes in the rest of the network. It is quite common for nodes to participate in multiple communities. Therefore a community detection algorithm for such applications should be able to detect overlapping communities. However, overlapping community detection is more computationally intensive than disjoint community detection and presents new challenges that algorithm designers have to face. Besides, the big data phenomenon with exabytes of data brings up datasets that take too long to analyze using even the fastest algorithms currently available. Fortunately, the amount of computing power available to researches also increases. This computing power usually comes structured as a number of cores, processors, or machines joined together to form a high performance computer, cluster or a supercomputer. In this thesis we analyze what other researchers have done to utilize high performance computing to perform efficient community detection in social, biological, and other networks. We use the Speaker-listener Label Propagation Algorithm (SLPA) as the basis for our parallel overlapping community detection implementation. SLPA provides near linear time community detection and is well suited for parallelization. We explore the benefits of a multithreaded programming paradigm for both synthetic and real-world networks and show that it yields a significant performance gain over sequential execution in detecting overlapping communities.

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

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

关键词： 社团检测   标记散播   结构相似度   模块度   邻居网络  

摘要： 现实生活中，我们常常将一些问题通过建模的方法，把对象和关系抽象成网络结构，进而发现对象间的共同特征，解决这些实际问题。随着数据量的与日俱增，大规模网络社团结构的检测已经成为一个重要研究课题。它是对静态群体进行归类划分、动态群体演变过程分析、寻找局部范围影响力最大的个体、制定简单有效的管理方案等现实问题进行研究的基础环节。因此，如何在规模庞大、内部结构复杂的网络上快速、有效地发现社团结构，对于数据分析、信息提取具有重要意义。 本文在经典标记散播社团检测方法的基础上，深入研究大规模复杂网络的特征，针对算法中的节点标记更新方法和迭代次数进行改进工作，取得了如下创新性成果。首先，提出了基于模块度最大约束的标记散播社团发现方法。该方法通过分析网络中节点间的结构相似度，构造基于网络模块度计算的带约束条件的目标函数，获得更合理的节点标记更新公式，提高网络社团划分结果的准确率。接下来，又提出了基于α-度邻居影响度的标记散播社团检测方法。该方法通过计算网络中节点在α-度范围内的邻居影响因子，判断节点标记的散播顺序和散播方向，可以在较准确的进行社团划分的同时有效降低运行时间。 在各类网络上的实验结果表明：本文提出的两种基于标记散播的社团发现方法均可以准确地对任意规模、任意内部结构的复杂网络发现任意各种形状的社团；且基于α-度邻居影响度的标记散播社团检测方法具有较高的运算效率和极强的实用性，可运用在动态网络的社团划分和演化分析中。

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

摘要： 现实世界中大量复杂系统可以抽象为复杂网络模型，社团结构是复杂网络的关键结构特征，网络的整体功能是网络中各社团相互作用的结果。因此社团结构检测是复杂网络研究中的重要内容。 本文研究复杂网络社团检测算法及其在生物领域和社会领域的应用，主要包括以下几点： 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数据验证朋友推荐算法的准确性。实验结果说明算法能够更准确的预测好友关系。

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

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

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

摘要： 社团检测分析作为社会网络领域中一个重要的研究领域,在国内外都受到学者们的广泛关注。随着数据挖掘技术的普及和互联网的发展,社团检测的地位也越来突出。其中标签传播算法(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算法的社团划分精度可达到非常理想的期望。

关键词： 动态网络   社团检测   局部模块度   重叠性   层次性  

摘要： 随时间缓慢变化的复杂系统可以建模为抽象的动态网络。由于动态网络在社会学、生物信息学、物理、计算机等研究领域有广泛应用,越来越受到科研工作者的重视。近几年动态网络成为科研热门领域,具有实际意义的动态社团结构是动态网络中普遍而又重要的特征。当前动态社团检测算法仍主要基于静态检测方法的相关理论基础。基于极大化Q函数的动态社团检测算法存在分辨率问题,即为了获得更优的模块度值小社团常被合并为大社团。另一方面,很多动态社团检测算法需要设置多个参数或阈值,这就要求对网络有一定的先验知识或需要借助Q函数对结果进行判定。而且,已有的动态社团检测算法不能识别出如社团间的重叠结构等重要拓扑特征。为解决上述问题,本文提出了一种基于进化聚类和局部模块度的重叠结构动态社团检测算法。基于局部模块度的社团检测方法,将整个网络的社团检测问题转化为自底向上的凝聚问题,能适应网络中规模不等、密度不均的社团结构。通过统计节点随机游走行为特征,增强无权网络的分辨率,并使用进化聚类框架下的时序开销嵌入技术来平衡当前社团的拓扑特征与历史信息,从而检测出社团演化的动态规律。该算法仅在进化聚类过程中对平衡因子进行设置,无需领域先验知识。本文使用真实网络数据对该动态网络社团检测算法进行评估,包括Drosophila melanogaster数据集和科学家合作网络(DBLP)数据集。实验结果表明,基于进化聚类框架和局部模块度的动态社团检测算法与基于进化和局部优先的算法相比,扩展模块性指标提高了15%,显著提高了Drosophila melanogaster社团检测结果质量。并且,该算法能有效刻画出DBLP中科研团队的动态演化过程。综上,该算法可适用于无社团结构先验知识的网络,有效检测出具有特定意义的小规模社团及其重叠结构。

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

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

关键词： 社团检测   复杂网络   自然最近邻居   结构相似度  

摘要： 很多自然和社会中的复杂系统，都可以按一定的方式描述成图或者网络。这些网络具有复杂的内部结构，因此称为复杂网络。近些年来，随着复杂网络在众多领域中的广泛应用，复杂网络中的社团检测与分析也越发受到人们的注意。社团结构的特点在于社团中的节点处于一种高密度的集聚状态而社团之间的节点则处于一种低密度的连接状态，而社团检测最基本的作用是将个体进行社团分类，将个体分配到若干社团中。该问题的深入研究有助于以一种分而治之的方式研究整个网络的模块、功能及其演化，更准确地理解复杂系统的组织原则、拓扑结构与动力学特性。 到目前为止，人们提出了许多算法来检测复杂网络中的社团结构。典型的社团检测算法大致可以分为传统的分级聚类和图形分割算法，比如Kemighan-Lin算法和谱平分算法，以及GN算法和Newman快速算法。这些算法都有各自的优势和不足，都有其特定的适用范围，还需要进一步改进。如有的算法在计算效率方面，有的算法在算法思想方面仍值得改进。但是，这些算法绝大多数都是将网络检测成为若干个相互分离的社团，准确度在一定程度上取决于初始条件的选择，并且不能识别网络中的一些重要节点。2011年Xu Xiaowei提出了一种基于结构相似的社团结构检测算法SCAN。该算法的优点是不仅可以对网络进行社团结构的检测，并且可以找出网络中的特殊节点。但该算法的不足在于对参数的选择非常敏感，难以保证检测出的社团的质量。 本文在SCAN算法的启发下，借用结构相似度的思想，利用自然最近邻居算法无需参数的优势，提出了一种新的社团检测算法——基于自然最近邻居的社团检测算法CD3N。同时，邻居本身就包含一种社团的概念，这使得自然最近邻居算法可以很好的理清复杂网络中的节点关系。本文对原有的自然最近邻居概念进行了改进，使用结构相似度代替距离作为邻居的判定依据，详细分析了各种自然最近邻域图的优缺点并提出了一种适用于社团检测的自然最近邻域图的构造方法。最后使用真实数据集进行实验，与源数据划分结果和SCAN算法结果进行对比分析，证明了算法的可行性和有效性。

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

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