关键词： 熵   超网络   重叠社团  

摘要： 研究了超网络的社团划分问题。超网络是实际应用中的超图,而超图则是一种广义上的图,它的一条超边可以连接任意多个顶点。提出了一个基于熵的超网络社团检测算法,该算法是对Cha等人的算法的推广,能够检测出重叠社团。将这两种算法应用到了中国大陆图论科研合作超网络中,对结果进行了分析和比较,认为提出的算法是有效的。

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

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

关键词： 社交网络   恶意链接   机器学习   网络安全  

摘要： 社交网络正逐渐成为人类社会交流的平台，用户群规模也不断扩大。无论在娱乐还是商务上，社交网络价值都日益凸显，逐渐成为我们生活中不可或缺的一部分。社交网络迅速发展的同时，也面临着很大的安全威胁。主要包括:XSS跨站脚本攻击、分布式拒绝服务攻击、蠕虫攻击、恶意链接攻击等。其中，恶意链接是社交网络面临的主要安全威胁之一。通过对社交网络中出现的链接地址进行安全性检查、提示及过滤，能够防止用户点击恶意链接，有效保护社交网络用户;同时能够帮助社交网站管理员了解社交网络安全态势，制定安全策略，消除社交网络安全威胁。\n 为了实现在社交网络中快速检测恶意链接，本文提出了一种基于社团结构的恶意链接检测方案。该方案首先结合网络爬虫和调用官方API的方式，实现了社交网络数据收集工具。然后，该方案基于社交网络的自身特性，根据关系紧密的用户行为的相似性，将社交网络中的用户预先划分成社团，能够将发布恶意链接且关系紧密的用户划分到相同的社团内，从而可以优先检测恶意度大的社团用户发布的链接，以提高恶意链接的检测效率和准确性。在检测方面，该方案使用了结合黑白名单匹配、Google API接口和机器学习技术的检测方法，以满足系统对已知恶意链接和未知恶意链接进行检测的要求。\n 本文根据上述方案实现了原型系统，利用数据收集工具收集了新浪微博用户的信息，并对其进行了社团划分和恶意链接检测。实验表明，针对社交网络用户采用社团分组检测的方式能够尽早地检测出恶意链接，综合了黑白名单匹配、API调用和机器学习技术的检测方法也可以进一步提高恶意链接检测的准确度。

关键词： 复杂网路   中心性   多目标优化   社团智能检测算法   信息流  

摘要： 人类已经生活在一个包含各种各样的复杂网络的世界中,自然界中许多相互作用的复杂系统,如互联网、电力系统、生物分子系统等,皆可抽象成复杂网络。迅速发展的计算机处理能力和海量数据存储能力使得科学家越来越容易地在现实世界中收集海量的网络数据,研究其内在规律。除了小世界特性、无标度特性,社团结构特性被认为是复杂网络中最重要的统计特性之一。揭示网络的内在社团结构对理解结构与功能关系、发现其演化规律、监控与预测其演变行为具有重要的理论意义和广泛的应用前景,已成为近几年来学术界的研究热点。本文对复杂网络中社团智能检测算法及中心性度量进行了探索和研究,主要工作和创新成果分为如下五个方面:\n 1.分析了基于优化模块度检测复杂网络社团结构的算法存在解的限制问题,该类算法不能检测出小于一定内在尺度的社团,并提出了基于极值优化模块密度来检测复杂网络社团结构的一种新的启发式算法,通过调整局部极值来优化全局的变量,使算法具有更好的持续搜索和跳出局优解的能力。通过人工网络和现实网络实验分析表明,所提算法在检测网络社团时,具有较高的正确率和效率,即使在网络结构变得很模糊时,算法也能很好地工作。\n 2.通过分析复杂网络重叠社团检测问题,提出了衡量重叠社团划分优劣的评判函数,并基于该函数提出一种基于混沌量子粒子群优化的复杂网络重叠社团检测算法,并证明了该算法以概率1收敛。所提算法采用量子编码,利用Logistic映射初始化粒子种群,以粒子群速度改变方式更新转角的大小。利用计算机生成的网络和实际网络进行了仿真实验,比较了所提算法与经典算法的性能,结果表明,所提算法所得检测结果具有较高的检测正确率,能更好地反映实际社团划分情况。\n 3.提出一种基于分解多目标优化的复杂网络社团检测新算法。新算法将社团检测问题构造成多目标优化问题,通过在多个目标之间权衡折衷,实现在更广泛的空间进行社团结构检测,克服了传统单目标优化存在解单一的缺陷。算法采用MOEA/D框架,运用Tchebycheff分解技术,引入基于加权法的模拟退火局部搜索算子,扩大了搜索范围,使算法不易陷入局部最优解。最后,在计算机生成的网络数据集以及真实网络数据集上对算法进行了仿真实验。结果表明,该算法与已有算法相比,具有较高的检测正确率,计算量较小。同时,获得的多个 Pareto最优解有助于揭示复杂网络社团的层次结构。\n 4.提出一种新的动态网络社团检测的多目标进化算法,算法以快照质量和时序价值为优化目标构成多目标优化模型。分别选择模块密度度量快照价值,标准互信息来度量时序价值。采用NSGA-II框架,结合问题特征,设计新的遗传算子。针对问题特定领域知识,设计了一个局部搜索算子来提高社团检测性能。对合成数据和真实数据进行实验,实验结果表明所提算法比对比算法可以更精确地检测动态网络社团结构,真实反映社团的演化。\n 5.提出一种基于信息流的复杂网络中心性测度,并将其扩展到组中心性,用来度量一组节点的中心性。所提测度克服了传统中心性测度的缺点,不仅适用于连通网络,也适用于非连通网络。利用标准测试集对所提测度与传统中心性测度进行了比较试验,结果表明所提测度具有较好的性能。最后,对所提测度在大规模计算机生成的数据集和现实数据集上的统计特性规律进行了研究。

关键词： 社交网络   社团检测算法   拓扑结构   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子图，在其上使用标签传播算法进行局部社团划分，之后以一种“自底向上”的视角不断合并局部社团直至得到网络的一组划分。在执行合并策略时，引入了覆盖率和分布率两个指标分别代表当前社团拓扑结构与历史信息两个方面，使用进化聚类框架来平衡这两个指标，从而使得到的社团具有时序演化性。 本文在真实网络数据上对提出的动态网络社团检测方法进行了实验。实验结果表明本文提出的基于进化和局部优先的社团检测算法能够有效地检测到社团的重叠结构，同时能够检测到具有实际意义的小规模社团结构。而与其他局部优先的算法相比时，本文的算法得到的社团结构更好，同时在相邻时刻间具有更紧密的联系。