{'fraction_non_alphanumeric': 0.024439918533604887, 'fraction_numerical': 0.0, 'mean_word_length': 5.551111111111111, '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': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Uniform Sampling in Real-World Networks

Uniform sampling in networks is at the core of a wide variety of randomized algorithms. Random sampling can be performed by modeling the system as a graph with associated transition probabilities and defining a corresponding Markov chain (MC). A random walk of prescribed minimum length, performed on this graph, yields a stationary distribution, and the corresponding random sample. This sample, however, is not uniform when network nodes have a nonuniform degree distribution. This poses a significant practical challenge since typical large scale, real-world, unstructured networks tend to have non-uniform degree distributions, e.g., power-law degree distribution in unstructured peer-to-peer networks. In this paper we present a distributed algorithm that enables efficient uniform sampling in large real-world networks. Specifically, we prescribe necessary conditions for uniform sampling in such networks and present distributed algorithms that satisfy these requirements. We empirically evaluate the performance of our algorithm in comparison to known algorithms. We also quantify, in context of the presented algorithms, the performance parameters in uniform sampling that are most relevant in a distributed setting – computational complexity, number of network messages, and the uniformity of the sampling. Detailed experimental results are used to support our claims relating to performance improvements of our algorithm.