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

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

基于相似度聚类的二分网络社区发现算法

针对往往不能提前预知社区个数的情况,提出了基于相似度聚类的二分网络社区发现算法(similarity clustering algorithm,简称SCA).算法通过计算U类节点之间的相似度获得核心节点,同时选取核心节点邻域中的节点扩展得到社区,将未划分到社区中的孤立点和只包含一个节点的社区分别放入与之联系最紧密的社区中,最后V类节点划分到已有的社区中得到完整的社区划分结果.通过在人工数据集与真实网络上的分析,分别利用归一化互信息和模块度作为评价指标,实验结果表明,SCA比BRIM等算法能够更有效挖掘二分网络社区结构,具有比较良好的社区划分效果.     

一种基于核心节点跳转的局部社区发现算法

针对现有算法受给定节点位置的限制而影响社区发现的稳定性和准确性问题,提出一种基于核心节点跳转的局部社区发现算法,避免从给定节点直接聚类,而是先搜寻给定节点附近的核心节点,并围绕核心节点向外扩张,根据节点适应度聚类邻接节点以构建核心节点子团;并根据子团相似度进行合并,从而得到给定节点所属的局部社区结构.在计算机生成网络和真实网络上的实验和分析证明,该算法能够有效地提升局部社区发现稳定性,并改善局部社区划分的准确性.     

基于共邻节点相似度的加权网络社区发现方法

为实现加权网络的准确划分,发现真实的社区结构,提出一种基于模块度和共邻节点相似性的层次聚类社区划分方法IEM.首先,定义两节点间基于共邻节点的相似度.之后,基于该度量快速聚合当前节点和与其关联紧密度最强的邻居节点以形成初始社区,并进行社区扩展.最后,以最大化网络模块度为目标进行社区合并以优化划分结果.算法通过形成初始社区、扩展社区、合并社区三步,实现了加权网络合理有效的社区划分.以加权模块度作为社区划分质量的评价标准,在多个数据集上的实验结果表明,IEM算法优于加权CN、加权AA、加权RA.同时,与CRMA算法相比,IEM算法对加权网络社区划分的有效性和正确性更高.     

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

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

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

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

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

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

一种基于节点稳定性的社区发现算法

许多成功的社区发现算法已经被广泛应用于复杂网络社区发现任务中.随着数据复杂性的增加,网络中节点间的关系也呈现多样化的特点,因此提出一种基于信息熵的节点稳定性度量方法,衡量网络中节点在社区划分中的稳定性;并在此基础上提出一种基于节点稳定性的社区发现算法(Node Stability-based Algorithm,NSA).首先得到网络的t种社区划分,计算各节点的标签熵,选择熵小于一定阈值的节点作为网络的稳定节点集S;然后,利用所得到的稳定节点集S从原网络中抽取一个包含S的连通子图Gs,使Gs中节点的不稳定性尽可能低;在连通子图Gs上进行社区发现,得到初始聚类结果,再计算其他未聚类节点与初始类簇的距离,确定其社区归属,得到最终聚类结果 .在四个带标签真实网络数据集和八个不带标签的真实网络数据集上,与LPA,Infomap,Walktrap,BGLL,LPA-S等经典算法的比较实验表明,所提出的NSA算法能够较好地进行社区发现,在NMI和模块度等方面表现良好.     

基于节点亲密度的标签传播重叠社区发现算法

针对基于标签传播的重叠社区发现算法中出现的随机性和不稳定性问题,提出了一种新的基于节点亲密度的标签传播算法.首先,利用网络的局部信息,以模块度增量为依据,对网络中节点进行粗聚类,实现对节点的初步划分;然后,定义节点亲密度函数进行标签的更新和选择.在人工和真实网络上对算法进行验证.结果表明,该算法能有效地提高大规模重叠社区检测的准确性和稳定性,并且具有近乎线性的时间复杂度.     

基于边聚类系数的谱聚类社区划分方法研究

针对图谱划分方法在划分社区结构不是很明显的网络时,不能得到好的划分效果,该文提出了基于边聚类系数的谱聚类社区划分方法.由于社区内部节点之间的连接比各个社区间节点的连接稠密,边聚类系数的大小反映了节点的聚集程度,因而通过网络中的边所构三角形的数量定义了聚类系数矩阵,矩阵中的元素即处于网络中的边实际构成三角形的数量.在增益函数最大化的过程中,使用了矩阵的特征值和特征向量,以此来进行社区划分.通过在真实网络数据中进行实验,结果表明该算法可行.     

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

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

