Network Histogram approximation [1].

Contains the estimated network histogram and the node labels.

Fields

• θ::Matrix{T}: Estimated stochastic block model parameters.
• node_labels::Vector{Int}: Node labels for each node in the adjacency matrix used to estimate the network histogram.

References

[1] - Olhede, Sofia C., and Patrick J. Wolfe. "Network histograms and universality of blockmodel approximation." Proceedings of the National Academy of Sciences 111.41 (2014): 14722-14727.

_graphhist(A, record_trace=Val{true}(); h, maxitr, swap_rule, starting_assignment_rule, accept_rule, stop_rule)

Internal version of graphhist which is type stable.

graphhist(A; h = select_bandwidth(A), maxitr = 1000, swap_rule = RandomNodeSwap(),
starting_assignment_rule = RandomStart(), accept_rule = Strict(),
stop_rule = PreviousBestValue(3), record_trace=true)

Computes the graph histogram approximation.

Arguments

• A: adjacency matrix of a simple graph

• h: bandwidth of the graph histogram (number of nodes in a group or percentage (in [0,1]) of nodes in a group)

• record_trace (optional): whether to record the trace of the optimization process and return it as part of the output. Default is true.

Returns

named tuple with the following fields:

• graphhist: the graph histogram approximation
• trace: the trace of the optimization process (if record_trace is true)
• likelihood: the loglikelihood of the graph histogram approximation

Examples

julia> A = [0 0 1 0 1 0 1 1 0 1
             0 0 1 1 1 1 1 1 0 0
             1 1 0 1 0 0 0 0 1 0
             0 1 1 0 1 0 1 0 0 0
             1 1 0 1 0 0 1 0 0 1
             0 1 0 0 0 0 0 1 0 0
             1 1 0 1 1 0 0 1 0 1
             1 1 0 0 0 1 1 0 0 1
             0 0 1 0 0 0 0 0 0 1
             1 0 0 0 1 0 1 1 1 0]
julia> out = graphhist(A);
julia> graphist_approx = out.graphist
...
julia> trace = out.trace
NetworkHistogram.TraceHistory{...}
  :best_likelihood => 1 elements {Int64,Float64}
  :proposal_likelihood => 5 elements {Int64,Float64}
  :current_likelihood => 5 elements {Int64,Float64})
julia> loglikelihood = out.likelihood
-22.337057781338277

graphhist_format_output(best, history)

Formates the graphhist output depending on the type of history requested by the user.

initialize(A, h, starting_assignment_rule, record_trace)

Initialize the memory required for finding optimal graph histogram.

compute_log_likelihood(number_groups, estimated_theta, counts, number_nodes)

Compute the scaled log-likelihood in terms of communities:

\[l(z;A) = \frac{1}{n} \sum_{g_1 = 1}^{G} \sum_{g_2 \geq g_1}^{G} \left[ \theta_{g_1g_2} \log(\theta_{g_1g_2}) + (1 - \theta_{g_1g_2}) \log(1 - \theta_{g_1g_2}) \right] \cdot c_{g_1g_2},\]

where $c_{g_1g_2}$ ($\theta_{g_1g_2}$) is the number of possible edges (estimated probability) between communities $g_1$ and $g_2$, $n$ is the number of nodes, and $z_i ∈ \{1, \dots, G\}$ is the community assignment of node $i$.

compute_log_likelihood(assignment::Assignment)

Compute the scaled log-likelihood of the assignment.

\[ l(z;A) = \frac{1}{n}\sum\limits_{i=1}^n \sum\limits_{j>i}^n \left[ A_{ij} \log(\hat{\theta}_{z_i z_j}) + (1 - A_{ij}) \log(1 - \hat{\theta}_{z_i z_j}) \right],\]

where $\hat{\theta}_{ab}$ is the estimated probability of an edge between communities $a$ and $b$

\[ \hat{\theta}_{ab} = \frac{\sum\limits_{i<j} A_{ij} \mathbb{1}(z_i = a, z_j = b) }{\sum\limits_{i<j} \mathbb{1}(z_i = a, z_j = b)}.\]

deepcopy!(a::Assignment, b::Assignment)

Deep copy the attributes of b to a.

Array-like storage for the number of nodes in each group.

create_proposal!(history::GraphOptimizationHistory, iteration::Int, proposal::Assignment,
                      current::Assignment, A, swap_rule)

Create a new proposal by swapping the labels of two nodes. The new assignment is stored in proposal. The swap is selected using the swap_rule function. The likelihood of the new proposal is stored in the history.

make_proposal!(proposal::Assignment, current::Assignment, swap::Tuple{Int, Int}, A)

From the current assignment, create a new assignment by swapping the labels of the nodes specified in swap. The new assignment is stored in proposal.

updateLL!(proposal::Assignment)

Update the likelihood of the proposal assignment based on its observed and estimated attributes.

update_labels!(proposal::Assignment, swap::Tuple{Int, Int}, current::Assignment)

Update the labels of the nodes specified in swap in the proposal assignment.