Scalable parallel simulation of dynamical processes on large stochastic Kronecker graphs

摘要

Complex networks are widely recognized today as a unified framework to model the dynamical processes in socio-technical systems at the level of interacting elements. A stochastic Kronecker graph (SKG) is a network generative model that allows reproducing real-world networks while keeping their important topological properties. When sizes of SKGs reach dozens of millions of nodes, there is a need to apply parallel computations to simulate processes on networks stored in a distributed manner. In general, parallel simulation of a dynamical process on a complex network implies all-to-all communication between subnetworks at each iteration. In this paper, we study the efficiency of different SKG partitioning algorithms and different data interchange algorithms for dynamical process simulation on large SKGs. We compare the theoretical efficiency given by parallel performance models with experimental results for different communication patterns. An experimental part of the study was carried out for sparse SKGs with a size up to one billion nodes using Lomonosov supercomputer (Moscow State University, Russian Federation). The results show that: (ⅰ) proposed algorithm of SKG partitioning provides highly balanced results, (ⅱ) observed parallel performance is well agreed with presented theoretical models, (ⅲ) the scheme with all-to-all-communications between subnetworks is the most efficient up to approximately one hundred cores, (ⅳ) master-slave scheme with a single master per node outperforms all-to-all scheme for a large size of a communicator (for our experiments, it has achieved near-linear speedup for up to several hundred processes).