Efficient Measuring of Node Centrality by Detecting Bridges and Communities

Sol Kim
Farragut High School

Abstract

Finding node centrality has significant applications to the real world. For example, node centrality can be used to determine a person that has the potential to spread a disease during a pandemic. However, modeling an entire city or nation and finding the most influential people in terms of disease spread would be difficult because of the increasing time complexity. There is a way to remedy this, and that is through the use of bridge and community detection. These two techniques can be used to analyze a graph by splitting it into more digestible pieces called subgraphs. From there, the node centralities of these more manageable subgraphs can be found and used to determine which nodes need to be studied. In addition to these methods, different algorithms to calculate centrality were analyzed for evaluation, which proved the efficiency of this model in regards to time complexity.

Please click to read the paper.