Graph energy is the energy of the matrix representation of the graph, where the energy of a matrix is the sum of singular values of the matrix. Depending on the definition of a matrix, one can contemplate graph energy, Randi 'c energy, Laplacian energy, distance energy, and many others. Although theoretical properties of various graph energies have been investigated in the past in the areas of mathematics, chemistry, physics, or graph theory, these explorations have been limited to relatively small graphs representing chemical compounds or theoretical graph classes with strictly defined properties. In this paper we investigate the usefulness of the concept of graph energy in the context of large, complex networks. We show that when graph energies are applied to local egocentric networks, the values of these energies correlate strongly with vertex centrality measures. In particular, for some generative network models graph energies tend to correlate strongly with the betweenness and the eigencentrality of vertices. As the exact computation of these centrality measures is expensive and requires global processing of a network, our research opens the possibility of devising efficient algorithms for the estimation of these centrality measures based only on local information.
Matrix spectra and matrix energies find surprising applications in many areas of computer science @cite_49 . For instance, singular values of a matrix can be used to re-construct a matrix from a small set of incomplete entries @cite_25 @cite_47 , a problem common in recommender systems. Another application is graph drawing, where eigenvalues alone provide enough information to produce nice graph visualizations @cite_11 . Graph eigenvalues have been successfully used to generate graph partitioning @cite_34 @cite_29 . For many years graph eigenvalues were used to approximate the distribution of random walks over graphs @cite_42 , with the PageRank algorithm being the most prominent example. Graph eigenvalues have found surprising applications in graph theory with respect to the graph coloring problem @cite_50 and independent set problem @cite_44 . Yet another area of application of matrix energies, far beyond the scope of this overview, is systems structural complexity. A comprehensive work on this subject can be found in @cite_18 .
@cite_18 @cite_29 @cite_42 @cite_44 @cite_49 @cite_50 @cite_47 @cite_34 @cite_25 @cite_11
1483628312 2031481696 2123820077 2014486909 2611328865 1587744656 2134332047 2044348081
We describe a new approximation algorithm for Max Cut. Our algorithm runs in @math time, where @math is the number of vertices, and achieves an approximation ratio of @math . In instances in which an optimal solution cuts a @math fraction of edges, our algorithm finds a solution that cuts a @math fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a @math fraction of edges, our spectral partitioning algorithm finds a set @math of vertices and a bipartition @math of @math such that at least a @math fraction of the edges incident on @math have one endpoint in @math and one endpoint in @math . (This can be seen as an analogue of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, var... Spectral graph theory is the study of the eigenvalues and eigenvectors of matrices associated with graphs. In this tutorial, we will try to provide some intuition as to why these eigenvectors and eigenvalues have combinatorial significance, and will sitn'ey some of their applications. A clothes dryer employs a pivotally mounted resilient spring bracket for tensioning a drive belt which is entrained about a pulley of the dryer drive motor and a rotatable dryer drum, the idler pivoting to a free position upon release of belt tension due to belt breakage or the like. A switch is serially connected in at least one power lead of the drive motor and includes a switch actuator disposed in the path of travel of the spring bracket for direct contact and operation thereby to open the circuit of the motor. The switch is mounted on the base of the dryer by a bracket including a shoulder which extends above the body of the switch and below the extent of the switch actuator to engage the spring bracket immediately subsequent to operation of the switch to prevent damage to the switch. We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys @math for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information. This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as the matrix completion problem, and comes up in a great number of applications, including the famous Netflix Prize and other similar questions in collaborative filtering. In general, accurate recovery of a matrix from a small number of entries is impossible, but the knowledge that the unknown matrix has low rank radically changes this premise, making the search for solutions meaningful. This paper presents optimality results quantifying the minimum number of entries needed to recover a matrix of rank r exactly by any method whatsoever (the information theoretic limit). More importantly, the paper shows that, under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convenient convex program as soon as the number of entries is on the order of the information theoretic limit (up to logarithmic factors). This convex program simply finds, among all matrices consistent with the observed entries, that with minimum nuclear norm. As an example, we show that on the order of nr log(n) samples are needed to recover a random n x n matrix of rank r by any method, and to be sure, nuclear norm minimization succeeds as soon as the number of entries is of the form nr polylog(n). In this paper the solution to the problem of placing n connected points (or nodes) in r-dimensional Euclidean space is given. The criterion for optimality is minimizing a weighted sum of squared distances between the points subject to quadratic constraints of the form X'X - 1, for each of the r unknown coordinate vectors. It is proved that the problem reduces to the minimization of a sum or r positive semi-definite quadratic forms which, under the quadratic constraints, reduces to the problem of finding r eigenvectors of a special "disconnection" matrix. It is shown, by example, how this can serve as a basis for cluster identification.