应用Normal矩阵谱平分法的多社团发现

现实世界中许多实际网络都有一个共同的性质,即社团结构。揭示网络中的社团结构,对于了解网络结构与分析网络性质都是很重要的。分析了常见的社团发现算法的特点,以及谱二分法在实际应用中必须不断迭代才能完成多社团发现的不足,提出了基于Normal矩阵和k-means聚类算法的多社团发现方法。该算法能选择合适的特征向量维数,为k-means划分社团提供有效数据,相比其他算法有着较高的准确率。

基于Normal矩阵谱平分法的快速电压控制分区

为提高电网中二级电压控制分区的速度,提出种基于复杂网络谱平分法的电压控制分区新算法。该算法采用节点导纳矩阵虚部作为电压控制分区简化拓扑模型的元素,并通过分析分区模型的Normal矩阵,直接获取分区聚类样本,在保证区域无功就地平衡的条件下,能够有效降低算法的时间复杂度。采用改进初始聚类中心的K-means聚类算法保证了分区时的稳定性,同时,模块度指标和无功储备校核的引入使优分区结果更客观、更可信。通过IEEE 39节点和IEEE 118节点标准测试系统对谱平分法分区的可行性和效率进行仿真计算和验证。分析表明,该方法能够快速有效地获取合理的电压控制分区方案,分区结果可为二级电压控制分区的工程实践提供参考。

利用基于Normal矩阵的谱平分法挖掘酵母蛋白质相互作用网络中的社团

蛋白质-蛋白质相互作用(protein-protein interaction,PPI)网络是生物网络的重要组成部分,也是后基因组时代的热点研究问题。揭示PPI网络中的社团结构,对于理解其复杂相互作用的结构和动态特征,了解活体细胞的结构和功能都有很大作用。但目前对于PPI网络结构的分析带有很强的试探性,还没有成熟可靠的方法。传统的谱平分法需要预先知道社团的个数,为了克服这一缺点,在无向无权的PPI网络中使用改进后的基于Normal矩阵的谱平分法,得到了55个有生物学意义的社团。实验结果表明:尽管PPI网络中的社团结构不是很明显,基于Normal矩阵的谱平分法依然可以有效地挖掘出其中具有生物学意义的社团结构。

基于Chameleon算法和谱平分法的聚类新方法

在分析传统的聚类算法优越性和存在不足的基础上,基于Chameleon算法和谱平分法的思想提出了一种新的聚类方法。相比传统聚类算法而言此算法克服了如k-means算法、EM算法等传统聚类算法在聚类不为凸的样本空间时容易陷入局部最优的缺点,能在任意形状的样本空间上聚类,且收敛于全局最优解,并且可以降低噪声和离群点的影响,提高了算法的有效性。在UCI数据集和5个特殊的二维数据点组成的数据集上进行了实验,证明了本方法的有效性。

基于复杂网络社团结构理论的同调等值算法

基于复杂网络社团结构理论,提出了一种同调等值的新算法。首先构造动态电力网络的加权Laplace矩阵,在此基础上利用谱平分法分析系统故障后的Laplace矩阵,将系统划分为2个区域,其中同步能力弱化系数最小的机组所在的区域被选为研究区域,另一个则为外部区域。然后基于模块度的概念构建分区评价指标,并利用凝聚算法分析故障前的Laplace矩阵,将外部区域划分为多个等值分区。对IEEE39节点系统的仿真分析表明,所提出的同调等值算法能够自动确定研究区域和外部区域,自动确定外部区域中等值分区的数目,而且计算量小,迅速准确。

基于多维特征向量的网络社团划分方法

为了寻找大规模复杂网络中的社团结构,提出了基于多维特征向量的社团划分方法,即多维特征向量谱平分法.利用网络连接矩阵的多维特征向量划分网络社团,通过仿真实验分析关键参数对划分效果的影响,从而确定使得划分结果最优的参量值,并综合多维特征量阈值和社团数目两方面的因素决定被划分的社团数目.在具有代表性的局域世界网络演化模型中进行仿真,证明该方法在网络聚簇特征不是很明显的情况下,能够有效划分网络中存在的多个社团,适应具有各种聚集特征的网络,说明该算法在实际网络中具有较高的应用价值.

复杂网络中分析社团结构算法研究概述

