THE DISTANCE CENTRALITY: MEASURING STRUCTURAL DISRUPTION OF A NETWORK
Author
Roginski, Jonathan W.
Date
2018-06Advisor
Borges, Carlos F.
Rasmussen, Craig W.
Gera, Ralucca
Alderson, David L. Jr.
Everton, Sean F.
Baumgartner, Gerry
Arney, David
Metadata
Show full item recordAbstract
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 “distance profile” of each vertex, identifying the number of vertices at each shortest path length from the given vertex. From the neighbor matrix, we can derive 11 oft-used graph invariants. Distance centrality uses the neighbor matrix to identify how much influence a given vertex has over graph structure by calculating the amount of neighbor matrix change resulting from vertex removal. We explore the distance centrality in the context of three synthetic graphs and three graphs representing actual social networks. Regression analysis enables the determination that the distance centrality contains different information than four current centrality measures (betweenness, closeness, degree, and eigenvector). The distance centrality proved to be more robust against small changes in graphs through analysis of graphs under edge swapping, deletion, and addition paradigms than betweenness and eigenvector centrality, though less so than degree and closeness centralities. We find that the neighbor matrix and the distance centrality reliably enable the identification of vertices that are significant in different and important contexts than current measures.
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 A Graph’s Degree Sequence
Roginski, Jonathan W.; Gera, Ralucca M.; Rye, Erik C. (ArXiv, 2016-08);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 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 Neighbor Matrix: Generalizing A Graph’s Degree Sequence
Roginski, Jonathan W. (Monterey, CA. Naval Postgraduate School, 2017);“Who:” The Neighbor Matrix; What does it do? Describes graph topology; Where: Globally – across the entire graph; When: All graphs; Why: Compact structure containing at least 11 graph invariants and topological descriptors; ...