基于KL-Ball的社区挖掘方法

针对邻接矩阵的稀疏特性,采用KL散度来计算网络节点间的距离,提出了一种基于KL-Ball的社区挖掘方法.该方法中,一个KL-Ball代表一个社区,它从质心、半径、互信息及密度4个方面来描述社区,其中质心决定了社区在网络中的位置,半径刻画了社区所能覆盖的范围,互信息度量了社区中包含节点的一致性,密度反映了社区包含节点的数量.给定一个半径,期望从复杂网络中寻找具有低信息、高密度的社区,低信息使得社区包含的节点具有较强的一致性,高密度使得一个社区具有较强的凝聚性.为此,定义了一个基于KL-Ball的社区挖掘目标函数,给出它的优化算法,并从理论上证明了该算法的收敛性.依据社区半径的大小及质心的位置,该算法可应用于非重叠社区挖掘以及重叠社区挖掘.实验结果表明,基于KL-Ball的社区挖掘方法可有效地挖掘网络中蕴含的社区结构,包括非重叠的社区及重叠的社区.     

结合拓扑势与信任度调整的重叠社区发现算法

现实世界中的复杂系统可建模为复杂网络,探究复杂网络中的社区发现算法对于分析复杂网络的拓扑结构和层次结构具有重要作用。早期研究通常将网络中的节点局限在一个社区中,但随着研究的深入发现社区结构呈现重叠特性。针对现有重叠社区发现算法存在划分社区结构不稳定、忽略节点交互和属性等问题,提出一种基于网络拓扑势与信任度调整的重叠社区发现算法。融合节点的属性和结构特征计算节点的拓扑势,依据节点的拓扑势选取核心节点。从核心节点出发构建初始社区群,计算各个社区间的调整信任度,实现社区的合并与再调整,从而识别重叠社区。在多个人工模拟网络和真实网络数据集上的实验结果表明,与基于贪婪派系扩张、种子扩张等的重叠社区发现算法相比,该算法将扩展模块度最高提升至0.719,能有效识别社区结构及重叠节点,提升重叠社区检测性能。     

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

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

一种基于粗糙集和密度峰值的重叠社区发现方法

随着互联网和社会的发展,各个领域每天都会产生大量相互关联、彼此依赖的数据,这些数据根据不同的主题形成了各种复杂网络。挖掘社区结构是复杂网络领域中的一项重要研究内容,因为其在推荐系统、行为预测和信息传播等方面具有极其重要的意义。社区结构中的重叠社区结构在生活中普遍存在,更具有实际研究意义。为有效发现复杂网络中的重叠社区,文中引入了粗糙集理论对社区进行分析,识别出重叠节点,进而提出了一种基于粗糙集和密度峰值的重叠社区发现方法OCDRD(Overlapping Community Detection Algorithm Based on Rough Sets and Density Peaks)。该方法在传统网络节点局部相似性度量的基础上,结合灰色关联分析方法求出网络节点间的全局相似性,进而将其转化为节点间距离。将密度峰值聚类算法的思想应用于该算法中,以根据网络结构自动选取社区中心节点。依据网络中节点的距离比例关系,定义了社区的上近似、下近似以及边界域。最后,不断调整距离比率阈值并进行划分迭代,在每次迭代中针对社区的边界域进行计算,从而获得最佳重叠社区划分结构。在LFR基准人工网络数据集和真实网络数据集上,基于标准互信息(Normalized Mutual Information,NMI)和具有重叠性模块度EQ这两个评价指标,将OCDRD方法与近几年效果较好的其他社区发现算法进行测试比较。实验结果显示,OCDRD方法在社区划分结构方面整体优于其他社区发现算法,表明了该算法的可行性和有效性。     

基于边图的线性流重叠社区发现算法

重叠网络的社区发现是复杂网络研究中的重要问题。为了提高网络中重叠社区发现的时间效率，提出一种基于边图的线性流重叠社区发现算法LBSA。算法首先对于边图网络中的边进行随机的依次处理，完成节点的初步社区划分，再将其中重叠小社区合并到相似度最大的其他大社区中得到最终的社区。通过以上步骤，算法能够以接近线性的时间复杂度得到网络的重叠结构。从最终的实验结果来看，与其他算法相比，该算法能够在更短的时间有质量地发现网络中的重叠社区。     

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

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

基于时间加权的重叠社区检测算法研究

随着网络结构的不断扩大和日益复杂, 重叠社区发现技术对挖掘复杂网络深层潜在结构具有重要意义. 本文提出一种基于时间加权的重叠社区检测算法. 该方法考虑了用户兴趣的时间因素, 构建带有时间加权链接的用户-用户图. 接着, 基于网络节点的影响力计算用户全局相似度, 在此基础上通过计算节点的中心度作为度量节点对社区结构影响力的重要性指标, 从而提出一种社区中心点的选取方法. 最后, 通过效用函数的迭代计算实现重叠社区检测. 利用人工网络和真实网络对提出的算法进行验证, 实验结果表明: 相对于传统的社区发现方法, 该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.     

基于线图与PSO的网络重叠社区发现

从优化模块度的角度出发,引入线图理论,给出线图的硬划分与原 图的有重叠划分相对应的理论证明, 提出了一种基于线图与粒子群优化技术的网络重叠社区发现算法(Communities discovery based on line graph and particle swarm optimization, LGPSO), 该方法通过粒子群优化 (Particle swarm optimization, PSO)算法寻找网络对应线图的最优划分来发现网络重叠社区, 实验结果显示,该方法能够在无先验信息的条件下快速有效地揭示网络的重叠社区结构.     

