Edit on GitHub

Kronecker powers and graphs

Kronecker powers

Repeated Kronecker multiplications of the same matrix, i.e.

\[A^{\otimes n}=\otimes_{i=1}^n A = \underbrace{A \otimes A \otimes \ldots \otimes A}_{n\text{ times}}\,.\]

Kronecker powers are supported using kronecker(A, n) or, equivalently, ⊗(A, n). These functions yield an instance of KroneckerPower, as struct which holds the matrix and the power. It works just like instances of KroneckerProduct, but more efficient since only a single matrix has to be stored and manipulated. These products work as expected.

julia> using Kronecker
julia> A = rand(2, 2)2×2 Array{Float64,2}:
 0.575462  0.556652
 0.745298  0.310024
julia> K2 = A ⊗ 24×4 KroneckerPower{Float64,Array{Float64,2}}:
 0.331156  0.320332  0.320332  0.309862
 0.428891  0.178407  0.414872  0.172576
 0.428891  0.414872  0.178407  0.172576
 0.555469  0.23106   0.23106   0.0961148
julia> inv(K2)4×4 KroneckerPower{Float64,Array{Float64,2}}:
  1.71892  -3.08635  -3.08635   5.54159
 -4.13229   3.19064   7.41959  -5.72884
 -4.13229   7.41959   3.19064  -5.72884
  9.93404  -7.6703   -7.6703    5.92242
julia> K12 = K2 ⊗ 6  # works recursively4096×4096 KroneckerPower{Float64,KroneckerPower{Float64,Array{Float64,2}}}:
 0.00131886  0.00127575   0.00127575   …  0.000915045  0.000885136
 0.0017081   0.000710522  0.00165227      0.0011851    0.00049297
 0.0017081   0.00165227   0.000710522     0.000509628  0.00049297
 0.00221221  0.000920218  0.000920218     0.000660034  0.000274556
 0.0017081   0.00165227   0.00165227      0.000509628  0.00049297
 0.00221221  0.000920218  0.0021399    …  0.000660034  0.000274556
 0.00221221  0.0021399    0.000920218     0.000283834  0.000274556
 0.0028651   0.0011918    0.0011918       0.000367602  0.000152912
 0.0017081   0.00165227   0.00165227      0.000509628  0.00049297
 0.00221221  0.000920218  0.0021399       0.000660034  0.000274556
 ⋮                                     ⋱               ⋮
 0.0226802   0.00943434   0.00943434      3.40302e-6   1.41556e-6
 0.0135213   0.0130794    0.0130794       4.71781e-6   4.5636e-6
 0.0175119   0.00728447   0.0169395       6.11017e-6   2.54167e-6
 0.0175119   0.0169395    0.00728447   …  2.62755e-6   2.54167e-6
 0.0226802   0.00943434   0.00943434      3.40302e-6   1.41556e-6
 0.0175119   0.0169395    0.0169395       2.62755e-6   2.54167e-6
 0.0226802   0.00943434   0.0219389       3.40302e-6   1.41556e-6
 0.0226802   0.0219389    0.00943434      1.4634e-6    1.41556e-6
 0.0293738   0.0122187    0.0122187    …  1.89529e-6   7.88389e-7
julia> K12^2  # example4096×4096 KroneckerPower{Float64,KroneckerPower{Float64,Array{Float64,2}}}:
 0.0297211   0.019637    0.019637    0.0129743   …  0.000311299  0.000205678
 0.0262918   0.0203572   0.0173713   0.0134502      0.000275381  0.000213222
 0.0262918   0.0173713   0.0203572   0.0134502      0.000322717  0.000213222
 0.0232582   0.0180084   0.0180084   0.0139435      0.000285482  0.000221043
 0.0262918   0.0173713   0.0173713   0.0114773      0.000322717  0.000213222
 0.0232582   0.0180084   0.0153669   0.0118983   …  0.000285482  0.000221043
 0.0232582   0.0153669   0.0180084   0.0118983      0.000334554  0.000221043
 0.0205747   0.0159306   0.0159306   0.0123347      0.000295953  0.00022915
 0.0262918   0.0173713   0.0173713   0.0114773      0.000322717  0.000213222
 0.0232582   0.0180084   0.0153669   0.0118983      0.000285482  0.000221043
 ⋮                                               ⋱               ⋮
 0.00771583  0.00597421  0.00597421  0.00462571     0.000394797  0.000305684
 0.00985985  0.00651449  0.00651449  0.00430418     0.000430501  0.000284436
 0.00872221  0.00675343  0.00576284  0.00446205     0.000380829  0.000294868
 0.00872221  0.00576284  0.00675343  0.00446205  …  0.000446291  0.000294868
 0.00771583  0.00597421  0.00597421  0.00462571     0.000394797  0.000305684
 0.00872221  0.00576284  0.00576284  0.00380756     0.000446291  0.000294868
 0.00771583  0.00597421  0.00509792  0.00394722     0.000394797  0.000305684
 0.00771583  0.00509792  0.00597421  0.00394722     0.00046266   0.000305684
 0.00682557  0.0052849   0.0052849   0.00409199  …  0.000409278  0.000316895
