Stochastic Kronecker graph edge-probability model

The model takes an n0 by n0 initiator matrix Theta of edge probabilities and forms its k-th Kronecker power; the result is the matrix of independent edge probabilities on N = n0^k nodes, so the whole distribution is determined by Theta and k and nothing has to be sampled. By multiplicativity of the Kronecker product the expected edge count equals (sum Theta)^k exactly. Drawing a realisation is a separate step and is deliberately not folded in, since it would make a closed form stochastic for no reason.

Usage

Krfgrp(seed, k)

Arguments

seed

Square initiator matrix with entries in [0, 1].

k

Kronecker power; the graph has n0^k nodes.

Value

List with estimate (expected edges), expected_edges, expected_self_loops, n_nodes, mean_degree, max_degree, min_degree, p_min, p_max, density, seed_sum, k, P, n, method.

Details

Formula: P[i,j] = prod_l Theta[i_l, j_l] over the base-n0 digits.

References

Leskovec, Chakrabarti, Kleinberg, Faloutsos and Ghahramani (2010), Kronecker graphs: an approach to modeling networks, Journal of Machine Learning Research 11:985-1042.

Examples

Krfgrp(seed = 1, k = 5L)
#> $estimate
#> [1] 1
#> 
#> $expected_edges
#> [1] 1
#> 
#> $expected_self_loops
#> [1] 1
#> 
#> $n_nodes
#> [1] 1
#> 
#> $mean_degree
#> [1] 1
#> 
#> $max_degree
#> [1] 1
#> 
#> $min_degree
#> [1] 1
#> 
#> $p_min
#> [1] 1
#> 
#> $p_max
#> [1] 1
#> 
#> $density
#> [1] 1
#> 
#> $seed_sum
#> [1] 1
#> 
#> $k
#> [1] 5
#> 
#> $P
#> [1] 1
#> 
#> $n
#> [1] 1
#> 
#> $method
#> [1] "P = Theta^[k]; sum(P) = (sum Theta)^k, Leskovec et al (2010) JMLR 11:985-1042"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"