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

摘要： 数据挖掘技术是近年来在人工智能、信息决策及数据库领域研究的热点之一。在众多数据挖掘分析工具中，聚类分析是一种最常用、最有力的工具。聚类分析的目的是将抽象出来的对象或样本集合根据相似度划分成若干具有特殊意义的团或者类，从而更好地理解和分析数据，发现样本的潜在分布结构。迄今为止，人们提出了大量聚类算法。但随着数据规模（包括样本个数及数据维度）越来越大，而先验知识相对匮乏，传统的聚类算法效果并不尽如人意。受量子力学启发，量子聚类（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算法进行评价,实验结果表明本文提出的两种社团检测算法具有较好的社团检测效果且运行效率较高。

关键词： 复杂网络   社团检测   重叠社团   离散粒子群算法  

摘要： 针对复杂网络重叠社团检测的问题,建立了衡量重叠社团划分优劣的评判函数,并基于该函数提出了一种采用混沌量子粒子群优化的复杂网络重叠社团检测算法。该算法采用量子编码,利用Logistic映射初始化粒子种群,并以粒子群速度改变方式更新转角的大小,以概率为1收敛。实验结果表明,所提算法具有较高的检测正确率,能更好地反映实际社团划分情况。

关键词： 社交网络   社团检测算法   拓扑结构   MDL函数   检测速度  

摘要： 随着互联网的快速发展，特别是web2.0的理念普及相关技术的日臻成熟，基于社交网络的新型互联网应用有了飞速的发展。这些应用使得社交网络的节点数量规模越来越大，节点之间的联系也越来越复杂。研究社交网络中的社团结构，有助于掌握网络的拓扑结构、揭示网络的特性、了解网络中各个部分的功能、发现隐藏在网络中的规律和预测网络的行为。现有的社团检测算法在检测速度和划分的准确度上很难达到一种平衡，特别是在网络规模越来越大的情况下，研究这一问题具有重要意义。\n 本文提出了基于改进的Infomap社团检测算法和基于扩散的层次化社团检测算法。其中基于infomap改进的社团检测算法在Infomap的基础上提出了基于合并最小MDL所对应社团的改进算法，将MDL函数优化为一个遍历节点访问频率和离开概率的函数，提高了算法在进行社团检测时的检测速度。基于扩散的层次化社团检测算法采用了扩散的、层次化的社团检测方法，在局部核心结构的发现中，应用了网络的树形结构的特征，通过不断调整边权重阈值，得到局部核心树结构；在扩散步骤中，先将剩余节点归到其最大权重边所连节点所属社团中，再进行剩余两个扩散步骤；在选择初始边权重阈值的过程中，算法采用了所发现的最稀疏社团的社团密度值作为优化的目标，使发现的社团结构更加明显。\n 仿真结果表明，本文算法可以将大量用户连接关系简化为社团与社团之间的连接关系，以及各个社团内部的关系。这样就能在很大程度上减少每次需要处理的数据量，对海量数据的分析能起到化繁为简的作用。

关键词： 复杂网络   社团结构   局部相似性   K-means聚类   检测算法  

