基于结构和适应度的社区发现

复杂社会网络无处不在,对复杂社会网络进行社区发现越来越被人们重视.基于局部结构的社区发现可以在不用了解全局的情况下对某些节点进行划分;社会网络的社区适应度特性可以找出不同适应度下的社区结构.基于局部结构以及社区适应度的网络属性,提出一种新的社区发现算法.通过实验比较,算法能较好、较快的发现社区结构,在人工网络以及真实社会网络均取得较之已有方法更好的效果.     

异质网络社区发现方法研究综述

社区结构是复杂网络研究中的重要领域,也是复杂网络的重要特征之一,发现网络中的社区结构在理解网络功能方面起着重要作用。通过对国内外异质网络社区发现文献进行深入研究,较为全面地对现有异质网络社区发现算法进行了归纳总结。首先,通过对国内外异质网络社区发现文献进行归纳,给出异质网络社区发现的基本概述,明确异质网络社区发现领域相关问题的基本定义。其次,介绍了异质网络社区发现算法及主要评价指标,利用不同网络结构以及算法对现有方法进行分类概述。最后,对异质网络社区发现算法的发展趋势进行了总结与展望,提出未来可以将研究重点集中在以下几个方面:1)探索基于异质网络的社区发现评价标准,以推动该领域的快速发展;2)设计更加通用的算法模型,解决由先验知识引起的未知社区数量问题;3)开展更多关于动态网络的研究。     

基于大规模复杂网络社区发现的科研合著网络分析

针对基于极大团的社区发现算法,设计了适应大规模数据的MapReduce并行计算框架,提出了基于大规模复杂网络社区发现的科研合著网络分析算法,并用于对我国管理科学与工程领域2012年科研合著网络进行社区结构划分。实验结果表明,基于MapReduce的并行社区发现算法可在保证正确性的同时有效提高计算效率,适用于大规模复杂网络的社区发现。针对我国管理科学与工程领域2012年科研合著网络的社区划分结果展现了我国管理科学与工程领域科研合作的特点和问题。     

在线社会网络的动态社区发现及其演化

分析了目前动态社区发现及其演化所存在的问题,提出了一种新的动态社区演化方法.该方法利用静态社区挖掘算法提取不同时间快照的每个社区,然后计算出相邻快照的社区之间的演化影响力,进一步分析连续快照中社区结构的发展演化过程.在新浪微博、网络测量Gnutella等大规模实验数据集上的验证,证明了该方法的有效性.此外,实验中还分析了社会网络中节点的出现和消失的频繁程度会影响社区稳定性以及社区结构的演化.      

动态网络中基于局部介数的重叠社区发现算法

针对现有静态网络社区发现算法的失真和动态网络社区发现算法时间复杂度较高的问题,本文提出了一种动态网络中的重叠社区发现算法。在网络中,边介数最大的边或分割介数最大的节点是网络中的关键边或点,即联系最不紧密的边或节点,因此,该算法利用去除最大边介数的边和分裂最大分割介数的节点的方法,并将网络社区的动态变化和重叠性考虑在内进行社区发现。最后利用模块度对社区发现进行控制,使发现的社区结构更加合理。     

基于联合引力度扩展的加权网络重叠社区划分算法

基于引力度扩展的重叠社区发现算法(GDE),主要用于挖掘无权社交网络的重叠社区结构.真实社区更多是具有加权属性的,本文根据 GDE 算法的种子策略思想,并依据加权网络的特征,以网络节点的度与强度来综合确定重叠社区的中心节点,提出基于联合引力度扩展的加权网络重叠社区划分算法(UGDE).算法的实验检测结果表明：该算法对划分加权网络中的重叠社区具有可行性与有效性.     

基于信息传递和峰值聚类的自适应社区发现算法

信息传递是网络具有的基本特征,基于此提出了一种基于信息传递和峰值聚类的自适应社区发现算法。首先,定义了节点与邻居之间的信任度函数,每个节点基于信任度独立的向网络中扩散信息量。扩散结束后,节点总信息量即为峰值聚类中的密度;网络中节点之间的距离通过所含节点信息量的倒数替代。然后,提出一种自动选取核心节点方法并为核心节点分配不同社区,把剩余节点分配到与它距离最短的核心节点所在社区,完成社区划分。本算法的优点在于无需额外参数并且能够发现社区内部结构。实验结果表明本算法发现的社区结构更加接近网络真实社区结构。     

采用模糊层次聚类的社会网络重叠社区检测算法

