GFN:基于“群”思想对Fast-Newman算法改进的复杂网络聚类算法

针对目前复杂网络优化聚类算法目标函数的有偏性影响聚类精度的问题,提出了"群"的概念,实现了对节点在聚类过程中局部信息决策环境的划定。提出了基于"群"概念改进的网络模块性评价函数,并以该函数作为目标函数对Fast-Newman(FN)算法进行了改进。在不同类别数据集上进行的聚类实验的结果表明,基于"群"思想改进的FN算法(GFN)在复杂网络中的聚类精度比FN算法平均提高了约70%,从而验证了"群"思想在揭示真实簇结构过程中的有效性。

改进RRT^(*)FN算法的机器人路径规划

针对传统渐近最优快速扩展随机树算法(RRT)随机性大、收敛精度低以及运行时间长等问题,提出一种改进的Informed-RRT^(*)-FN算法。改进算法在找到初始路径前采用基于贪心思想改进的目标偏置采样策略和随机删除叶子节点策略以降低找到初始路径的时间;找到初始路径后进一步在椭圆子空间中采样,使用基于节点权重的节点删除策略优先删除“无效”节点和动态重连半径的策略以提高收敛精度并保持较低的运行时间。改进算法在3种地图开展了仿真实验,结果表明相较于RRT^(*)-FN、Informed-RRT和Informed-RRT^(*)-FN算法,该算法收敛精度最高,且运行时间最短。该算法进一步在ROS平台开展全局路径规划实验,验证了其可靠性和实用性。

基于改进Newman快速划分算法的城市动态交通子区划分方法

城市交通网络紧密联系,交叉口、干线和交通子区存在复杂关联性。从复杂系统角度提出一种基于Newman快速划分算法(Fast Newman,FN)的控制子区划分方法。首先,考虑城市道路网络拓扑结构复杂性,根据相邻交叉口的交叉口间距、路段交通流量、车流离散特性、交通流速度、车流密度等分析交叉口关联性,建立综合关联度计算模型;其次,将交叉口关联性引入到FN算法中,基于改进的Newman快速划分算法对路网控制子区进行划分;最后,通过实际路网,进行模型验证。结果表明:该子区动态划分方法有效考虑路网拓扑结构复杂性,更符合实际交通流特性,对城市区域路网子区划分更加合理。

用于社团发现的Girvan-Newman改进算法

为了克服Girvan-Newman算法运行效率的不足,提出了一个基于modularity极值近似的社团发现算法MEA。该算法采用modularity增量作为社团结构的度量,使用贪心策略获得最优社团分划的近似解。通过理论分析,并在实际的数据集上进行实验验证,结果表明MEA算法是快速、有效的。

基于改进Newman算法的动态控制子区划分

为了优化现有控制子区划分方法,以区域协调控制为目标,提出基于改进的Newman社团快速划分的动态子区划分方法.综合考虑路网中相邻交叉口之间的距离、交通流量、行程时间、车流离散特性、信号周期和路段交通流密度等因素,定量分析交叉口关联性;分别计算相邻交叉口的流量关联系数、信号周期关联系数和路段交通流密度关联系数,建立相邻交叉口的总关联度模型;对传统Newman算法进行改进,引入交叉口关联度,依据不同交通特性对区域路网进行动态子区划分;选取实际区域路网,进行模型验证分析.结果表明:Newman算法子区划分结果不能随着交通特性的改变而改变;与之相比,所提出模型的子区划分结果更加细致,更加符合实际交通流特性,且可以依据不同时段交通特性实现动态子区划分,可以为信号控制方案制定提供良好基础.

社交网络中FN算法结果的后处理研究

在复杂网络问题的研究中,众多聚类算法的横向比较与改进研究方面的工作在近几年吸引了大量注意并得到深入研究。其中,基于模块度的算法被广泛应用,而模块度也作为评价聚类的一项指标。在这类算法中,基于模块度的快速Newman算法(Fast-Newman algorithm,FN)显得较为突出,许多相关的深入研究由此展开,但多数工作是基于算子改进、应用领域等方向展开的,而对于算法结果的研究工作则更多偏向于评价、测量和总结。该研究从FN算法的结果入手,对算法的分类结果进行数据的后处理。在研究中发现了FN算法中常见的错误类型,并提出了3种不同的解决方案,使得最终结果更加符合实际,达到更好的聚类效果。在部分案例中准确率可提高至100%。

