The Neighbor Matrix: generalizing the degree sequence
Roginski, Jonathan W.
Gera, Ralucca M.
Rye, Eric C.
MetadataShow full item record
The newly introduced neighborhood matrix extends the power of adjacency and distance matrices to describe the topology of graphs. The adjacency matrix enumerates which pairs of vertices share an edge and it may be summarized by the degree sequence, a list of the adjacency matrix row sums. the distance matrix shows more information, namely the length of shortest paths between vertex pairs. We introduce and explore the neighborhood matrix, which we have found to be an analog to the distance matrix what the degree sequence is to the adjacency matrix. The neighborhood matrix includes the degree sequence as its first column and the sequence of all other distances in the graph up to the graph's diameter, enumerating the number of neighbors each vertex has at every distance present in the graph. We prove this matrix to contain eleven oft-used graph statistics and topological descriptors. We also provide proofs of concept for two applications that show potential utility of the neighbor matrix in comparing graphs and identifying topologically significant vertices in a graph.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Florkowski, Stanley F. (Monterey, California. Naval Postgraduate School, 2008-12);In Graph Theory, every graph can be expressed in terms of certain real, symmetric matrices derived from the graph, most notably the adjacency or Laplacian matrices. Spectral Graph Theory focuses on the set of eigenvalues ...
DeHaemer, Michael Joseph (Monterey, California; Naval Postgraduate School, 1970-04);A branch-and-bound algorithm, which finds the optimal route through n nodes when a different cost matrix occurs after each arc in the sequence is traversed, is presented. The route may begin at any node and must pass ...
Matty, Douglas M. (Monterey, California. Naval Postgraduate School, 1999-06);A commonly studied problem in the field of cryptography is the Discrete Logarithm Problem. This problem is also referred to as the "distance" problem. Basically, one would like to know where a particular binary n-tuple is ...