The Neighbor Matrix: Generalizing A Graph’s Degree Sequence

Download
Author
Roginski, Jonathan W.
Gera, Ralucca M.
Rye, Erik C.
Date
2016-08Metadata
Show full item recordAbstract
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.
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
The Neighbor Matrix: generalizing the degree sequence
Roginski, Jonathan W.; Gera, Ralucca M.; Rye, Eric C. (American Mathematical Society, 2015-10-19);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 ... -
THE DISTANCE CENTRALITY: MEASURING STRUCTURAL DISRUPTION OF A NETWORK
Roginski, Jonathan W. (Monterey, CA; Naval Postgraduate School, 2018-06);This research provides an innovative approach to identifying the influence of vertices on the topology of a graph by introducing and exploring the neighbor matrix and distance centrality. The neighbor matrix depicts the ... -
Network monitoring method using phantom nodes
Johnson, Jamie Lynn; Parker, Thomas; Tummala, Murali; McEachen, John C. (The United States of America as represented by the Secretary of the Navy, Washington, DC (US), 2018-05-01);Determining flow rules in a software defined network (SDN) of a plurality of forwarding devices includes determining, by a controller device, a network adjacency matrix of the SDN, wherein the network adjacency matrix ...