基于相邻节点聚类的社团划分算法

社团结构是复杂网络中的拓扑属性之一,具有同一社团内的节点连接紧密而不同社团的节点连接疏松的性质.作者基于复杂网络中的社团结构的性质并根据网络中相邻节点的距离关系,提出了一种社团划分算法--基于相邻节点聚类的社团划分算法.笔者对算法的基本概念以及实现进行了详细的描述,通过应用在实例上所得结果说明算法的可行性.     

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

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

改进的K-均值聚类算法在社团划分中的应用

为了快速准确地寻找大规模复杂网络的社团结构,文中基于K-均值聚类算法的思想,提出了寻找初始聚类中心的新方法.该算法应用于社会网络分析中的一个经典问题--Zachary网络,获得了满意的结果.     

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

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

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

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

基于聚类的复杂网络社团结构发现

我校计算机与信息技术学院教师李艳灵博士获批国家自然科学基金项目:基于聚类的复杂网络社团结构发现,项目编号:61202194.复杂网络是指具有复杂拓扑结构和复杂节点行为的网络系统,它是对现实世界中各种各样的大规模复杂系统的抽象.复杂网络中的社团发现旨在寻找复杂网络中真实存在的社团结构,发现网络中的社团结构对分析     

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

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

基于转移矩阵P的复杂网络聚类方法

提出了一种相对简单、有效的划分复杂网络社团结构的方法.该算法利用复杂网络的转移矩阵P和K均值聚类算法来划分社团结构,并且用F统计量判定最优的聚类结果,在探测社团结构明显的人工网时具有较高的准确度.     

基于边信任度的混合参数自适应重叠社区发现算法

网络中的社区结构有助于简化网络拓扑结构分析,揭示系统内部的规律,能够为信息推荐和信息传播控制提供有力的支撑.网络重叠社区结构与真实生活更加接近,但其分析较非重叠社区结构更加困难.因此,针对重叠社区发现问题,在对网络的边进行峰值聚类的基础上提出了一种基于边信任度的混合参数的自适应重叠社区发现算法.定义了网络边的邻居边集合及与其邻居边之间的信任度函数,通过信息传递获取边的总信息量,并且基于此引入混合参数的概念.基于k-means算法使用混合参数对网络中的边进行聚类,即将网络中的边划分为核心边集与非核心边集,每个核心边作为一个聚类中心.根据非核心边到核心边的距离将所有非核心边划分至距离其最近的聚类中心所在社区.再根据网络中边与节点的关系实现重叠节点发现,最终实现重叠社区的发现.该算法的优点是每条边通过独立地完成信息扩散找到社区的结构,相比于传统的峰值聚类算法,不需要人为设置相关参数,实现重叠社区的自适应发现.为验证算法的可行性,对算法复杂度进行了分析,并且使用两种社区划分评价指标——标准化互信息和模块度,分别在人工数据集及6种真实数据集上进行实验,通过与其他算法进行对比分析,实验结果表明该算法更具可行性和有效性.     

基于量子模糊聚类算法的复杂网络社团结构探测

研究了复杂网络的社团结构特性,探讨了复杂网络的社团结构探测算法.针对现有算法中判断社团结构时的主观性问题,提出了量子模糊聚类算法,并将该算法用于复杂网络社团结构的探测.实验结果表明:该算法可以准确、有效地探测到网络中实际存在的社团结构.