摘要： 现实生活中的很多网络,如互联网,电力系统网,神经网,人际关系网,都可以看成是复杂网络。这些网络共同的特点就是具有小世界,无标度,社团结构等特性。其中社团结构是复杂网络最重要的特性之一,寻找和分析社团结构有助于更好地了解网络的内部结构,分析网络的性质。所以,复杂网络的社团结构研究近年来成为人们研究的热点问题,大量的复杂网络社团挖掘算法陆续被提出来。本文从社团的相似性定义出发,研究了现有的节点相似性度量指标,提出了一种新的局部相似性指数,结合现有的基于相似性的社团检测算法对网络社团进行划分。主要工作如下:　　(1)研究经典的复杂网络社团结构检测算法,分析了研究复杂网络社团结构的一般方法。　　(2)在研究现有的网络节点的相似性指标的基础上,定义了一种新的局部相似性指数,从理论上证明了该局部相似性指数在社团检测方面比其它局部相似性指数更具优势。　　(3)提出了一种基于局部相似性的K-means谱聚类算法,该算法采用网络节点相似性矩阵的前 K个最大特征值所对应的特征向量为坐标,将网络节点映射到欧式空间,再采用 K-means谱聚类算法对其进行社团划分,算法根据最大特征值间距预测社团个数,再采用模块度进行验证。在计算机生成的网络和大量的实际网络验证该算法的可行性和有效性。　　(4)提出了一种基于局部相似性的AP聚类算法,该算法以节点的局部相似性矩阵作为基础,起初将所有的节点视为聚类中心,通过对每个节点的“吸引度”和“归属度”不断修改,来确定最优的聚类中心和每个节点的社团归属。在计算机生成的网络和大量的实际网络上验证了算法的可行性和有效性。　　(5)将定义的局部相似性指数和现有的基于相似性的聚类算法相结合对计算机生成的网络和大量的实际网络进行社团划分,并和GN算法,快速算法等做了比较,结果表明,所定义的相似性指数和传统局部相似性指数相比,能够更为准确的刻画网络节点的相似性,该相似性和大多数基于相似性的算法相结合都能够较为准确的检测网络的社团结构,因此,所提相似性指数是一种比较有竞争力的相似性指标。

关键词： 社会网络   社团检测   模块度   时间序列   动态演变  

摘要： 社会网络是用来描述社会成员之间关系的网络。随着计算机网络技术的迅猛发展，基于互联网的电子邮件网络、对等网络、社交网络和博客网络等新兴社会网络也得到了极大的发展。对社会网络开展研究，具有重要的理论意义和实用价值。由于社会网络往往规模庞大、结构复杂，所以我们通常采用复杂网络的理论和模型来对社会网络进行研究和建模。 真实社会网络通常具有复杂网络的一些结构特征，如:社团结构，无标度的度分布，聚类、“小世界”网络、动态演变等。社团结构是社会网络的一个重要结构特征，准确检测复杂社会网络的社团结构是近年来社会网络研究的重点。在社团结构的检测中，模块度起了很重要的作用，它可以用来评价社团结构划分的质量。另外由于社会网络消耗了互联网上的大部份流量，对社会网络进行测量也是一项重要工作，有助于我们深入了解社会网络的拓扑特征，监控网络流量，保障网络安全。本论文的主要研究工作是基于复杂网络理论挖掘社会网络的社团结构，统计分析其结构特征，并对社会网络进行主动测量，从而揭示真实社会网络的演化规律。本论文取得的创新性成果如下： (1)提出了一个基于有向加权模块度的静态社会网络社团结构检测方法 基于无向和有向网络、无权和加权网络社团结构分析的可统一性，提出了一个新的模块度最优化的静态社会网络社团结构检测方法SNCD。该方法引入了边的方向和权重，使用有向加权模块度来进行社团结构的检测。由于社团划分时可参考的有用信息更多，从而提高了算法的准确性和有效性。该方法使用堆结构和多任务的模块架构，大幅度提高了计算效率，在结点数目达到百万级的网络规模下，仍能获得较优的执行效率，并且社团划分的质量高于当前应用较广泛的一些典型算法。 (2)设计了一个基于时间序列的动态社会网络社团结构检测模型 将社会网络的时序动态性和时刻静态性用时间序列的方式来表示，即社会网络在时间序列的每一个时刻是静态的，同时又随时间序列动态演变。通过使用基于结构相似度的模块度新定义，设计了一个基于时间序列的动态社会网络社团结构检测模型。该模型首先提出了一个静态社会网络社团结构检测方法LMA，用以检测时间序列上每一个时刻的静态社团集合，为下一步DNCD方法提供中间过程社团集合。随后扩展LMA方法，提出了一个基于时间序列的动态社会网络社团结构检测方法DNCD。该方法将中间过程社团集合与社团时间序列链进行匹配，以得到社团演变的轨迹和反映网络结构的稳定社团集合。 (3)提出了一个社会网络主动测量策略 为了深入了解社会网络的结构特征，监控网络的实时状态，提出了一个多协议模块化的社会网络主动测量策略。以对等网络中的BitTorrent协议作为测量对象，采用拟定的主动测量策略，设计了相应的测量指标，实现了对真实社会网络的实时测量，揭示了真实社会网络的内在结构特征和行为模式。

