Transport properties of a complex network can be reflected by the two-point resistance between any pair of two nodes. We systematically investigate a variety of typical complex networks encountered in nature and techn...Transport properties of a complex network can be reflected by the two-point resistance between any pair of two nodes. We systematically investigate a variety of typical complex networks encountered in nature and technology, in which we assume each link has unit resistance, and we find for non-sparse network connections a universal relation exists that the two-point resistance is equal to the sum of the inverse degree of two nodes up to a constant. We interpret our observations by the localization property of the network＇s Laplacian eigenvectors. The findings in this work can possibly be applied to probe transport properties of general non-sparse complex networks.展开更多
Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L（G） of G. As L...Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L（G） of G. As L（G） is positive semidefinite, the singularity of L（G） is determined by its least eigenvalue λ1 （G）. This paper introduces a new parameter edge singularity εs（G） that reflects the singularity of L（G）, which is the minimum number of edges of G whose deletion yields that all the components of the resulting graph are singular. We give some inequalities between εs（G） and λ1 （G） （and other parameters） of G. In the case of εs（G） = 1, we obtain a property on the structure of the eigenvectors of G corresponding to λ1 （G）, which is similar to the property of Fiedler vectors of a simple graph given by Fiedler.展开更多
An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discret...An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discrete constraints in the original problem with one single continuous constraint. A feasible direction method is designed to solve the resulting nonlinear programming problem. The method employs only the gradient evaluations of the objective function, and no any matrix calculations and no line searches are required. This greatly reduces the calculation cost of the method, and is suitable for the solution of large size max-cut problems. The convergence properties of the proposed method to KKT points of the nonlinear programming are analyzed. If the solution obtained by the proposed method is a global solution of the nonlinear programming problem, the solution will provide an upper bound on the max-cut value. Then an approximate solution to the max-cut problem is generated from the solution of the nonlinear programming and provides a lower bound on the max-cut value. Numerical experiments and comparisons on some max-cut test problems （small and large size） show that the proposed algorithm is efficient to get the exact solutions for all small test problems andwell satisfied solutions for most of the large size test problems with less calculation costs.展开更多
基金Supported by Natural Science Foundation of Department of Education of Anhui Province and the Projectof Anhui University for Talents Gruop Construction.
基金supported by the National Natural Science Foundation of China(Grant Nos.11305268 and 11465017)
文摘Transport properties of a complex network can be reflected by the two-point resistance between any pair of two nodes. We systematically investigate a variety of typical complex networks encountered in nature and technology, in which we assume each link has unit resistance, and we find for non-sparse network connections a universal relation exists that the two-point resistance is equal to the sum of the inverse degree of two nodes up to a constant. We interpret our observations by the localization property of the network＇s Laplacian eigenvectors. The findings in this work can possibly be applied to probe transport properties of general non-sparse complex networks.
基金Supported by the Fundamental Research Funds for the Central Universities and National Natural Science Foundation of China(61272008,11271348,10871189)
基金National Natural Science Foundation of China (10601001)Anhui Provincial Natural Science Foundation (050460102)+3 种基金NSF of Department of Education of Anhui province (2004kj027,2005kj005zd)Foundation of Anhui Institute of Architecture and Industry (200510307)Foundation of Innovation Team on Basic Mathematics of Anhui UniversityFoundation of Talents Group Construction of Anhui University
文摘Let G be a mixed glaph which is obtained from an undirected graph by orienting some of its edges. The eigenvalues and eigenvectors of G are, respectively, defined to be those of the Laplacian matrix L（G） of G. As L（G） is positive semidefinite, the singularity of L（G） is determined by its least eigenvalue λ1 （G）. This paper introduces a new parameter edge singularity εs（G） that reflects the singularity of L（G）, which is the minimum number of edges of G whose deletion yields that all the components of the resulting graph are singular. We give some inequalities between εs（G） and λ1 （G） （and other parameters） of G. In the case of εs（G） = 1, we obtain a property on the structure of the eigenvectors of G corresponding to λ1 （G）, which is similar to the property of Fiedler vectors of a simple graph given by Fiedler.
基金This work is supported by National Natural Science Foundation of China at 10231060.
文摘An effective continuous algorithm is proposed to find approximate solutions of NP-hard max-cut problems. The algorithm relaxes the max-cut problem into a continuous nonlinear programming problem by replacing n discrete constraints in the original problem with one single continuous constraint. A feasible direction method is designed to solve the resulting nonlinear programming problem. The method employs only the gradient evaluations of the objective function, and no any matrix calculations and no line searches are required. This greatly reduces the calculation cost of the method, and is suitable for the solution of large size max-cut problems. The convergence properties of the proposed method to KKT points of the nonlinear programming are analyzed. If the solution obtained by the proposed method is a global solution of the nonlinear programming problem, the solution will provide an upper bound on the max-cut value. Then an approximate solution to the max-cut problem is generated from the solution of the nonlinear programming and provides a lower bound on the max-cut value. Numerical experiments and comparisons on some max-cut test problems （small and large size） show that the proposed algorithm is efficient to get the exact solutions for all small test problems andwell satisfied solutions for most of the large size test problems with less calculation costs.
