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

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

基于子团规模的社团划分算法与地理位置

针对以往社团划分算法中存在的子团规模过大的问题,在CNM算法的基础上重新定义子团规模,提出了CLCNM社团划分算法.社团划分结果表明,改进后的算法在子团数量和模块度方面要优于CNM算法.在此基础上,研究社团划分与地理位置间的关系,提出地址前缀相似度的概念,子团地址前缀相似度越大,说明社团划分后的地理效应越明显.CLCNM社团划分结果表明:IPv6网络子团具有明显的地理效应,即子团中节点分布在相邻的地理位置.这一结论可对网络拓扑的再部署提供借鉴性意见.     

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

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

基于最小社团链接度增量的社团结构挖掘算法

针对复杂网络社团结构挖掘算法复杂度高的问题,定义了一个衡量局部社团结构的指标,提出了一种基于最小社团链接度增量的社团结构挖掘算法.本算法的时间复杂度为O(kd),其中d为网络的平均节点度数,k为搜索的节点数.为了验证本算法的性能和计算的准确性,把本算法与一种经典的挖掘局部社团结构方法——Clauset算法,进行了比较.实验结果表明:本算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有了显著提高.     

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

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

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

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

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

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

基于多属性融合策略的复杂网络社团划分算法

为解决目前社团划分算法依赖于单一度量方法,划分结果不够准确,无法适应不同类型的网络划分需求的问题,通过一种多属性融合策略方法研究社团划分。该算法首先基于节点连接,综合度量了多个影响社团划分的属性,并引入模块度概念确定各属性融合的权重,为划分增加了客观的参考信息,从而提高划分准确率;其次,针对传统划分方法迭代次数过多、效率低的问题,利用人工免疫网络内在的全局并行搜索能力实现对社团核心节点的快速寻优,并提出动态算子、免疫检测因子和反向学习机制对人工免疫网络的收敛速度和局部最优问题加以改进,从而提高寻优效率,缩短算法执行时间。最后,在三个经典真实数据集(Zachary、Dolphin、College Football)上进行实验,并将结果与经典算法对比。结果表明,该算法能适应不同的网络,且在较短的执行时间里实现更加精确的划分。可见,相比传统算法,本文算法具有更高的划分效率。     

复杂网络的社团结构发现

社团结构是复杂网络的一个重要拓扑特征,社团结构发现是研究复杂网络的一个基础性问题,近十年来得到了广泛的关注。本文概要了非重叠社团发现的典型算法,较全面地归纳分析了重叠社团发现算法。并指出了社团发现研究尚存在的一些问题和进一步的研究方向。     

基于虚拟力牵引的社团划分算法

文中基于虚拟引力的思想,提出了一种新的社团划分算法.其基本思想是将相连节点之间看作是引力,不相连节点看作是斥力,让节点之间进行相互作用,直到节点以社团的形式聚集起来,从而达到划分社团的目的.通过在计算机生成网络和已知社团结构的现实网络中对本算法进行仿真,发现算法具有较高可靠性和接近线性的时间复杂度.     

基于复杂网络的世界贸易格局探测

利用复杂网络的社团结构概念挖掘国际贸易宏观情报,从而探测世界贸易格局.研究结果表明该方法可以科学、便捷地处理贸易数据情报,可以作为相关领域情报加工的一种新思路.     

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

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

基于复杂网络的济南市公交网络研究

本文运用复杂网络的相关知识对济南市公交网络进行了实证性研究,通过统计各站点的线路,绘出了它的度分布和累积度分布图像,证实济南市公交网络是一个无标度网络,并进行了分析,最后提出了一些建议。     

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

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

基于谱聚类的二分网络社团检测算法

针对二分网络社团检测算法存在精度不高和丢失原始网络信息等问题,设计了一种新的融合奇异值分解的谱聚类(SVD-MS)算法.该方法是将Barber的二分网络模块度最大化问题映射到奇异值向量分解上,并结合启发式算法快速求解向量划分问题.在3个真实世界的网络中对比SVD-MS算法与7种算法的模块度,结果表明,在保留原始网络信息的情况下,SVD-MS算法能更有效地划分二分网络的社团结构.     

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

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

改进的Jaccard贴近度的群落划分算法

针对复杂网络群落划分的准确性差和时间复杂度高的问题,设计了一种基于修正Jaccard贴近度和群落合并的用于非堆叠群落的划分算法IJCD(Improved Jaccard community detection)。该算法针对Jaccard贴近度的计算结果中存在距离不同但贴近度可能相同的情况,引入了改进的Jaccard贴近度算法计算节点之间的贴近度,选择多个贴近节点在一个群落而不是最贴近的两个节点,从而得到初始群落,再进行群落合并。计算所得的初始群落的准确率较高且群落个数较少,提高了整个算法的效率。最后,采用了几种经典的算法对网络进行群落划分,在选取的几个真实网络和计算机生成网络上的实验结果表明：IJCD算法能够有效地对群落进行划分,并且有较高的准确度和较低的时间复杂度。     

基于关系强度的复杂网络社团结构发现算法比较

实际复杂网络数据的合理预处理是社团结构分析的基础与前提,对划分结果有着显著的影响。本文通过定义节点间的关系强度,将社会调查得到的社交网络数据处理成社团结构算法中通用的邻接矩阵,提出了处理实际复杂网络数据使之适用于经典社团算法分析的一种方法。同时,本文进一步给出了关系强度强联系定义和关系强度弱联系定义,并比较了算法在这两种定义下展示出的不同性能。     

基于相似度的加权复杂网络社区发现方法

针对加权复杂网络中的社区结构发现问题,本文定义基于权重关系的相似度,并在此基础上定义了节点中心度和归属度,改进GN算法的模块度评价函数,提出一种基于相似度的中心聚类算法(SCC).该算法通过计算节点间的相似度,选取合理的中心度大的节点作为社区中心节点,最后基于节点归属度来聚集从而形成社区;同时,提出了用相似度代替边介数的改进GN算法SGN.通过理论分析,并在数据集上进行实验验证,结果表明SCC算法与WGN算法、SGN算法相比,速度和精度上均有较大改善.同时与I2C算法相比,社区的划分有效性更好.     

一种基于复杂网络属性值的K-means聚类算法

传统-means聚类算法的性能依赖于初始聚类中心的选择.本文将复杂网络节点的属性值作为节点的度、聚集度与聚集系数的加权值,通过计算所有节点的加权综合聚集特征值,选取综合聚集特征值高,并且彼此之间无高聚集性特征的K个节点作为聚类的初始聚类中心,然后进行聚类迭代过程.实验结果表明,新算法对初始聚类中心的选取更迅速有效,避免了传统K-means算法初始聚类节点选取的敏感性,进而提高K-means算法的聚类质量.