THE DISTANCE CENTRALITY: MEASURING STRUCTURAL DISRUPTION OF A NETWORK
Roginski, Jonathan W.
Borges, Carlos F.
Rasmussen, Craig W.
Alderson, David L. Jr.
Everton, Sean F. F.
MetadataShow full item record
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.
Approved for public release. distribution is unlimited
Showing items related by title, author, creator and subject.
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 ...
Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without K5 minors Solus, Liam; Uhler, Caroline; Yoshida, Ruriko (Elsevier, 2016);For a graph G with p vertices the closed convex cone S≽0(G) consists of all real positive semidefinite p × p matrices whose sparsity pattern is given by G, that is, those matrices with zeros in the off-diagonal entries ...
Krahn, Gary William (Monterey, California. Naval Postgraduate School, 1994-06);A binary de Bruijn sequence has the property that every n-tuple is distinct on a given period of length 2". An efficient algorithm to generate a class of classi- cal de Bruijn sequences is ...