Distributed Computation of Graph Spectrum, Eigenvector Centrality, and Solution to Linear Equations

Yang, Mu

Distributed Computation of Graph Spectrum, Eigenvector Centrality, and Solution to Linear Equations

dc.contributor.advisor	Tang, Choon Yik
dc.contributor.author	Yang, Mu
dc.contributor.committeeMember	Cruz, J. R.
dc.contributor.committeeMember	Lakshmivarahan, S.
dc.contributor.committeeMember	Thulasiraman, Krishnaiyan
dc.contributor.committeeMember	Runolfsson, Thordur
dc.date.accessioned	2017-12-18T14:53:23Z
dc.date.available	2017-12-18T14:53:23Z
dc.date.issued	2017-12-15
dc.date.manuscript	2017-12-15
dc.description.abstract	This dissertation is devoted to the development of distributed algorithms, with which nodes in a large decentralized network can accomplish tasks that are seemingly difficult without an omniscient central node. The tasks include estimating the graph spectrum, from which each node can draw its own conclusion about the network structure, computing the eigenvector centrality, from which every node can judge its own importance in the network, and solving a system of linear equations whose data are scattered across the network or discovering that no solution exists. The ability to perform these tasks enhances the capability of existing and emerging networks such as smart power grids, social networks, and ad hoc sensor networks, potentially allowing them to function in ways that are not previously thought to be possible. We begin with the design of a novel, two-stage distributed algorithm that enables nodes in an undirected and connected graph to jointly estimate the spectrum of a matrix associated with the graph, which includes the adjacency and Laplacian matrices as special cases. In the first stage, the algorithm uses a discrete-time linear iteration and the Cayley-Hamilton theorem to convert the problem into one of solving linear equations, where each equation is known to a node. In the second stage, if the nodes happen to know that said matrix is cyclic, the algorithm uses a Lyapunov approach to asymptotically solve the equations with an exponential rate of convergence. Otherwise, it uses a random perturbation approach and a structural controllability result to approximately solve the equations with an error that can be made small. We then consider the fundamental problem of cooperatively solving a general system of linear equations over a network, for which a continuous-time distributed algorithm is devised. We show that the algorithm enables the nodes to asymptotically agree on a solution when there are infinitely many solutions, determine the solution when there is exactly one, and detect that no solution exists when there are none. We also establish that the algorithm is globally exponentially convergent, derive an explicit lower bound on its convergence rate that it can do no worse than, and prove that the larger the network's algebraic connectivity, or the further away from being singular the system of equations, the larger this lower bound. Finally, we address the open question of whether it is possible to calculate eigenvector centrality over a network. We provide an affirmative answer by presenting a class of continuous-time distributed algorithms and an asynchronous gossip algorithm, which allow every node $i$ in a graph to compute the $i$th entry of the Perron-Frobenius eigenvector of a symmetric, Metzler, and irreducible matrix induced by the graph, as well as the corresponding eigenvalue, when node $i$ knows only row $i$ of the matrix. We show that each continuous-time distributed algorithm is a nonlinear networked dynamical system with a skew-symmetric structure, whose state is guaranteed to stay on a sphere, remain nonnegative, and converge asymptotically to said eigenvector at an $O(\frac{1}{t})$ rate. We also show that under a mild assumption on the gossiping pattern, the gossip algorithm is able to do the same.	en_US
dc.identifier.uri	https://hdl.handle.net/11244/53080
dc.language	en	en_US
dc.subject	Control	en_US
dc.subject	Distributed Algorithm	en_US
dc.subject	Network System	en_US
dc.subject	Dynamic System	en_US
dc.thesis.degree	Ph.D.	en_US
dc.title	Distributed Computation of Graph Spectrum, Eigenvector Centrality, and Solution to Linear Equations	en_US
ou.group	College of Engineering::School of Electrical and Computer Engineering	en_US