A Parallel Algorithm for Modeling of Dynamical Processes on Large Stochastic Kronecker Graphs

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.

• Publication year

  2016

• Venue

  International Conference on Conceptual Structures

• Publication date

  2016-06-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.procs.2016.05.539
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Russian-Dutch double-degree Master's programme in computational science in the age of global education

  2015cited by this paper
• Indemics

  2014cited by this paper
• Guest editors’ introduction to special issue on the third INFORMS simulation society research workshop

  2014cited by this paper
• Parallel Algorithms for Generating Random Networks with Given Degree Sequences

  2014cited by this paper
• Distributed-memory parallel algorithms for generating massive scale-free networks using preferential attachment model

  2013cited by this paper
• Modeling and simulation of large-scale social networks using parallel discrete event simulation

  2013cited by this paper
• Stochastic Kronecker Graph on Vertex-Centric BSP

  2012cited by this paper
• Parallel Generation of Massive Scale-Free Graphs

  2010cited by this paper
• EpiFast: a fast algorithm for large scale realistic epidemic simulations on distributed memory systems

  2009cited by this paper
• EpiSimdemics: An efficient algorithm for simulating the spread of infectious disease over large realistic social networks

  2008cited by this paper
• Kronecker Graphs: An Approach to Modeling Networks

  2008cited by this paper
• EpiSimS simulation of a multi-component strategy for pandemic influenza

  2008cited by this paper

• Scalable parallel simulation of dynamical processes on large stochastic Kronecker graphs

  2018cites this paper
• Visualization of parallel modeling of dynamical processes on stochastic Kronecker graphs

  2016influential citation