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 Matrix{Float64}:
 0.102639  0.815315
 0.416922  0.989475
julia> K2 = A ⊗ 24×4 KroneckerPower{Float64, Matrix{Float64}}:
 0.0105348  0.0836831  0.0836831  0.664739
 0.0427925  0.101559   0.339923   0.806734
 0.0427925  0.339923   0.101559   0.806734
 0.173824   0.412534   0.412534   0.979061
julia> inv(K2)4×4 KroneckerPower{Float64, Matrix{Float64}}:
 17.2317   -14.1987    -14.1987    11.6995
 -7.26068    1.78745     5.98271   -1.47284
 -7.26068    5.98271     1.78745   -1.47284
  3.05934   -0.753156   -0.753156   0.185414
julia> K12 = K2 ⊗ 6  # works recursively4096×4096 KroneckerPower{Float64, KroneckerPower{Float64, Matrix{Float64}}}:
 1.36693e-12  1.08583e-11  1.08583e-11  …  0.0108616  0.0108616  0.0862795
 5.55252e-12  1.31777e-11  4.41066e-11     0.0131818  0.0441201  0.10471
 5.55252e-12  4.41066e-11  1.31777e-11     0.0441201  0.0131818  0.10471
 2.25545e-11  5.35282e-11  5.35282e-11     0.0535447  0.0535447  0.127077
 5.55252e-12  4.41066e-11  4.41066e-11     0.0131818  0.0131818  0.10471
 2.25545e-11  5.35282e-11  1.79162e-10  …  0.0159975  0.0535447  0.127077
 2.25545e-11  1.79162e-10  5.35282e-11     0.0535447  0.0159975  0.127077
 9.16169e-11  2.17433e-10  2.17433e-10     0.0649824  0.0649824  0.154222
 5.55252e-12  4.41066e-11  4.41066e-11     0.0131818  0.0131818  0.10471
 2.25545e-11  5.35282e-11  1.79162e-10     0.0159975  0.0535447  0.127077
 ⋮                                      ⋱                        ⋮
 6.79074e-6   1.61164e-5   1.61164e-5      0.305795   0.305795   0.725738
 4.11559e-7   3.26923e-6   3.26923e-6      0.0620309  0.0620309  0.492744
 1.67176e-6   3.96757e-6   1.32797e-5      0.0752813  0.251971   0.597999
 1.67176e-6   1.32797e-5   3.96757e-6   …  0.251971   0.0752813  0.597999
 6.79074e-6   1.61164e-5   1.61164e-5      0.305795   0.305795   0.725738
 1.67176e-6   1.32797e-5   1.32797e-5      0.0752813  0.0752813  0.597999
 6.79074e-6   1.61164e-5   5.39425e-5      0.0913622  0.305795   0.725738
 6.79074e-6   5.39425e-5   1.61164e-5      0.305795   0.0913622  0.725738
 2.75842e-5   6.54651e-5   6.54651e-5   …  0.371116   0.371116   0.880763
julia> K12^2  # example4096×4096 KroneckerPower{Float64, KroneckerPower{Float64, Matrix{Float64}}}:
 3.43265e-6  8.72142e-6   8.72142e-6   …  0.0977612  0.0977612   0.248384
 4.45981e-6  1.29191e-5   1.13312e-5      0.144815   0.127015    0.367934
 4.45981e-6  1.13312e-5   1.29191e-5      0.127015   0.144815    0.367934
 5.79434e-6  1.6785e-5    1.6785e-5       0.188148   0.188148    0.545025
 4.45981e-6  1.13312e-5   1.13312e-5      0.144815   0.144815    0.367934
 5.79434e-6  1.6785e-5    1.47218e-5   …  0.214515   0.188148    0.545025
 5.79434e-6  1.47218e-5   1.6785e-5       0.188148   0.214515    0.545025
 7.5282e-6   2.18076e-5   2.18076e-5      0.278706   0.278706    0.80735
 4.45981e-6  1.13312e-5   1.13312e-5      0.144815   0.144815    0.367934
 5.79434e-6  1.6785e-5    1.47218e-5      0.214515   0.188148    0.545025
 ⋮                                     ⋱                         ⋮
 6.11209e-5  0.000177054  0.000177054     6.4612     6.4612     18.7167
 3.62089e-5  9.19968e-5   9.19968e-5      3.35722    3.35722     8.52978
 4.70438e-5  0.000136276  0.000119525     4.97308    4.36181    12.6352
 4.70438e-5  0.000119525  0.000136276  …  4.36181    4.97308    12.6352
 6.11209e-5  0.000177054  0.000177054     6.4612     6.4612     18.7167
 4.70438e-5  0.000119525  0.000119525     4.97308    4.97308    12.6352
 6.11209e-5  0.000177054  0.000155291     7.36668    6.4612     18.7167
 6.11209e-5  0.000155291  0.000177054     6.4612     7.36668    18.7167
 7.94103e-5  0.000230035  0.000230035  …  9.57104    9.57104    27.7253