关键词： 模糊聚类   Weka   和声搜索   谱聚类   社团检测  

摘要： 聚类分析是一种重要的数据挖掘工具，在传统意义上，聚类是准确地将数据样本分到不同的类当中，这就是所谓的硬划分。但生活中的多种事物属性都存在着一定的模糊性，也就是说事物之间没有明确的判断依据,无法准确地进行事物的划分与判断,因此模糊聚类就发挥了自己的作用。模糊聚类分析是数据挖掘领域中的一个重要分支，在工程、计算机科学、生命和医学科学、社会科学和经济学等领域得到了广泛的应用。由于模糊聚类中的样本同时属于不同的类别，而且在各个类别的隶属度不同，这种不确定性反映了样本类属的模糊性，更能客观地反映现实世界，因此研究模糊聚类的算法及其应用具有十分重要的价值。 Weka是新西兰Waikato大学开发的数据挖掘平台，它为数据挖掘领域研究者提供了多种分类、聚类和关联规则等数据挖掘方法，数据预处理功能，以及算法性能评估的多种方法。作为一个开源平台，Weka具有非常良好的扩展性和兼容性，有良好定义的数据结构和基本的统计接口，为开发者提供了一个非常便利的工具。 本文主要从模糊聚类的现有问题中寻找有效措施，提高聚类结果的准确性，算法的稳定性和健壮性，减少人工的干预和对不同领域专业知识的依赖。因此，本文将基于和声搜索和谱分析的模糊聚类算法在Weka平台上实现了封装和应用，丰富该平台的聚类算法组合，扩大其使用范围。本文的工作和创新如下： 首先，提出了全局动态自适应和声搜索自动模糊聚类（Global DynamicAdaptive Clustering Harmony Search K-Harmonic Means， GDACHSKHM）算法，它是基于和声搜索与KHM混合的元启发模糊聚类算法。GDACHSKHM利用了和声搜索的全局搜索能力，能够分析数据本身的特点来确定簇的数目而不需要任何先验知识，同时能自适应地找到问题的全局近似最优解。算法运行过程中，参数能够根据每次迭代的结果来更新其值而无需手动调整，减少了人工干预。经过实验证明GDACHSKHM具有良好的聚类效果和健壮性。 其次，提出了谱差分进化调和K均值模糊聚类（Spectral DifferentialEvolution KHM，SPDEKHM）算法。该算法分为两步：谱映射和模糊聚类。谱映射实际上是Laplacian矩阵的特征求解过程，它将数据从原来空间映射到低维的解空间，减少了数据维数，让数据集的划分更加明显;映射过程中通过分析Laplacian矩阵的特征值梯度来自动确定簇个数。再利用DEKHM算法将映射空间的节点进行聚类，发挥DE和KHM各自的优点已达到最好的聚类结果。实验证实该算法在大多数的情况下能获得准确率较高的聚类结果。 最后，将谱聚类的思想应用到复杂网络的社团结构检测问题中，提出了基于关联矩阵谱映射的自动社团检测（Correlation Spectral MappingAutomatic Community Detection, CSMACD）算法。该算法首先通过关联矩阵的谱映射将社团检测问题转换为聚类问题，再以模块度值为目标函数，通过DEKHM算法来寻找最优的社团数目和相应的网络划分方案。在模拟网络和真实网络上的实验表明CSMACD能够准确地分析结构复杂，社团大小不同的网络社团结构，具有良好的健壮性。

关键词： 数据挖掘   社会网络   社团检测   随机游走   线性阈值   协同方法  

