The Neighbor Matrix: Generalizing A Graph’s Degree Sequence
Loading...
Authors
Roginski, Jonathan W.
Gera, Ralucca M.
Rye, Erik C.
Subjects
adjacency matrix
distance
graph topology
centrality
graph power
distance
graph topology
centrality
graph power
Advisors
Date of Issue
2016-08
Date
Publisher
ArXiv
Language
Abstract
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 neighbor 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 insight into two applications that show potential utility of the neighbor matrix in comparing graphs and identifying topologically significant vertices in a graph.
Type
Preprint
Description
Series/Report No
Department
Applied Mathematics
Organization
Identifiers
NPS Report Number
Sponsors
This work was partially funded by a grant from the Department of Defense.
Funder
Format
17 p.
Citation
Roginski, Jonathan W., Ralucca M. Gera, and Erik C. Rye. "The neighbor matrix: Generalizing the degree distribution." arXiv preprint arXiv:1510.06952 (2015).
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.