基于相似性模块度最大约束标记传播的网络社团发现算法

提出一种基于相似性模块度最大约束标记传播的快速网络社团发现算法(MLPA)。该方法采用结构相似度计算, 通过最大约束标记传播模型更新节点标记, 使社团的划分结果更加符合社团内部结构相对紧密、 社团之间结构相对稀疏的特点, 提高社团划分的精确度。结合标记传播5次循环迭代可以完成95%或者更多节点标记过程的实验结果, 判定标记更新过程趋于稳定, 从而在稳定时停止更新, 降低了运行时间。MLPA避免了传统的邻接矩阵计算方法, 适合大规模网络的社团发现。     

基于中心度发现的中心社团

使用度中心度与流介数中心度相结合的方法,首先计算出节点的度中心度和流介数中心度,得出网络中的几何中心点和信息、物质或能量在网络上传输时经过路径最多的节点,并将这两个指标作为一个整体考虑,得到这两个指标相对比较大的节点,再在这些节点和其邻居节点上利用CPM社团发现算法,从而发现网络中的中心社团.此方法可以发现网络中相对"重要"的社团,对复杂网络上的传播机理、相继故障等分析都有一定的意义.随后利用该方法分析兰州市公共交通线路网络的中心社团结构,结果表明该社团在网络中的确可以起到比较重要的作用.     

一种基于节点重要度的社团划分算法

指出了通过挖掘复杂网络中存在的社团结构,可以分析整个复杂网络的拓扑结构和功能,还可以发现网络中隐藏的规律.为了得到最佳社团划分结构,定义了网络的节点重要度矩阵和聚类矩阵,结合图的特征谱平分法和模块度函数,提出了一种基于节点重要度的社团划分算法(CDNIM).通过在空手道俱乐部、海豚关系网络等多个经典数据集上应用,结果表明:该算法能够有效提高发现社团结构的准确率.     

基于吸收度的三支决策社团划分算法

该文针对社团划分存在的重叠区域问题引入三支决策思想,提出了一种基于吸收度的社团划分算法(3WD-PPOC).3WD-PPOC首先根据网络结构的重要度矩阵进行社团的初始划分,再利用F吸收度来构建社团间的重叠区,即社团边界域,并得到各社团的正域,最后通过P吸收度来完成对在社团边界域中节点的再次划分和社团正域的更新.对比同类算法,3WD-PPOC具有较低的时间复杂度.实验结果进一步表明:3WD-PPOC能够有效地进行社团划分,相比其他社团划分算法,3WD-PPOC表现出更好的社团划分质量,划分后的各社团结构更紧密.该算法对社团重叠节点的划分具有较好的稳定性.     

基于节点向量和密度峰值的重叠社团检测方法

在真实世界网络中,数据量往往较大、维度较高,这使得数据难以处理,并且所包含的社团大多重叠,而大多数已经存在的算法针对的是非重叠社团,基于改进的密度峰值和标签传播的重叠社团检测算法(DPCL算法).采用低维向量表示网络中节点信息,根据节点的局部密度和相对距离选出中心节点.将只与一个中心节点直接相邻的节点分配到该中心节点所在的社团内,对剩余节点通过计算归属度进行分配,从而实现对重叠社团进行检测;在真实世界网络和LFR基准合成网络上与其他社团检测方法进行比较,实验结果表明能够有效的检测重叠社团.     

基于贝叶斯后验模型的局部社团发现

基于节点的局部社团发现在大数据社会网络分析中非常重要。针对Newman模块度在社团发现中的局限性,基于贝叶斯后验模型提出了BS模块度度量法。该方法结合节点的模块度和推荐概率进行建模,并以邻接并入为框架得到了一种新的局部社团发现算法。该方法克服了Newman模块度在稀疏网络中区分度低的问题以及社团结构差异大的分辨率问题,有效地寻找大规模网络中的局部社团。通过与Newman模块度在真实社团中的比较,验证了该度量方法的有效性。     

一种改进的基于节点相异度的社团结构划分算法