Kronecker.KroneckerPower — Type

Efficient way of storing Kronecker powers, e.g.

K = A ⊗ A ⊗ ... ⊗ A.

source

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 Matrix{Float64}:
 0.601454  0.667837
 0.432422  0.153827
julia> P10 = P ⊗ 101024×1024 KroneckerPower{Float64, Matrix{Float64}}:
 0.00619476   0.00687848   0.00687848   …  0.0158941    0.0176483
 0.0044538    0.00158436   0.00494536      0.0114272    0.00406505
 0.0044538    0.00494536   0.00158436      0.00366098   0.00406505
 0.00320211   0.0011391    0.0011391       0.00263211   0.000936327
 0.0044538    0.00494536   0.00494536      0.00366098   0.00406505
 0.00320211   0.0011391    0.00355553   …  0.00263211   0.000936327
 0.00320211   0.00355553   0.0011391       0.000843256  0.000936327
 0.00230219   0.000818966  0.000818966     0.000606269  0.00021567
 0.0044538    0.00494536   0.00494536      0.00366098   0.00406505
 0.00320211   0.0011391    0.00355553      0.00263211   0.000936327
 ⋮                                      ⋱
 0.000317962  0.00011311   0.00011311   …  9.05391e-8   3.22078e-8
 0.000615126  0.000683018  0.000683018     5.46725e-7   6.07067e-7
 0.000442252  0.000157324  0.000491064     3.93074e-7   1.39829e-7
 0.000442252  0.000491064  0.000157324     1.2593e-7    1.39829e-7
 0.000317962  0.00011311   0.00011311      9.05391e-8   3.22078e-8
 0.000442252  0.000491064  0.000491064  …  1.2593e-7    1.39829e-7
 0.000317962  0.00011311   0.000353056     9.05391e-8   3.22078e-8
 0.000317962  0.000353056  0.00011311      2.90063e-8   3.22078e-8
 0.000228603  8.13215e-5   8.13215e-5      2.08544e-8   7.41861e-9
