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 Kroneckerjulia> A = rand(2, 2)2×2 Matrix{Float64}: 0.474831 0.385281 0.267081 0.360953julia> K2 = A ⊗ 24×4 KroneckerPower{Float64, Matrix{Float64}}: 0.225464 0.182943 0.182943 0.148441 0.126818 0.171392 0.102901 0.139068 0.126818 0.102901 0.171392 0.139068 0.0713322 0.0964036 0.0964036 0.130287julia> inv(K2)4×4 KroneckerPower{Float64, Matrix{Float64}}: 27.7742 -29.6462 -29.6462 31.6443 -20.5511 36.5368 21.9362 -38.9993 -20.5511 21.9362 36.5368 -38.9993 15.2064 -27.0348 -27.0348 48.0638julia> K12 = K2 ⊗ 6 # works recursively4096×4096 KroneckerPower{Float64, KroneckerPower{Float64, Matrix{Float64}}}: 0.000131361 0.000106587 0.000106587 … 1.31853e-5 1.31853e-5 1.06986e-5 7.38876e-5 9.98571e-5 5.99528e-5 1.23527e-5 7.4164e-6 1.00231e-5 7.38876e-5 5.99528e-5 9.98571e-5 7.4164e-6 1.23527e-5 1.00231e-5 4.156e-5 5.61672e-5 5.61672e-5 6.9481e-6 6.9481e-6 9.39018e-6 7.38876e-5 5.99528e-5 5.99528e-5 1.23527e-5 1.23527e-5 1.00231e-5 4.156e-5 5.61672e-5 3.3722e-5 … 1.15727e-5 6.9481e-6 9.39018e-6 4.156e-5 3.3722e-5 5.61672e-5 6.9481e-6 1.15727e-5 9.39018e-6 2.33765e-5 3.15927e-5 3.15927e-5 6.50938e-6 6.50938e-6 8.79725e-6 7.38876e-5 5.99528e-5 5.99528e-5 1.23527e-5 1.23527e-5 1.00231e-5 4.156e-5 5.61672e-5 3.3722e-5 1.15727e-5 6.9481e-6 9.39018e-6 ⋮ ⋱ ⋮ 2.34213e-7 3.16533e-7 3.16533e-7 3.863e-6 3.863e-6 5.22074e-6 7.40293e-7 6.00678e-7 6.00678e-7 7.33074e-6 7.33074e-6 5.94821e-6 4.16397e-7 5.62749e-7 3.37867e-7 6.86785e-6 4.12336e-6 5.57262e-6 4.16397e-7 3.37867e-7 5.62749e-7 … 4.12336e-6 6.86785e-6 5.57262e-6 2.34213e-7 3.16533e-7 3.16533e-7 3.863e-6 3.863e-6 5.22074e-6 4.16397e-7 3.37867e-7 3.37867e-7 6.86785e-6 6.86785e-6 5.57262e-6 2.34213e-7 3.16533e-7 1.90042e-7 6.43419e-6 3.863e-6 5.22074e-6 2.34213e-7 1.90042e-7 3.16533e-7 3.863e-6 6.43419e-6 5.22074e-6 1.31739e-7 1.78042e-7 1.78042e-7 … 3.61908e-6 3.61908e-6 4.89109e-6julia> K12^2 # example4096×4096 KroneckerPower{Float64, KroneckerPower{Float64, Matrix{Float64}}}: 1.57141e-6 1.541e-6 1.541e-6 … 1.26748e-6 1.26748e-6 1.24295e-6 1.06824e-6 1.11594e-6 1.04757e-6 9.17859e-7 8.61628e-7 9.00097e-7 1.06824e-6 1.04757e-6 1.11594e-6 8.61628e-7 9.17859e-7 9.00097e-7 7.26188e-7 7.5861e-7 7.5861e-7 6.23958e-7 6.23958e-7 6.51815e-7 1.06824e-6 1.04757e-6 1.04757e-6 9.17859e-7 9.17859e-7 9.00097e-7 7.26188e-7 7.5861e-7 7.12135e-7 … 6.64678e-7 6.23958e-7 6.51815e-7 7.26188e-7 7.12135e-7 7.5861e-7 6.23958e-7 6.64678e-7 6.51815e-7 4.9366e-7 5.15701e-7 5.15701e-7 4.51846e-7 4.51846e-7 4.72019e-7 1.06824e-6 1.04757e-6 1.04757e-6 9.17859e-7 9.17859e-7 9.00097e-7 7.26188e-7 7.5861e-7 7.12135e-7 6.64678e-7 6.23958e-7 6.51815e-7 ⋮ ⋱ ⋮ 2.25145e-8 2.35197e-8 2.35197e-8 3.41721e-8 3.41721e-8 3.56978e-8 4.87197e-8 4.77769e-8 4.77769e-8 6.94157e-8 6.94157e-8 6.80724e-8 3.31195e-8 3.45982e-8 3.24786e-8 5.02681e-8 4.71886e-8 4.92954e-8 3.31195e-8 3.24786e-8 3.45982e-8 … 4.71886e-8 5.02681e-8 4.92954e-8 2.25145e-8 2.35197e-8 2.35197e-8 3.41721e-8 3.41721e-8 3.56978e-8 3.31195e-8 3.24786e-8 3.24786e-8 5.02681e-8 5.02681e-8 4.92954e-8 2.25145e-8 2.35197e-8 2.20789e-8 3.64022e-8 3.41721e-8 3.56978e-8 2.25145e-8 2.20789e-8 2.35197e-8 3.41721e-8 3.64022e-8 3.56978e-8 1.53053e-8 1.59886e-8 1.59886e-8 … 2.47461e-8 2.47461e-8 2.5851e-8
Kronecker.kronecker — Methodkronecker(A::AbstractMatrix, pow::Int)Kronecker power, computes A ⊗ A ⊗ ... ⊗ A. Returns a lazy KroneckerPower type.
Kronecker.:⊗ — Method⊗(A::AbstractMatrix, pow::Int)Kronecker power, computes A ⊗ A ⊗ ... ⊗ A. Returns a lazy KroneckerPower type.
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:
naivesamplegives exact samples, but has a computational time proportional to the number of elements and hence prohibitive for large graphs;fastsamplea 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 Kroneckerjulia> P = rand(2, 2)2×2 Matrix{Float64}: 0.834098 0.437779 0.453521 0.055507julia> P10 = P ⊗ 101024×1024 KroneckerPower{Float64, Matrix{Float64}}: 0.162993 0.0855474 0.0855474 … 0.000492619 0.000258553 0.0886237 0.0108467 0.0465144 0.00026785 3.27825e-5 0.0886237 0.0465144 0.0108467 6.24603e-5 3.27825e-5 0.0481871 0.00589767 0.00589767 3.39614e-5 4.15657e-6 0.0886237 0.0465144 0.0465144 6.24603e-5 3.27825e-5 0.0481871 0.00589767 0.0252912 … 3.39614e-5 4.15657e-6 0.0481871 0.0252912 0.00589767 7.91948e-6 4.15657e-6 0.0262006 0.00320672 0.00320672 4.30604e-6 5.27021e-7 0.0886237 0.0465144 0.0465144 6.24603e-5 3.27825e-5 0.0481871 0.00589767 0.0252912 3.39614e-5 4.15657e-6 ⋮ ⋱ 0.000677014 8.28605e-5 8.28605e-5 … 1.7891e-11 2.1897e-12 0.00229 0.00120192 0.00120192 2.59514e-10 1.36207e-10 0.00124514 0.000152394 0.000653514 1.41105e-10 1.72699e-11 0.00124514 0.000653514 0.000152394 3.29043e-11 1.72699e-11 0.000677014 8.28605e-5 8.28605e-5 1.7891e-11 2.1897e-12 0.00124514 0.000653514 0.000653514 … 3.29043e-11 1.72699e-11 0.000677014 8.28605e-5 0.000355333 1.7891e-11 2.1897e-12 0.000677014 0.000355333 8.28605e-5 4.17201e-12 2.1897e-12 0.000368111 4.50535e-5 4.50535e-5 2.26844e-12 2.77636e-13julia> sum(P10) # expected number of edges320.92816782397193julia> A = fastsample(P10)1024×1024 SparseArrays.SparseMatrixCSC{Bool, Int64} with 321 stored entries: ⎡⣘⠩⠹⠈⠠⢉⠄⠊⠈⠁⠇⠐⠘⠁⠀⠌⠑⢀⠀⠀⠟⠘⠚⠐⠈⠉⠈⠀⠀⠜⠆⠌⠀⠀⠀⠀⠁⠀⠀⠀⎤ ⎢⡡⠐⡐⠈⠂⠙⠀⠨⠀⠀⠀⠂⠠⠀⠀⠂⠂⠀⠀⠀⡀⠂⢄⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⎥ ⎢⢜⠁⠈⠀⠀⠁⢀⠀⠀⠀⡈⠀⢀⠀⠀⠀⠀⠀⠀⠀⢂⠀⠀⠀⠄⠀⠀⠀⠀⢈⢄⠀⠀⠀⠀⠀⠀⠠⠀⠀⎥ ⎢⡠⠂⠂⠐⠀⠀⠀⠀⠀⠀⠁⡀⠀⠈⠀⠀⠀⠀⠀⠂⠐⡀⠀⠊⠀⠀⠀⠀⠀⠀⠐⠀⠠⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠁⠁⠐⠂⠀⠀⠀⠀⠀⠀⠠⠀⠀⠀⠂⠀⠀⠀⠀⠀⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⡚⠊⢁⠄⠀⠅⠀⠀⢀⠁⠁⠀⠈⠀⠀⠀⠈⠀⠀⠀⢂⠃⠎⠈⠀⢃⠁⠁⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⢃⠰⠀⠀⠀⠒⠐⡀⠀⠀⠅⠀⠀⠀⠀⠀⠀⠀⠀⠀⡄⠀⠁⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠐⠀⠀⠀⎥ ⎢⡄⠀⠄⠀⠀⠀⠀⢐⠀⠀⠤⠠⠀⠀⠀⠀⠀⠀⠀⠀⠂⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⡀⡀⠨⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠑⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠂⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⡾⠉⠩⠄⠂⠕⠀⠉⠀⠀⠍⠋⢈⠘⠈⠂⠈⠀⠉⠀⠀⠁⠈⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠑⠁⠀⠀⠀⢡⠀⠈⠀⠀⠉⠀⢀⠀⠀⠀⠂⠀⠀⠀⠀⠂⠂⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⎥ ⎢⠠⠔⠀⠀⠂⠈⠀⠀⠀⠀⡠⠀⠐⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⡀⠀⠀⠃⠈⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⡠⢀⡀⠀⡀⠀⠀⢀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⠄⠀⠁⠀⠁⠨⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠄⠆⡀⠀⠀⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⡐⠀⠠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎢⠀⢀⡀⠀⠀⠐⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎥ ⎣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⎦
Kronecker.isprob — Functionisprob(A::AbstractArray)Test if a matrix can be interpeted as a probability matrix, i.e., all elements are between 0 and 1.
isprob(K::AbstractKroneckerProduct)Test if a Kronecker product can be interpeted as a probability matrix, i.e., all elements are between 0 and 1.
Kronecker.naivesample — Functionnaivesample(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.
Kronecker.fastsample — Functionfastsample(P::AbstractKroneckerProduct)Uses the heuristic sampling from Leskovec et al. (2008) to sample a large Kronecker graph.