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.

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.

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.

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.

MEAN-VARIANCE MODEL BASED ON FILTERS OF MINIMUM SPANNING TREE

This study aims to reduce the statistical uncertainty of the correlation coefficient matrix in the mean-variance model of Markowitz. A filtering algorithm based on minimum spanning tree （MST） is proposed. Daily data of the 30 stocks of the Hang Seng Index （HSI） and Dow Jones Index （DJI） from 2004 to 2009 are selected as the base dataset. The proposed algorithm is compared with the Markowitz method in terms of risk, reliability, and effective size of the portfolio. Results show that （1） although the predicted risk of portfolio built with the MST is slightly higher than that of Markowitz, the realized risk of MST filtering algorithm is much smaller; and （2） the reliability and the effective size of filtering algorithm based on MST is apparently better than that of the Markowitz portfolio. Therefore, conclusion is that filtering algorithm based on MST improves the mean-variance model of Markowitz.

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.

Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.

Investigating the Disparities of China's Insurance Market Based on Minimum Spanning Tree from the Viewpoint of Geography and Enterprise

In this paper, we investigate the disparities of China’s insurance market from the viewpoint of geography and enterprise by using the monthly data from January 2006 to December 2015. We divide the whole insurance market into two parts, namely property insurance and personal insurance.By constructing and analyzing minimum spanning trees of insurance market, we obtain the results as follows:(i) The connections between provinces are much closer than those of firms, and there are regional links between neighboring provinces in the minimum spanning tree(MST); and(ii) the domestic funded firms and foreign funded firms form two explicit clusters in the MSTs of property and personal insurance market.

Minimum Spanning Trees Across Well-Connected Cities and with Location-Dependent Weights

Consider n nodes{X_(i)}_(1≤i≤n) independently and identically distributed(i.i.d.)across N cities located within the unit square S.Each city is modelled as an r_(n)×r_(n)square,and MSTC_(n)denotes the weighted length of the minimum spanning tree containing all the n nodes,where the edge length between nodes X_(i)and X_(j)is weighted by a factor that depends on the individual locations of X_(i)and X_(j).We use approximation methods to obtain variance estimates for MSTC_(n)and prove that if the cities are well connected in a certain sense,then MSTC_(n)appropriately centred and scaled converges to zero in probability.Using the above proof techniques we also study MST_(n),the length of the minimum weighted spanning tree for nodes distributed throughout the unit square S with location-dependent edge weights.In this case,the variance of MST_(n)grows at most as a power of the logarithm of n and we use a subsequence argument to get almost sure convergence of MST_(n),appropriately centred and scaled.

Finding Cut-Edges and the Minimum Spanning Tree via Semi-Tensor Product Approach

Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.

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.

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)).

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.

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

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

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

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

基于改进Prim算法的路径规划研究

文中提出一种基于聚类分析改进Prim(普里姆)最小生成树的路径规划算法,采用二分法将站网中的站点先聚类,分成多个微小的站点聚类中心,再以各聚类中心进行Prim最小生成树的路径规划,量化站网空间分布特征,通过聚类增强最小生成树,达到路径优化的目的。实践结果证明,改进的Prim算法适用于大型稠密的站网,在稠密的连通图中,只要调整指数进而控制聚类中心的数量,就能简化站网布局,降低算法的空间复杂度,达到更好的实际应用。

面向空地中继网络优化的无人机运动控制方法

本文提出一种基于模型的通信中继无人机运动控制方法,旨在提高地面车辆编队的网络连通性和通信性能。通过联合考虑未知多用户移动性、环境对信道特性的影响以及接收信号的不可用到达角信息来解决中继无人机运动控制问题。该方法主要由两部分构成:①利用图论中的最小生成树构建网络连接性并定义通信性能指标,该网络连接性同时考虑了地面节点与无人机的通信链路及地面节点与地面节点的通信链路;②针对移动节点的通信中继,提出一种改进粒子群优化(particle swarm optimization,PSO)和非线性模型预测控制(nonlinear model predictive control,NMPC)相结合的中继无人机运动控制策略,其中移动节点的未来位置由卡尔曼滤波器进行预测。在单一环境和复杂环境下的仿真结果表明,所提出的运动控制方法可以驱使无人机到达或跟踪最优中继位置的运动并提高网络性能,同时论证了考虑环境对信道的影响是有益的。

格式塔原则下的建筑群空间分布智能理解

在格式塔原则下对建筑群进行聚类是计算机理解建筑群空间分布特征并实现地图自动综合的基础.在格式塔原则约束下,首先,利用最小生成树的阈值聚类及参数聚类,实现了对集中和分散均匀排列建筑群空间分布特征的挖掘,并利用C_(v)^(-)值定量评价了挖掘质量;其次,提出了阈值聚类和参数聚类的异同,以及阈值聚类具有局限性的原因;最后,根据建筑物语义特征获得最终聚类结果.试验表明:1)传统的MST阈值聚类不能维持分散均匀排列建筑群的空间分布特征;2)MST参数聚类的适应性要高于阈值聚类,更加符合人类的视觉认知.该方法更有助于提高计算机对建筑群空间分布的智能理解能力.

基于局部密度峰和标签传播的最小生成树聚类

基于最小生成树(minimum spanning tree,MST)的聚类算法能够识别具有任意形状的簇,该算法在如何有效构建最小生成树和识别无效边方面存在不足,而且易受到噪声点影响.本文利用密度峰值聚类算法思想的优点来寻找局部密度峰,局部密度峰在保留原始数据集分布结构的同时,排除了噪声点,因此,将局部密度峰与最小生成树聚类算法相结合,采用标签传播,提出了基于局部密度峰和标签传播的最小生成树聚类算法(DPMST).该算法采用了局部密度峰之间基于共享邻的距离,利用局部密度峰之间的邻域信息,有效构造最小生成树和识别无效边,使算法能够发现具有复杂结构的簇.标签传播增强强标签,削弱弱标签,以细化错误的标签,特别是对于边界点以及揭示复杂流形,能够提高聚类结果的质量.人工和真实数据集上的实验结果表明,与经典聚类算法DPC、MST、K-means、DBSCAN、AP、SC和BIRCH比较,DPMST算法表现优异.