julia> sum(P10)  # expected number of edges483.8418654825
julia> A = fastsample(P10)1024×1024 SparseArrays.SparseMatrixCSC{Bool, Int64} with 484 stored entries:
⎡⠈⠉⠘⠦⠂⠄⠁⢑⠀⠈⡹⡀⠹⠐⠃⠌⡐⠁⡪⠍⡈⠆⠁⢲⠀⠀⠁⠸⣁⠁⢘⡀⠲⠰⠀⠤⠻⠏⠱⢐⎤
⎢⠈⡀⠀⠀⠤⠄⠡⠈⠈⠀⢆⢂⠪⠀⠀⠀⠂⠄⢀⠀⣡⢑⠂⠁⠀⠠⠀⠂⢈⠠⠑⢀⠀⠕⠀⠡⢆⠀⠀⠀⎥
⎢⠀⠀⢄⡀⠀⠀⠀⠠⠀⠀⠀⠀⡄⡀⠀⠀⠀⠀⠀⠀⠤⠤⢄⠀⠀⠆⠈⠠⡁⠀⢠⠪⠴⠈⡀⠀⠀⠀⠀⠀⎥
⎢⠀⡂⠈⠀⠀⠀⡀⡀⠀⠀⠀⠠⡐⠉⢀⢈⠀⠉⠈⠀⢐⠀⡘⠐⢀⡂⠀⠀⠀⠐⢀⠀⠂⠈⠈⠀⠀⠀⠀⠀⎥
⎢⠣⡐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣉⠀⠀⠀⠀⠀⠀⠈⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠜⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠈⠈⢀⠌⠘⠠⠀⠀⣀⠈⠀⠐⠠⡀⠀⠀⠊⠂⡀⠀⠀⢈⠒⠈⠠⡱⠀⠐⠁⠠⠀⠀⠉⠀⠀⠀⠐⠀⢀⠀⎥
⎢⠀⡂⠐⠀⠀⡒⠀⠀⠁⠁⠀⠂⠀⠀⠀⢀⠐⠀⠀⠀⠅⠐⠄⠐⠀⢁⠀⠀⠐⠀⡀⠐⠀⠀⠀⣀⠀⠀⠀⠀⎥
⎢⡀⠠⠀⠄⢄⠄⠄⢀⠀⠀⠀⠀⢀⠀⡀⠀⠠⠀⠀⠀⠀⠠⠀⠠⠠⠀⢀⠀⠀⠀⠀⡀⠠⢀⠀⠀⠀⠀⠀⠀⎥
⎢⢀⢀⠀⠁⠀⠀⠂⠠⠀⠀⠐⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠀⠀⡀⠀⠀⠀⠀⠀⢀⠀⠀⠀⎥
⎢⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠂⡈⢖⢇⠉⠠⢉⠠⠁⠠⢀⠜⠁⠊⠑⠀⠑⠈⢙⠠⠀⠀⠀⠀⠀⠀⡄⠈⠀⠒⠠⠁⠀⠀⠀⠀⠂⠒⠐⠀⎥
⎢⠀⠐⠀⠐⠀⠄⠂⠀⠀⠀⠐⠀⡂⠀⠐⠀⠤⠀⠀⠀⠐⠀⠀⠀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠐⠄⠀⠀⠀⎥
⎢⢶⠀⠄⠀⠂⡀⠀⠂⠀⡀⠐⢠⠀⠀⠠⠀⠀⠀⠁⠀⠀⠀⠀⠀⡐⠈⠀⡀⠀⢀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠀⠁⠈⠄⠀⠁⠀⠀⠀⠬⠠⠀⠈⠂⠀⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠁⠀⎥
⎢⠀⠈⠁⠀⢀⠀⠀⢀⠀⠀⡀⠀⠀⠈⠀⠁⠀⠀⠀⠀⠀⠐⡀⠀⡀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠨⠐⠁⠀⠤⠄⠂⡦⠄⠘⠀⠀⠀⠀⢠⠀⠐⠀⠀⠀⠀⠍⠀⡐⠂⠤⠂⠀⠐⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠀⠈⢈⣀⠀⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⠀⠀⠀⠀⠀⠀⠑⠀⠀⡐⠀⠁⠀⠀⠀⠠⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎢⠠⠄⣀⠀⠀⠀⠀⠂⠀⠀⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⢀⠀⠀⠀⠀⠀⠀⎥
⎢⡁⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥
⎣⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎦

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([rng::AbstractRNG,] 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([rng::AbstractRNG,] P::AbstractKroneckerProduct)

Uses the heuristic sampling from Leskovec et al. (2008) to sample a large Kronecker graph: edges are drawn proportionally to their probability until the expected number of edges round(Int, sum(P)) is reached, re-sampling any duplicates (collisions) along the way.

source

Kronecker.sampleindices — Function

sampleindices([rng::AbstractRNG,] A::AbstractMatrix, s::Int)

Samples the indices from an AbstractMatrix. Probability of sampling indices is proportional to the size of the corresponding value. Does not do any checks on A.

source

sampleindices([rng::AbstractRNG,] K::AbstractKroneckerProduct, s::Int)

Samples the indices from an AbstractKroneckerProduct. Probability of sampling indices is proportional to the size of the corresponding value. Does not do any checks on A.

source