一种面向大型网络的快速随机化社区挖掘算法

寻找网络的社区结构对于理解真实网络的自组织机制、可视化大网络有重要的作用.然而,现有的社区挖掘算法由于性能较低,还难以处理大型网络,特别是有着百万顶点的网络.然而,百万规模的大网络却在越来越多的真实应用中大量涌现,这对于高效的有效社区识别算法提出新的需求.为此,一种新颖的随机算法被提出,能够在接近线性时间内,从大型网络上高效地挖掘质量较高的网络社区:新算法的核心思路是在每一随机步骤中对网络中的顶点进行基于深度优先顺序的编码,这样的编码有助于有效地识别社区之间的边.最后,通过针对模拟网络和真实网络的一系列实验验证了新算法的高效性和有效性.     

可探测社区稳定结构的局部社区发现算法

社交网络的动态变化使社区发现的精确度面临更高挑战。目前提出的大部分算法都是以寻求模块度最优解来发现社区,但往往会忽略所发现的社区结构是否稳定。根据力学平衡原理即当一个物体所受内部力和外部力平衡的条件下可达稳定状态,因此基于点的稳定性机制,判断节点来自社区内部连边数量与来自外部社区连边数量的最大值是否保持平衡,提出一种可探测稳定结构的局部社区发现算法。网络的稳定性大小与社区的结构有很大的关系,因此将网络的稳定性作为一种新的评价社区结构优良的标准。通过在真实网络和人工集成网络上进行实验对比发现提出的算法的社区结构稳定度比其他算法高,同时能发现精确度高的社区。     

基于Node2Vec的重叠社区发现算法

针对目前基于种子节点选择的社区发现算法在准确性和复杂度等方面存在的不足, 提出了一种基于Node2Vec的重叠社区发现算法. 首先, 使用Node2Vec算法学习到网络中每个节点的向量表示, 用以计算节点间的相似度, 其次, 利用节点影响力函数计算节点影响力并找出种子节点, 然后基于每个种子节点进行社区的扩展优化, 最终挖掘出高质量的重叠社区结构. 本文选取多个真实网络进行了对比实验, 结果表明, 本文所提出的算法能够在保证良好稳定性的前提下发现高质量的社区结构.     

一种新的基于标签传播的复杂网络重叠社区识别算法

针对现有基于标签传播的复杂网络重叠社区识别方法所存在的社区识别精度不稳定,以及随机性较强等缺陷,提出一种新的基于标签传播的复杂网络重叠社区识别算法NOCDLP(a novel algorithm for overlapping community detection based on label propagation).该算法首先搜索网络中若干以度较高节点为中心的完全子图,并以这些完全子图为起点进行标签传播;其次通过分析节点与社区连接强度以及社区接纳某节点后的社区内部连接紧密度情况给出节点归属社区强度函数,以此作为标签传播的依据提高社区的识别精度;再次,在标签传播过程中,NOCDLP算法设置标签传播控制标记,以避免标签传播算法随机性较强的缺陷;最后,在已形成的社区中通过整理重叠节点获得更准确的重叠社区结构.算法在人工网络与真实网络中完成测试,同时与多个经典算法进行对比分析,实验结果验证了NOCDLP算法是有效的、可行的.     

基于动态距离的模糊社区识别算法

社区识别技术是公共安全领域潜在危害行为预警预测和已发生危害行为追踪溯源的基础，针对传统社区识别算法将社区视作单一集合而无法描述社区主次成员的问题，提出一种基于动态距离的模糊社区识别算法。该算法将传统的单一社区结构划分为核心区域和边际区域，以边际区域来描述社区的模糊区间。该算法首先将网络设想为动态演变模型，网络中的任意节点均会与其他节点产生互动，互动将改变各节点间距离，距离也反过来影响互动。在阈值的界定下，受到多个社区吸引的节点被划分到边际区域，最终距离分布趋于稳定，各个社区结构得以显现。通过对比实验验证了CDFDD算法在社区识别上的有效性。     

动态社会网络中的社区演变挖掘

在静态网络图中对社会网络进行分析,可能忽略网络的时间特性,从而错过捕捉动态网络演变模式的机会.为检测社区的演变及社区结构随时间的变化,分析动态社区,为每一个社区定义一系列重大事件,给出社区匹配算法,并对元社区的概念进行定义.实验结果证明,采用该算法建模和检测社会网络中的社区演变,可有效识别和追踪随时间变化的相似社区.     

基于三角形的重叠社团发现算法

社区结构是复杂网络的重要属性之一, 有效挖掘出复杂网络中隐藏的社区结构具有重要的理论研究意义和广泛的应用前景。真实网络在一定程度上都表现为重叠的社区结构, 针对这一问题, 提出了一种基于三角形的重叠社区发现算法。通过判断两个节点与其共享邻居节点能否构成一个三角形来判断, 若能构成三角形, 则这两个节点属于同一社区。在计算机生成网络与真实网络上进行了实验, 都正确地识别出了社区结构以及重叠节点, 表明了此算法对于发现重叠社区结构的有效性和可行性。     

