Useful functions

Here we report the documentation of some useful functions, used both in the static and dynamic settings.

CoDeBetHe.matrix_C — Function

For a given diagonal matrix Π, with Tr(Π) = 1, this function generates a class affinity matrix C such that CΠ has the all ones vector as leading eigenvector with eigenvalue equal to c. The parameter f allows to add randomness in the elements of C ∈ R^{k×k}

Usage

C = matrix_C(c_out,c,f,π_v)

Entry

  • c_out: average value of the off-diagonal terms of the matrix C (Float64)
  • c : leading eigenvalue of CΠ (Float64)
  • f : variance of the off-diagonal terms of the matrix C (Float64)
  • π_v : vector of size k containing the diagonal elements of Π (Array{Float64,1})

Returns

C : matrix C (Array{Float64,2})

CoDeBetHe.create_label_vector — Function

This function generates a label vector of size n, given the class sizes

Usage

ℓ = create_label_vector(n, k, π_v)

Entry

  • n : number of nodes (Int64)
  • k : number of classes (Int64)
  • π_v : vector of size k; the i-th entry corresponds to the fraction of nodes with label equal to i, so that ∑ π_v = 1 (Array{Float64,1})

Returns

ℓ : label vector (Array{Int64,1})

CoDeBetHe.adjacency_matrix_DCSBM — Function

This function generates the sparse representation of an adjacency matrix A ∈ R^{n×n} according to the degree-corrected stochastic block model.

Usage

A = adjacency_matrix_DCSBM(C::Array{Float64,2},c::Float64,ℓ::Array{Int64,1},θ::Array{Float64,1})

Entry

  • C : class affinity matrix C (Array{Float64,2})
  • c : average degree (Float64)
  • ℓ : label vector of size n (Array{Int64,1})
  • θ : vector generating an arbitrary degree distribution. The value cθ_i is the expected degree of node i (Array{Float64,1})

Returns

A : sparse representation of the adjacency matrix (SparseMatrixCSC{Float64,Int64})

CoDeBetHe.community_detection_optimal_BH — Function

This function performs community detection of a graph, according to Algorithm 2 of (Dall'Amico 2020)

Usage

cluster = community_detection_optimal_BH(A; k, ℓ, ϵ, projection, k_max, verbose)

Entry

A : sparse representation of the adjacenccy matrix (SparseMatrixCSC{Float64,Int64})

Optional inputs

  • k : number of classes (Int64). If not provided, it is estimated
  • ℓ : ground-truth vector (Array{Int32,1}). If not provided, the overlap will not be computed.
  • ϵ : precision error (Float64). If not provided, it is set to 2*10^(-5)
  • projection : (Bool) if true, the embedding on which k-means is run will be projected on the unitary hypersphere. Default is true.
  • verbose : (0, 1, or 2) if 0, nothing is printed. If 1, some information is printed. If 2, more information is printed. Default is 1.

Returns

  • cluster.ℓ : estimated assignement vector (Array{Int64,1})
  • cluster.k : number of classes obtained (Int64)
  • cluster.overlap : overlap obtained (Float64)
  • cluster.modularity : modularity obtained (Float64)
  • cluster.ζ : vector containing the values of ζ_p for 2≤p≤k (Array{Float64,1})
CoDeBetHe.adjacency_matrix_DDCSBM — Function

This function generates a series of T adjacency matrices A_t ∈ R^{n×n} in sparse represention from the dynamical degree-corrected stochastic block model

Usage

AT, ℓ_T = adjacency_matrix_DDCSBM(T, C, c, η, θ, π_v)

Entry

  • T: number of time steps (Int64)
  • C : matrix C (Array{Float64,2})
  • c : average degree (Float64)
  • η : label persistence (Float64)
  • θ : vector generating an arbitrary degree distribution. The value cθ_i is the expected degree of node i (Array{Float64,1})
  • π_v : vector of size k; the i-th entry corresponds to the fraction of nodes with label equal to i, so that ∑ π_v = 1 (Array{Float64,1})

Returns

  • AT : At[t] is the sparse representation of the adjacency matrix at time t (Array{SparseMatrixCSC{Float64,Int64},1})
  • ℓ_T : the entry ℓ_T[t,i] contains the label of node i at time t (T×n Array{Int64,2})
CoDeBetHe.dynamic_community_detection_BH — Function

This function implements algorithm 1 of (Dall'Amico 2020) for dynamical community detection.

Usage

cluster = dynamic_community_detection_BH(AT, η, k; ℓ_T, approx_embedding, verbose, m)

Entry

  • AT : At[t] is the sparse representation of the adjacency matrix at time t (Array{SparseMatrixCSC{Float64,Int64},1})
  • η : label persistence (Float64)
  • k : number of communities (Int64)

Optional inputs

  • ℓ_T : the entry ℓ_T[t,i] contains the label of node i at time t (T×n Array{Int64,2}). If not available, the overlap with the ground-truth is not computed.
  • approx_embedding : (Bool), if true the informative eigenvectors are obtained using the approximate procedure detailed in Algorithm 2 of (Dall'Amico 2020). By default set to false
  • verbose : (0, 1, or 2) if 0, nothing is printed. If 1, some information is printed. If 2, more information is printed. Default is 1.
  • m : order of the polynomial approximation (Int64). If m is not known, an adaptive choice for m will be adopted. By default set to nothing

Returns

  • cluster.modularity : cluster.modularity[t] is the modularity obtained at time t (Array{Float64,1})
  • cluster.overlap : cluster.overlap[t] is the overlap obtained at time t (Array{Float64,1})
  • cluster.ℓ : cluster.ℓ[t,i] is the vector of the estimated label i at time t (Array{Array{Int64,1},1})