Implementation of Computing Node Centrality with Bridge and Community Detection

Abstract

As our society grows, the potential of certain people affecting the masses has increased dramatically with the presence of media, virality, and celebrities. Therefore, it is essential to know which persons might be influencing, swaying, or manipulating the public the most in a social network. Similarly, finding the most important webpage can impact advertisement spending for corporations. I propose and determine a better method to find the most significant "influencer" and other real-world applications using graph theory in discrete mathematics. There are many methods of node centrality, and some have more advantages than others. As measuring this score becomes more complex, accuracy is guaranteed, but time complexity increases simultaneously. In particular, when the score is a case where the relationship between nodes is important, the time complexity shows an extreme increase. Graphs representing the real world have a lot of nodes and edges in many cases, and experiments have found that if applied as they are, the time efficiency will be extremely low. To compensate for this point, bridge detection and community detection, a method of dividing a large graph into several subgraphs at a low level, were applied to change the nested loop operation to a simple sum of operations in series. Furthermore, a model, which is the most appropriate combination, was proposed and experimentally proved in consideration of trade-offs. The reason for selecting the ratio of node and edge numbers to increase the experiment's credibility was also described.