时态网络节点相似性度量及链路预测算法

详细分析和阐述了时态网络中的链路预测问题，将时态网络按时间顺序划分为具有相同时间间隔的多层网络快照序列.针对基于共同邻居的相似性指标对网络链路刻画粒度较粗糙的问题，提出了基于邻居节点聚类系数的相似性度量指标NCC和NCCP，并基于此提出时态网络链路预测算法.通过在真实数据集上的对比实验验证了利用邻居节点的聚类信息可以提高预测精度.利用真实邮件数据集验证了所提出的链路预测算法预测效果的优越性，并且实验结果证明越接近预测时间的网络结构对预测结果影响越大.     

基于密度峰值及肘方法的类数目确定

为确定数据集真实类数目,降低参数对于密度峰值算法的影响,本文基于自然邻居思想提出了密度峰值(DP)算法的新内核,以摆脱参数的限制,实现真正的自适应聚类.将密度峰值算法与肘方法联合,提出了自然密度峰(NDP)指标.此外,通过减而治之的思想,改进了自然邻居的搜索算法.新的指标和方法可以适用于多种类型的数据集(例如线形、流形...     

基于DCBM的马尔可夫谱聚类社区发现算法

谱聚类划分算法是经典社区发现算法之一,由于目前构造的相似图承载的社区结构信息较少,导致聚类效果与理想效果具有较大差距,因此,提出了基于DCBM的马尔可夫谱聚类社区发现算法MSCD.首先,基于DCBM模型提出了以节点间连接概率为元素的概率矩阵,并建立了概率矩阵与相似矩阵之间的映射关系;其次,利用马尔可夫链重构了谱聚类的相似图;最后,使用重构的相似图对网络进行社区划分.在人工合成网络和真实网络上与SC,MRW-KNN和FluidC三种典型算法进行了对比实验.实验结果表明,MSCD算法具有更加高效的聚类性能,能够揭示更加清晰的社区结构.     

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

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

基于谱聚类带有节点特征的社区发现算法

提出一类基于谱聚类算法的带有节点特征的社区发现算法(SCSA),该算法首先将带有节点特征的网络图转化为加权图,其中边的权重用节点特征相似度度量,然后将谱聚类算法应用到加权图上进行社区检测.SCSA算法将带有节点特征的网络图分成K个社区,每个社区内节点不仅连接良好而且具有相似的特征属性.注意到不是所有节点的特征在社区划分过程中都是有用的,与划分无关的特征信息会降低社区发现算法的准确度.为此,提出了一类节点特征权重自调整机制嵌入到谱聚类中以提高社区检测质量.数值实验的结果验证了所提算法的有效性.     

基于密度峰值和网络嵌入的重叠社区发现

密度峰值是一种基于密度的聚类算法,该算法假设类簇中心点具有较高的密度且被密度较小的节点包围.由于图结构的性质,密度峰值无法直接适用于网络结构,现有的基于密度峰值的社区发现算法大部分是基于图的拓扑结构或者邻接矩阵度量节点近似度,这种方法往往引入较大的计算复杂度.文中结合网络嵌入方法通过低维向量表示网络中的节点信息,提出了...     

基于拓扑势的局部化重叠社区识别

针对传统社区识别算法中需要根据先验知识设定参数、 社区划分结果具有随机性及复杂度过高的问题, 提出一种基于拓扑势的局部化重叠社区识别算法. 该算法通过引入拓扑势计算节点的影响力, 利用节点间的局部相似性度量指标, 采用标签传播策略进行重叠结构的社区识别. 在真实网络及人工合成网络上与多种经典算法进行对比实验验证了算法的高效性.     

一种基于广度优先搜索的社区发现方法

由于当前的算法不能很好地将网络的联通性和单个节点的属性综合考虑,分析了凝聚和分裂层次聚类经典算法的局限性,从而给出边的载荷、边的权重、连接度门限、图形分割等定义.综合考虑网络的拓扑结构和边的权重关系,提出了基于广度优先搜索的社会网络社区发现算法SoNetCD.算法通过删除社区之间的边而得到社区结构,它对社区之间的边判断准确,对社区内部的边误删率低.运用经典数据集进行实验的结果表明,该算法具有比经典GN算法更好的结果.     

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

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