基于种子节点选择的重叠社区发现算法*

识别网络社区对于了解社会网络的结构和功能具有重要意义。由于网络中某些节点可能属于多个社区,因此重叠社区的研究已经吸引了人们越来越多的关注。本文针对目前从局部社区扩展成全局社区时有关算法的种子节点选择不合理的情形,提出了一种基于种子节点选择的重叠社区发现算法。本算法首先根据影响力函数找出局部影响力最大的节点,由这些节点构成的种子集合较好的分布在整个网络中,然后以这些种子点构造初始社区,根据设定的吸引度函数选择性添加节点来进行社区扩展。实验结果表明,该算法在真实网络上进行测试时能够有效的挖掘网络中的重叠社区。     

基于引力因子的加权网络重叠社区识别算法

通过挖掘大数据来识别复杂社会网络上的社区,有利于对经济、政治、人口等方面的重要问题进行定量研究,社区的识别算法已经成为当前研究的热点问题。重点研究了重叠社区识别问题,提出了基于引力因子的加权复杂网络的重叠社区识别算法GWCR。该算法首先选取万有引力因子大的节点为中心节点,将节点与中心节点之间的引力因子作为衡量标准,并将节点归入社区引力因子大于某一阈值的社区,最后通过识别重叠节点来识别重叠社区。在3个真实网络数据集上的实验结果表明,与传统的重叠社区识别算法相比,GWCR算法划分的社区的模块度较高。     

一种基于局部扩展优化的重叠社区发现算法

挖掘复杂网络的重叠社区结构对研究复杂系统具有重要的理论和实践意义。提出一种基于局部扩展优化的重叠社区识别算法。 首先基于网络节点的聚集系数筛选种子节点,选取不相关的、局部聚集系数大的种子作为初始社区;然后采用贪心策略扩展初始社区,得到局部连接紧密的自然社区;最后检测并合并相似的社区,获得高覆盖率的重叠社区结构。在人工生成网络和真实网络数据集上的实验结果表明,与现有的基于局部扩展的代表性重叠社区发现算法相比,所提算法能在稀疏程度不同的网络上发现更高质量的重叠社区。     

基于联合矩阵分解的动态异质网络社区发现方法

动态网络的社区发现是目前复杂网络分析领域的重要研究内容,然而现有动态网络社区发现方法主要针对同质网络,当网络包含多种异质信息时,现有方法不再适用。针对这个问题,本文提出了一个基于联合矩阵分解的动态异质网络社区发现方法,首先计算动态异质网路中各个快照图的拓扑相似度矩阵和多关系相似度矩阵,其次利用时序联合非负矩阵分解方法,约束各个时刻快照图的社区划分,最后在真实网络数据集上的实验结果表明,该算法可以有效检测出动态异质网络中潜在的社区结构。     

基于权重信息挖掘社会网络中的隐含社团

社团结构是一种普遍存在于各类真实网络中的结构特性.挖掘网络的社团结构对于理解网络的功能与行为有着重要作用.然而,现有的各种社团挖掘算法仅仅基于网络拓扑结构信息,而忽视了蕴涵于真实社会网络边权信息中丰富的语义信息.目前普遍使用的基于模块性最大化的社团挖掘算法倾向于将小社团合并,这使得语义上丰富的小社团容易湮灭于基于拓扑结构信息所挖掘出的大社团中.而挖掘出这些隐含于大社团中的有着丰富语义内涵的小社团对于加深社会网络语义层面的理解有着重要作用.为此,提出一个接近线性复杂度的有权网络社团挖掘算法.通过充分利用权重信息,算法可以将社会网络划分为富含语义信息的粒度较细且相对较小的隐含社团.通过对基于DBLP作者合作网络的实证分析,证实了新算法的有效性和高效性.     

面向大规模学术社交网络的社区发现模型

针对基于标签传播的复杂网络重叠社区发现算法中预先输入参数在真实网络中的局限性以及标签冗余等问题,提出一种基于标签传播的面向大规模学术社交网络的社区发现模型。该模型通过寻找网络中互不相交的最大极大团(UMC)并对每个UMC中的节点赋予唯一标签来减少冗余标签,提高社区发现的效率以及稳定性。标签更新时以UMC作为核心单位采用亲密度的方式由中心向四周更新UMC邻接节点的标签及权重,以权重最大值的方式更新网络中非UMC邻接节点的权重。后期处理阶段采用自适应阈值方式去除节点标签中的噪声,有效克服了预先输入重叠社区个数在真实网络中的局限性。通过在学术社交网络平台——学者网数据集上的实验表明,该模型能够将具有一定共性的节点划分到同一个社区中,并为学术社交网络平台进一步的好友推荐、论文分享等精确的个性化服务提供了支持。     

网络社区发现的多目标分解粒子群优化算法

