基于加权边相似度的重叠社区发现算法

社区发现是复杂网络研究的基础,其目的是发现网络的真实结构,对于分析复杂网络的拓扑结构、理解其功能和寻找其潜在的性质具有重要的意义.Palla,Yong和James等人分别提出了CPM、LINK算法,此类算法基于网络拓扑结构或边密度发现复杂网络中的社区,性能较好,但不足是计算出的社区存在过度重叠问题.如何设计新算法,避免社区发现的过度重叠问题,是一个亟待解决的重要问题.本文基于加权边相似度,提出了一种社区发现算法LINKw,可以高效发现社区结构,与其他算法相比,本算法能更好地解决社区过度重叠问题.     

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

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

基于动量粒子群优化的社会网络分析

针对社会网络分析中的社区发现问题,在原有的粒子群优化算法的基础上,提出了一种基于动量粒子群优化算法,并且将此算法应用于社会网络分析中的社区发现研究中,提出了一种自适应社区发现方法.利用Newman提出的模块度作为适应度函数,在优化过程中自动获取社区数目,在Karate网络上的实验结果表明,所提出的算法能够有效地进行社区...     

一种稳定的标签传播社区发现算法

网络中的社区发现是当前的一个研究热点。在众多社区发现算法中,标签传播算法因简单快速而被广泛应用。但标签传播算法也存在结果稳定性较差的问题。通过提取非重叠完全子图来避免社区重叠,提取最小极大团来避免巨型社区的出现,基于此,对标签传播算法的初始化过程进行改进,提出了一种稳定的标签传播社区发现算法,即非重叠最小极大团提取算法。在真实网络中的实验结果表明该算法可以大幅提高结果的稳定性。     

基于复杂网络的社区发现算法

针对现有社区发现算法准确度较低的问题,该文提出了1种基于中心节点的社区发现算法。通过各节点度数及节点间相似度寻找社区的中心节点,然后利用局部模块度对各个社区进行优化,并根据节点吸引力将孤立节点和重叠社区节点尽量归入其社区,从而获得整个网络的社区划分。将该文算法分别与3种局部社区发现算法、4种全局社区发现算法相比较,实验结果表明,该算法可以提高社区发现的准确度,具有可行性。     

有向网络兴趣社区的快速挖掘算法及其在僵尸粉检测中的应用

针对传统的无向网络社区挖掘方法无法实现大规模有向网络中社区有效发现的问题,提出了一种新的有向图社区及其兴趣特征快速挖掘算法。采用贪心算法求解社区划分模块性最大化的优化问题,较好地平衡了有向图社区挖掘中准确性与有效性之间的矛盾,实现对大规模微博类有向网络社区结构的有效识别;基于发现的社区,采用tf-idf算法进一步挖掘社区用户的兴趣爱好,实现了对微博网络中兴趣小组的精确挖掘。基于新浪微博的实验结果表明:所提算法不仅可以快速有效地挖掘有向网络中的社区结构及其用户的兴趣特征,还能够准确地检测出微博网络中的僵尸粉社区,研究结果对微博系统的净化、谣言控制、网络广告的精准投放等研究具有重要的参考价值。     

基于矩阵运算加速的改进社区发现遗传算法

社区发现算法是复杂网络领域的重要研究工具,然而传统的社区发现遗传算法在大规模网络下存在初始种群质量不佳和运行效率低下的问题。为此,本文提出一种基于矩阵运算加速的改进社区发现遗传算法。针对初始种群质量不佳的问题,提出一种新的初始化算子,采用闭包系数有偏向地选择节点构建高质量初始社区;针对计算效率低下的问题,基于矩阵运算重构了传统社区发现遗传算法各个算子,使得算法能使用GPU加速,提升计算效率。仿真实验结果表明,在不同规模的真实网络和LFR合成网络下,本文算法既能保证良好的划分精度,又展现出较其他主流同类算法更高的计算效率。     

基于k-shell的社区发现算法研究

集对分析作为将事物视为确定性和不确性相结合的系统的数学理论,适合用于关系复杂的社会网络研究。目前,已有研究将集对分析理论与社会网络分析相结合,提出了加权聚集系数联系度的节点间相似性度量方法以及相应的社区发现方法 VSFCM算法。针对VSFCM算法在独立社区初步聚合阶段存在的节点提早合并问题,引入边聚集系数与相似度共同作为社区合并标准,提高独立社区阶段社区合并的准确性。为了改善VSFCM算法的时间效率,结合k-shell方法,为了实现社区结构更为合理以及社区划分更为贴近现实划分的社区发现算法,分别提出以kshell值优先的层次聚类算法KPCM和KPCMV。     

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

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