Kronecker.kronecker — Method
kronecker(A::AbstractMatrix, pow::Int)

Kronecker power, computes A ⊗ A ⊗ ... ⊗ A. Returns a lazy KroneckerPower type.

source
Kronecker.:⊗ — Method
⊗(A::AbstractMatrix, pow::Int)

Kronecker power, computes A ⊗ A ⊗ ... ⊗ A. Returns a lazy KroneckerPower type.

source

Kronecker graphs

An exciting application of Kronecker powers (or Krocker products in general) is generating large, realistic graphs from an initial 'seed' via a stochastic process. This is called a Kronecker graph and is described in detail in Leskovec et al. (2008).

If we use an initial matrix $P$ with values in $[0,1]$ as a seed, then $P_n=P^{\otimes n}$ can be seen as a probability distribution for an adjacency matrix of a graph. The elements $(P_n)_{i,j}$ give the probabilities that there is an edge from node $i$ to node $j$. Leskovec and co-authors give two algorithms for sampling adjacency matrices from this distribution, both provided by Kronecker.jl:

  • naivesample gives exact samples, but has a computational time proportional to the number of elements and hence prohibitive for large graphs;
  • fastsample a recursive heuristic, has a computational time proportional to the expected number of edges in the graph.

The latter can easily scale to generate graphs of millions of nodes. Both return the adjacency matrix as a sparse array.

julia> using Kronecker
julia> P = rand(2, 2)2×2 Array{Float64,2}:
 0.30703   0.553901
 0.745568  0.558225
julia> P10 = P ⊗ 101024×1024 KroneckerPower{Float64,Array{Float64,2}}:
 7.44413e-6   1.34297e-5  1.34297e-5  …  0.00150686  0.00150686  0.00271846
 1.80767e-5   1.35345e-5  3.26115e-5     0.00151862  0.00365914  0.00273969
 1.80767e-5   3.26115e-5  1.35345e-5     0.00365914  0.00151862  0.00273969
 4.38961e-5   3.28661e-5  3.28661e-5     0.0036877   0.0036877   0.00276108
 1.80767e-5   3.26115e-5  3.26115e-5     0.00151862  0.00151862  0.00273969
 4.38961e-5   3.28661e-5  7.91912e-5  …  0.00153048  0.0036877   0.00276108
 4.38961e-5   7.91912e-5  3.28661e-5     0.0036877   0.00153048  0.00276108
 0.000106594  7.98094e-5  7.98094e-5     0.00371649  0.00371649  0.00278263
 1.80767e-5   3.26115e-5  3.26115e-5     0.00151862  0.00151862  0.00273969
 4.38961e-5   3.28661e-5  7.91912e-5     0.00153048  0.0036877   0.00276108
 ⋮                                    ⋱
 0.0218559    0.016364    0.016364    …  0.00389401  0.00389401  0.00291554
 0.00370643   0.00668663  0.00668663     0.00159116  0.00159116  0.00287055
 0.0090004    0.00673883  0.0162373      0.00160358  0.00386384  0.00289296
 0.0090004    0.0162373   0.00673883     0.00386384  0.00160358  0.00289296
 0.0218559    0.016364    0.016364       0.00389401  0.00389401  0.00291554
 0.0090004    0.0162373   0.0162373   …  0.00160358  0.00160358  0.00289296
 0.0218559    0.016364    0.0394293      0.0016161   0.00389401  0.00291554
 0.0218559    0.0394293   0.016364       0.00389401  0.0016161   0.00291554
 0.053073     0.0397371   0.0397371      0.00392441  0.00392441  0.0029383
julia> sum(P10)  # expected number of edges2259.5821501399823
julia> A = fastsample(P10)1024×1024 SparseArrays.SparseMatrixCSC{Bool,Int64} with 2250 stored entries:
  [702 ,    4]  =  1
  [749 ,    4]  =  1
  [761 ,    4]  =  1
  [878 ,    4]  =  1
  [925 ,    4]  =  1
  [248 ,    5]  =  1
  [571 ,    5]  =  1
  [1024,    5]  =  1
  [120 ,    6]  =  1
  ⋮
  [119 , 1022]  =  1
  [188 , 1023]  =  1
  [510 , 1023]  =  1
  [294 , 1024]  =  1
  [389 , 1024]  =  1
  [410 , 1024]  =  1
  [576 , 1024]  =  1
  [660 , 1024]  =  1
  [700 , 1024]  =  1
  [998 , 1024]  =  1
Kronecker.isprob — Function
isprob(A::AbstractArray)

Test if a matrix can be interpeted as a probability matrix, i.e., all elements are between 0 and 1.

source
isprob(K::AbstractKroneckerProduct)

Test if a Kronecker product can be interpeted as a probability matrix, i.e., all elements are between 0 and 1.

source
Kronecker.naivesample — Function
naivesample(P::AbstractKroneckerProduct)

Sample a Kronecker graph from a probabilistic Kronecker product P using the naive method. This method has a time complexity in the size of the Kronecker product (but is still light in memory use). Consider using fastsample.

source
Kronecker.fastsample — Function
fastsample(P::AbstractKroneckerProduct)

Uses the heuristic sampling from Leskovec et al. (2008) to sample a large Kronecker graph.

source