通过分析社会网络中社区发现问题的优化目标,构造了社区发现的多目标优化模型,提出一种网络社区发现的多目标分解粒子群优化算法。该算法采用切比雪夫法将多目标优化问题分解为多个单目标优化子问题,使用粒子群优化(PSO)算法对社区结构进行挖掘,并引入了一种新颖的基于局部搜索的变异策略以提高算法的搜索效率和收敛速度,该算法克服了单目标优化算法存在的解单一以及难以发现社区层次结构的缺陷。人工网络及真实网络上的实验结果表明,该算法能够快速准确地挖掘网络社区并揭示社区的层次结构。     

一种面向语义重叠社区发现的Link-Block算法

语义社会网络是一种由信息节点及社会关系构成的新型复杂网络,传统语义社会网络分析算法在进行社区挖掘时需要预先设定社区个数,且无法发现重叠社区.针对这一问题,提出一种面向语义社区发现的link-block算法.该算法首先以LDA模型为语义信息模型,创新性地建立了以link为核心的block区域LBT(link-block-topic)取样模型;其次,根据link-block语义分析结果,建立可度量link-block区域的语义链接权重方法,实现了语义信息的可度量化;最后,根据语义链接权重建立了以link-block为单位的聚类算法以及可评价语义社区的SQ模型,并通过实验分析,验证了该算法及SQ模型的有效性及可行性.     

动态社区发现方法研究综述

随着社交媒体多样性的增加,实时分析社交网络的需求不断增大,动态社区发现的研究受到了广泛的关注。已有的社区发现综述多是侧重静态社区发现,以及相关方法的探讨,无法进行网络演化分析,此外社区的实体数据往往具有交叉更替性和时序性,因此对动态社区发现的研究现状进行分析和综述。首先,基于复杂网络的研究背景,提出了通用的动态社区发现研究框架;接着,形式化表示动态社区发现的相关定义,并从网络层面和节点层面对动态社区演化进行详细分析;然后,根据架构和技术的不同,对动态社区发现方法进行归纳分类,并结合常用数据集和评价指标对经典静态社区发现算法进行定性和定量分析;最后,介绍了社区发现的典型应用场景,探讨了当前动态社区发现研究面临的主要挑战,针对性地提出了相关解决方案,为动态社区发现研究领域勾画出较为清晰和全面的研究方向。     

基于动态有噪网络的增量社团发现算法

在动态社会网络中,诸如垃圾邮件之类的噪声会影响网络的稳定性,导致其社团结构难以被准确发现。针对该问题,提出一种采用增量结构的社团发现算法。利用相对熵处理噪声,通过改进的增量算法发现社团结构。实验结果表明,该算法针对不同动态社会网络的发现性能均优于传统动态社团发现算法,其模块度可达到0.8左右,互信息值变化也较平稳,可有效避免噪声对算法性能的影响。     

基于空间尺度粗粒化的异常检测方法

目前,大部分基于链路预测对社会网络进行异常检测的研究中,缺乏对异常节点演化影响的分析,且受社会网络规模以及复杂度的限制,检测效率普遍不高。针对上述问题,提出了一种基于空间尺度粗粒化和异常节点加权机制的异常检测方法。首先利用凝聚型社区发现算法Louvain对社会网络进行粗粒化得到简化网络,然后在简化网络的演化过程中识别有异常演化行为的节点,并将其异常演化过程量化,引入异常节点加权机制到链路预测方法中进行异常检测。在真实社会网络数据集VAST、Email-EU（dept1和dept2）以及Enron上,与基于LinkEvent的不同调整策略算法和NESO_ED方法进行对比。结果表明,该方法可以兼顾异常检测的稳定性和敏感性,能够更合理地描述网络演化过程,得到更好的异常检测效果。     

基于联系度的主题关注网络社区发现方法研究

目前,以兴趣或主题分享等为目的的兴趣型社交网络则引领着社交网络改革的浪潮。融合社交关系和兴趣爱好关系构建一个新型社交网络模型--主题关注模型。在此模型基础上,采用集对联系度刻画顶点间相似性度量指标,该度量方法可以更好地刻画网络结构特征,提高传统局部相似性度量指标对某些顶点间相似性值的计算精度,降低全局相似性度量指标的计算复杂度。综合考虑主题影响和社交关系,将集对联系度与凝聚型聚类算法相结合,提出一种新的主题社区发现方法。在Karate网络和豆瓣数据集上进行主题社区发现,实验结果表明,考虑主题影响的划分具有更好的社区结构。     

图重构下大规模网络的社团检测算法

对大型复杂网络进行高质量的社团检测通常依赖图的拓扑结构来划分节点集,然而现实世界的网络通常带有嘈杂且与集群无关的链接,这些链接可能会导致模型将来自不同集群的节点划分在一起。为此,提出了基于图重构的社团检测算法（graph reconstruction based community detection,GRCD）,该方法能够处理大规模复杂网络的社团检测。首先,删除社团之间的相互连接的边来重新构建原始图的社团结构;然后,将网络视为一个社交系统,旨在以更直观的方式揭示社团;提出了一种高效的社团检测策略,即基于话语权的社团组织生成策略;最后,在不同规模数据集上进行实验。实验结果表明,GRCD算法不仅能够处理大规模网络,而且在保持较高稳定性的同时,其社团划分的质量对比现有的几种基准算法都有很强的竞争力。