Optimization Of Graph Laplacian Eigenvalues And Its Applications

Spectral graph theory is a commonly used research method, and it can describe a graphas a Laplacian matrix. We can get a clearer understanding of graph structure by analyzingits Laplacian matrix and eigenvalues. Especially, increasing the second smaller eigenvalueof Laplacian matrixλ2under certain constraints, always has a practical significance. Andthis problem is a typical convex optimization which can be solved easily. Semi-definiteprogram belongs to convex optimization. Then if a problem can be transferred to semi-definite program, the problem can be solved.The road network design problem is to optimize the road network by selecting pathsto improve or adding paths in the existing road network, under certain constraints, e.g.,the weighted sum of modifying costs. Since its multi-objective nature, the road networkdesign problem is often challenging for designers. Empirically, the smaller diameter aroad network has, the more connected and efcient the road network is. Based on thisobservation, we propose a set of constrained convex models for designing road networkswith small diameters. To be specific, we theoretically prove that the diameter of the roadnetwork, which is evaluated w.r.t the travel times in the network, can be bounded by theλ2in spectral graph theory since that the upper and lower bounds of diameter are inverselyproportional toλ2. Then we can focus on increasingλ2instead of reducing the networkdiameter, under the budget constraints. The above formulation leads to a semi-definiteprogram, in which we can get its global solution easily.Increase influence problem is proposed for marketing in social network. Increaseinfluence problem is about this process: after finishing the influence maximization problem,how to select and increase the influence between individuals, so that the influence and thesales of a product can both be improved, with the constraints in practice (e.g. budget). Alarger rate of information spreading the social network has, and the more information thespecific individuals (e.g. the individuals who have large purchase) get, more product can besold. Increasing theλ2means increasing the rate of information spreading. What’s more,adjusting the stationary distribution of the random walk, can improve the information thespecific individuals get. Then, the objective of increase influence problem can be transferredinto increasing theλ2with a stationary distribution. What’s more, this problem can be transferred into a semi-definite program,in which we can get its result easily.