社团结构在复杂网络中是一种普遍存在的特征。因而在复杂网络中分析和计算出大量大规模的社团结构就显得尤为重要,学者们也提出了很多算法。本文主要概述了近年来较有代表性的一些算法,如:Kernighan-Lin算法、谱平分法和社会学中典型分析方法凝聚方法和分裂方法,着重介绍了谱平分法中的一种算法复杂度相对较小的线性时间的物理方法Wu-Huberman算法,最后指出了进一步的研究方向。

复杂网络中的社团结构分析算法研究综述

许多实际网络中都存在着社团结构。为了寻找大规模复杂网络中的社团结构,人们提出了很多算法。本文综述了近几年来比较有代表性的一些算法。首先介绍了计算机科学中最有名的谱平分法和Kernighan-Lin算法,然后介绍了社会学中具有代表性的分裂算法和凝聚算法,并着重分析了最新提出来的一种寻找网络中彼此重叠的社团结构的派系过滤算法。最后指出了进一步的研究方向。

基于改进的Jaccard相似系数矩阵的社团划分算法

社会网络结构反映了网络中个体节点行为的区域特点以及群体之间的关联性。为了提高社团划分的效率和准确性,设计了一种新的基于改进的Jaccard相似系数矩阵的社团划分算法IJ-CD。该算法首先对社会网络的Jaccard相似系数矩阵中的零元素进行处理得到改进的Jaccard相似系数矩阵;然后基于谱平分法思想将改进的矩阵标准化,并选取适当的特征向量维数;最后应用K-means聚类算法划分社团。基于三个经典社会网络数据集的社团划分实验结果表明:IJ-CD算法不仅在社团结构不很明显时也能很好划分出社团,而且能有效地提高社团划分的准确性和降低时间复杂度。

基于节点重要度的社团划分方法研究

通过对复杂网络中存在的社团结构进行划分,有助于发现整个网络的功能、结构、隐藏的规律及网络具有的影响力。为了得到较好的网络社团结构的划分结果,多一种社团划分的途径,本文定义了网络的节点重要度评价函数,结合谱平分法提出了一种基于节点重要度的社团划分算法。实例表明,该算法能很好地划分复杂网络中的社团结构。

复杂网络中社团结构算法的综述

社团结构是复杂网络重要特征之一。本文综述了三种比较有代表性的算法,Kernighan-Lin算法,谱平分法和GN算法;比较了他们的优缺点。

基于LabVIEW的社团结构识别实验软件

社团结构识别是网络结构分析的基本环节,文中基于LabVIEW开发了一种具有识别结果演示功能的社团结构识别实验软件。该软件利用LabVIEW组织实验数据、规划人机界面、显示识别结果并管理操作流程,利用Matlab进行社团结构识别算法的计算。在软件的开发过程中,识别结果的显示采用属性节点技术,操作流程的管理采用有限状态机技术,社团结构识别算法的计算采用LabVIEW与Matlab混合编程技术。该软件实现了谱平分法、GN算法和Newman算法共3种典型算法的计算与结果显示,给出了软件的运行效果和算法之间的对比图。

2种社团发现算法对工业共生网络演化过程描述的比较

针对工业共生网络特点,分别应用改进后的谱平分算法和凝聚算法2种典型的社团发现算法对卡伦堡及鲁北工业共生网络进行社团划分,并对其集聚性程度进行定量的比较和评价,从而对卡伦堡及鲁北工业共生网络演化过程做出定量描述,并与其实际工业共生网络的演化发展过程做出对比。结果表明,采用复杂网络社团划分算法可以实现对工业共生网络发展演化过程的定量描述,而改进后的谱平分算法比凝聚算法对工业共生网络演化过程的描述更接近其实际的发展状况。

复杂性工业共生网络的社团结构划分

针对复杂性工业共生网络难以实现定量区域划分的现状,应用复杂网络理论中社团划分算法,提出对复杂性工业共生网络进行定量区域划分的方法,同时针对复杂性工业共生网络社团结构特点,在Grirvan-Newman模块度以及连接密度和内聚系数的基础上,提出一种对复杂性工业共生网络社团划分结果的评价方法,此方法不受复杂性工业共生网络分辨率的限制,当网络中社团大小差异较大时仍然适用。以锦界生态园为例,应用Capocci谱平分法对其网络结构进行了社团划分,采用所提出的评价方法对划分结果进行了评价,验证了复杂性工业共生网络社团划分结果的评价方法。结果表明,采用复杂网络理论中社团划分算法对复杂性工业共生网络的定量区域划分是可行的。