UBCM

Maximum entropy model for the Undirected Binary Configuration Model (UBCM).

The object holds the maximum likelihood parameters of the model (θ) and optionally the expected adjacency matrix (G), and the variance for the elements of the adjacency matrix (σ). All settings and other metadata are stored in the status field.

UBCM(G::T; d::Vector=Graphs.degree(G), precision::N=Float64, kwargs...) where {T<:Graphs.AbstractGraph, N<:Real}
UBCM(d::Vector{T}, precision::Type{<:AbstractFloat}=Float64, kwargs...)

Constructor function for the UBCM type.

By default and dependng on the graph type T, the definition of degree from Graphs.jl is applied. If you want to use a different definition of degree, you can pass a vector of degrees as the second argument. If you want to generate a model directly from a degree sequence without an underlying graph, you can simply pass the degree sequence as an argument. If you want to work from an adjacency matrix, or edge list, you can use the graph constructors from the JuliaGraphs ecosystem.

Examples

# generating a model from a graph
julia> G = MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate)
{34, 78} undirected simple Int64 graph
julia> model = UBCM(G)
UBCM{Graphs.SimpleGraphs.SimpleGraph{Int64}, Float64} (34 vertices, 11 unique degrees, 0.32 compression ratio)

# generating a model directly from a degree sequence
julia> model = UBCM(d=[4;3;3;3;2])
UBCM{Nothing, Float64} (5 vertices, 3 unique degrees, 0.60 compression ratio)

# generating a model directly from a degree sequence with a different precision
julia> model = UBCM(d=[4;3;3;3;2], precision=Float16)
UBCM{Nothing, Float16} (5 vertices, 3 unique degrees, 0.60 compression ratio)

# generating a model from an adjacency matrix
julia> A = [0 1 1;1 0 0;1 0 0];

julia> G = MaxEntropyGraphs.Graphs.SimpleGraph(A)
{3, 2} undirected simple Int64 graph
julia> model = UBCM(G)
UBCM{Graphs.SimpleGraphs.SimpleGraph{Int64}, Float64} (3 vertices, 2 unique degrees, 0.67 compression ratio)

# generating a model from an edge list
julia> E = [(1,2),(1,3),(2,3)];

julia> edgelist = [MaxEntropyGraphs.Graphs.Edge(x,y) for (x,y) in E];

julia> G = MaxEntropyGraphs.Graphs.SimpleGraphFromIterator(edgelist)
{3, 3} undirected simple Int64 graph
julia> model = UBCM(G)
UBCM{Graphs.SimpleGraphs.SimpleGraph{Int64}, Float64} (3 vertices, 1 unique degrees, 0.33 compression ratio)

See also Graphs.degree, SimpleWeightedGraphs.inneighbors.

solve_model!(m::UBCM; kwargs...)

Compute the likelihood maximising parameters of the UBCM model m.

Arguments

• method::Symbol: solution method to use, can be :fixedpoint (default), or :NelderMead, :BFGS, :LBFGS and :Newton.
• initial::Symbol: initial guess for the parameters $\Theta$, can be :degrees, :degreesminor, :random, :uniform, or :chunglu.
• maxiters::Int: maximum number of iterations for the solver (defaults to 1000).
• verbose::Bool: set to show log messages (defaults to false).
• ftol::Real: function tolerance for convergence with the fixedpoint method (defaults to 1e-8).
• abstol::Union{Number, Nothing}: absolute function tolerance for convergence with the other methods (defaults to nothing).
• reltol::Union{Number, Nothing}: relative function tolerance for convergence with the other methods (defaults to nothing).
• AD_method::Symbol: autodiff method to use, can be any of :AutoZygote, :AutoReverseDiff, :AutoForwardDiff and :AutoFiniteDiff. Performance depends on the size of the problem (defaults to :AutoZygote),
• analytical_gradient::Bool: set the use the analytical gradient instead of the one generated with autodiff (defaults to false)

Examples

# default use
julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> solve_model!(model);

# using analytical gradient and degrees minor initial guess
julia> solve_model!(model, method=:BFGS, analytical_gradient=true, initial=:degrees_minor)
(UBCM{Graphs.SimpleGraphs.SimpleGraph{Int64}, Float64} (34 vertices, 11 unique degrees, 0.32 compression ratio), retcode: Success
u: [2.851659905903854, 2.053008374573552, 1.5432639513870743, 1.152360118212239, 0.8271267490690292, 0.5445045274064909, -0.1398726818076551, -0.3293252270659469, -0.6706207459338859, -1.2685575582149227, -1.410096540372487]
Final objective value:     168.68325136302835
)

See also: initial_guess, ∇L_UBCM_reduced!

initial_guess(m::UBCM, method::Symbol=:degrees)

Compute an initial guess for the maximum likelihood parameters of the UBCM model m using the method method.

The methods available are:

