Brain Functional Network Based on Small-Worldness and Minimum Spanning Tree for Depression Analysis

Since the outbreak and spread of corona virus disease 2019(COVID-19),the prevalence of mental disorders,such as depression,has continued to increase.To explore the abnormal changes of brain functional connections in patients with depression,this paper proposes a depression analysis method based on brain function network(BFN).To avoid the volume conductor effect,BFN was constructed based on phase lag index(PLI).Then the indicators closely related to depression were selected from weighted BFN based on small-worldness(SW)characteristics and binarization BFN based on the minimum spanning tree(MST).Differences analysis between groups and correlation analysis between these indicators and diagnostic indicators were performed in turn.The resting state electroencephalogram(EEG)data of 24 patients with depression and 29 healthy controls(HC)was used to verify our proposed method.The results showed that compared with HC,the information processing of BFN in patients with depression decreased,and BFN showed a trend of randomization.

SOLVING MINIMUM SPANNING TREE PROBLEM WITH DNA COMPUTING

Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

High-resolution Remote Sensing Image Segmentation Using Minimum Spanning Tree Tessellation and RHMRF-FCM Algorithm

It is proposed a high resolution remote sensing image segmentation method which combines static minimum spanning tree(MST)tessellation considering shape information and the RHMRF-FCM algorithm.It solves the problems in the traditional pixel-based HMRF-FCM algorithm in which poor noise resistance and low precision segmentation in a complex boundary exist.By using the MST model and shape information,the object boundary and geometrical noise can be expressed and reduced respectively.Firstly,the static MST tessellation is employed for dividing the image domain into some sub-regions corresponding to the components of homogeneous regions needed to be segmented.Secondly,based on the tessellation results,the RHMRF model is built,and regulation terms considering the KL information and the information entropy are introduced into the FCM objective function.Finally,the partial differential method and Lagrange function are employed to calculate the parameters of the fuzzy objective function for obtaining the global optimal segmentation results.To verify the robustness and effectiveness of the proposed algorithm,the experiments are carried out with WorldView-3(WV-3)high resolution image.The results from proposed method with different parameters and comparing methods(multi-resolution method and watershed segmentation method in eCognition software)are analyzed qualitatively and quantitatively.

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).

Salience adaptive morphological structuring element construction method based on minimum spanning tree

Classical mathematical morphology operations use a fixed size and shape structuring element to process the whole image.Due to the diversity of image content and the complexity of target structure,for processed image,its shape may be changed and part of the information may be lost.Therefore,we propose a method for constructing salience adaptive morphological structuring elements based on minimum spanning tree(MST).First,the gradient image of the input image is calculated,the edge image is obtained by non-maximum suppression(NMS)of the gradient image,and then chamfer distance transformation is performed on the edge image to obtain a salience map(SM).Second,the radius of structuring element is determined by calculating the maximum and minimum values of SM and then the minimum spanning tree is calculated on the SM.Finally,the radius is used to construct a structuring element whose shape and size adaptively change with the local features of the input image.In addition,the basic morphological operators such as erosion,dilation,opening and closing are redefined using the adaptive structuring elements and then compared with the classical morphological operators.The simulation results show that the proposed method can make full use of the local features of the image and has better processing results in image structure preservation and image filtering.

A Novel Binary Firefly Algorithm for the Minimum Labeling Spanning Tree Problem

Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.

The Design of the Minimum Spanning Tree Algorithms

Based on the graphic theory and improved genetic algorithm,an improved genetic algorithm to search the minimum spanning trees is given . The algorithm uses binary code to represent the problem of minimum spanning trees. It designs the corresponding fitness function,operator and few controlling strategies to improve its speed and evolutionary efficiency.Only one solution can be gotten with running traditional al-gorithem atone time.The new algorithm can get a set of the solutions with higher probability in a shorter time.The experiment shows that it has a better performance than traditional methods.

On the Minimum Spanning Tree Determined by n Points in the Unit Square

Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.

基于MST-改进PSO的电-气-热综合能源系统负荷恢复策略

以往故障恢复的研究大多集中在配电网方面且恢复目标仅为单一的负荷恢复量,未考虑资源成本以及能源消耗的环境保护成本等。对此,提出一种多侧协调优化的多目标负荷恢复策略,该方法不仅实现了网络的重构、较高等级负荷的优先恢复,还实现了系统运行成本最优。在系统发生故障后,分两阶段进行恢复:首先,使用最小生成树(minimum spanning tree,MST)对系统结构进行改造,实现系统网络的重构,形成可恢复负荷的最终区域;然后,综合考虑源侧资源购买成本、用户侧切负荷补偿成本以及碳排放环保成本等,构建优化目标函数,使用改进粒子群(particle swarm optimization,PSO)算法对其进行求解,得到最终恢复方案。通过33节点配电网、14节点气网和6节点热网测试系统仿真,验证了该负荷恢复策略的有效性。

基于最小Spanning树的中继节点部署算法

在能量受限的无线传感器网络(WSNs)中,部署中继节点成为确保通信覆盖的常用方法。提出基于最小Spanning树的中继节点部署算法(MST-DRN)。MST-DRN算法引用基于无线充电的能量模型。再依据节点的能量采集率计算边权值。依据边权值的图模型构建最小Spanning树(MST)。检测MST中不满足生存条件的非支叶节点,在节点附近部署中继节点,维持网络连通。实验数据表明:提出的MST-DRN算法在确保网络连通时,减少了成本(中继节点数),并提高了数据包传递率。

NeuroPrim:An attention-based model for solving NP-hard spanning tree problems

Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.

融合局部搜索策略求解DCMST的改进稳态遗传算法

