Reference

Hypergraph{T} <: AbstractMatrix{Union{T, Nothing}}

A hypergraph storing information about vertices and hyperedges.

Constructors

Hypergraph{T}(n::Integer,k::Integer) where {T<:Real}
Hypergraph{T,V}(n::Integer, k::Integer;
    v_meta=Vector{Union{V,Nothing}}(nothing, n)
    ) where {T<:Real, V}
Hypergraph{T,V,E}(n::Integer, k::Integer;
    v_meta=Vector{Union{V,Nothing}}(nothing, n),
    he_meta=Vector{Union{E,Nothing}}(nothing, k)
    ) where {T<:Real, V, E}
Hypergraph{T,V,E,D}(n::Integer, k::Integer,
    v_meta=Vector{Union{V,Nothing}}(nothing, n),
    he_meta=Vector{Union{E,Nothing}}(nothing, k)
    ) where {T<:Real,V,E,D<:AbstractDict{Int,T}}

Construct a hypergraph with a given number of vertices and hyperedges. Optionally, values of type V can be stored at vertices and values of type E can be stored at hyperedges. By default the hypegraph uses a Dict{Int,T} for the internal data storage, however a different dictionary such as SortedDict to ensure result replicability can be used (e.g. when doing stochastic simulations on hypergraphs).

Hypergraph(m::AbstractMatrix{Union{T, Nothing}}) where {T<:Real}
Hypergraph{T, V}(m::AbstractMatrix{Union{T, Nothing}};
    v_meta=Vector{Union{V,Nothing}}(nothing, size(m,1))
    ) where {T<:Real, V}
Hypergraph{T, V, E}(m::AbstractMatrix{Union{T, Nothing}};
    v_meta=Vector{Union{V,Nothing}}(nothing, size(m,1)),
    he_meta=Vector{Union{E,Nothing}}(nothing, size(m,2))
    ) where {T<:Real, V, E}
Hypergraph{T, V, E, D}(m::AbstractMatrix{Union{T, Nothing}};
    v_meta=Vector{Union{V,Nothing}}(nothing, size(m,1)),
    he_meta=Vector{Union{E,Nothing}}(nothing, size(m,2))
    ) where {T<:Real, V, E, D<:AbstractDict{Int,T}}

Construct a hypergraph using its matrix representation. In the matrix representation rows are vertices and columns are hyperedges. Optionally, values of type V can be stored at vertices and values of type E can be stored at hyperedges. By default the hypegraph uses a Dict{Int,T} for the internal data storage, however a different dictionary such as SortedDict to ensure result replicability can be used (e.g. when doing stochastic simulations on hypergraphs).

Hypergraph(g::Graphs.Graph)

Constructs a hypergraph of degree 2 by making a deep copy of Graphs.Graph. A SortedDict will be used for internal data storage of the hypergraph.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph
• D : dictionary for storing values the default is Dict{Int, T}
• n : number of vertices
• k : number of hyperedges
• m : a matrix representation rows are vertices and columns are hyperedges

random_model(nVertices::Int, nEdges::Int)

Generate a random hypergraph without any structural constraints.

The Algorithm

Given two integer parameters nVertices and nEdges (the number of nodes and hyperedges, respectively), the algorithm computes - for each hyperedge he={1,...,m} - a random number s ϵ [1, n] (i.e. the hyperedge size). Then, the algorithm selects uniformly at random s vertices from V to be added in he.

random_kuniform_model(nVertices::Int, nEdges::Int, k::Int)

Generates a k-uniform hypergraph, i.e. an hypergraph where each hyperedge has size k.

The Algorithm

The algorithm proceeds as the randomH, forcing the size of each hyperedge equal to k.

random_dregular_model(nVertices::Int, nEdges::Int, d::Int)

Generates a d-regular hypergraph, where each node has degree d.

The Algorithm

The algorithm exploits the k-uniform approach described for the randomkuniformmodel method to build a d-regular hypergraph H having nVertices nodes and nEdges edges. It returns the hypergraph H^* dual of H.

random_preferential_model(nVertices::Int, p::Real; H = random_model(5,5))