复杂网络中社区发现方法的研究

研究复杂网络中社区发现方法对分析复杂网络的拓扑结构和层次结构、理解社区的形成过程、预测复杂网络的变化趋势、挖掘复杂网络蕴含的规律特征具有十分重要的意义。同时,复杂网络社区发现方法在众多实际领域还有广泛的应用前景。综述了复杂网络社区发现方法的研究现状,将社区发现方法分为无重叠社区发现、重叠社区发现、演化发展社区发现三个方面,并分析比较了算法时间复杂度和准确度。试图为社区发现方法的研究工作提供有益的帮助和参考。     

复杂网络重叠社区结构发现的演化算法研究

复杂网络重叠社区结构的划分已成为复杂网络研究的一个热点,目前已提出了很多关于社区结构发现的算法。提出了一种基于个体从众的演化算法ICEA,基本思想是由节点邻居组成的个体依概率进行从众和变异操作,用较短时间找到最优(或拟最优)模块度的社区划分,社区结构确定后利用邻居投票机制NV发现网络的重叠节点,完成重叠社区的划分。在真实网络的实验结果表明,此算法的使用时间和划分结果都优于典型算法。     

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

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

复杂网络重叠社团检测算法研究综述

社团结构是复杂网络的一项基本特性,对复杂网络中社团结构特别是重叠社团结构的检测,是复杂网络理论研究的一项重要且充满挑战的课题.对当前常用的重叠社团检测算法进行了分析和归纳,阐述每类算法特点,并介绍用于评价算法性能的一些基准图,对复杂网络重叠社团检测领域未来的研究方向提出了一些思考和建议.     

动态加权网络中的演化社区发现算法研究

在动态网络中发现社区结构是一个非常复杂而有意义的过程,可以更好地观察和分析网络的演化情况。针对动态加权网络中的社区发现问题,提出了一种结合历史网络社区结构的算法,叫做动态加权网络中的演化社区发现算法（ECDA）。该算法分为两步：结合历史社区和网络结构信息,计算当前时间跳的输入矩阵;然后通过该输入矩阵计算得到结合历史时间跳信息的社区划分结果。该算法有以下优点：可以自动发现动态加权网络中每个时间跳的社区结构;对网络结构的变化和社区结构的变化具有较高的敏锐性。在人工数据集和真实数据集中进行了实验,实验结果证明该算法可以有效地发现动态加权网络中的社区结构,与其他算法相比具有较好的竞争力。     

基于群体智能的自组织重叠社团结构分析算法

社团结构分析是复杂网络研究的一项重要内容。基于群体智能思想提出了一种自组织的重叠社团结构分析算法SO^2CSA^2。基本思想是：把网络视为一个群体,网络节点是其中的一个个具有简单智能的个体,每个个体依据定义的社团连接分数自主决定要加入的社团（可同时加入多个社团）。首先在网络中寻找一组K-派系作为初始社团结构;在此基础上,所有个体迭代地选择其社团归属,最终整个网络的社团结构将逐渐生长出来;最后对获得的社团结构进行后处理,即调整少量节点的社团归属,以提高其质量。在一组合成网络和现实世界网络上的实验表明,SO^2CSA^2发现的社团结构的质量比两种对比算法（SLPA和OSLOM）更好,尤其是在网络中重叠节点较多或节点重叠度较大的情况下,社团结构质量的提升更为明显。     

基于节点拓扑结构和属性的重叠社区检测算法

近些年来,网络中的重叠社区检测应用越来越广泛,这极大引起了人们的兴趣。通常重叠社区检测只考虑节点的拓扑结构信息,忽略了节点的属性信息,这可能会遗漏数据间的重要结构。本文提出了一种基于节点拓扑结构和属性相似度的局部社区检测算法。首先,计算出节点与社区之间属性相似度。其次,为挖掘内部紧耦合的社区,计算出能够表示耦合性的模块度增量。最后,通过融合多个已检测到局部社区,计算出隶属矩阵从而获取全局重叠社区结构。在三个有真实社区的数据集上的实验结果从内部指标模块度和与真实社区的比较验证了基于节点拓扑结构和属性相似度的重叠社区检测算法比目前基于节点结构的社区检测算法在效率和有效性上有所提升。     

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

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

基于物理场论的探测复杂网络社团结构的分布估计算法

探测社团结构是复杂网络分析中一个基本和重要的问题。为提高探测社团结构的效率,本文提出了基于复杂网络场论的社团结构分布估计算法。通过设置不同种群规模,本文算法运用经典物理场论理论构建节点间场论模型,并在此基础上建立了社团结构概率模型,按照社团结构概率模型建立了分布估计算法。将该算法与GN(Girvan Newman)算法、遗传算法及启发式算法比较其产生的最优解,并分析它们的均值及方差的差异,结果表明：基于复杂网络场论的社团结构分布估计算法收敛速度较快,划分效果较好。     

基于标签传递的有向图重叠社团发现算法研究

社团发现作为网络科学中一个重要的基础问题受到了广泛的关注和重视.针对社团结构的研究为我们提供了从中尺度上分析和理解网络的途径,具有重要的理论和实际意义.已有的研究大多关注无向图和非重叠社团的发现.本文基于标签传递和用户排序的思想设计了一个有向图上的重叠社团发现算法,实际数据上的实验表明了算法在发现用户多重社团属性和确定社团规模方面的有效性.