A stochastic Kronecker graph (SKG) is one of the most widely used approaches to model complex networks due to the simplicity of generative procedure and the ability to reproduce the properties of real graphs. In this paper, we present a novel parallel algorithm for modeling dynamical processes on large Poisson SKGs (PSKGs). Proposed algorithm combines the modeling of spreading of a process with the generation of vertices and edges which are involved in it. An experimental study of an algorithm was carried out for different initiator matrices and graphs with the widely varying (from several million to one billion) number of vertices using the supercomputer from Lobachevsky State University of Nizhni Novgorod, Russia. The results confirmed the applicability of an algorithm for mid-size HPC clusters with the efficiency varying on average from 0.2 to 0.7. © The Authors. Published by Elsevier B.V.