一种基于介数和时效性的动态社区发现算法

为了发现动态变化的社区结构,在分析了动态社区划分算法的研究现状基础上,提出一种基于时效性和介数的动态社区发现算法,对历史信息的时效性进行了计算,建立了综合有权网络,基于局部边介数进行社区划分,发现了稳定社区结构。实验表明了算法的有效性。     

基于标签传播的重叠社区发现算法

重叠社区发现是复杂网络研究的重要课题.提出一种基于标签传播的重叠社区发现算法.首先利用标签传播算法得到初始无重叠社区划分结果,之后通过设计新的重叠节点识别算法确定重叠节点,最后再根据重叠节点的识别结果对社区进行合并从而得到最终的重叠社区划分结果.该算法克服了已有算法重叠节点占比过大的弊端.为验证算法的有效性,在LFR人工数据集、3个标准公开测试集以及真实的大豆基因共表达网络上进行实验,并与已有算法进行对比.实验结果表明,该算法性能明显优于对比算法,极大地改善了重叠节点比重过大问题.     

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

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

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

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

一种基于加权共同邻居相似度的局部社区发现算法

传统的社区发现算法能够找出网络中所有的社区,其时间复杂度取决于网络的规模.挖掘大网络中的全局社区结构因为时间复杂度高而难以实现,局部社区发现作为一种不需要知道网络的整体结构,从给定的节点逐步向外扩展,寻找该节点所在社区的方法,在大网络时代具有重要的应用意义.目前这方面的研究已经获得广泛关注,并提出了很多局部社区发现算法.针对已有局部社区发现算法需要人工设置参数、准确率低的问题,提出一种新的局部社区发现算法.首先,提出一种加权邻居节点的共同邻居相似度指标,用于计算网络中两个节点间的相似度;然后,基于该相似度指标,给出一种新的局部社区质量度量指标,在保证社区度量指标不下降的前提下,不断选择与当前局部社区嵌入度最大的节点加入到局部社区,逐步找出给定节点所在的社区;最后,在真实网络和仿真网络数据集上进行了实验.实验结果表明,该算法能有效地挖掘出给定节点所在的局部社区,相比具有代表性的Clauset,LWP,GMAC等局部社区发现算法有更高的准确率.     

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

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

内容相似度微博社区发现方法研究

针对现有微博社区发现的准确性与效用性问题,提出了一种高效的基于用户内容相似度的微博社区发现算法。首先对微博用户兴趣模型进行分析,进而挖掘微博意见领袖,通过AP算法对意见领袖进行兴趣聚类,以聚类结果为社区中心结合模块度优化算法完成微博社区发现。经实验验证了该方法可以更好地发现微博社区结构。     

复杂网络中的社区发现--理论与应用

复杂网络是对于复杂系统的高度抽象,其中许多性质如小世界性质、无标度性质以及聚集性质等等已经得到了充分的研究。大量文献表明,复杂网络呈现出的社区结构(Communitystructure)特性,以及如何在大型网络中高效地发现社区(Communityfinding)问题是近年来复杂网络的研究热点。本文较为全面地综述了关于社区发现方面的概念、理论、算法及应用等,期望对于社区发现问题的进一步研究及若干基本问题的早日解决起到一定作用。     

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

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

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

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

基于粒子群优化与模糊聚类的社区发现算法

针对现有基于改进的K-means模糊聚类的社区发现算法(k-means algorithm for community structures detection based on fuzzy clustering,NKFCM)执行效率较差的问题,将粒子群算法与模糊聚类算法相结合提出了基于粒子群优化与模糊聚类的社区发现算法(community detection algorithm based on particle swarm optimization and fuzzy clustering,PFCM).该算法首先进行迭代运算,找出初始聚类核心,利用以云模型为运行条件的粒子群优化算法确定最优聚类核心与最佳社区个数,最后利用模糊聚类算法(fuzzy c-means algorithm,FCM)进行具体的社区划分.理论解析与测试结果表明:该算法发现网络社区的准确性较高,且与NKFCM算法相比,PFCM在处理网络数据时执行效率获得了极大地提升.