SimpleHypergraphs.jl¶

Overview¶

SimpleHypergraphs.jl is a package for hypergraph algorithms in Julia. The package is written in pure Julia. However a compability with Python's HyperNetX package is provided for plotting purposes.

Getting ready¶

Installing the library¶

Note that this code has been tested with Julia 1.5.1 and SimpleHypergraphs.jl version v0.1.13.

In [1]:
using Pkg
In [2]:
#pkg"add SimpleHypergraphs"
In [3]:
using SimpleHypergraphs

Installation of the plotting packages¶

The GraphPlot package will make it possible to vizualize classic graph representations of a hypergraph such as bisection or 2-section representation.

In [4]:
# pkg"add GraphPlot"

The second option is to use for visualisation the Python's HyperNetX. In order for this integration to work you need to install PyCall.jl and Conda.jl along with appropiate Python modules.

In [5]:
#pkg"add PyCall Conda"
#using PyCall
#using Conda
#Conda.runconda(`install matplotlib --yes`)
#Conda.runconda(`install networkx --yes`)
#run(`$(PyCall.python) -m pip install hypernetx==1.2.5`)`
# since the output of this command is long it is not included in this notebook

A simple example¶

Include the library package with using.

In [6]:
using SimpleHypergraphs

Usually SimpleHypergraphs is used together with standard LightGraphs.jl library

In [7]:
import Graphs

We start by creating an empty hyperaph with 5 vertices and 4 hyperedges

In [8]:
h = Hypergraph{Float64}(5,4)
Out[8]:
5×4 Hypergraph{Float64, Nothing, Nothing, Dict{Int64, Float64}}:
 nothing  nothing  nothing  nothing
 nothing  nothing  nothing  nothing
 nothing  nothing  nothing  nothing
 nothing  nothing  nothing  nothing
 nothing  nothing  nothing  nothing

Now we add the connection weights

In [9]:
h[1:3,1] .= 1.5
h[3,4] = 2.5
h[2,3] = 3.5
h[4,3:4] .= 4.5
h[5,4] = 5.5
h[5,2] = 6.5

h
Out[9]:
5×4 Hypergraph{Float64, Nothing, Nothing, Dict{Int64, Float64}}:
 1.5        nothing   nothing   nothing
 1.5        nothing  3.5        nothing
 1.5        nothing   nothing  2.5
  nothing   nothing  4.5       4.5
  nothing  6.5        nothing  5.5
In [10]:
#basic operations over the hg h
@assert add_vertex!(h) == 6
@assert add_hyperedge!(h) == 5

h[5,5] = 1.2
h[6,5] = 1.3

h
Out[10]:
6×5 Hypergraph{Float64, Nothing, Nothing, Dict{Int64, Float64}}:
 1.5        nothing   nothing   nothing   nothing
 1.5        nothing  3.5        nothing   nothing
 1.5        nothing   nothing  2.5        nothing
  nothing   nothing  4.5       4.5        nothing
  nothing  6.5        nothing  5.5       1.2
  nothing   nothing   nothing   nothing  1.3

Visualizing a hypegraph¶

To visualize a given hypergraph h, the user needs to specify two mandatory parameters:

  1. the hypergraph h to draw
  2. which method should be used to visualize h
    • GraphBased represents each hyperedge he with a fake vertex fv to which each vertex v ∈ he is connected.
    • HyperNetX renders an Euler diagram of the hypergraph where vertices are black dots and hyper edges are convex shapes containing the vertices belonging to the edge set.

A GraphBased visualization¶

Vertices options¶

  • If with_node_labels=true, but node_labels is not specified, vertex ids will be used as their label.
In [11]:
SimpleHypergraphs.draw(h, 
    GraphBased; 
    width=500, 
    height=500,
    radius=10, #same radius for each node
    node_color = "yellow", #same color for each node
    node_stroke="orange", #same stroke for each node
    stroke_width=2, #same stroke-width value for each node
    node_opacity=0.5, #same opacity for each node
    with_node_labels=true, #wheter displaying or not node labels
    with_node_metadata_hover=true,
)
Out[11]:
  • Different radii, colors, strokes, stroke-widths, opacities and labels can be specified for each node. If one of these parameters is specified, the corresponding default value for each vertex will be ignored.
