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.144279  0.119372
 0.898004  0.0204967

julia> K2 = A ⊗ 2
4×4 KroneckerPower{Float64,Array{Float64,2},2}:
 0.0208163  0.0172229   0.0172229   0.0142498
 0.129563   0.00295723  0.107197    0.00244673
 0.129563   0.107197    0.00295723  0.00244673
 0.806411   0.0184061   0.0184061   0.000420113

julia> inv(K2)
4×4 KroneckerPower{Float64,Array{Float64,2},2}:
  0.0386635   -0.225176   -0.225176   1.31142
 -1.69393      0.272157    9.86544   -1.58504
 -1.69393      9.86544     0.272157  -1.58504
 74.2149     -11.9238    -11.9238     1.91575

julia> K12 = K2 ⊗ 6  # works recursively
4096×4096 KroneckerPower{Float64,KroneckerPower{Float64,Array{Float64,2},2},6}:
 8.13628e-11  6.73174e-11  6.73174e-11  …  1.01191e-11  8.37228e-12
 5.0641e-10   1.15586e-11  4.1899e-10      6.29823e-11  1.43755e-12
 5.0641e-10   4.1899e-10   1.15586e-11     1.73749e-12  1.43755e-12
 3.15194e-9   7.1942e-11   7.1942e-11      1.08143e-11  2.46833e-13
 5.0641e-10   4.1899e-10   4.1899e-10      1.73749e-12  1.43755e-12
 3.15194e-9   7.1942e-11   2.60783e-9   …  1.08143e-11  2.46833e-13
 3.15194e-9   2.60783e-9   7.1942e-11      2.98333e-13  2.46833e-13
 1.9618e-8    4.47774e-10  4.47774e-10     1.85685e-12  4.2382e-14
 5.0641e-10   4.1899e-10   4.1899e-10      1.73749e-12  1.43755e-12
 3.15194e-9   7.1942e-11   2.60783e-9      1.08143e-11  2.46833e-13
 ⋮                                      ⋱               ⋮
 0.0441837    0.00100848   0.00100848      1.40285e-18  3.20196e-20
 0.00114054   0.000943652  0.000943652     1.31267e-18  1.08607e-18
 0.00709882   0.000162028  0.00587338      8.17019e-18  1.86482e-19
 0.00709882   0.00587338   0.000162028  …  2.2539e-19   1.86482e-19
 0.0441837    0.00100848   0.00100848      1.40285e-18  3.20196e-20
 0.00709882   0.00587338   0.00587338      2.2539e-19   1.86482e-19
 0.0441837    0.00100848   0.0365564       1.40285e-18  3.20196e-20
 0.0441837    0.0365564    0.00100848      3.87003e-20  3.20196e-20
 0.275004     0.00627687   0.00627687   …  2.40874e-19  5.49788e-21

julia> K12^2  # example
4096×4096 KroneckerPower{Float64,KroneckerPower{Float64,Array{Float64,2},2},6}:
 1.93667e-11  2.97575e-12  2.97575e-12  …  2.18277e-20  3.3539e-21
 2.23857e-11  1.6281e-11   3.43963e-12     2.52304e-20  1.835e-20
 2.23857e-11  3.43963e-12  1.6281e-11      1.19425e-19  1.835e-20
 2.58754e-11  1.8819e-11   1.8819e-11      1.38041e-19  1.00397e-19
 2.23857e-11  3.43963e-12  3.43963e-12     1.19425e-19  1.835e-20
 2.58754e-11  1.8819e-11   3.97583e-12  …  1.38041e-19  1.00397e-19
 2.58754e-11  3.97583e-12  1.8819e-11      6.53399e-19  1.00397e-19
 2.9909e-11   2.17527e-11  2.17527e-11     7.55256e-19  5.49293e-19
 2.23857e-11  3.43963e-12  3.43963e-12     1.19425e-19  1.835e-20
 2.58754e-11  1.8819e-11   3.97583e-12     1.38041e-19  1.00397e-19
 ⋮                                      ⋱               ⋮
 9.53079e-11  6.93169e-11  6.93169e-11     6.06418e-13  4.41044e-13
 7.13341e-11  1.09607e-11  1.09607e-11     9.58895e-14  1.47337e-14
 8.24542e-11  5.99685e-11  1.26693e-11     1.10838e-13  8.06115e-14
 8.24542e-11  1.26693e-11  5.99685e-11  …  5.24633e-13  8.06115e-14
 9.53079e-11  6.93169e-11  6.93169e-11     6.06418e-13  4.41044e-13
 8.24542e-11  1.26693e-11  1.26693e-11     5.24633e-13  8.06115e-14
 9.53079e-11  6.93169e-11  1.46444e-11     6.06418e-13  4.41044e-13
 9.53079e-11  1.46444e-11  6.93169e-11     2.87039e-12  4.41044e-13
 1.10165e-10  8.01226e-11  8.01226e-11  …  3.31785e-12  2.41305e-12

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.622603  0.754372
 0.699774  0.171832