摘要： 21世纪,随着信息技术的普及发展以及各种社交网站的流行,研究人员可以便捷地收集复杂社会网络数据集,这极大程度上促进了人们对复杂社会网络的研究分析。研究表明复杂社会网络具有小世界性、无尺度性、模块性等特性。社团目前尚无明确统一的定义,一般认为是满足社团内部节点联系紧密而社团间节点联系稀疏的节点集合。社团检测算法一直是复杂社会网络中的一大研究热点,主要研究如何从复杂社会网络中发现高质量的社团结构。清晰的社团结构对研究分析复杂社会网络问题有极大的帮助。 本文的主要工作是社团检测算法研究,文中共提出了三个社团检测相关算法。第一,本文提出一种基于随机游走改进的节点相似性计算方法(RWS),可用于根据网络的拓扑图及权重信息快速计算网络中节点的相似性：第二,本文提出一种基于线性阈值模型的社团检测算法(LTCD),该算法通过初始社团不断激活边界节点的方式来扩展社团；第三,本文还提出一种基于协同方法的社团检测算法(CMCD),该算法旨在提高社团检测算法的性能。这三个算法出发点和侧重点各不相同,RWS是用来计算节点相似性,LTCD是一种简单的社团检测算法,而CMCD是一种提升社团结构检测质量的框架算法。 本文在多个真实和人工合成社会网络数据集上进行实验,从模块度、准确率和标准互信息等方面对实验结果进行分析。实验结果表明本文提出的算法能得到较高质量的社团结构。

关键词： 动态网络   进化方法   局部优先   重叠社团   时序演化  

摘要： 作为一种对现实中大规模复杂系统的抽象工具，复杂网络得到了广泛的关注。现实世界中的复杂系统往往随时间缓慢变化，动态网络作为刻画复杂网络动态性的有效手段，具有很高的研究价值。目前对复杂网络进行分析的方法主要集中在社团检测上。对动态网络进行社团检测，有助于人们认识网络特性以及发展趋势，具有重要的理论和实际意义。 传统的动态网络社团检测算法通常在每个时刻对网络快照进行划分，试图找到“模块性”较高的社团结构，然后分析社团之间的关系。这种方法忽视了动态网络的时序性，难以发现社团结构的演化性。同时，传统的社团检测算法通常以一种“自顶向下”的视角对网络进行划分，这种方法通常难以发现小于一定规模的小社团。然而，现实中这些小社团可能具有一些实际的功能和意义。另一方面，现有的动态社团检测算法通常不能检测到社团的重叠结构，而重叠性作为社团结构的重要特征，很有研究的必要。综上所述，本文提出了一种基于进化和局部优先的动态社团检测算法，对每个节点抽取其EgoMinusEgo子图，在其上使用标签传播算法进行局部社团划分，之后以一种“自底向上”的视角不断合并局部社团直至得到网络的一组划分。在执行合并策略时，引入了覆盖率和分布率两个指标分别代表当前社团拓扑结构与历史信息两个方面，使用进化聚类框架来平衡这两个指标，从而使得到的社团具有时序演化性。 本文在真实网络数据上对提出的动态网络社团检测方法进行了实验。实验结果表明本文提出的基于进化和局部优先的社团检测算法能够有效地检测到社团的重叠结构，同时能够检测到具有实际意义的小规模社团结构。而与其他局部优先的算法相比时，本文的算法得到的社团结构更好，同时在相邻时刻间具有更紧密的联系。

关键词： 网络   社团结构   模块度优化启发式算法   社团检测  

摘要： 模块度优化的启发式快速算法常常用来检测复杂网络中的社团结构。较之其余的社团检测方法,该算法在计算时间上更具优势,而且用模块度衡量发现检测社团的质量很高。运用模块度优化启发式算法划分空手道俱乐部网络、大学足球俱乐部网络和区域贸易网络等,并对其结构和功能做出一定的分析。特别地,针对贸易网络中自由贸易区往往表现为一个社团的特点,以221个国家或地区为研究对象,对贸易协定与地域之间的关系做了大量的实证研究。首先,从世贸组织网站上采集了区域贸易协定中国家之间贸易的数据;其次,通过模块度启发式算法进行社团划分,共得出7个主要的贸易区,其中欧盟自由贸易区的社团表现极为明显;最后,从社团结构的表现形式推断实际区域间的贸易情况。