In [12]:
SimpleHypergraphs.draw(
    h, 
    GraphBased; 
    width=500, 
    height=500,
    radius=10, #same radius for each node
    node_color = "yellow", #same color for each node
    node_colors = ["yellow", "yellow", "yellow", "blue", "red", "red", "blue"],
    node_stroke = "orange", #same stroke for each node
    node_strokes =  ["orange", "orange", "orange", "orange", "black", "black", "black"],
    stroke_width=2, #same stroke-width value for each node
    node_opacity=0.5, #same opacity for each node
    with_node_labels=true, #whether displaying or not node labels
    node_labels=["A","B","C","D","E","F","G"],
    with_node_metadata_hover=true,
)
Out[12]:
  • If with_node_weight=true, each vertex weight within the hyperedges it belongs to will be displayed.
In [13]:
SimpleHypergraphs.draw(
    h, 
    GraphBased; 
    width=500, 
    height=500,
    radius=10, #same radius for each node
    node_color = "yellow", #same color for each node
    node_stroke="orange", #same stroke for each node
    stroke_width=2, #same stroke-width value for each node
    node_opacity=0.5, #same opacity for each node
    with_node_labels=true, #whether displaying or not node labels
    node_labels=["A","B","C","D","E","F","G"],
    with_node_metadata_hover=true,
    with_node_weight=true
)
Out[13]:

Hyperedges options¶

In [14]:
draw(
    h, 
    GraphBased; 
    width=500, 
    height=500,
    radius=10, #same radius for each node
    node_color = "yellow", #same color for each node
    node_stroke="orange", #same stroke for each node
    stroke_width=2, #same stroke-width value for each node
    node_opacity=0.5, #same opacity for each node
    with_node_labels=true, #whether displaying or not node labels
    with_node_metadata_hover=true,
    with_node_weight=true, #whether displaying vertices metadata on mouse hover
    he_colors=["green", "blue", "red", "yellow","black"], #hyperedges colors
    with_he_labels=true, #whether displaying or not hyperedge labels
    he_labels=["a","b","c","d"], #hyperedges labels
    with_he_metadata_hover=true #whether displaying hyperedges metadata on mouse hover
)
Out[14]:

A Euler-based visualization¶

SimpleHypergraphs integates the Python library HyperNetX to let the user visualize a hypergraph h exploiting an Euler-diagram visualization. For more details, please refer to the library HyperNetX.

In [15]:
draw(h, HyperNetX; width=5, height=5, no_border=true)

There are many options for Hypergraph plotting. Type ?draw to see them all.

In [16]:
?draw  # press Ctrl+Enter to see documentation for `draw`
search: draw RoundNearestTiesAway dirname isdirpath deg2rad @deprecate

Out[16]:
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.

Bipartite View of the hypergraph¶

The type BipartiteView represents a non-materialized view of a bipartite representation hypergraph h. Note this is a view - changes to the original hypergraph will be automatically reflected in the view.

The bipartite view of a hypergraph is suitable for processing with the LightGraphs.jl package.

Several LightGraphs methods are provided for the compability.

In [17]:
b = BipartiteView(h)
Out[17]:
{11, 11} undirected simple Int64 graph

The BipartiteView provide LightGraphs.jl compability.

In [18]:
supertype(typeof(b))
Out[18]:
Graphs.SimpleGraphs.AbstractSimpleGraph{Int64}

We add here a edge to a parent Hypergraph of a bisection view. Note that this change will be reflected in the bipartite view

In [19]:
add_vertex!(h)
Out[19]:
7

This graph can be plotted using LightGraphs tools.

In [20]:
using GraphPlot
using Graphs
nodes, hyperedges = size(h)
nodes_membership = fill(1, nodes)
hyperedges_membership = fill(2, hyperedges)

membership = vcat(nodes_membership, hyperedges_membership)

nodecolor = ["lightseagreen", "orange"]
#membership color
nodefillc = nodecolor[membership]