Generate a hypergraph with a preferential attachment rule between nodes, as presented in Avin, C., Lotker, Z., and Peleg, D.Random preferential attachment hyper-graphs. Computer Science 23 (2015).

The Algorithm

The algorithm starts with a random graph with 5 nodes and 5 edges. For this reason, the generated random graph has at least 5 nodes and 5 edges. It iteratively adds a node or a edge, according to a given parameter p, which defines the probability of creating a new node or a new hyperedge.

More in detail, the connections with the new node/hyperedge are generated according to a preferential attachment policy defined by p.

The so-built hypergraph will have nVertices vertices.

The starting hypergraph can be instantiated as preferred.

add_hyperedge!(h::Hypergraph{T, V, E, D};
               vertices::D = D(), he_meta::Union{E,Nothing}=nothing
               ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Adds a hyperedge to a given hypergraph h. Optionally, existing vertices can be added to the created hyperedge. The paramater vertices represents a dictionary of vertex identifiers and values stored at the hyperedges. Additionally, a value can be stored with the hyperedge using the he_meta keyword parameter.

add_vertex!(h::Hypergraph{T, V, E, D};
            hyperedges::D = D(), v_meta::Union{V,Nothing} = nothing
            ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Adds a vertex to a given hypergraph h. Optionally, the vertex can be added to existing hyperedges. The hyperedges parameter presents a dictionary of hyperedge identifiers and values stored at the hyperedges. Additionally, a value can be stored with the vertex using the v_meta keyword parameter.

set_vertex_meta!(h::Hypergraph{T, V, E, D}, new_value::Union{V,Nothing},
    id::Int) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Sets a new meta value new_value for the vertex id in the hypegraph h.

get_vertex_meta(h::Hypergraph{T, V, E, D}, id::Int
                ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Returns a meta value stored at the vertex id in the hypergraph h.

set_hyperedge_meta!(h::Hypergraph{T, V, E, D},
    new_value::Union{E,Nothing}, id::Int
    ) where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Sets a new meta value new_value for the hyperedge id in the hypegraph h.

get_hyperedge_meta(h::Hypergraph{T, V, E, D}, id::Int)
    where {T <: Real, V, E, D <: AbstractDict{Int,T}}

Returns a meta value stored at the hyperedge id in the hypergraph h.

remove_vertex!(h::Hypergraph, v::Int)

Removes the vertex v from a given hypergraph h. Note that running this function will cause reordering of vertices in the hypergraph: the vertex v will replaced by the last vertex of the hypergraph and the list of vertices will be shrunk.

remove_hyperedge!(h::Hypergraph, e::Int)

Removes the heyperedge e from a given hypergraph h. Note that running this function will cause reordering of hyperedges in the hypergraph: the hyperedge e will replaced by the last hyperedge of the hypergraph and the list of hyperedges will be shrunk.

Base.getindex(h::Hypergraph, idx::Vararg{Int,2})

Returns a value for a given vertex-hyperedge pair idx for a hypergraph h. If a vertex does not belong to a hyperedge nothing is returned.

Base.setindex!(h::Hypergraph, ::Nothing, idx::Vararg{Int,2})

Removes a vertex from a given hyperedge for a hypergraph h and a given vertex-hyperedge pair idx. Note that trying to remove a vertex from a hyperedge when it is not present will not throw an error.

Base.setindex!(h::Hypergraph, v::Real, idx::Vararg{Int,2})

Adds a vertex to a hyperedge (represented by indices idx) and assigns value v to be stored with that assignment.

BipartiteView{T<:Real} <: Graphs.SimpleGraphs.AbstractSimpleGraph{Int}

Represents a bipartite view of a hypergraph h. Note this is a view - changes to the original hypergraph will be automatically reflected in the view.

Constructors

BipartiteView(::Hypergraph)

The bipartite view of a hypergraph is suitable for processing with the Graphs.jl package. Several Graphs methods are provided for the compability.

shortest_path(b::BipartiteView,source::Int, target::Int)

Finds a single shortest path in a graph b between vertices source and target. Note that if several paths of the same length exist, only one will be returned.

TwoSectionView{T<:Real} <: Graphs.SimpleGraphs.AbstractSimpleGraph{Int64}

Represents a 2-section view of a hypergraph h. Note (1) this is a view - changes to the original hypergraph will be automatically reflected in the view.

Note (2) The view will only work correctly for hypergraphs not having overlapping hyperedges. To check whether a graph has overlapping edges try has_overlapping_hedges(h) - for such graph you need to fully materialize it rather than use a view. This can be achieved via the get_twosection_adjacency_mx(h) method.

Constructors

TwoSectionView(::Hypergraph)

The 2-section view of a hypergraph is suitable for processing with the Graphs.jl package. Several Graphs methods are provided for the compability.

shortest_path(t::TwoSectionView,source::Int, target::Int)

Finds a single shortest path in a graph b between vertices source and target. Note that if several paths of the same length exist, only one will be returned.

Base.size(h::Hypergraph)

Returns the size of Hypergraph h. The result is a tuple of the number of vertices and the number of hyperedges

nhv(h::Hypergraph)

Return the number of vertices in the hypergraph h.

nhe(h::Hypergraph)

Return the number of hyperedges in the hypergraph h.

getvertices(h::Hypergraph, he_id::Int)

Returns vertices from a hypergraph a for a given hyperedge he_id.

gethyperedges(h::Hypergraph, v_id::Int)

Returns hyperedges for a given vertex v_id in a hypergraph h.

get_connected_components(h::Hypergraph)

Return an array of connected components in the hypergraph h (array of vectors of vertices) using recurrence.

conductance(h::Hypergraph, subset::Set{Int})::Float64

Calculate unweighted hypergraph conductance of subset. note: ∅ ⊊ subset ⊊ 1:nhv(h)

For more information see 1. Introduction at: Generalizing the Hypergraph Laplacian via a Diffusion Processwith Mediators, auhtors: T-H. Hubert Chan, Xhibin Liang.

get_twosection_adjacency_mx(h::Hypergraph{T,V,E}; count_self_loops::Bool=false,
                            replace_weights::Union{Nothing,Real}=nothing ) where {T<:Real, V, E}

Returns an adjacency matrix for a two section view of a hypergraph h.

random_walk(h::Hypergraph, start::Int; heselect::Function, vselect::Function)

Return a next vertex visited in assuming a random walk starting from vertex start. First a hyperedge is sampled with weights proportional to heselect function (by default each hyperedge is sampled with the same probability). Next a vertex within hyperedge is with weights proportional to vselect function (by default each vertex, including the source, is sampled with the same probability).

heselect and vselect functions take two arguments a Hypergraph and respectively a vertex identifier or a hyperedge identifier. The return values of both functions should be respectively a list of hyperedges or vertices and their weights.

Graphs.modularity(h::Hypergraph, partition::Vector{Set{Int}},

ha::HypergraphAggs=HypergraphAggs(h))

Calculates the strict modularity of a hypergraph h for a given partition using the precomputed aggregates ha.

HypergraphAggs(h::Hypergraph)

Precomputes vertex and edge basic stats for a hypergraph. The stats are being used for efficiency reasons by community search algorithms.

randompartition(N::Int, n::Int)::Vector{Set{Int}}

Generates a random partition for graph having N vertices into n subsets.

randompartition(h::Hypergraph, n::Int)::Vector{Set{Int}}

Generates a random partition for vertices of a hypergraph h into n subsets.

The base type for all algorithms representing various community search patterns.

CFModularityRandom(n::Int, reps::Int) <: AbstractCommunityFinder

Represents a random search over the hypergraph h that finds a partition into n communities (subsets) having the maximum modularity value. During the search reps random n-partitions will be evaluated. If there are many partitions having the same value the first one that was randomly found will be returned.

CFModularityCNMLike(n::Int, reps::Int) <: AbstractCommunityFinder

Represents a CNM-Like algorithm for finding communities. In the algorithm we start with a partition where each node is in its own part. Then in each step, we randomly select a hyperedge. Subsequently, we consider merging each set of that parts it touches. We actually merge the parts if the new best modularity is at least as high as the modularity from the previous step. The algortithm iterates through reps of repetitions.

For more information see Algorithm 1 at: Clustering via Hypergraph Modularity (submitted to Plos ONE), auhtors: Bogumił Kamiński, Valerie Poulin, Paweł Prałat, Przemysław Szufel, Francois Theberge

findcommunities(h::Hypergraph, method::CFModularityRandom)

Makes a random search over the hypergraph h and finds a partition into method.n communities (subsets) having the maximum modularity value. During the search method.reps random n-partitions will be evaluated. If there are many partitions having the same value the first one that was randomly found will be returned.

Returns a NamedTuple where the field bp contains partition and the field bm contains the modularity value for that partition.

findcommunities(h::Hypergraph, method::CFModularityCNMLike)

Iterates a CNM-Like algorithm for finding communities. In the algorithm we start with a partition where each node is in its own part. Then in each step, we randomly select a hyperedge. Subsequently, we consider merging each set of that parts it touches. We actually merge the parts if the new best modularity is at least as high as the modularity from the previous step.

Returns a NamedTuple where the field bp contains partition and the field bm contains the modularity value for that partition, finally, the fiel mod_history represents modularities achieved in subsequent steps of the algorithm.

For more information see Algorithm 1 at: Clustering via Hypergraph Modularity (submitted to Plos ONE), authors: Bogumił Kamiński, Valerie Poulin, Paweł Prałat, Przemysław Szufel, Francois Theberge

hg_save(io::IO, h::Hypergraph, format::HGF_Format)

Saves a hypergraph h to an output stream io in hgf format.

hg_save(io::IO, h::Hypergraph, format::JSON_Format)

Saves a hypergraph h to an output stream io in json format.

If h has Composite Types either for vertex metadata or hyperedges metadata, the user has to explicit tell the JSON3 package about it, for instance using:

JSON3.StructType(::Type{MyType}) = JSON3.Struct().

See the (JSON3.jl documentation)[https://github.com/quinnj/JSON3.jl] for more details.

The json in output contains the following information (keys):

• n : number of vertices
• k : number of hyperedges
• m : a matrix representation of h where rows are vertices and columns are hyperedges
• v2he : mapping vertices to hyperedges
• v_meta : vertices metadata
• he_meta : hyperedges metadata

hg_save(
    fname::AbstractString, h::Hypergraph;
    format::Abstract_HG_format=HGF_Format()
)

Saves a hypergraph h to a file fname in the specified format. The default saving format is hgf.

hg_load(
    io::IO,
    format::HGF_Format();
    T::Type{U} = Bool,
    D::Type{<:AbstractDict{Int, U}} = Dict{Int,U},
    V=Nothing,
    E=Nothing
) where {U <: Real}

Loads a hypergraph from a stream io from hgf format.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• D : dictionary for storing values the default is Dict{Int, T}
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph

Skips a single initial comment.

hg_load(
    io::IO,
    format::JSON_Format;
    T::Type{U} = Bool,
    D::Type{<:AbstractDict{Int, U}} = Dict{Int,U},
    V = Nothing,
    E = Nothing
) where {U <: Real}

Loads a hypergraph from a stream io from json format.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• D : dictionary for storing values the default is Dict{Int, T}
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph

hg_load(
    fname::AbstractString;
    format::Abstract_HG_format = HGF_Format(),
    T::Type{U} = Bool,
    D::Type{<:AbstractDict{Int, U}} = Dict{Int,U},
    V = Nothing,
    E = Nothing) where {U <: Real}
)

Loads a hypergraph from a file fname. The default saving format is hgf.

Arguments

• T : type of weight values stored in the hypergraph's adjacency matrix
• D : dictionary for storing values the default is Dict{Int, T}
• V : type of values stored in the vertices of the hypergraph
• E : type of values stored in the edges of the hypergraph

function draw(
        h::Hypergraph,
        type::Type{GraphBased};
        element::Union{String, Int}=get_next_div_id(),
        width::Int=500,
        height::Int=500,
        radius::Real=10,
        node_radii::Union{AbstractVector{<:Real}, Nothing}=nothing,
        node_color::String="#999",
        node_colors::Union{AbstractVector{String}, Nothing}=nothing,
        node_stroke::Union{String, Nothing} = nothing,
        node_strokes::Union{AbstractVector{String}, Nothing}=nothing,
        stroke_width::Real=0,
        stroke_widths::Union{AbstractVector{<:Real}, Nothing}=nothing,
        node_opacity::Real=1,
        node_opacities::Union{AbstractVector{<:Real}, Nothing}=nothing,
        stroke_opacity::Real=1,
        stroke_opacities::Union{AbstractVector{<:Real}, Nothing}=nothing,
        with_node_labels::Bool=false,
        node_labels::Union{AbstractVector{String}, Nothing}=nothing,
        with_node_metadata_hover::Bool=false,
        with_node_weight::Bool=false,
        he_colors::Union{AbstractVector{String}, Nothing}=nothing,
        with_he_labels::Bool=false,
        he_labels::Union{AbstractVector{String}, Nothing}=nothing,
        with_he_metadata_hover::Bool=false
    )

Draw a hypergraph h in a web-based environment (e.g. Jupyter Notebook), using a js script based on the library (D3)[https://d3js.org/]. Each hyperedge he is represented by a fake vertex fv to which each vertex v ∈ he is connected.

Arguments

• h : the hypergraph to draw
• type : how the hypergraph will be drawn. If type=GraphBased, each hyperedge

will be represented as a vertex (see above)

• width : width of the figure
• height : height of the figure
• radius : same default radius for each vertex (represented as a circle)
• node_radii : distinct radius values for each vertex
• node_color : same default color for each vertex
• node_colors : distinct node colors for each vertex
• node_stroke : same default stroke for each vertex
• node_strokes : distinct node strokes for each vertex
• stroke_width : same default stroke-width for each vertex
• stroke_widths : distinct stroke-width values for each vertex
• node_opacity : same default opacity for each vertex
• node_opacities : distinct node-opacity values for each vertex
• stroke_opacity : same default stroke-opacity for each vertex
• stroke_opacities : distinct stroke-opacity values for each vertex
• with_node_labels : whether displaying node labels
• node_labels : node labels to be shown
• with_node_metadata_hover : whether displaying node metadata when hovering each vertex
• with_node_weight : whether displaying node weights within each hyperedge
• he_colors : distinct hyperedge colors for each hyperedge
• with_he_labels : whether displaying hyoeredges labels
• with_he_metadata_hover : whether displaying hyperedge metadata when hovering each hyperedge

draw(
    h::Hypergraph,
    type::Type{HyperNetX};
    width::Int=10,
    height::Int=10,
    node_labels::Union{Dict{Int, String}, Nothing}=nothing,
    edge_labels::Union{Dict{Int, String}, Nothing}=nothing,
    collapse_nodes::Bool=false,
    collapse_edges::Bool=false,
    pos::Union{Dict{Int,Pair{Int,Int}}, Nothing}=nothing,
    with_color::Bool=true,
    with_node_counts::Bool=false,
    with_edge_counts::Bool=false,
    layout::PyObject=nx.spring_layout,
    layout_kwargs::Dict=Dict{String, Any}(),
    ax::Union{PyObject, Nothing}=nothing,
    no_border::Bool=false,
    edges_kwargs::Dict=Dict{String, Any}(),
    nodes_kwargs::Dict=Dict{String, Any}(),
    edge_labels_kwargs::Dict=Dict{String, Any}(),
    node_labels_kwargs::Dict=Dict{String, Any}(),
    with_edge_labels::Bool=true,
    with_node_labels::Bool=true,
    label_alpha::Float64=.35
    )

Draw a hypergraph h as an Euler diagram, using the library HyperNetX.

Arguments

• h : the hypergraph to draw
• type : how the hypergraph will be drawn. If type=HyperNetX, the hypergraph will be represented as a Euler Diagram
• width : width of the figure
• height : height of the figure
• node_labels : node labels to be shown
• edge_labels : edge labels to be shown
• collapse_nodes : draws the hypergraph gotten by identifying nodes contained by the same edges (from HyperNetX)
• collapse_edges : draws the hypergraph gotten by identifying edges containing the same nodes (from HyperNetX)
• no_border : indicates wheter the figure should have a border

For more details about the other parameters, please refer to the library HyperNetX.