为了能够发现社会网络中的重叠社区以及解决重叠社区之间关系的模糊性和层次性,提出了一种基于模糊层次聚类的重叠社区检测算法(CDHC)。算法中引入了距离加权因子来计算社区间的相似度,通过模糊层次聚类来合并相似度高的社区;针对合并生成的原始社区计算社区中节点的隶属度,再将隶属度小于阈值的节点从社区中移除,从而形成最终的网络重叠社区结构。该算法不仅可以发现重叠的社区结构,还可以处理孤立节点。在Lancichinetti基准网络和真实网络上将CDHC算法与具有代表性的重叠社区发现算法CMP和LFM进行了比较,结果表明:影响社区检测精度的主要因素是社区间的混合程度,而网络规模和网络中社区的规模的影响并不显著;CDHC算法在小社区网络上的社区检测精度优于LFM,在大社区网络上的社区检测精度优于CMP。CDHC算法在保持社区检测质量的同时,还具有较好的稳定性,是一种有效的社会网络重叠社区检测算法。     

一种基于网络嵌入的社区发现方法

社区发现是社会网络分析的重要任务,有助于理解中观尺度的网络结构.现有的诸多社区发现方法仅考虑网络的拓扑信息,忽略了网络中每个节点所包含的属性信息.为此,本研究首先基于社会网络的拓扑结构信息与节点属性信息分别构建初始特征矩阵;然后基于网络嵌入模型,融合初始特征矩阵的主成分信息,构建共识嵌入矩阵;最后,给出社会网络中"领袖节点"的泛化定义形式,并提出一种改进的图聚类算法(LIK-means)挖掘社会网络中潜在的社区结构.实验表明,LIKmeans较其他经典算法有较好的可扩展性,同时在真实社会网络中的社区识别精度更高.     

局部引力度扩展的重叠社区发现算法

社交网络拥有社区结构,而网络中的一些节点又被两个或更多社区共享,这就使网络呈现出重叠社区结构.在前面对重叠社区划分算法的研究中提出了基于引力度扩展的重叠社区发现算法(GDE),以引力度最大的节点为种子来扩展与发现重叠社区.这里,提出基于h-域的局部引力度扩展的改进算法(LGDE).改进算法的实验测试结果表明该算法的执行效率获得了极大的提高,并且是可行的.     

基于标记注意力机制的社区发现算法

针对网络的聚类进行研究,提出了一种基于标记注意力机制的社区发现算法,网络特征通过标记节点频率及反示例节点频率联合度量,为使网络特征的度量更加关注于示例节点的细节信息,引入注意力机制来处理网络特征。社区划分由复杂网络预处理、网络节点的策略、社区博弈归并三个部分组成,其中网络节点的策略由无贡献节点归并、节点到社区的判断以及节点逻辑标记和的判断三个步骤组成。实验借助于真实网络进行验证,在归一化互信息、模块度、社区划分数量及运行时间四个方面,基于标记注意力机制的社区发现算法都优于其它社区发现算法。在实际生活中应用此算法,能够更加直观地显示网络内部之间存在的联系。     

融合节点影响力与多标签传播的重叠社区发现算法

重叠社区发现是复杂网络分析研究的重要目标之一。针对传统多标签传播算法存在的社区发现结果具有随机性、不稳定性,以及忽视节点影响力对标签传播的影响等问题,提出一种基于节点影响力与多标签传播的能够生成稳定社区的重叠社区发现算法。算法在节点影响力的计算、排序和核心节点识别基础上,通过邻居节点初始标签的再处理和基于平衡系数的节点标签异步更新策略,实现复杂网络重叠社区的有效识别。在真实数据集和人工数据集上的实验综合表明,算法性能优于各对比算法,适用于大规模复杂网络。     

基于H指数的改进标签传播算法研究

发现复杂网络中的结构和特征是社区发现的一个重要任务.标签传播算法(LPA)因具有接近线性的时间复杂度,常用于快速处理大规模的社区网络.针对该算法在节点的更新顺序和标签选择策略上存在很大的随机性,严重破坏了算法的稳定性和社区划分结果的准确性.提出了一种基于节点H指数的标签传播算法,即利用节点的综合影响力改进标签传播算法的节点更新顺序和标签选择策略.实验研究表明,改进算法有效地降低了算法的随机性,提高了社区划分的稳定性和准确性.     

基于密度峰值聚类标签传播的社区发现方法

