Efficient Simulation and Analysis of Mid-Sized Networks

There is growing interest in developing the abilities to simulate realistic social networks and analyze data generated from existing online social networks such as Facebook and Twitter. Amongst other things, researchers and practitioners need these abilities to study how opinions and information diffuse over networks and identify the influential agents in networks. However, the sizes of the social networks that need to be simulated and the amount of user generated data that needs to be analyzed is growing at a faster rate than the computational power of most of the modern day computers. This paper presents a memory efficient network representation and computational resource allocation algorithm that yields a scale-up of about 400; thus, given a constraint on the availability of computational resources, researchers can now use the proposed algorithm to simulate and analyze networks that are more than 100 times larger than what they could simulate otherwise. The proposed network representation is conducive to multi-core processing and random node sampling. Algorithms for computationally efficient execution of three random-node-sampling-based methods to estimate network metrics such as the network diameter and average path length are also presented in the paper. These algorithms yield a speed-up of about 40 even when the researcher requires a precision of more than 98%. The scale-up and speed-up numbers are based on a detailed performance analysis of the proposed algorithms that was conducted on synthetic networks of sizes ranging from 1000-1,000,000 nodes. The observed scale-up and speed-up performance of the proposed algorithms has been validated against the algorithms used in igraph and statnet-two popular network data analysis software package, and these results are also presented in this paper