提出一种改进的基于节点相异度的社团结构划分算法.首先根据度和平均度评估标准,筛选出核心节点作为初始核心节点集,然后基于节点相异度进行划分,直至社团结构划分完成.实验结果证明,与其他一些算法相比,该算法的划分效果比较精确且易于实现.     

基于局部稠密度的社团划分算法

社团划分是研究复杂网络结构与功能之间关系的基础,提出了一种基于局部稠密度的社团划分算法。算法首先计算网络中节点的局域密度,从局域密度最大的节点v开始,找出以节点v及其邻居如果αlocal(vi)≥γin则将其设为初始社团S。首次定义了节点的入团率β,并且使用整体和单个入团的方式将节点加入到初始社团中,直到αlocalγout时算法停止。然后再使用内部连接P来检测社团划分的效果,并将错误划分的节点重新归类。把这个算法用在三个社会网络中,都得到了正确的划分。并用MATLAB仿真结果表明:划分出的社团内部连接相当紧密,从而达到了内部连接紧外部连接稀疏的划分社团的要求。此算法不需要计算模块度,在找到初始社团后,并不需要对整个网络的所有节点进行计算,只需计算其一阶邻居节点。这样算法所占用时间少,结果精确率高。     

一种信任关系网络中的社团结构检测算法

针对群智计算和感知服务中不可信服务节点可能引入的安全威胁问题,提出了一种基于节点间信任关系网络的社团结构检测算法。该算法通过分析信任关系网络的功能和结构特点,引入连接的方向和权值因素,建立有向加权网络模型,定义最优路径相似度作为节点聚合标准,提出社团离散指数作为评价函数控制检测过程,从而准确识别信任关系网络中的可信节点集合,为服务节点选择提供参考。算法引入节点相似度阈值和归属判定指数控制社团聚合,与误分类节点再筛选环节配合,有效降低了检测过程中的节点误判概率,有针对性地设计社团离散指数作为评价函数,动态评估检测结果并调节聚合参数,保证了社团结构检测结果的准确率及合理性。实验结果表明:该算法能够有效实现信任关系网络中社团结构的检测与识别,与已有算法相比,检测准确率提高了5.88%。     

基于社团密合度的复杂网络社团发现算法

传统的社团发现算法大多存在划分效果和复杂度相矛盾的问题,为了解决该问题,提出一种新的单社团结构评价标准——社团密合度(group density).在此基础上,设计了一种基于凝聚思想的社团发现算法,该算法通过不断融合小社团,使网络的社团结构向平均社团密合度最大的方向发展,并使用模块度检测算法的划分结果.通过与经典的GN,Fast Newman,LPA等算法对多个数据集进行实验对比,验证了本文算法在获得较好的划分效果的同时具有较低的时间复杂度.     

基于加权树的层次社团划分算法

社团发现常用于挖掘复杂网络中的隐藏信息,如功能模块和拓扑结构.为提高复杂网络中社团结构挖掘的质量,提出一种基于加权树的层次社团划分算法HCD_WTree(Hierarchical Community Detection Algorithm Based on Weighted Tree).首先,结合邻域重叠比和节点的度中心性来度量节点间关系强度,基于该度量将原无权网络转换成加权网络;接着,对网络进行简化,得到加权树;最后,基于层次社团挖掘方法,根据边权依序裁剪加权树,得到层次的社团结构,并结合模块度函数获得最优的社团划分结果.在公用数据集上的实验结果表明,与现有的社团挖掘技术相比,HCD_WTree算法能够更准确地划分复杂网络中的社团结构.     

基于Spark的并行增量动态社团发现算法

动态社团发现是研究网络演化的关键步骤。在数据量迅猛增长的情况下,社团发现的单机算法效率较低。该文提出了一种基于Spark的并行增量动态社团发现算法(parallel incremental dynamic community detection algorithm based on Spark,PIDCDS),为了在GraphX并行图计算平台上通过最大化持久力发现社团,该算法对节点的持久力计算公式进行了有效修正。PIDCDS计算每个时间片中增量节点的持久力指标,更新其社团归属,在保证一定的社团划分准确性的基础上减少计算量。通过与FacetNet动态社团发现算法做比较,该算法能够获得更好的稳定性,同时能发现更真实的社团划分。对比不同规模网络在PIDCDS上的运行时间,发现该时间随着网络节点和边数的增加缓慢增长,性能较高,并且增加执行器核数将在一定程度上加速算法的执行。     

