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"
   Updating registry at `c:\JuliaPkg\Julia1.5.1\registries\General`
  Resolving package versions...
No Changes to `C:\JuliaPkg\Julia1.5.1\environments\v1.5\Project.toml`
No Changes to `C:\JuliaPkg\Julia1.5.1\environments\v1.5\Manifest.toml`
In [3]:
pkg"status SimpleHypergraphs"
Status `C:\JuliaPkg\Julia1.5.1\environments\v1.5\Project.toml`
  [aa4a32ff] SimpleHypergraphs v0.1.13

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"
  Resolving package versions...
  Installed Compose ─── v0.8.2
  Installed GraphPlot ─ v0.4.3
Updating `C:\JuliaPkg\Julia1.5.1\environments\v1.5\Project.toml`
  [a2cc645c] + GraphPlot v0.4.3
Updating `C:\JuliaPkg\Julia1.5.1\environments\v1.5\Manifest.toml`
  [a81c6b42] + Compose v0.8.2
  [a2cc645c] + GraphPlot v0.4.3

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 [ ]:
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`)`
# 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 [5]:
using SimpleHypergraphs

Usually SimpleHypergraphs is used together with standard LightGraphs.jl library

In [6]:
import LightGraphs

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

In [7]:
h = Hypergraph{Float64}(5,4)
Out[7]:
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

No we add the connection weights

In [8]:
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[8]:
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 [9]:
#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[9]:
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 [10]:
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[10]:
  • 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 [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_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[11]:
  • If with_node_weight=true, each vertex weight within the hyperedges it belongs to will be displayed.
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_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[12]:

Hyperedges options

In [13]:
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[13]:

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 [14]:
draw(h, HyperNetX; width=5, height=5, no_border=true)

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

In [11]:
?draw  # press Ctrl+Enter to see documentation for `draw`

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 [16]:
b = BipartiteView(h)
Out[16]:
{11, 11} undirected simple Int64 graph

The BipartiteView provide LightGraphs.jl compability.

In [17]:
supertype(typeof(b))
Out[17]:
LightGraphs.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 [18]:
add_vertex!(h)
Out[18]:
7

This graph can be plotted using LightGraphs tools.

In [22]:
using GraphPlot
using LightGraphs
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:LightGraphs.nv(b), layout=circular_layout)
Out[22]:
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 [23]:
LightGraphs.a_star(b, 1, 3)
Out[23]:
2-element Array{LightGraphs.SimpleGraphs.SimpleEdge{Int64},1}:
 Edge 1 => 8
 Edge 8 => 3
In [24]:
#number of vertices
LightGraphs.nv(b)
Out[24]:
12
In [25]:
#number of edges
LightGraphs.ne(b)
Out[25]:
11
In [26]:
#neighbors
sort(collect(LightGraphs.outneighbors(b,5)))
Out[26]:
3-element Array{Int64,1}:
  9
 11
 12
In [27]:
#neighbors
sort(collect(LightGraphs.inneighbors(b,9)))
Out[27]:
1-element Array{Int64,1}:
 5
In [28]:
#shortest path - it does not consider the nodes associated with a hyperedge
shortest_path(b,1,4)
Out[28]:
3-element Array{Int64,1}:
 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 [29]:
# This condition is required for an unmaterialized `TwoSectionView` representation of a hypergraph to make sense
@assert SimpleHypergraphs.has_overlapping_hedges(h) == false
In [30]:
t = TwoSectionView(h)
Out[30]:
{7, 8} undirected simple Int64 graph
In [31]:
gplot(t, nodelabel=1:LightGraphs.nv(t))
Out[31]:
1 2 3 4 5 6 7
In [32]:
#number of vertices
LightGraphs.nv(t)
Out[32]:
7
In [33]:
#number of edges
LightGraphs.ne(t)
Out[33]:
8
In [34]:
#neighbors
sort(collect(LightGraphs.outneighbors(t,5)))
Out[34]:
3-element Array{Int64,1}:
 3
 4
 6
In [35]:
#neighbors
sort(collect(LightGraphs.inneighbors(t,1)))
Out[35]:
2-element Array{Int64,1}:
 2
 3
In [36]:
#shortest path 
shortest_path(t,1,5)
Out[36]:
3-element Array{Int64,1}:
 1
 3
 5

Community detection in hypergraphs

Let us consider the following hypergraph

In [37]:
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[37]:
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 [38]:
best_comm = findcommunities(h, CFModularityCNMLike(100))

display(best_comm.bm)

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

And now we visualize them in 2-section view

In [39]:
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:LightGraphs.nv(t), nodefillc=get_color.(1:LightGraphs.nv(t), Ref(best_comm.bp) ))
Out[39]:
1 2 3 4 5 6 7 8