加权Fast Newman模块化算法在人脑结构网络中的应用

针对二值人脑结构网络的模块化方法不足以反映复杂的人脑生理特征这一问题,提出一种基于Fast Newman二值算法的加权脑网络模块化算法。该算法以凝聚节点的层次聚类思想为基础,以脑网络中单个脑区节点的权重值和脑网络总权重值为主要依据构建加权模块度评价指标,并将其增量作为度量值来确定加权脑网络中节点的合并从而实现模块划分。将该算法应用于60个健康人的组平均数据中的实验结果显示,与二值人脑网络模块化结果相对比,所提算法得到的模块度提高了28%,并且模块内部和模块外部的特征区分更加明显,所得到的人脑模块也更符合已知的人脑生理特性;而与现有的两种加权模块化算法实验对比结果表明,所提算法在合理划分人脑网络模块结构的同时也小幅提高了模块度。

一种基于改进的Newman快速算法的文本聚类方法

针对文本聚类计算量大的特点,提出了一种将概念格和Newman快速算法两种理论相结合的聚类方法。首先将文本表示为特征词语集,用统计方法抽取特征向量;同时,用IDF权重计算公式来计算词语的权重,并将词语权值离散化;然后,用形式背景表达关键词,通过相似度公式,计算出形式概念相似度大小;最后,构造Newman网络,根据Newman网络算法规则对待聚类文本进行聚类。实例表明,该算法不仅得到了正确的分类结果,而且大大降低了算法的复杂度,Newman快速算法仅为O((m+n)n)。

基于含权Newman算法的交通控制子区划分

为使交通网络控制子区内的交通流具有更好的同质性,本文将道路网络中的路段抽象为点,相邻路段之间的连接关系抽象为边,形成一个对偶的网络拓扑结构图。以用户均衡交通分配得到的路段交通流数据除以路段长度计算得到路段的“拟交通密度”;通过引入路段拟交通密度,扩展了Newman子区划分算法。最后,选取实际路网、以NSK (Normalized cut Silhouette)指标验证K均值聚类算法、传统Newman算法和扩展的Newman子区划分算法的优劣。研究发现:传统K均值聚类算法得到的各子区NSK指标和路网NSK指标都相对最小,但同一个子区内的路段在空间位置上不相连,没有实际运用价值;扩展的Newman子区划分算法的NSK值优于传统Newman快速划分算法,证实引入了路段拟交通密度作为边权,使得划分出来的结果更加符合交通网络的特性。

基于复杂网络Newman快速算法的船舶柴油机故障诊断

将船舶柴油机故障诊断中的聚类问题转化为复杂网络社团发现问题,在定义线性相似度、反比相似度、指数相似度和椭圆相似度函数的基础上,构造以相似度权重为边权,以样本点为节点的加权无向网络,提出了利用Newman快速算法中的准则函数作为聚类的准则函数,逐步寻找网络中的社团结构的故障诊断方法。以自主研发的轮机模拟器主机系统故障数据为例进行故障分析与诊断,验证新方法的有效性,并分析阈值和相似度系数变化对方法性能的影响。研究结果表明:新故障诊断方法具有计算量小和准确性高且运算时间短的特点,能够达到在线诊断的要求,有识别未知故障的能力,解决了聚类中必须找到类的问题。

基于Newman快速算法的航运网络社团结构

为了研究航运网络的网络结构及其相关特性,以航运网络的社团结构为对象研究,构建了基于模块度的Newman快速算法。选择由453个港口和3 444条边构成的"二十一世纪海上丝绸之路"(简称"海丝之路")无向无权航运网络为案例,从航运网络连接性视角,采用Newman快速算法对"海丝之路"航运网络进行计算,得出该航运网络的社团结构性质:网络中只有一个由173个港口节点构成的核心社团,且为领导者社团,度值接近于幂律分布,其他均为小型社团,表明"海丝之路"集装箱航运网络为巨型社团结构,且具有核心节点。

基于Newman快速算法的中国航空网络社团结构研究