julia> P10 = P ⊗ 10
1024×1024 KroneckerPower{Float64,Array{Float64,2},10}:
 0.00875209  0.0106044   0.0106044   …  0.0492583   0.0492583   0.0596835
 0.0098369   0.00241549  0.0119188      0.0112201   0.0553639   0.0135948
 0.0098369   0.0119188   0.00241549     0.0553639   0.0112201   0.0135948
 0.0110562   0.00271488  0.00271488     0.0126109   0.0126109   0.00309664
 0.0098369   0.0119188   0.0119188      0.0112201   0.0112201   0.0135948
 0.0110562   0.00271488  0.0133961   …  0.00255574  0.0126109   0.00309664
 0.0110562   0.0133961   0.00271488     0.0126109   0.00255574  0.00309664
 0.0124266   0.00305139  0.00305139     0.00287252  0.00287252  0.000705358
 0.0098369   0.0119188   0.0119188      0.0112201   0.0112201   0.0135948
 0.0110562   0.00271488  0.0133961      0.00255574  0.0126109   0.00309664
 ⋮                                   ⋱
 0.0250514   0.00615145  0.00615145  …  4.01212e-7  4.01212e-7  9.8519e-8
 0.0198307   0.0240277   0.0240277      1.56714e-6  1.56714e-6  1.89882e-6
 0.0222887   0.00547307  0.0270059      3.56966e-7  1.76139e-6  4.32515e-7
 0.0222887   0.0270059   0.00547307     1.76139e-6  3.56966e-7  4.32515e-7
 0.0250514   0.00615145  0.00615145     4.01212e-7  4.01212e-7  9.8519e-8
 0.0222887   0.0270059   0.0270059   …  3.56966e-7  3.56966e-7  4.32515e-7
 0.0250514   0.00615145  0.0303533      8.13103e-8  4.01212e-7  9.8519e-8
 0.0250514   0.0303533   0.00615145     4.01212e-7  8.13103e-8  9.8519e-8
 0.0281565   0.00691392  0.00691392     9.13887e-8  9.13887e-8  2.24408e-8

julia> sum(P10)  # expected number of edges
3304.339831345834

julia> A = fastsample(P10)
1024×1024 SparseArrays.SparseMatrixCSC{Bool,Int64} with 3279 stored entries:
  [91 ,    1]  =  1
  [140,    1]  =  1
  [174,    1]  =  1
  [189,    1]  =  1
  [418,    1]  =  1
  [532,    1]  =  1
  [606,    1]  =  1
  [626,    1]  =  1
  [764,    1]  =  1
  ⋮
  [45 , 1011]  =  1
  [519, 1011]  =  1
  [299, 1014]  =  1
  [539, 1016]  =  1
  [70 , 1017]  =  1
  [264, 1018]  =  1
  [658, 1020]  =  1
  [65 , 1024]  =  1
  [69 , 1024]  =  1
  [257, 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