社区发现的目标是发现复杂网络的结构、行为和组织形式。标签传播算法是一种快速有效的社区发现算法,然而在初始的标签传播算法中,节点的结构信息和特征信息没有得到充分利用,且存在标签传播过程不稳定的问题。针对上述问题,文章提出了一种基于改进的密度峰值聚类算法和标签传播算法的有向加权复杂网络社区发现算法(DPC-LPA)。该算法首先根据节点的结构和特征对其进行加权,充分利用了结构信息和特征信息;然后,采用改进的密度峰值聚类算法来寻找网络的社区中心,并据此构建初始社区,提高了社区划分的质量;其次,基于节点相似度和节点权重,合理确定标签传播的更新顺序,并通过衡量节点间标签传播的强度来完成标签传播,解决了标签传播算法不稳定的问题。最后,在CiteSeer、Cora、WebKB和SCHOLAT真实数据集上,将DPC-LPA算法与DCN、WCF-LPA、CLPE算法进行对比实验。实验结果证明了DPC-LPA算法的可行性和有效性：从模块度来看,利用DPC-LPA算法划分的社区具有更加显著的社区结构;从调整兰德系数来看,DPC-LPA算法的社区划分质量更稳定;从运行时间来看,DPC-LPA算法具有较高的效率。     

基于随机游走的进化计算社区发现

网络结构关系错综复杂,在复杂网络上寻找最优的社区结构是一个NP-Hard问题,进化计算被认为是解决这类问题的有效方案,人们尝试利用群智能方法来搜索最优的社区结构。目前,针对包含节点属性的属性网络,基于进化计算的社区发现方法还面临若干挑战：（1）基因编码策略都直接或间接采用邻位编码,致使算法的搜索空间受限于拓扑结构,属性信息利用程度低,导致算法精度不足;（2）缺少对社区边缘度较小的节点的考虑,造成社区边界识别较低。针对上述问题,提出了一种基于随机游走的进化计算社区发现算法。首先,设计了一种基于拓扑及属性信息随机游走的社区初始化策略,以准确识别社区边界,提高社区发现的精度。其次,设计了综合考虑拓扑和属性的节点嵌入向量更新策略,使节点的属性信息能够在进化过程中被有效利用,以提高社区划分的质量。通过在真实和人工数据集上实验,验证了提出的新算法能够比现有方法得到更好的社区划分。     

基于重要结点的社区发现算法

复杂网络中内部的社区结构是复杂网络结构特征和属性特征的具体体现。首先依据模块度最大化理论计算网络的模块度矩阵的最大k特征向量矩阵;然后提出聚类中心方法,并用于求出k个社团的重要结点作为k聚类中心,利用欧几里得距离计算每一个结点到k个聚类中心的距离,将结点分配到距离聚类中心最近的社区中;最后对网络应用k-means方法进行迭代计算,得到k个社区的划分。分别在Karate Club Network和American College Football数据集上对算法进行了实验验证,实验结果表明该算法可以有效发现潜在社区,其纯度与模块度比已有的社区发现算法都有一定的提高,并且迭代次数较少,效率较高。     

基于社区森林模型的分布式重叠社区发现算法

重叠社区发现是复杂网络挖掘中的重要基础工作,可以应用于社交网络、通讯网络、蛋白质相互作用网络、代谢路径网络、交通网络等多种网络的数据分析,从而服务智慧交通、传染病防治、舆情分析、新药研制和人力资源管理等领域.传统的单机运算架构已经难以满足各类大规模复杂网络的分析和计算要求.人工智能领域的研究人员提出将社区发现应用到网络...     

一种可变分辨率的社团发现算法

介绍了复杂网络及社团结构的相关概念,给出节点的综合特征值和增益函数的定义,然后提出一种新的社团发现算法(CNCD).综合特征值与节点的度数及其聚类系数有关,用于发现社团中的核心节点;增益函数决定何时获得社团结构的最佳划分.作者用C++语言实现算法,并使用经典数据集对算法进行验证,实验结果表明此算法不仅能够得到正确的社团结构,而且通过动态调整算法中的参数值,能够得到比传统算法更加详细的社团划分结果,获得网络的细节信息.     

基于先验知识与模块性的网络社区结构探测算法

在分析模块性指标和Newman有关网络社区结构探测算法的基础上，提出了一种基于先验知识与模块性的社区结构探测算法．利用节点度等社会网络结构先验知识，获得一个社区结构的基本划分，然后进行社区的合并，以此获得一个清晰的社区结构．经计算机模拟网络、Ucinet软件网络和中国农民工社会网络的社区结构探测，结果表明所提算法比Newman的迭代次数减少近50％，并且可以获得更好的模块性指标．