针对目前遗传算法求解度约束最小生成树存在的求解质量不稳定、局部搜索不完全的问题,提出一种融合局部搜索策略求解度约束最小生成树(DCMST)的改进稳态遗传算法。提出服从边隶属度值的度约束初始生成树算法,用来提高初始种群的质量;在局部搜索时引入禁忌搜索,防止相似解大量重复搜索;融合自适应变量和点替换的局部搜索方法,提升算法的局部搜索能力。仿真结果表明,提出的算法提高了初始解的质量,加快了算法的收敛速度,加强局部搜索从而提高了算法的求解质量,可获得较好的有效性与稳定性。

融合均值榜样的反向互学习水母搜索算法

为解决水母搜索算法(jellyfish search algorithm,JS)的洋流运动缺乏多样性、群内运动缺乏引导性、种群间信息无交流,造成搜索速度慢、稳定性差及易早熟的问题,构建了一种融合均值榜样的反向互学习水母搜索算法(oppositional-mutual learning jellyfish search algorithm based on mean-value example,OMLJS).首先在水母跟随洋流运动(全局搜索)部分,利用前两代水母的平均位置代替只考虑上一代水母的平均位置来引导水母个体的位置更新,提高算法的全局搜索能力;其次在水母的群内主动运动(局部搜索)部分,利用最优个体代替随机个体来引导水母进行更有效的搜索,加快算法的收敛速度;然后在水母进入下一次迭代前增加对水母种群进行动态反向互学习步骤,增加种群多样性及增强种群间的信息交流,达到互补另外两个策略,提高算法的整体优化性能.选用12个经典的基准测试优化函数,将OMLJS与5个对比算法从解的平均值、最优值及方差进行对比分析,并用于求解最小生成树问题,OMLJS能够更快地找到最小生成树.实验结果表明,OMLJS的收敛速度、求解精度明显提高.

原油价格不确定性测度及其对宏观经济的非对称影响研究

有效测度原油价格不确定性并研究其对我国宏观经济的影响,具有重要的理论和现实意义。本文基于最小生成树模型,从全局视角衡量原油多元定价机制中195个影响因素的相对重要程度,并采用高维因子非预期条件波动率模型测度国际原油价格的不确定性。基于收敛交叉映射模型,本文对原油价格不确定性与宏观经济间的非线性因果关系进行识别,研究发现仅存在原油价格不确定性对固定资产投资、产出增速的单向因果关系。进一步地,在厘清原油价格不确定性对宏观经济影响机制的基础上,利用包含马尔可夫区制转移特征的向量自回归模型考察原油价格不确定性对我国宏观经济的影响,理论与实证结果均表明原油价格不确定性对我国宏观经济具有显著负向影响;在不同经济状态下,原油价格不确定性对投资、产出增速的影响具有非对称性。本研究为有效防范原油市场风险、保障能源安全和推动经济稳定增长提供了理论支持。

基于MST的辽宁省上市公司风格聚集研究

在风格投资分析中,传统的参数分析方法将带来分析结果的多样性,为此提出了采用具有准确拓扑序列的亚超度量空间方法.首先,计算出股票间任意两个股价间的相关系数,并在此基础上计算出超度量空间的欧式距离;其次,利用Kruskal的最小生成树算法,构建出证券组合的亚超度量空间;最后,将亚超度量空间映射为指数分层结构.对2005年7月至2007年12月的辽宁省上市公司样本的日数据进行实证研究,结果发现存在行业风格、事件风格、业绩风格及现金流风格,这表明亚超度量空间方法是有效的.

结合mean-shift与MST的K-means聚类算法

针对初始点选择不当导致K-means陷入局部最小值问题,提出一种结合自适应mean-shift与最小生成树(MST)的K-means聚类算法。将数据对象投影到主成分分析(PCA)子空间,给出自适应mean-shift算法,并在PCA子空间内将数据向密度大的区域聚集,再利用MST与图连通分量算法,找出数据的类别数和类标签,据此计算原始空间的密度峰值,并将其作为K-means聚类的初始中心点。对K-means的目标函数、聚类精度和运行时间进行比较,结果表明,该算法在较短的运行时间内能给出较优的全局解。

度约束最小生成树(DCMST)的竞争决策算法

度约束最小生成树是网络设计和优化中的一个NP难题,介绍了一种基于竞争造就优化和决策左右结果的新型算法———竞争决策算法,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想求解度约束最小生成树的快速求解方法,经过数据测试和验证,并与其它算法的结果进行了比较,得到了较好的结果.

基于MST算法的离散数据解缠方法研究

在对不规则网格中残差计算的性质进行分析的基础上,提出了用于离散数据的相位解缠的MST-FloodFill方法,该方法利用Delaunay三角网连接离散数据,在每个三角形中计算残差值,通过最小跨越树（MST）算法建立正负残差平衡的最小生成树,利用FloodFill算法绕过枝切线进行积分得到离散数据的解缠相位,从而实现离散数据的相位解缠。利用模拟数据和真实数据进行的实验以及将所得结果与真实结果进行的比对显示,利用这种离散数据解缠方法得出的结果完全正确,而且有较高的解缠效率,从而验证了该方法对于离散数据解缠的正确性和有效性。

银行信贷资产证券化信用风险度量及传染研究——基于修正KMV模型和MST算法的实证

精准科学地度量和描述信用风险及传染机制有利于银行信贷资产证券化的高效健康发展和货币市场系统性风险的防范。运用修正KMV模型测度银行信贷资产证券化产品在不同时期的信用风险,并采用最小生成树(MST)算法考察银行间信用风险的传染机制。结果显示:政策性银行和大型商业银行发行的产品在各个时期信用风险均处于较低水平;股份制银行、城商行和农商行发行的产品违约率前期略高于前两类银行,但后期明显下降;后三类银行位于银行股票收益率网络的中心位置,具有传递信息和维系网络稳定的重要作用。