研究中国航空网络的复杂特性,探究网络内部的演变规律和发展趋势,有助于航线结构调整和后续政策制定等。以2012-2017年航空网络为研究对象,构建拓扑结构并基于R平台,采用Newman快速算法分析社团结构及内部特征。研究结果显示,中国航空网络符合小世界特性且有向无标度网络演化的趋势;网络中存在核心节点,且逐步形成以北上广为三大中心枢纽,核心节点为区域枢纽的机场群格局,研究为机场群打造中枢辐射型航空网络构建提供了实证基础。

融合改进关联度与Newman算法的区域交通划分研究

针对区域路网复杂度高、现有子区动态划分方法的不足,以优化区域协调控制为目标,提出一种基于引入改进关联度模型的改进Newman算法的区域路网动态划分方法。综合分析车队离散性和车流密度两种因素,提出了一种改进关联度模型;以模块度Q为划分标准,将交叉口关联度作为边权,改进传统的无权社团凝聚算法,使其能够依据交通流特性将路网动态划分为不同子区。仿真实验结果表明,所提出的改进划分方法能够有效结合实际交通流特性,对路网子区进行更加准确的实时动态划分。

一种基于Newman快速算法改进的社团划分算法

社团划分目前是从海量科技文献中进行知识组织和发现的一种重要方法,其中Newman快速算法是目前效率较高的一种社团划分算法,然而由于Newman快速算法是一种基于局部搜索算法,算法的结果集往往是局部最优而不是全局最优,导致科技文献关系网络中的社团划分结果往往不是最优的社团结构。根据网络图中社团结构拓扑关系的特点,提出了社团贡献度的概念,并给出了计算公式;同时,为了克服Newman快速算法在社团合并迭代过程中获取到局部最优解而终止迭代的缺点,提出一种直接以社团贡献度为社团合并条件的CCN算法。最后在MATLAB环境中,用实际网络数据进行对比实验验证,结果表明,改进的CCN算法在社团划分效率和Q值结果上有更理想的效果。

图T(F_(n,8),P_m)奇优美标号算法及实现

给出了图T(F_(n,8),P_m)的定义,提出了该类图的计算机标号算法,理论证明了这种算法的正确性,从而说明图T(F_(n,8),P_m)是奇优美图;最后,编制了"图T(F_(n,8),P_m)奇优美标号算法"程序,并通过大量实验数据说明利用该算法给图T(F_(n,8),P_m)进行奇优美标号是行之有效的.

基于社团结构的文本聚类算法研究

为了提高文本聚类的有效性,提出一种基于网络社团结构的文本聚类算法。基于语义知识库理论,利用文本集与词语间的关系,引入文本相似度概念,再结合Newman社团聚类算法特性,将文本集作为独立社团,用文本相似度表示社团联系的紧密程度,对网络文本进行聚类。实验结果表明,该方法有效可行。

FNS技术

本文介绍了功能性神经肌肉电刺激(FNS)基本原理,针对的其中的几个关键问题,提出了研究的方案,并对FNS测控实验结果进行了分析.

一种基于适度贪心算法思路的社团划分改进方法

当前问题背景下贪心算法存在不足,由此提出一种适度贪心的算法思路,引入适度原则,约束贪婪幅度,以避免过度贪婪、谬误累积的情况,并将适度贪心算法思路应用于FN社团划分算法的改进研究,构建了一种新的网络社团区划算法.通过算例对提出的算法进行了测试与分析,实验结果验证了新算法的可行性与有效性.

图F_(n,8)的奇优美性及标号算法

本文给出了图Fn,8的定义,证明了它们都是奇优美图;给出这类图奇优美标号算法;证明了该算法的时间复杂度为O(N),而且证明了该算法的时间最优性.

基于复杂网络的社区划分算法分析

近年来,复杂网咯吸引了大量的学者,作为一个新兴起来的学科,来自各个领域的学者们都开始对其进行研究分析。社区划分是复杂网络的重要特征之一。针对复杂网络中社区划分问题,对三种的社区划分算法进行了研究,传统GN算法、FN算法和谱聚类算法,分别阐述了各种算法的基本原理,并对这两种算法基于真实世界网络模型进行了适当的分析和比较,选取出较为高效的谱聚类算法,用于现实世界复杂网络中的社区划分,为实际应用中社区划分算法的认识与应用提供了方法参考。