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.

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.

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.

Simulating Transport Capacity, Delivery Speed, and Routing Efficiency to Predict Economic Growth

This study uses a simulation-based approach to investigate the impact of delivery delays due to constraints on transport capacity, transit speed, and routing efficiencies on an economy with various levels of interdependency among firms. The simulation uses object-oriented programming to create specialized production, consumption, and transportation classes. A set of objects from each class is distributed randomly on a 2D plane. A road network is then established between fixed objects using Prim’s MST (Minimum Spanning Tree) algorithm, followed by construction of an all-pair shortest path matrix using the Floyd Warshall algorithm. A genetic algorithm-based vehicle routing problem solver employs the all-pair shortest path matrix to best plan multiple pickup and delivery orders. Production units utilize economic order quantities (EOQ) and reorder points (ROP) to manage inventory levels. Hicksian and Marshallian demand functions are utilized by consumption units to maximize personal utility. The transport capacity, transit speed, routing efficiency, and level of interdependence serve as 4 factors in the simulation, each assigned 3 distinct levels. Federov’s exchange algorithm is used to generate an orthogonal array to reduce the number of combination replays from 34 to just 9. The simulation results of a 9-run orthogonal array on an economy with 6 mining facilities, 12 industries, 8 market centers, and 8 transport hubs show that the level of firm interdependence, followed by transit speed, has the most significant impact on economic productivity. The principal component analysis (PCA) indicates that interdependence and transit speed can explain 90.27% of the variance in the data. According to the findings of this research, a dependable and efficient regional transportation network among various types of industries is critical for regional economic development.

TWO IMPROVED GRAPH-THEORETICAL CLUSTERING ALGORITHMS

Graph-theoretical approaches have been widely used for data clustering and image segmentation recently. The goal of data clustering is to discover the underlying distribution and structural information of the given data, while image segmentation is to partition an image into several non-overlapping regions. Therefore, two popular graph-theoretical clustering methods are analyzed, including the directed tree based data clustering and the minimum spanning tree based image segmentation. There are two contributions： （1） To improve the directed tree based data clustering for image segmentation, （2） To improve the minimum spanning tree based image segmentation for data clustering. The extensive experiments using artificial and real-world data indicate that the improved directed tree based image segmentation can partition images well by preserving enough details, and the improved minimum spanning tree based data clustering can well cluster data in manifold structure.

TABLE BASED METHOD FOR COMPETENCE SET EXPANSION

Each directed graph with the asymmetric costs defined over its arcs,can be represented by a table,which we call an expansion table.The basic properties of cycles and spanning tables of the expansion table corresponding to the cycles and spanning trees of the directed graph is first explored.An algorithm is then derived to find a minimum spanning table corresponding to a minimum spanning tree in the directed graph.Finally,how to use the algorithm to find the optimal expansion of competence set and related problems are discussed.

Distribution algorithm of entangled particles for wireless quantum communication mesh networks

With ensured network connectivity in quantum channels, the issue of distributing entangled particles in wireless quantum communication mesh networks can be equivalently regarded as a problem of quantum backbone nodes selection in order to save cost and reduce complexity. A minimum spanning tree（ MST）-based quantum distribution algorithm（ QDMST） is presented to construct the mesh backbone network. First, the articulation points are found,and for each connected block uncovered by the articulation points, the general centers are solved. Then, both articulation points and general centers are classified as backbone nodes and an M ST is formed. The quantum path between every two neighbor nodes on the MST is calculated. The nodes on these paths are also classified as backbone nodes. Simulation results validate the advantages of QDMST in the average backbone nodes number and average quantum channel distance compared to the existing random selection algorithm under multiple network scenarios.

A CAPACITY EXPANSION PROBLEM WITH BUDGET CONSTRAINT AND BOTTLENECK LIMITATION

This paper considers a capacity expansion problem with budget constraint. Suppose each edge in the network has two attributes: capacity and the degree of difficulty. The difficulty degree of a tree T is the maximum. degree of difficulty of all edges in the tree and the cost for coping with the difficulty in a tree is a nondecreasing function about the difficulty degree of the tree. The authors need to increase capacities of some edges so that there is a spanning tree whose capacity can be increased to the maximum extent, meanwhile the total cost for increasing capacity as well as overcoming the difficulty in the spanning tree does not exceed a given budget D*. Suppose the cost for increasing capacity on each edge is a linear function about the increment of capacity, they transform this problem into solving some hybrid parametric spanning tree problems([1]) and propose a strongly polynomial algorithm.

General election effect on the network topology of Pakistan’s stock market: network-based study of a political event

To examine the interdependency and evolution of Pakistan’s stock market,we consider the cross-correlation coefficients of daily stock returns belonging to the blue chip Karachi stock exchange(KSE-100)index.Using the minimum spanning tree network-based method,we extend the financial network literature by examining the topological properties of the network and generating six minimum spanning tree networks around three general elections in Pakistan.Our results reveal a star-like structure after the general elections of 2018 and before those in 2008,and a tree-like structure otherwise.We also highlight key nodes,the presence of different clusters,and compare the differences between the three elections.Additionally,the sectorial centrality measures reveal economic expansion in three industrial sectors—cement,oil and gas,and fertilizers.Moreover,a strong overall intermediary role of the fertilizer sector is observed.The results indicate a structural change in the stock market network due to general elections.Consequently,through this analysis,policy makers can focus on monitoring key nodes around general elections to estimate stock market stability,while local and international investors can form optimal diversification strategies.