{'fraction_non_alphanumeric': 0.030318091451292245, 'fraction_numerical': 0.009940357852882704, 'mean_word_length': 4.973293768545994, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Scalable Group Testing Based Algorithm for Finding d-highest Betweenness Centrality Vertices in Large-Scale Networks ∗

1. Problem and Motivation Systems of interacting entities from diverse disciplines, such as biology (correlation among genes) and sociology (collaboration networks), can be modeled as networks. Networks (also termed as graphs) consist of a set of vertices that correspond to the entities in the system, and a set of edges that correspond to the interaction between a pair of entities. The importance of a vertex is evaluated based on centrality metrics. Betweenness centrality (BC) is a popular centrality metric that measures the importance with respect to the flow of information in a network [1], [2], [3], [11]. Vertices (or edges) with high betweenness centrality are the most vulnerable points in an information flow network and also are used in divisive algorithms to detect communities [12]. Current algorithms for finding high BC vertices, first cumulatively find the values for all vertices in the network and then sort them to obtain the ones with the highest values. However most real-world networks are massive. For example, currently Facebook has over 845 million vertices. Thus even polynomial time algorithms can be computationally very expensive. Our goal is to lower the execution time for finding the highest BC vertices. We note that only the few highest BC vertices are required for most applications, and even then we need only the identity of the vertices and not their values. This observation inspired us to apply group testing (GT). The primary idea of group testing is to identify highly sensitive entities from a collection of objects. The idea originated in the spring of 1942, during World War II, by Robert Dorfman and David Rosenblatt [5] to efficiently test blood samples for millions of draftees. Since then, group testing has been used in many applications including finding counterfeit coins, finding patterns in data [15] and DNA library screening [16].