一种基于相似社团和节点角色划分的社交网络用户推荐方案

针对现有的社交网络用户推荐方案中主要考虑个体相似性问题以及节点角色无层次差别的问题,提出一种基于相似社团和节点角色划分的推荐方案。在传统的用户相似度计算基础上,从社团结构和属性两方面,综合考虑社团间联系的紧密程度和社团用户兴趣爱好相似程度,提出一种社团相似度的计算方法;其次,从用户节点所在的社团内部和外部2个维度度量节点间紧密度,并据此度量节点的社会影响力,进而将它们划分成不同角色,实现用户推荐的差异化。通过新浪微博真实社交数据对方案进行验证,实验结果表明,该方案适用于存在社团现象的社交网络层次化用户推荐,并具有良好的推荐效果。     

具有小世界特性的复杂液压系统故障源搜索方法

针对复杂液压系统故障多样、成因复杂、隐蔽性强,故障源辨识困难,提出了一种基于小世界特性的先网络社团结构划分、后社团内的复杂液压系统故障源搜索的层次分析方法.构建了复杂液压系统的网络拓扑结构,以同时具有大的介数和度数的节点作为网络中故障传播社团的中心,来改进Wu-Huberman算法,从而实现了社团结构的划分.根据各社团连接边对应管路的液压参数变化,确定包含故障源的社团,进一步计算该社团故障传播的可达矩阵,定位了故障源节点.经过对轧钢加热炉液压系统起升故障的分析和故障源查找,证实了该方法可以根据系统网络的结构特征和间接故障表现,实现复杂液压系统故障源的识别.     

采用链路聚类的动态网络社团发现算法

针对当前基于节点的动态网络社团结构发现算法难以发现稳定的社团结构的问题,提出了一种采用链路聚类的动态网络社团发现算法(LDC)。该算法首先从链路的角度得到网络的链路图结构;然后对比不同时刻的链路图结构,将动态网络中节点的添加与移除以及边的添加与移除等复杂的变化信息简化为链路添加和链路移除2种增量变化信息;再在前一时刻社团结构的基础上以改进的链路划分密度函数对增量变化信息中变化的链路进行处理,判断该链路是否加入到社团中从而得到最优的社团结构;最后将得到的链路社团转化成为最终的节点社团结构。实验结果表明,相比于当前基于节点的动态社团发现算法,LDC算法能够有效地发现网络中结构稳定的社团结构,其模块度值和标准化互信息值至少提高了0.19和0.13,且算法的运行效率要明显优于基于节点的动态社团发现算法。     

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

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

基于三角模体的社团发现算法

为了提高社团发现算法的效率,提出了一种基于三角模体和期望极大的社团结构发现(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型的社团发现算法。CSDTME模型采用三角模体对网络进行表示,考虑了节点的混合隶属度及社团间的链接关系,用期望极大算法计算模型涉及的参数,采用全三角模体和两边三角模体作为计算对象,通过减少计算对象来提高算法的效率,根据参数结果可得到节点的社团隶属度及社团间的链接关系。实验结果表明:在保证社团发现能力的同时,该算法能够提高社团发现的效率。     

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

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

基于最短路径相似度的复杂网社团识别算法

基于最短路径的思想,定义新的节点相似度,利用谱平分算法来识别复杂网络的社团结构.首先根据节点间最短路径的思想计算改进的共享最近邻(SNN)相似度,将其标准化后求出标准化矩阵的特征值及特征向量,然后根据网络选取一定数目的第一非平凡特征向量作为聚类样本,利用FCM算法可识别网络的社团.实验结果表明,该算法对于社团结构不明显的网络划分效果很好.     

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

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