Kronecker graphs are a construction for generating
graphs
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
for modeling systems. The method constructs a sequence of graphs from a small base graph by iterating the
Kronecker product
In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors to ...
. A variety of generalizations of Kronecker graphs exist.
The
Graph500
The Graph500 is a rating of supercomputer systems, focused on data-intensive loads. The project was announced on International Supercomputing Conference in June 2010. The first list was published at the ACM/IEEE Supercomputing Conference in Novem ...
benchmark for supercomputers is based on the use of a stochastic version of Kronecker graphs. Stochastic kronecker graph is a kronecker graph with each component of the matrix made by real numbers between 0 and 1. The stochastic version of kronecker graph eliminates the staircase effect, which happens due to large multiplicity of kronecker graph.
References
Graph families
{{combin-stub