Spectral Graph Theory, Tree Decomposition, and Pseudospectral Graph Theory
Abstract
Network Science is an essential tool for identifying enemies of the United States who might attack with weapons of mass destruction. Our proposal outlined two approaches for basic research in networks, spectral graph theory coupled with tree decomposition and pseudospectral graph theory. Following a site visit last November, we re-directed our focus toward the problem of link prediction in networks to more closely meet the anticipated needs of DTRA. A network is a collection of points joined together in pairs by lines. The points are called nodes and the lines are called edges. Network science belongs to the mathematical area of graph theory, which has especially flourished in the past 40 years. Network science can be thought of as the applied side of graph theory and large networks abound in today’s world. Examples are the Internet and social and information networks. Given a specific network, link prediction is concerned with either foretelling the most likely new edge(s) to occur in the near future or to conjecture edge(s) already present that have yet to be observed. Relevant applications are the inference of promising interactions or collaborations within an organization and the prediction of unknown links in a terrorist network. Several methods previously employed are graph distance, most common neighbors, hitting times, page rank methods, etc. The “spectral” methods we have employed rely on the use of characteristic values and vectors of certain matrices associated with the graph. These matrices are square arrays of numbers and we have focused on the well-known Laplacian matrix of a network. Given a network with n nodes labeled with the integers 1 through n, its Laplacian matrix consists of n rows and n columns. Rows are labeled by the index i running from 1 to n and columns by an index j. For distinct i and j, the entry in row i and column j is minus 1 if there is an edge from i to j, and 0 otherwise. Each diagonal entry (entries for which i equals j) is set equal to the positive integer that makes the sum of the entries in that row equal to 0. The Laplacian matrix is symmetric, so its characteristic values and vectors have exceptionally nice properties. The characteristic values of the Laplacian matrix are numbers ranging from 0 to n, and the characteristic vectors associated with the smallest positive characteristic value of the matrix, called Fiedler vectors, reveal remarkable properties of a network when its n entries are used to label the nodes of the network. (Fiedler’s pioneering paper has been cited over 1400 times.) We have adapted the use of Fiedler vectors to link prediction and initial results on small networks show it to be competitive with but not superior to existing methods of link prediction. However, incorporating all characteristic vectors associated with positive characteristic values, each scaled by the reciprocal of its corresponding characteristic value, and, independently, using the ideas of ``sparsification” of the Laplacian matrix, we were led to a new link prediction method expressible in terms of the Moore-Penrose inverse of the Laplacian, a method that can be viewed as “effective resistance” of an associated electrical network. Initial investigations show this method could be superior to existing methods of link prediction. Moreover, there are multiple ways to fine-tune this method as we study larger networks. There is a total of 5 faculty and 7 students actively engaged in research on this grant.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 26, 2016
- Source ID
- HDTRA11510049
Entities
People
- Jeffrey Humpherys
Organizations
- Brigham Young University
- Defense Threat Reduction Agency