• :degrees (default): the initial guess is computed using the degrees of the graph, i.e. $\theta_{i} = -\log(d_{i})$
• :degrees_minor: the initial guess is computed using the degrees of the graph and the number of edges, i.e. $\theta_{i} = -\log(d_{i}/(\sqrt{E} + 1))$
• :random: the initial guess is computed using random values between 0 and 1, i.e. $\theta_{i} = -\log(r_{i})$ where $r_{i} \sim U(0,1)$
• :uniform: the initial guess is uniformily set to 0.5, i.e. $\theta_{i} = -\log(0.5)$
• :chung_lu: the initial guess is computed using the degrees of the graph and the number of edges, i.e. $\theta_{i} = -\log(d_{i}/(2E))$

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> initial_guess(model, method=:random);

julia> initial_guess(model, method=:uniform);

julia> initial_guess(model, method=:degrees_minor);

julia> initial_guess(model, method=:chung_lu);

julia> initial_guess(model)
11-element Vector{Float64}:
 -0.0
 -0.6931471805599453
 -1.0986122886681098
 -1.3862943611198906
 -1.6094379124341003
 -1.791759469228055
 -2.1972245773362196
 -2.302585092994046
 -2.4849066497880004
 -2.772588722239781
 -2.833213344056216

rand(m::UBCM; precomputed=false)

Generate a random graph from the UBCM model m.

Arguments

• precomputed::Bool: if true, the precomputed expected adjacency matrix (m.Ĝ) is used to generate the random graph, otherwise the maximum likelihood parameters are used to generate the random graph on the fly. For larger networks, it is recommended to not precompute the expected adjacency matrix to limit memory pressure.

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate)); # generate a UBCM model from the karate club network

julia> solve_model!(model); # compute the maximum likelihood parameters

julia> sample = rand(model); # sample a random graph

julia> typeof(sample)
Graphs.SimpleGraphs.SimpleGraph{Int64}

rand(m::UBCM, n::Int; precomputed=false)

Generate n random graphs from the UBCM model m. If multithreading is available, the graphs are generated in parallel.

Arguments

• precomputed::Bool: if true, the precomputed expected adjacency matrix (m.Ĝ) is used to generate the random graph, otherwise the maximum likelihood parameters are used to generate the random graph on the fly. For larger networks, it is recommended to not precompute the expected adjacency matrix to limit memory pressure.

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate)); # generate a UBCM model from the karate club network

julia> solve_model!(model); # compute the maximum likelihood parameters

julia> sample = rand(model, 10); # sample a set of random graphs

julia> typeof(sample)
Vector{SimpleGraph{Int64}} (alias for Array{Graphs.SimpleGraphs.SimpleGraph{Int64}, 1})

AIC(m::UBCM)

Compute the Akaike Information Criterion (AIC) for the UBCM model m. The parameters of the models most be computed beforehand. If the number of empirical observations becomes too small with respect to the number of parameters, you will get a warning. In that case, the corrected AIC (AICc) should be used instead.

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> solve_model!(model);

julia> AIC(model);
[...]

See also AICc, L_UBCM_reduced.

AICc(m::UBCM)

Compute the corrected Akaike Information Criterion (AICc) for the UBCM model m. The parameters of the models most be computed beforehand.

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> solve_model!(model);

julia> AICc(model)
409.891217554954

See also AIC, L_UBCM_reduced.

BIC(m::UBCM)

Compute the Bayesian Information Criterion (BIC) for the UBCM model m. The parameters of the models most be computed beforehand. BIC is believed to be more restrictive than AIC, as the former favors models with a lower number of parameters than those favored by the latter.

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> solve_model!(model);

julia> BIC(model)
552.5770135138283

See also AIC, L_UBCM_reduced.

Return the reduced number of nodes in the UBCM network

L_UBCM_reduced(θ::Vector, K::Vector, F::Vector)

Compute the log-likelihood of the reduced UBCM model using the exponential formulation in order to maintain convexity.

Arguments

• θ: the maximum likelihood parameters of the model
• K: the reduced degree sequence
• F: the frequency of each degree in the degree sequence

The function returns the log-likelihood of the reduced model. For the optimisation, this function will be used to generate an anonymous function associated with a specific model.

Examples

# Generic use:
julia> θ = [1.0, 2.0, 3.0, 4.0, 5.0];

julia> K = [1, 2, 3, 4, 5];

julia> F = [1, 2, 3, 4, 5];

julia> L_UBCM_reduced(θ, K, F)
-225.3065566905141

L_UBCM_reduced(m::UBCM)

Return the log-likelihood of the UBCM model m based on the computed maximum likelihood parameters.

Examples

# Use with UBCM model:
julia> G = MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate);

julia> model = UBCM(G);

julia> solve_model!(model);

julia> L_UBCM_reduced(model)
-168.68325136302832