gplot(b, nodefillc=nodefillc, nodelabel=1:nv(b), layout=circular_layout)
Out[20]:
1 2 3 4 5 6 7 8 9 10 11 12

The functionality of LightGraphs can be used directly on a bipartite view of a hypergraph.

In [21]:
Graphs.a_star(b, 1, 3)
Out[21]:
2-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 1 => 8
 Edge 8 => 3
In [22]:
#number of vertices
nv(b)
Out[22]:
12
In [23]:
#number of edges
ne(b)
Out[23]:
11
In [24]:
#neighbors
sort(collect(outneighbors(b,5)))
Out[24]:
3-element Vector{Int64}:
  9
 11
 12
In [25]:
#neighbors
sort(collect(inneighbors(b,9)))
Out[25]:
1-element Vector{Int64}:
 5
In [26]:
#shortest path - it does not consider the nodes associated with a hyperedge
shortest_path(b,1,4)
Out[26]:
3-element Vector{Int64}:
 1
 2
 4

Twosection View of the hypergraph¶

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

The bipartite view of a hypergraph is suitable for processing with the LightGraphs.jl package.

Several LightGraphs methods are provided for the compability.

Note that 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.

In [27]:
# This condition is required for an unmaterialized `TwoSectionView` representation of a hypergraph to make sense
@assert SimpleHypergraphs.has_overlapping_hedges(h) == false
In [28]:
t = TwoSectionView(h)
Out[28]:
{7, 8} undirected simple Int64 graph
In [29]:
gplot(t, nodelabel=1:nv(t))
Out[29]:
1 2 3 4 5 6 7
In [30]:
#number of vertices
nv(t)
Out[30]:
7
In [31]:
#number of edges
ne(t)
Out[31]:
8
In [32]:
#neighbors
sort(collect(outneighbors(t,5)))
Out[32]:
3-element Vector{Int64}:
 3
 4
 6
In [33]:
#neighbors
sort(collect(inneighbors(t,1)))
Out[33]:
2-element Vector{Int64}:
 2
 3
In [34]:
#shortest path 
shortest_path(t,1,5)
Out[34]:
3-element Vector{Int64}:
 1
 3
 5

Community detection in hypergraphs¶

Let us consider the following hypergraph

In [35]:
h = Hypergraph{Float64}(8,7)
h[1:3,1] .= 1.5
h[3,4] = 2.5
h[2,3] = 3.5
h[4,3:4] .= 4.5
h[5,4] = 5.5
h[5,2] = 6.5
h[5,5] = 5.5
h[5,6] = 6.5
h[6,7] = 5.5
h[7,7] = 6.5
h[8,7] = 6.5
h[8,6] = 6.5

h
Out[35]:
8×7 Hypergraph{Float64, Nothing, Nothing, Dict{Int64, Float64}}:
 1.5        nothing   nothing   nothing   nothing   nothing   nothing
 1.5        nothing  3.5        nothing   nothing   nothing   nothing
 1.5        nothing   nothing  2.5        nothing   nothing   nothing
  nothing   nothing  4.5       4.5        nothing   nothing   nothing
  nothing  6.5        nothing  5.5       5.5       6.5        nothing
  nothing   nothing   nothing   nothing   nothing   nothing  5.5
  nothing   nothing   nothing   nothing   nothing   nothing  6.5
  nothing   nothing   nothing   nothing   nothing  6.5       6.5

Let us search for communities in the hypergraph h

In [36]:
best_comm = findcommunities(h, CFModularityCNMLike(100))

display(best_comm.bm)

display(best_comm.bp)
0.3193650793650794
2-element Vector{Set{Int64}}:
 Set([4, 2, 3, 1])
 Set([5, 6, 7, 8])

And now we visualize them in 2-section view

In [37]:
t = TwoSectionView(h)

function get_color(i, bp)
    color = ["red","green","blue","yellow"]
    for j in 1:length(bp)
        if i in bp[j]
            return color[j]
        end
    end
    return "black"
end

gplot(t, nodelabel=1:nv(t), nodefillc=get_color.(1:nv(t), Ref(best_comm.bp) ))
Out[37]:
1 2 3 4 5 6 7 8