See also L_UBCM_reduced(::Vector, ::Vector, ::Vector)

∇L_UBCM_reduced!(∇L::Vector, θ::Vector, K::Vector, F::Vector, x::Vector)

Compute the gradient of the log-likelihood of the reduced UBCM model using the exponential formulation (to maintain convexity).

For the optimisation, this function will be used togenerate an anonymous function associated with a specific model. The gradient is non-allocating and will update pre-allocated vectors (∇L and x) for speed.

Arguments

• ∇L: the gradient of the log-likelihood of the reduced model
• θ: the maximum likelihood parameters of the model
• K: the reduced degree sequence
• F: the frequency of each degree in the degree sequence
• x: the exponentiated maximum likelihood parameters of the model ( xᵢ = exp(-θᵢ) )

Examples

# Explicit use with UBCM model:
julia> G = MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate);

julia> model = UBCM(G);

julia> ∇L = zeros(Real, length(model.θᵣ));

julia> x  = zeros(Real, length(model.θᵣ));

julia> ∇model_fun! = θ -> ∇L_UBCM_reduced!(∇L, θ, model.dᵣ, model.f, x);

julia> ∇model_fun!(model.θᵣ);

# Use within optimisation.jl framework:
julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> fun =  (θ, p) ->  - L_UBCM_reduced(θ, model.dᵣ, model.f);

julia> x  = zeros(Real, length(model.θᵣ)); # initialise gradient buffer

julia> ∇fun! = (∇L, θ, p) -> ∇L_UBCM_reduced!(∇L, θ, model.dᵣ, model.f, x); # define gradient

julia> θ₀ = initial_guess(model); # initial condition

julia> foo = MaxEntropyGraphs.Optimization.OptimizationFunction(fun, grad=∇fun!); # define target function 

julia> prob  = MaxEntropyGraphs.Optimization.OptimizationProblem(foo, θ₀); # define the optimisation problem

julia> method = MaxEntropyGraphs.OptimizationOptimJL.LBFGS(); # set the optimisation method

julia> MaxEntropyGraphs.Optimization.solve(prob, method); # solve it

∇L_UBCM_reduced_minus!(args...)

Compute minus the gradient of the log-likelihood of the reduced UBCM model using the exponential formulation in order to maintain convexity. Used for optimisation in a non-allocating manner.

See also ∇L_UBCM_reduced!

UBCM_reduced_iter!(θ, K, F, x, G)

Computer the next fixed-point iteration for the UBCM model using the exponential formulation in order to maintain convexity. The function will update pre-allocated vectors (G and x) for speed.

Arguments

• θ: the maximum likelihood parameters of the model
• K: the reduced degree sequence
• F: the frequency of each degree in the degree sequence
• x: the exponentiated maximum likelihood parameters of the model ( xᵢ = exp(-θᵢ) ) (pre-allocated)
• G: the next fixed-point iteration for the UBCM model (pre-allocated)

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> G = zeros(eltype(model.θᵣ), length(model.θᵣ));

julia> x = zeros(eltype(model.θᵣ), length(model.θᵣ));

julia> UBCM_FP! = θ -> UBCM_reduced_iter!(θ, model.dᵣ, model.f, x, G);

julia> UBCM_FP!(initial_guess(model));

set_xᵣ!(m::UBCM)

Set the value of xᵣ to exp(-θᵣ) for the UBCM model m

Ĝ(m::UBCM)

Compute the expected adjacency matrix for the UBCM model m

set_Ĝ!(m::UBCM)

Set the expected adjacency matrix for the UBCM model m

σˣ(m::UBCM{T,N}) where {T,N}

Compute the standard deviation for the elements of the adjacency matrix for the UBCM model m.

Note: read as "sigma star"

set_σ!(m::UBCM)

Set the standard deviation for the elements of the adjacency matrix for the UBCM model m

precision(m::UBCM)

Determine the compute precision of the UBCM model m.

Examples

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate));

julia> MaxEntropyGraphs.precision(model)
Float64

julia> model = UBCM(MaxEntropyGraphs.Graphs.SimpleGraphs.smallgraph(:karate), precision=Float32);

julia> MaxEntropyGraphs.precision(model)
Float32

A(m::UBCM,i::Int,j::Int)

Return the expected value of the adjacency matrix for the UBCM model m at the node pair (i,j).

❗ For perfomance reasons, the function does not check:

• if the node pair is valid.
• if the parameters of the model have been computed.

f_UBCM(x::T)

Helper function for the UBCM model to compute the expected value of the adjacency matrix. The function computes the expression x / (1 + x). As an argument you need to pass the product of the maximum likelihood parameters xᵣ[i] * xᵣ[j] from a UBCM model.

σₓ(m::UBCM, X::function)

Compute the standard deviation of metric X for the UBCM model m.

This requires that both the expected values (m.Ĝ) and standard deviations (m.σ) are computed for m.