Hypergraphs: an introduction and review

Xavier Ouvrard1,2
arXiv:2002.05014v1 [cs.DM] 12 Feb 2020

1 : CERN 2 : University of Geneva

xavier.ouvrard@cern.ch

February 13, 2020

Abstract
Hypergraphs were introduced in 1973 by Bergé. This review aims at
giving some hints on the main results that we can find in the literature,
both on the mathematical side and on their practical usage. Particularly,
different definitions of hypergraphs are compared, some unpublished work
on the visualisation of large hypergraphs done by the author. This review
does not pretend to be exhaustive.
In 1736, Euler was the first to use a graph approach to solve the problem of the
Seven Bridges of Königsberg. In 1878, Sylvester coined the word graph itself.
Graphs are extensively used in various domains. A lot of developments on graphs
have been realized during the first half of the twentieth century, but graphs
are still an active field of research and applications, in mathematics, physics,
computer science and various other fields, ranging from biology to economic and
social network analysis.
Berge and Minieka [1973] introduces hypergraphs as a means to generalize
the graph approach. Graphs only support pairwise relationships. Hypergraphs
preserve the multi-adic relationships and, therefore, become a natural modeling
of collaboration networks and various other situations. They already allow a
huge step in modeling, but some limitations remain that will be discussed further
in this article that has pushed us to introduce an extension of hypergraphs. In
this Section, we aim at giving a synthesis of the hypergraphs. Further details
on hypergraphs can be found either in Berge and Minieka [1973] or in Bretto
[2013] and in many of the references cited throughout this article.

1 Generalities
As given in Berge and Minieka [1973], a hypergraph H = (V, E) on a finite set
∆
of vertices (or nodes) V = {vi : i ∈ JnK}1 is defined as a family of hyperedges
1 We write for n ∈ N∗ : JnK = {i : i ∈ N∗ ∧ i 6 n}

1
1 GENERALITIES 2

∆
E = (ej )j∈JpK where each hyperedge is a non-empty subset of V and such that
S
ej = V.
j∈JpK
It means that in a hypergraph, a Shyperedge links one or more vertices. In
Bretto [2013], this last hypothesis— ej = V —is relaxed to enable isolated
j∈JpK
vertices in hypergraphs, opening the use of hypergraphs in various collaboration
networks.
Other interesting definitions of hypergraphs exist. Two of them are given in
Stell [2012].
A hypergraph H is firstly defined as consisting of a set V of vertices and a
set E of hyperedges with an incidence function ι : E → P (V ) , where P (V )
is the poset of V . Also H = (V, E, ι) .
The author emphasizes the fact that this definition allows several hyperedges
to be incident to the same set of vertices and, also, to have hyperedges that are
linked to the empty set of vertices. This definition is tightly linked to the one
of Bretto [2013], with the advantage of having the incident function to link
hyperedges and their corresponding set of vertices, instead of an equality.
A hypergraph is secondly defined in Stell [2012] as consisting of a set H
containing both vertices and hyperedges and a binary relation ϕ such that:
1. ∀x ∈ H, ∀y ∈ H, (x, y) ∈ ϕ =⇒ (y, y) ∈ ϕ;
2. ∀x ∈ H, ∀y ∈ H, ∀z ∈ H, (x, y) ∈ ϕ ∧ (y, z) ∈ ϕ =⇒ y = z.
The link can be made with the other definitions in considering the set V such
that:
∆
V = {v ∈ H : (v, v) ∈ ϕ}
which corresponds to the set of vertices of the hypergraph H and the set E such
that:
∆
E = {e ∈ H : (e, e) ∈ / ϕ}
which corresponds to the set of hyperedges of the hypergraph.
This last definition treats on the same footing vertices and hyperedges.
Nonetheless, in this definition, the set aspect of hyperedges is implicit. Effec-
tively, to know which vertex set a hyperedge e contains, the information needs
to be rebuilt—using ι(e) as in the former definition—:
ι(e) = {v ∈ H : (e, v) ∈ ϕ} .
This definition leads to a representation of the hypergraph as a directed
multi-graph where the vertices point to themselves and hyperedges are linked
to vertices in this order.
Depending on the needs, either the first definition of Stell [2012] or equiva-
lently the one given in Bretto [2013] without specifying the incidence relation
will be used and referred as poset definition of hypergraphs—PoDef for short.
Switching between these two definitions reverts to abusively identifying the hy-
peredge with the subset of vertices it identifies. The second definition of Stell
[2012] will also be used—referred to as MuRelDef .
2 PARTICULAR HYPERGRAPHS 3

When using a PoDef defined hypergraph, H = (V, E, ι) designates a hyper-

graph. If the MuRelDef is used, the hypergraph H = (U, ϕ) is used, with U =
V ∪E, with V = {v ∈ H : (v, v) ∈ ϕ} the set of vertices and E = {e ∈ H : (e, e) ∈
/ ϕ} .
In the following definitions, we put in perspective these two approaches.

2 Particular hypergraphs
When needed, elements of V will be written (vi )i∈JnK and those of E will be
written as (ej )j∈JpK . Abusively, ej will also designate the subset ι (ej ) of V.
Two hyperedges ej1 ∈ E and ej2 ∈ E, with j1 , j2 ∈ JpK and j1 6= j2 such that
ej1 = ej2 are said repeated hyperedges.
A hypergraph is said with no repeated hyperedge, if it has no repeated
hyperedges.
Following Chazelle and Friedman [1988], where the hyperedge family is
viewed as a multiset of hyperedges, a hypergraph with repeated hyperedges
is called a multi-hypergraph.
A hypergraph is said simple, if for any two hyperedges ej1 ∈ E and ej2 ∈ E :

ej1 ⊆ ej2 ⇒ j1 = j2 .

Hence, a simple hypergraph has no repeated hyperedges.

A hyperedge e ∈ E such that: |e| = 1 is called a loop.
A hypergraph is said linear if it is simple and such that every pair of hy-
peredges shares at most one vertex.
A sub-hypergraph K of a hypergraph H is the hypergraph formed by a
subset W of the vertices of H and the hyperedges of H that are subsets of W .
Formally, with
• PoDef: K = (W, F, ι|F ), such that: F = {ej ∈ E : ι|F (ej ) ⊆ W } ;
• MuRelDef: K = (T, ϕ), with T ⊆ U , where ∀t ∈ T, ∀u ∈ U : (t, u) ∈
ϕ =⇒ u ∈ T and ∀t ∈ T : (t, t) ∈ ϕ =⇒ t ∈ W.

A partial hypergraph H0 generated by a subset E 0 ⊆ E of the hyperedges is a

hypergraph containing exactly these hyperedges and whose vertex set contains
at least all the vertices incident to this hyperedge subset.
Formally, with:
∆
• PoDef: H0 = (V 0 , E 0 , S
ι|E 0 ), where E 0 = {ej : j ∈ K 0 } ⊆ E with K 0 ⊆ JpK
0
and V is such that ι|E 0 (ek ) ⊆ V 0 ;
k∈K 0

∆
• MuRelDef: H0 = (T 0 , ϕ), with T 0 ⊆ U , where ∀t ∈ U, ∀t0 ∈ T 0 : (t, t0 ) ∈
ϕ =⇒ t ∈ T 0 and ∀t ∈ T 0 : (t, t) ∈
/ ϕ =⇒ t ∈ E 0 .
3 DUALITY 4

3 Duality
The star of a vertex v ∈ V of a hypergraph H, written H(v), is the family of
hyperedges containing v.
Also with:
∆
• PoDef: H(v) = {ek ∈ E : v ∈ ι (ek )} ;
∆
• MuRelDef: H(v) = {t ∈ U : (t, v) ∈ ϕ ∧ (t, t) ∈
/ ϕ} .
The dual of a hypergraph H is the hypergraph H∗ whose vertices corresponds
to the hyperedges of H and the hyperedges of H∗ are the vertices of H, with
the incident relation that links each vertex to its star.
Formally with:
• PoDef: The dual is given by H∗ = (V ∗ , E ∗ , ι∗ ) , with V ∗ = E and where
E ∗ = {v ∈ V } and ∀v ∈ V : ι∗ (v) = H (v) ;
∆
• MuRelDef: The dual is given by: (U, ϕ∗ ) where ϕ∗ = ¬ϕ ∩ (10 ∪ ` ϕ) ,
with:
• ¬ϕ the complement of the relation ϕ : ∀x ∈ U, ∀y ∈ U : (x, y) ∈ ¬ϕ ⇔
(x, y) ∈
/ ϕ;

• 1’ the binary identity: ∀x ∈ U, ∀y ∈ U : (x, y) ∈ 10 ⇔ x = y;

• ` ϕ the converse relation: ∀x ∈ U, ∀y ∈ U : (x, y) ∈` ϕ ⇔ (y, x) ∈ ϕ.
Proof for (MuRelDef ). (not given in Stell [2012]) Let x ∈ U such that (x, x) ∈
ϕ∗ . Then (x, x) ∈ ¬ϕ and x is a hyperedge of (U, ϕ) .
If x ∈ U such that (x, x) ∈ / ϕ∗ , then (x, x) ∈
/ ¬ϕ and x is a vertex of (U, ϕ)
as (x, x) ∈ 1 and, therefore: (x, x) ∈ 10 ∪ ` ϕ.
0

Let (x, y) ∈ ϕ∗ and suppose that x 6= y. Then as ϕ∗ = ¬ϕ ∩ (10 ∪ ` ϕ) ,

we have: (x, y) ∈ 10 ∪ ` ϕ. As x 6= y, (x, y) ∈ / 10 , so we have (x, y) ∈` ϕ, i.e.
(y, x) ∈ ϕ. It implies that (x, x) ∈ ϕ and thus a vertex of (U, ϕ) . As y is a vertex
of (U, ϕ∗ ) , it is a hyperedge of (U, ϕ) .

Some interesting properties can be derived from the MuRelDef and might
be useful for computation.
Proposition 1. Let (U, ϕ) be a hypergraph.
∆
The set of vertices is given by the binary relation: ν = ϕ ∩ 10 .
∆
The set of hyperedges is given by the binary relation: η = ϕ ∩ (¬ν) .
Proof. Let x ∈ U : (x, x) ∈ ϕ ⇔ (x, x) ∈ ϕ ∩ 10 , so ν gives exactly the vertices
of (U, ϕ) .
Moreover: (x, x) ∈ ϕ ⇔ (x, x) ∈ / ¬ν, so η = ϕ ∩ (¬ν) does not hold the
vertices of (U, ϕ) .
4 NEIGHBORHOOD OF A VERTEX 5

Let us take x, y ∈ U with x 6= y. We have (x, y) ∈ ϕ =⇒ (x, y) ∈ / ϕ ∩ 10 ⇔

0
(x, y) ∈ ¬ (ϕ ∩ 1 ) . Therefore: (x, y) ∈ ϕ =⇒ (x, y) ∈ ϕ ∩ (¬ν) .
Reciprocally, if x 6= y : (x, y) ∈ ϕ∩(¬ν) =⇒ (x, y) ∈ ϕ, then η gives exactly
the hyperedges’ content of (U, ϕ) .
Proposition 2. Using the dual relation:
∆
The set of hyperedges can be retrieved by the binary relation: ν ∗ = ϕ∗ ∩ 10 .
∆
The set of incident hyperedges can be retrieved by the binary relation: η ∗ =
∗ ∗
ϕ ∩ (¬ν ) .
Proof. Immediate with duality.
Proposition 3. Let (U, ϕ) be a hypergraph and ϕ∗ its dual relation.
(i) The binary relation α = (ϕ ◦ ϕ∗ ) ∩ (¬η) allows to retrieve the adjacency
of vertices.
(ii) The binary relation β = (ϕ∗ ◦ ϕ) ∩ (¬η ∗ ) allows to retrieve the intersec-
tion of hyperedges.
Proof for (i). In (U, ϕ∗ ) , when we select an element of x ∈ U , either it is a vertex
of (U, ϕ∗ ) , and then (x, x) ∈ ϕ∗ , or it is a hyperedge and then (x, x) ∈ / ϕ∗ .
∗
Let x ∈ (U, ϕ ) be such that (x, x) ∈ / ϕ . x is a hyperedge of (U, ϕ∗ ) and,
∗

therefore, a vertex of (U, ϕ) . If there exists e ∈ U, such that (x, e) ∈ ϕ∗ , then

e is a vertex of (U, ϕ∗ ) , also a hyperedge of (U, ϕ) . If this hyperedge is non
empty in (U, ϕ) , there exists x0 ∈ (U, ϕ) , such that (e, x0 ) ∈ ϕ, and, necessarily
by definition, (x0 , x0 ) ∈ ϕ. (x, x0 ) links two vertices of (U, ϕ) . Either x = x0
which implies: (x, x0 ) ∈ ¬η or x 6= x0 which implies (x, x0 ) ∈ / ϕ, so (x, x0 ) ∈ ¬η.
0 ∗
Therefore, (x, x ) ∈ (ϕ ◦ ϕ ) ∩ (¬η) links two vertices and points the adjacency
of these two vertices.
Let x ∈ (U, ϕ∗ ) be such that (x, x) ∈ ϕ∗ . x is a vertex of (U, ϕ∗ ) and,
therefore, a hyperedge of (U, ϕ) , i.e. (x, x) ∈ / ϕ. If this hyperedge is non empty
in (U, ϕ) , there exists x0 ∈ (U, ϕ) , such that (x, x0 ) ∈ ϕ, and necessarily, by
definition, (x0 , x0 ) ∈ ϕ, and x0 is a vertex of (U, ϕ) . Therefore, (x, x0 ) ∈ (ϕ ◦ ϕ∗ )∩
η.

Proof for (ii). This proof is similar to the former one.

4 Neighborhood of a vertex
The neighborhood of a vertex in a hypergraph is defined similarly to what is
done for graphs.
The neighborhood of a vertex v ∈ V is the set Γ (v) of vertices that
belongs to the hyperedges this vertex is belonging.
That is with:
S
• PoDef: Γ(v) = ι(e);
e∈H(v)
5 WEIGHTED HYPERGRAPH 6

• MuRelDef: For v such that (v, v) ∈ ϕ :

Γ(v) = {s ∈ U : (s, s) ∈ ϕ ∧ (∃w ∈ U : (w, s) ∈ ϕ ∧ (w, v) ∈ ϕ ∧ (w, w) ∈

/ ϕ)} ,

which is equivalent to:

Γ(v) = {s ∈ U : (s, s) ∈ ϕ ∧ (s, v) ∈ ϕ ◦ ϕ∗ } .

Proof for (MuRelDef ). As (v, v) ∈ ϕ, (v, v) ∈ / ϕ∗ . If there exists t ∈ U such

∗
that (t, v) ∈ ϕ , t is a hyperedge of (U, ϕ) . Therefore, any s, if there exists,
such that (s, t) ∈ ϕ is a vertex and is in the same hyperedge than v, so in its
neighborhood. The other inclusion is straightforward.

5 Weighted hypergraph
In Zhou et al. [2007], the definition of a weighted hypergraph is given, based on
the definition of Berge and Minieka [1973] of a hypergraph.
Hwe = (V, E, we ) is a weighted hypergraph, if (V, E) is a hypergraph and
we : E → R is a function that associates to each hyperedge e ∈ E a weight
we (e) .
We can refine this definition to handle weights on individual vertices, by
using a second function wv : V → R that associates to each vertex v ∈ V a
weight wv (v) . But putting weights that are hyperedge dependent cannot be
achieved with hypergraphs as it would imply to move to a new algebra, as we
will see with the introduction of hb-graphs.

6 Hypergraph features
Hypergraph features are very similar to those of graphs with some arrangements
to account for their differences in structure.
∆
The order oH of a hypergraph H is defined as oH = |V | .
The rank rH of a hypergraph H is the maximum of the cardinalities of the
hyperedges:
∆
rH = max |e| ,
e∈E

while the anti-rank sH corresponds to the minimum:

∆
sH = min |e| .
e∈E

The degree of a vertex vi ∈ V , written deg (vi ) = di , corresponds to the

number of hyperedges that this vertex participates in. Hence:
∆
deg (vi ) = |H (vi )| .

It is also designated as hyper-degree in some articles.

7 PATHS AND RELATED NOTIONS 7

7 Paths and related notions

A path vi0 ej1 vi1 . . . ejs vis in a hypergraph H from a vertex u to a vertex v is a
vertex / hyperedge alternation with s hyperedges ejk such that: ∀k ∈ JsK , jk ∈
JpK and s + 1 vertices vik with ∀k ∈ {0} ∪ JsK , ik ∈ JnK and such that vi0 = u,
vis = v, u ∈ ej1 and v ∈ ejs and that for all k ∈ Js − 1K, vik ∈ ejk ∩ ejk+1 .
The length of a path from u to v is the number of hyperedges it tra-
verses; given a path P, we write l (P) its length. It holds that if P =
vi0 ej1 vi1 . . . ejs vis , we have: l (P) = s.
The hypergraph distance d (u, v) between two vertices u and v of a hy-
pergraph is the length of the shortest path between u and v, if there exists, that
can be found in the hypergraph. In the case where there is no path between the
two vertices, they are said to be disconnected, and we set: d (u, v) = +∞. A
hypergraph is said to be connected if there exists a path between every pair
of vertices of the hypergraph, and disconnected otherwise.
A connected component of a hypergraph is a maximal subset of the vertex
set for which there exists a path between any two vertices of this maximal subset
in the hypergraph.

8 Multi-graph, graph, 2-section

A hypergraph with rank at most 2 is called a multi-graph. A simple multi-
graph without loop is a graph.
For the moment, we keep the original concept of adjacency as it is implicitly
given in Bretto [2013]; we mention it here as 2-adjacency since it is a pairwise
adjacency.
Two distinct vertices vi1 ∈ V and vi2 ∈ V are said 2-adjacent if there exists
e ∈ E such that vi1 ∈ e and vi2 ∈ e.
∆

The graph [H]2 = V[2] , E[2] obtained from a hypergraph H = (V, E) by
∆
considering: V[2] = V and such that if vi1 and vi2 are 2-adjacent in H, {vi1 , vi2 } ∈
E[2] is called the 2-section of the hypergraph H.
∆
The graph [H]I = (VI , EI ) obtained from a hypergraph H = (V, E) by
∆
considering: VI = V ∗ and, such that, if ej1 ∈ E and ej2 ∈ E—with j1 6= j2 —
are intersecting hyperedges in H, then {ej1 , ej2 } ∈ EI , is called the intersection
graph of the hypergraph H.
Let k ∈ N∗ . A hypergraph is said to be k-uniform if all its hyperedges have
the same cardinality k.
A directed hypergraph H = (V, E) on a finite set of n vertices (or vertices)
V = {vi : i ∈ JnK} is defined as a family of p hyperedges E = (ej )j∈JpK where
each hyperedge ej contains exactly two non-empty subsets of V , one which
is called the source—written es j —and the other one which is the target—
written et j . A hypergraph that is not directed is said to be an undirected
hypergraph.
9 SUM OF HYPERGRAPHS 8

9 Sum of hypergraphs
Let H1 = (V1 , E1 ) and H2 = (V2 , E2 ) be two hypergraphs. The sum of these
two hypergraphs is the hypergraph written H1 + H2 defined as:
∆
H1 + H2 = (V1 ∪ V2 , E1 ∪ E2 ) .

This sum is said direct if E1 ∩ E2 = ∅. In this case, the sum is written H1 ⊕ H2 .

10 Matrix definitions of hypergraphs

10.0.1 Incidence matrix
The incidence matrix:
∆
H = [hij ]i∈JnK
j∈JpK

of a hypergraph is the matrix having rows indexed by the corresponding indices

of vertices of H and columns by the hyperedge indices, and where the coefficient
∆ ∆
hij = 1 when vi ∈ ej , and hij = 0 when vi ∈
/ ej .

10.0.2 Adjacency matrix

We focus in this paragraph on the pairwise adjacency as defined in Berge and
Minieka [1973] and Bretto [2013]. In the latter, the adjacency matrix of
∆
a hypergraph H is defined as the square matrix A = [aij ] having rows and
columns indexed by indices corresponding to the indices of vertices of H and
where for all i, j ∈ JpK , i 6= j :
∆
aij = |{e ∈ E : vi ∈ e ∧ vj ∈ e}|

and for all i ∈ JpK :

∆
aii = 0.
It holds, following Estrada and Rodriguez-Velazquez [2005]:

A = HH | − DV
 
∆
where DV = diag (di )i∈JnK is the diagonal matrix containing vertex degrees.
The adjacency matrix of a weighted hypergraph Hw is defined in Zhou
et al. [2007] as the matrix Aw of size n × n defined as:
∆
Aw = HW H | − Dw

where:  
∆
W = diag (wj )j∈JpK
11 HYPERGRAPH VISUALISATION 9

is a diagonal matrix of size p×p containing the weights (wj )j∈JpK of the respective
hyperedges (ej )j∈JpK and Dw is the diagonal matrix of size n × n:
 
∆
Dw = diag (dw (vi ))i∈JnK

and where for all i ∈ JnK:

∆
X
dw (vi ) = wj
j∈{k:k∈JpK∧vi ∈ek }

is the weighted degree of the vertex vi ∈ V.

We will refine the concept of adjacency in general hypergraphs in the next
Chapter.

10.0.3 Additional features

In Estrada and Rodriguez-Velazquez [2005], the authors introduce particular
features to characterize hypergraphs. They evaluate the centrality of a vertex
in a simple unweighted hypergraph, by orthogonalizing the adjacency matrix in:

A = U ΛU | ,
 
∆ ∆
where U = (uij )(i,j)∈JnK2 and Λ = diag (λi )i∈JnK is the diagonal matrix formed
of the eigenvalues λi of A with i ∈ JnK .
The sub-hypergraph centrality CSH (i) is defined as the sum of the closed
walks of different lengths in the network, starting and ending at a given vertex.
For a simple hypergraph, it can be calculated using:
n
∆
X 2
CSH (i) = (uij ) eλj .
j=1

A clustering coefficient for hypergraph is also defined as:

∆ 6 × number of hyper-triangles
C(H) =
number of 2-paths
where a hyper-triangle is defined as a sequence of three different vertices that
are separated by three different hyperedges vi ep vj eq vk er vi and a 2-path is a
sequence vi ep vj eq vk .

11 Hypergraph visualisation
In Mäkinen [1990], hypergraph visualizations are classified in two categories
called the “subset standard” and the “edge standard”. These two types of repre-
sentations reflect the two facets of hypergraphs. The subset standard reflects
that hyperedges are subsets of the vertex set: the vertices of a hyperedge are
11 HYPERGRAPH VISUALISATION 10

 v4

 v6
 v7  v2
 v3  v2  v6  v3  v7
 v1  v4  v1
 v5  v5
 v8  v8

(a) Euler diagram. (b) Venn diagram.

Figure 1: Difference between (a) Euler diagram and (b) Venn diagram.

drawn as points and hyperedges as closed envelopes. The edge standard re-
flects that vertices of a hyperedge maintain together a multi-adic relationship.
We then cover the Zykov representation which can be seen as a bridge between
the two representations.

11.0.1 The subset standard

Euler diagram represents sets by simple closed shapes in a two dimensional
plane. Shapes can overlap to represent relationships within the sets; these rela-
tionships can be either fully inclusive, partially inclusive or disjoint.
In Venn [1881], the author introduces a particular case of Euler diagram that
shows the 2n logical relations between n sets with the aim to formalize logical
propositions by diagrams, now called Venn diagrams.
In Mäkinen [1990], the author presents the Venn diagram representation
of hypergraphs: a Venn representation of a hypergraph represents hyperedges
as closed curves that contains points symbolizing the vertices. In Johnson and
Pollak [1987], the authors present two representations with the subset standard.
The first representation is a hyperedge-based Venn diagram based on the rep-
resentation of the hypergraph as a planar graph, an embedding of this planar
graph and a one-to-one map between the hyperedges and the embedding faces,
such that taking any subset of the vertices, the union of the faces corresponding
to this subset includes a region of the plane with a connected interior. Hyper-
graphs that can be represented in such a way are said hyperedge-planar. The
second representation is a vertex-based Venn diagram where the mapping is from
the set of vertices to the embedding faces such that for every hyperedge the inte-
rior of the face union that contains all the hyperedge vertices is connected, with
a corresponding notion of vertex-planar when such a representation is feasible.
In Bertault and Eades [2001], a drawing system is presented, named PATATE,
where hypergraphs are represented using the subset standard: a graph is built
11 HYPERGRAPH VISUALISATION 11

combining three possibilities. The first representation is achieved by building the

incidence graph of the hypergraph, adding a dummy vertex for each hyperedge
that is linked by an edge, placed at the barycenter. The second representation
is built using a minimal Euclidean spanning-tree that covers the vertices of each
hyperedge: the edges of the spanning-tree are added to the graph. The third
representation is built using a minimal Steiner tree: a vertex is added for every
Steiner point and the edges of the tree are added. A force directed algorithm
is applied to the built graph and the convex hull of each hyperedge is then
computed.
The Venn diagram representation is also addressed in Estrada and Rodriguez-
Velazquez [2005]. The Venn diagram is relevant for small hypergraphs but is
harder to use for large hypergraphs.
A large survey on set representations is available in Alsallakh et al. [2016].

11.0.2 The edge standard

The edge standard includes two main representations: the clique expansion
and the extra-node representation also called the incidence representation
in Kaufmann et al. [2009].
The clique expansion is based on the 2-section of the hypergraph where a
n (n − 1)
hyperedge of cardinality n is represented by undirected edges.
2
The extra vertex representation corresponds to the incidence graph of the
hypergraph, which is a bipartite graph. It is called the König representation of
the hypergraph in Zykov [1974]. In this case, a hyperedge of size n is represented
with only n edges connecting hyperedge vertices to a central vertex called extra-
node.
Figure 2 illustrates these two representations.

Figure 2: Clique expansion vs extra-node representation of a hyperedge.

The clique expansion generates graph with more edges than the extra-node
representation for values of n > 4. Moreover, if a hyperedge ej1 is a strict
subset of an other hyperedge ej2 , the clique expansion of ej1 does not add any
other edge, while the extra-node representation brings |ej1 | new edges and an
additional vertex. An example of an unfavorable case is given in Figure 3.
11 HYPERGRAPH VISUALISATION 12

Clique view extra-node view

In this case: 10 edges, 5 vertices In this case: 11 edges, 5 vertices and 3 extra-nodes

Figure 3: Unfavorable case for the extra-node view.

In the clique representation, vertices of hyperedges are seen as interacting

with 2-adic relationships and the information on the meso-structure is lost Tara-
masco et al. [2010]. The extra-node representation allows to keep the multi-adic
relationships. Moreover, we have shown in Ouvrard et al. [2017] that the num-
ber of edges can be substantially reduced by the extra-node representation for
a power-law hypergraph.
Junghans [2008] focuses on hyperedge drawing so that they do not intersect
cluster groups, giving a solution based on force attraction/repulsion.
Other representations in the node standard exist: in Paquette and Tokuyasu
[2011], the authors propose a representation using a pie-chart node approach,
which is valuable for hypergraphs where the hyperedges do not intersect one
another with too high cardinality. In Kerren and Jusufi [2013], a radial approach
is presented that fits for small hypergraphs. In Kaufmann et al. [2009], a Steiner
tree representation of the hyperedges is considered as the edge representation
of a hypergraph.

11.0.3 The Zykov representation

In Zykov [1974], the author tackles the representation of hypergraphs and pro-
poses a notion of hypergraph planarity. A planar hypergraph is a hypergraph
where the vertices are represented as points in a plane and hyperedges as closed
curves not intersecting one another but in the neighborhood of a common inci-
dent vertex of hyperedges.
This notion of Zykov-planarity corresponds to the planarity of the incidence
graph of the hypergraph.
The author proposes a representation, called now the Zykov representation
and shown in Figure 4 (c), that is based on a continuous deformation of the
edges, starting with the Euler diagram in Figure 4 (a) via the PaintSplash rep-
resentation in Figure 4 (b) and that stops just before obtaining the incidence
graph as shown in Figure 4 (d). Hyperedges are represented as faces of a subdi-
vision realized by the vertices belonging to the corresponding hyperedge. Two
hyperedges with a common vertex are incident at that vertex. The represen-
tation in the original article is in black and white; hence, this representation
requires two colors: one for the background and an other one for the faces—we
keep here the colors for helping to the understanding of the continuous defor-
mation of the hyperedges from the Euler representation to the extra-node rep-
resentation. This representation is intensively used with simplicial complexes
11 HYPERGRAPH VISUALISATION 13

(a) Euler diagram. (b) PaintSplash representation.

(c) Zykov representation. (d) Extra-node representation.

Figure 4: Moving from the Euler diagram (a) via the PaintSplash representation
(b) and the Zykov representation (c) to the incident representation (d) based
on Zykov [1974]—in the order of the arrows. The original figure is in black and
white.

which are particular case of hypergraphs.

The Zykov representation cannot be totally put neither in the edge standard
nor in the subset standard.

11.0.4 PaintSplash representation

It is worth mentioning that Figure 4 (b) can lead to a good compromise between
the subset standard and the edge standard, that we have called in its modern
colored version the PaintSplash representation of a hypergraph, presented in
Figure 5.
11 HYPERGRAPH VISUALISATION 14

Figure 5: PaintSplash representation of a hypergraph.

11.0.5 Large hypergraph visualisation

Large hypergraphs require strategies to be properly visualized. We have shown
in Ouvrard et al. [2017] that switching from the 2-section representation to the
incidence representation reduces considerably the overall cognitive load, as the
number of edges to be represented is effectively highly diminished in real net-
works; moreover, true collaborations are seen more distinguishably. An example
is given in Figure 6, that shows how the representation in the two modes impact
on the cognitive load.
Other strategies have been implemented in order to improve the global layout
and information retrieval of large hypergraphs. It includes the segmentation
of the hypergraph into connected components, ordering them by the number
of references they represent, and then with respect to the number of vertices
within co-occurrences they contain. The layout of each connected component
is computed separately, by considering the communities based on the Louvain
algorithm presented in Blondel et al. [2008] and using a force directed algorithm,
named ForceAtlas2, presented in Jacomy et al. [2014], to ensure the layout
of the communities and of the vertices inside the communities. To achieve a
proper layout, vertices of importance for the community are placed first and the
remaining vertices are then placed around those fixed important vertices, with
an optimization of the layout. The principle of the calculus is given in Figure 9
and the results is shown in Figure 11.0.5 and Figure 8.
Optimizing the layout of a large hypergraph is a challenging task. It requires
to capture important vertices of the hypergraph, i.e. the ones we do not want to
loose by overwhelming or overlapping in the representation. This requirement
has been the starting point of our quest for a diffusion tensor.
11 HYPERGRAPH VISUALISATION 15

Sub-figure 6 (a): Clique representation: The coordinates of the nodes are cal-
culated by ForceAtlas2 on the extra-node view and then transferred to this view.

Sub-figure 6 (b): Extra-node representation: The coordinates of the nodes are

calculated by ForceAtlas2 for this representation.

Figure 6: Hypergraph of organizations: Sub-figures (a) and (b) refer to the

search:
title:((bgo AND cryst*) OR (bgo AND calor*)) abstract:((bgo AND cryst*) OR
(bgo AND calor*)) from Ouvrard et al. [2017].
11 HYPERGRAPH VISUALISATION 16

Figure 7: Keyword collaborations from search: “TITLE: hypergraph”.

#publications = 200, #nodes = 707, #edges = 1655, #clusters = 102,

#isolated clusters = 67.
11 HYPERGRAPH VISUALISATION 17

Figure 8: Organization collaborations from search: “TITLE:graph”.

#publications = 3969, #patents=893

#nodes = 2932, #edges = 4731, #clusters = 951, #isolated clusters = 914.
11 HYPERGRAPH VISUALISATION 18

Hypergraph
Connected components (xCC − ωCC , yCC − ωCC )
Connected components
Connected components Quotient Hypergraph
Quotient Hypergraph
Layout

Connected component Communities

Size and center (xCl − ωCl , yCl − ωCl )
Communities Quotient
Communities detection of connected
Quotient Hypergraph Hypergraph
component
Layout

Community
Layout

Important nodes

+
Size and center (xN − ωC , yN − ωC )
Coarsening Other nodes of community
+

Overlapping
optimisation

Hypergraph
layout

Figure 9: Principle of the calculation of coordinates for large hypergraphs.

12 MORPHISMS, CATEGORY AND HYPERGRAPHS 19

12 Morphisms, category and hypergraphs

12.0.1 A parenthesis on categories
The notions presented in this paragraph are taken from different sources includ-
ing the page on Category2 and the reference book Adámek et al. [2004].
A category C is formed by:

• a class of objects denoted Ob (C)

• a class of elements called arrows or morphisms mor (C)
and such that:
• given a pair (X, Y ) , with X ∈ Ob (C) and Y ∈ Ob (C) , there exists a set:
Hom(X, Y ) ∈ mor (C) called the morphisms from X to Y in C. If f is such
an homomorphism, we write it f : X → Y. X is called the source and Y
the target.
• for every X ∈ Ob (C) , there exists a morphism written idX ∈ Hom (X, X)
called the identity on X.

• a composition law ◦ such that for two morphisms f : A → B and g : B →

C are associated to a morphism g ◦ f : A → C called composition of f and
g, such that:
• the composition is an associative law: for any f ∈ Hom (A, B), g∈ Hom (B, C)
and h ∈ Hom (C, D) :

(h ◦ g) ◦ f = h ◦ (g ◦ f )

• the identity are the neutral elements of the composition: given any mor-
phism f ∈ Hom (A, B) :

f ◦ IdA = f = IdB ◦ f

For instance, the category where the objects are sets and where morphisms are
applications between sets with the natural composition of applications is the
Set category, written Set.
As summarized in Isah and Tella [2015], different kinds of morphisms exist.
We consider a morphism f : A → B of a category C where A and B are two
objects of C. f is:
• a monomorphism if for all pairs of morphisms of C with h : C → A and
k : C → A, f ◦ h = f ◦ k implies h = k i.e. if f is left-cancellable.

• a split monomorphism (or section) if it is left-invertible i.e. there exists

a morphism g : B → A of C such that: g ◦ f = IdA .
2 https://en.wikipedia.org/wiki/Category_(mathematics)
12 MORPHISMS, CATEGORY AND HYPERGRAPHS 20

• an epimorphism if it is right-cancellable i.e. for all pairs h : B → C and

k : B → C, h ◦ f = k ◦ f implies h = k.
• a split epimorphism (or retraction) if it is right-invertible i.e. there
exists g : B → A such that f ◦ g = IdB .

• a bimorphism if it is both a monomorphism and an epimorphism.

• an isomorphism if it is both a split monomorphism and a split epimor-
phism.
A sub-category S of a category C is a category where the objects are objects
of C and where the morphisms are morphism of C between objects of S.
When a sub-category S of a category C has its morphisms that are exactly
all the morphisms of C between objects of S, this sub-category is said full.
Correspondences between two categories are possible by associating to each
object (resp. a morphism) of the first category, an object (resp. a morphism)
of the second category: such correspondences are called functors.
Let C and D be two categories. A functor from C to D (or covariant functor),
written F : C → D, is defined by giving:
• a function such that for all X ∈ Obj (C) , there exists an object F (X) ∈
Obj (D) ;
• a function such that for all f ∈ mor (C), with f : X → Y, there exists
F (f ) ∈ mor (D) such that: F (f ) : F (X) → F (Y ) ;
and, such that:
• for all X ∈ C, we have (identity conservation):

F (idX ) = idF (X) ;

• for all X, Y, Z ∈ C and f ∈ Hom (X, Y ) and g ∈ Hom (Y, Z) , it holds

(composition conservation):

F (g ◦ f ) = F (g) ◦ F (f ) .

The construction of new categories can be achieved by using the dual of a

category C, written C op , where the objects are the ones of C and the arrows
of C op are the ones of C taken reversely. An other usual way is to consider the
product category of two categories C and C 0 , denoted C × C 0 , where the objects
are pairs of objects of C and C 0 taken in this order and the arrows are constituted
of pairs of arrows of C and C 0 taken in this order.
12 MORPHISMS, CATEGORY AND HYPERGRAPHS 21

12.0.2 Hypergraph homomorphism and category

In Dörfler and Waller [1980], the authors use the category theory to consider
hypergraph product. In this article, a hypergraph (V, E, f ) is defined as a
triple with V the vertex set, E the hyperedge set and f : E → P (V ) \ {∅} a
function that assigns to each hyperedge its non-empty set of vertices. Duplicated
hyperedges are allowed, i.e. two hyperedges can have the same image by f.
The following definitions and properties are taken from Dörfler and Waller
[1980].
The covariant power set functor P : Set → Set is defined by:
• for A ∈ Obj (Set), P (A) is the set of all subsets of A;
• for h ∈ mor(Set), h : A → B, P (h) is the homomorphism: P (A) → P (B)
such that for all A0 ⊂ A, P (h) : A0 → h (A0 ) .

Considering two hypergraphs H1 = (V1 , E1 , f1 ) and H2 = (V2 , E2 , f2 ) , a homo-

morphism of hypergraphs h : H1 → H2 consists of two functions, abusively
written h, h : V1 → V2 and h : E1 → E2 such that the diagram:
f1
E1 P (V1 ) \ {∅}
h P(h)
f2
E2 P (V2 ) \ {∅}

is commutative.
We write Hyp the category whose objects are hypergraphs and whose mor-
phisms are hypergraph homomorphisms. We write Graph the category of simple
graphs and their homomorphisms.
The results of interest for this article are the followings:
Lemma 1. Graph is a full subcategory of Hyp.

Lemma 2. Duality of hypergraphs is a covariant functor d : Hyp → Hyp.

Lemma 3. The incidence bipartite graph of a hypergraph allows a covariant
functor B : Hyp → Graph.
Given two hypergraphs H1 and H2 and their respective incidence bipartite
graph BH1 and BH2 , and a homomorphism h : H1 → H2 , B (h) : BH1 → BH2
with x 7→ h(x) and e 7→ h(e).
It is shown in Dörfler and Waller [1980] that B confuses a hypergraph with
its dual.
Lemma 4. The 2-section of a hypergraph induces the definition of a covariant
functor G : Hyp → Graph.
Lemma 5. To the intersection graph of a hypergraph corresponds the definition
of a covariant functor I : Hyp → Graph.
13 ABSTRACT SIMPLICIAL COMPLEXES 22

13 Abstract simplicial complexes

We just make a parenthesis on abstract simplicial complexes which are in fact
very particular hypergraphs.
In Lee [2010], the author introduces abstract simplicial complexes as a
collection K of nonempty finite sets called abstract simplexes that is conditioned
to only one rule: if S ∈ K, then any nonempty subset S 0 ⊆ S, S 0 6= ∅ is also
in K. Such a subset is called a face of S and the elements of S are called the
vertices of S. S
Defining V = S and for every S ∈ K, ES = (eS )eS ∈P(S) and E =  ES
S∈K S∈K
where  is the concatenation operation on families, i.e. the family of all the
elements of every family that is concatenated. H = (V, E) is then the unique
hypergraph that corresponds to this simplicial complex.
Reciprocally, given a hypergraph H = (V, E), such that for every e ∈ E,
if for all e0 ⊆ e, e0 ∈ E, then H is in correspondence with a unique abstract
simplicial complex.
Simplicial complexes find their strength in the fact that simplicial homology
can be used on them, to study the number of holes of their structure. Simplicial
homology depends only on the associated topological space and hence gives
a way to distinguish simplicial complexes. The interested reader can refer to
Hatcher [2005] for an introduction on simplicial homology3 .
As mentioned in Wasserman and Faust [1994], simplicial complexes are use-
ful to study the overlaps between subsets and the connectivity of the network,
as well as defining a dimensionality of the network. More complex than hyper-
graphs by their hierarchical structure, they have been used in different studies
such as the structural analysis of a game, using q-holes in Gould and Gatrell
[1979].
Abstract simplicial complexes are used quite often in the literature for study-
ing co-occurrence networks. In Nikolaev [2016], the author studies systems with
higher-order interaction by considering different models and particularly using
a simplicial complex model and a hypergraph model. It is also the case in Sal-
nikov et al. [2018] where co-occurrence simplicial complexes are used to identify
the homological holes in mathematic knowledge, in order to discover emerging
knowledge. In Benson et al. [2018], the authors study the temporal evolution of
different co-occurrence datasets in order to detect and predict higher-order in-
teraction using simplicial closure, studying particularly the life-cycles of triples
and quadruples of nodes, showing that the edge density and tie strength are two
preponderant factors in the evolution of the group to a closed simplex.

14 Hypergraph coloring
The subject of hypergraph coloring extends the one of graph coloring; but there
is not a single way of doing so. Bujtás et al. [2015] is a full survey on the
3 Course of A. Hatcher on Cornell.edu
15 HYPERGRAPH PARTITIONING AND CLUSTERING 23

subject: we just give here a very basic definition extracted from it and send the
interested reader to this reference for further details.
A proper hypergraph coloring is a mapping of a vertex of V to a color
number taken in JλK where λ is a nonnegative integer such that for every hy-
peredge there are at least two vertices of different colors. The minimum value
of λ for which a proper coloring exists is called the chromatic number of the
hypergraph H and written χ (H) . A hypergraph is k-colorable if its chromatic
number is no more than k and k-chromatic if χ (H) = k.
Hypergraph coloring has found applications in finding bounds of the chro-
matic number of some graphs in Kierstead and Rodl [1996]. They are used
in different optimization problems such as divide and conquer approach in Lu
[2004]. In Voloshin [1993, 2002], the author explores the coloring of mixed
hypergraphs, in which the hyperedge family is partitioned in two sub-families
called the hyperedges and anti-hyperedges. The author applies it to problem of
energy supply. Coloring is also used in partition problems in Lu [2004].
The subject of hyperedge coloring is also tackled in Gyárfás and Sárközy
[2013] to find monochromatic paths and cycles in hypergraphs.

15 Hypergraph partitioning and clustering

Hypergraph partitioning is defined in the Encyclopedia of Parallel Computing4
as the “task of dividing a hypergraph into two or more roughly equal-sized parts
such that a cost function on the hyperedges connecting vertices in different parts
is minimized.”
Very often this definition is too restrictive and requires strictly more than
two parts. The problem of partitioning a hypergraph is at least NP-hard as
mentioned in Garey and Johnson [2002]. In Karypis et al. [1999], the au-
thors present a hypergraph partitioning algorithm, called hMetis, based on a
multilevel coarsening of the hypergraph, working by iterative bisections of the
coarsened hypergraphs, starting from the smallest one. In Karypis and Kumar
[2000], the authors present an other hypergraph partitioning that is k ways,
called hMeTiS-Kway algorithm.
In Papa and Markov [2007], the author gives several methods for hypergraph
partitioning and see the action of clustering as “The process of computing a
coarser hypergraph from an input hypergraph by merging vertices into larger
groups of vertices called clusters.” Moreover, the author gives several appli-
cations of partitioning and clustering, including VLSI design, numerical linear
algebra, automated theorem-proving and formal verification.
The literature is abundant in applications and methods: for more details a
survey on clustering ensembles techniques has been done in Ghaemi et al. [2009],
which includes hypergraph partitioning.
Clustering and partitioning require often multi-level strategies approach:
this is a well studied domain, as it has been extensively used for VLSI design—
see for instance, Karypis et al. [1999]—, for parallel scientific computing—
4 Hypergraph Partitioning in Encyclopedia of Parallel computing
16 APPLICATION OF HYPERGRAPHS 24

Catalyurek and Aykanat [1999], Devine et al. [2006], Ballard et al. [2016]—, for
image categorization—Yuchi Huang et al. [2011]—, for social networks—Zhou
et al. [2007], Yang et al. [2017].

16 Application of hypergraphs
Hypergraphs fit to model multi-adic relationships in structures where the tra-
ditional pairwise relationship of graphs is insufficient: they are used in many
areas such as social networks in particular in collaboration networks—Newman
[2001b,a]—, co-author networks—Grossman and Ion [1995], Taramasco et al.
[2010]—, chemical reactions—Temkin et al. [1996]—, genome—Chauve et al.
[2013]—, VLSI design—Karypis et al. [1999]. Hypergraphs are also used in
information retrieval for different purposes such as query formulation in text
retrieval—Bendersky and Croft [2012]— or in music recommendation—Bu et al.
[2010]. Several applications of hypergraphs exist based on the diffusion process
firstly developed by Zhou et al. [2007]. Gao et al. [2012] uses Zhou et al. [2007] for
3D-object retrieval and recognition by building multiple hypergraphs of objects
based on their 2D-views that are analyzed using the same approach. In Zhu et al.
[2015], multiple hypergraphs are constructed to characterize the complex rela-
tions between landmark images and are gathered into a multi-modal hypergraph
that allows the integration of heterogeneous sources providing content-based vi-
sual landmark searches. Hypergraphs are also used in multi-feature indexing to
help image retrieval Xu et al. [2016]. For each image, a hyperedge gathers the
first n most similar images based on different features. Hyperedges are weighted
by average similarity. A spectral clustering algorithm is then applied to divide
the dataset into k sub-hypergraphs. A random walk on these sub-hypergraphs
allows to retrieve significant images: they are used to build a new inverted index,
useful to query images. In Wang et al. [2018], a joint-hypergraph learning is
achieved for image retrieval, combining efficiently a semantic hypergraph based
on image tags with a visual hypergraph based on image features.

16.0.1 VLSI design

Very Large Scale Integration—VLSI for short—aims at integrating numerous
transistors and devices into a single chip to create an integrated circuit. In
VLSI design, hypergraphs are intensively used for placement of chipsets: in this
case, the important thing is to achieve an efficient clustering and partitioning of
the hypergraph in order to minimize connections between elements of the circuit;
more details are given in Papa and Markov [2007]. In this case, the targeted
layout is an orthogonal layout. Dedicated algorithms have been implemented to
achieve this—Eschbach et al. [2006], Karypis et al. [1999], Karypis and Kumar
[2000].

16.0.2 Collaboration networks

The comments of this Section are directly cited from Ouvrard et al. [2017].
16 APPLICATION OF HYPERGRAPHS 25

As mentioned in Newman [2001a], a collaboration is a multi-adic relation-

ship between occurrences, and, therefore, the proper modeling is done by hy-
pergraphs. Nonetheless, in Newman [2001a], this multi-adic relationship is ap-
proximated by a 2-adic relationship in between pairs of collaborators when it
comes to be studied. The same approximation is made in many other studies
such as Ramasco et al. [2004].
The reasons for this approximation are numerous. It enables the use of clas-
sical graph techniques and properties when studying the different characteristics
of collaboration networks, such as degree distribution, clustering coefficient and
also when applying quantifying metrics. Today, many different techniques that
help with the retrieval of information from graphs are available.
This 2-adic relationship approximation has been developed in many articles,
where even if the multi-adic relationship of the data was pointed to be more
pertinent, this multi-adic relationship was not used when getting to clustering.
Since the end of the year 2000s, the limitations of the 2-adic approach are more
and more challenged, as it leads to a partial loss of the information contained
in the multi-adic relationship. As a result, in Estrada and Rodriguez-Velazquez
[2005] complex networks are modeled by hypergraphs.
In Taramasco et al. [2010], the authors study the academic team formation
using epistemic hypergraphs where hyperedges are subsets of unions of a set
of agents and a set of concepts. They introduce new features to characterize
the evolution of collaboration networks taking into account the hypergraphic
nature of networks. This paper brings keystones in the study of a bi-dimensional
hypergraph and shows how the keeping of multi-adic relationships can help to
gain in the understanding of the evolution of a network.

16.0.3 Recommender systems and hypergraphs

Recommender systems contain two big methods of recommendation: the item-
item recommendation and the user-item recommendation. Both of them require
to make groups of items that have been bought for either the purchase of the
same item or for the same profile of user.
In Bu et al. [2010], the authors use a unified hypergraph, i.e. a hypergraph
that has multiple types of vertices to perform music recommendation that takes
not only into account the preference of other users and similar music to the
ones they listen. They start by learning on the hypergraph using a cost func-
tion with a regularization term that takes the vector of ranking scores as variable
and the query vector. The optimal solution for the ranking vector is found when
the gradient of the cost function is zero leading to an explicit expression of the
recommendation vector, based on the invert of the α-Laplacian matrix of the hy-
pergraph, where α is learned off-line. In Lü et al. [2012], news recommendation
is achieved by using a hypergraph partition and a recommendation via ranking
on the hypergraph similar to the previous approach on a hybrid hypergraph
that contains seven different implicit relations with different objects.
In Zhu et al. [2016], a heterogeneous hypergraph is built regrouping the in-
formation on users, tags and documents for document recommendation. They
16 APPLICATION OF HYPERGRAPHS 26

consider different cost functions, one for annotation relations, one for tag rela-
tions and one for document relations, based on the Laplacian of the correspond-
ing sub-hypergraphs. The final cost relation is a linear combination of the three
cost functions that is optimized using the first k eigenvectors corresponding to
the smallest eigenvalues of the total cost matrix.
In Zheng et al. [2018], a social network hybrid recommender system is pro-
posed based on hypergraph topological structure, that combined with a hybrid
matrix factorization model helps to enhance the description of the interior re-
lationships of a social network; in particular the neighborhood of the users and
items is used.
Additional references can be found to related work in the previous references
and in Lü et al. [2012].

16.0.4 Hypergraph grammar

Hypergraph grammars are extension of graph grammars. Graph grammars, also
known as graph rewriting systems, aim at enumerating all the possible graphs
from a starting graph, by considering a set of graph rewriting rules, searching
an occurrence of the pattern graph (i.e. the current graph) and replacing it
by an instance of the replacement graph. Graph rewriting is intensively used
in software engineering for construction and verification, in layout algorithms,
picture generation but also in chemistry for the search of new molecules.
Several studies exist on hypergraph grammars. Particularly, in Drewes
et al. [1997], a handle hyperedge replacement is proposed: a handle is a sub-
hypergraph constituted of a hyperedge with its incident vertices, extending the
hyperedge replacement proposed in Habel and Kreowski [1987].
Application of hypergraph grammars to molecular hypergraphs is still an
active subject of research—Kajino [2018] for instance. Hypergraph rewriting is
also used for name binding in Yasen and Ueda [2018], and also for graph design
in Luerssen and Powers [2007].

16.0.5 Hypergraphs and linear algebra calculus

In Catalyurek and Aykanat [1999], the authors use a hypergraph-partitioning
of the rows (or columns) of a sparse matrix that has to be multiplied by a
vector to be used by an iterative solver in order to achieve parallel computation.
The partitioning aims at minimizing the total communication volume required
between its different segments. The authors use two hypergraphs: one in which
the vertices represent the rows of the matrix and the hyperedges represent the
columns that have a nonzero intersection with the rows and the other, its dual
model.
There are several methods of matrix factorization that use hypergraph reg-
ularization. They are all based on the fact that a hypergraph can represent a
matrix, by considering either the rows as vertices and columns as hyperedges
containing vertices of nonzero elements or reversely using the dual hypergraph.
This approach is applied to propose a hypergraph-based non-symmetrical nested
17 SOME ADDITIONAL COMMENTS 27

dissection ordering algorithm for LU decomposition of sparse matrices in Grigori

et al. [2010].
In Zeng et al. [2014], the authors propose a Hypergraph regularized Non-
negative Matrix Factorization (HNMF for short) to refine the classical NMF
approach and apply it to image clustering.
In Jin et al. [2015], the authors propose a multiple hypergraph regularized
low-rank matrix factorization, where the pool of hypergraphs used for the reg-
ularization comes from the selection of neighbors in the manifold through the
bandwidth parameter used in the heat kernel. The hypergraph Laplacian ma-
trices are combined together allowing the construction of a multi-hypergraph
regularization that is added to the regularization term of the original Truncated
Singular Value Decomposition—TSVD for short.
In Wu et al. [2018], the authors propose a mixed hypergraph regularized
non-negative matrix factorization framework that constrains the vertices of a
hyperedge to be projected onto the same latent subspace. The heterogeneity
comes from the fact that hyperedges are built using two kind of neighbors, one
based on topological information and the other on similarity information.

17 Some additional comments

A common objection to hypergraphs is: “O.K., hypergraphs extend graphs, but
the same can be done with bipartite graphs.” To answer this objection different
arguments can be developed. We regroup here some of the common arguments
found either on Internet56 or in the literature.
First, graphs are particular case of hypergraphs: every graph is a hyper-
graph, but not all hypergraphs are graphs. Bipartite graphs are particular case
of graphs: not every graph is a bipartite graph, but all bipartite graphs are
graphs. Hence:

B ( G ( H

writing B the set of all bipartite graphs, G the set of all graphs and H
the set of all hypergraphs.
Second, it is true that to a given hypergraph H = (V, E) corresponds a bi-
partite graph G = (V ∪ V 0 , EG ) . The bipartite graph is obtained
 by considering
for each hyperedge ej ∈ E an additional vertex vej . V 0 = vej : ej ∈ E and

that there is an edge between v ∈ V and vej ∈ V 0 if and only if v ∈ ej . The

bipartite graph is then called the incidence graph of the hypergraph H. Con-
versely, only bipartite graphs with no isolated vertex in any of their vertex part
can represent a hypergraph with non-empty hyperedge, as required in Berge
and Minieka [1973].
5 https://cs.stackexchange.com/questions/12769/how-is-a-hypergraph-different-from-a-

bipartite-graph
6 http://en.wikipedia.org/wiki/Hypergraph#Bipartite_graph_model
18 ACKNOWLEDGMENTS 28

Third, from the previous argument, we can develop the argument of factor-
ization. A hypergraph is a factorized version of its incidence graph: a hyperedge
ej is defined as a collection of distinct vertices: ej = {vji : i ∈ Jnj K} ,with nj
representing the cardinality of ej . The associated bipartite graph, also called
incidence graph, is the developed version: there is an edge—i.e. a pair (vji , ej )—
per vertex membership of hyperedge and the vertex set is extended to hold a
vertex representation of the original hyperedge. Hence, the vertex set of the
incidence graph is varying depending on the hyperedges content, which is not
the case for hypergraphs. Hypergraphs bring the power of sets: operations on
sets such as union, intersection, complementation or subsets are well defined.
Nonetheless, one has to remark that a hypergraph and its dual have the same
corresponding bipartite graph: the bipartite graph confuses the hypergraph with
its dual Dörfler and Waller [1980].
Fourth, bipartite graphs correspond exactly to 2-colorable graphs. Coloring
a hypergraph is defined in Berge and Minieka [1973] as assigning a color to each
vertex such that no hyperedge, differing from a singleton, is monochromatic. In
Seymour [1974], a hypergraph that is not 2-colourable but where every proper
subset is 2-colourable is called a condenser. Condensers are shown to be min-
imal hypergraphs that are not 2-colourable. Examples of such condensers are:
{{1, 2} , {2, 3} , . . . , {n − 1, n} , {n, 1}} with n odd or {{1, 2, . . . , n}}∪{{0, i} : 1 6 i 6 n}
with n > 2.
Fifth, in Zykov [1974], the author insists on the fact that while the isomor-
phism between a hypergraph and its incident bipartite representation, called
the König graph, is indubitable, some of the statements made with hypergraphs
have a very “artificial and cumbersome character in terms of König representa-
tion which obscures the point”. The author takes the example of the chromatic
number definition of an ordinary graph, which is a very particular case of hy-
pergraph, in terms of its König representation.
Sixth, in Berge and Minieka [1973], the author focuses on some problems
that have solutions only with hypergraphs: the representative graph or line
graph is the 2-section of the dual hypergraph. Given a representative graph G,
the question raised is to know if there exists a hypergraph H having G as its
representative graph. The problem is shown feasible for general hypergraphs,
but Berge and Minieka [1973] shows that this problem has no solution when it is
required that H is r-uniform and that a vertex belongs to more than r cliques.
Hence, the graph shown in Figure 10 cannot be the representative graph of a
2-uniform hypergraph.

18 Acknowledgments
This work was done during the writing of the Thesis of Xavier OUVRARD, done
at University of Geneva, supervised by Pr. Stéphane MARCHAND-MAILLET
and founded by a doctoral position at CERN, in Collaboration Spotting team,
supervised by Dr. Jean-Marie LE GOFF.
REFERENCES 29

c b

d a g

e f

Figure 10: Counter-example of graph that cannot be the representative graph

of a 2-uniform hypergraph.

References
Jiří Adámek, Horst Herrlich, and George E Strecker. Abstract and concrete
categories. The joy of cats. 2004. URL http://katmat.math.uni-bremen.
de/acc/acc.pdf.

Bilal Alsallakh, Luana Micallef, Wolfgang Aigner, Helwig Hauser, Silvia Miksch,
and Peter Rodgers. The State-of-the-Art of Set Visualization: The State-
of-the-Art of Set Visualization. Computer Graphics Forum, 35(1):234–260,
February 2016. ISSN 01677055. doi: 10.1111/cgf.12722. URL https://doi.
org/10.1111/cgf.12722.

Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. Hypergraph
Partitioning for Sparse Matrix-Matrix Multiplication. ACM Transactions on
Parallel Computing, 3(3):1–34, December 2016. ISSN 23294949. doi: 10.1145/
3015144. URL https://doi.org/10.1145/3015144.
Michael Bendersky and W. Bruce Croft. Modeling higher-order term dependen-
cies in information retrieval using query hypergraphs. In Proceedings of the
35th international ACM SIGIR conference on Research and development in
information retrieval - SIGIR ’12, page 941, Portland, Oregon, USA, 2012.
ACM Press. ISBN 978-1-4503-1472-5. doi: 10.1145/2348283.2348408. URL
https://doi.org/10.1145/2348283.2348408.

Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon
Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of
the National Academy of Sciences, 115(48):E11221–E11230, November 2018.
ISSN 0027-8424, 1091-6490. doi: 10.1073/pnas.1800683115. URL https:
//doi.org/10.1073/pnas.1800683115.

Claude Berge and Edward Minieka. Graphs and hypergraphs, volume 7. North-
Holland publishing company Amsterdam, 1973.
REFERENCES 30

François Bertault and Peter Eades. Drawing Hypergraphs in the Subset Stan-
dard (Short Demo Paper). In Graph Drawing, volume 1984, pages 164–
169. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001. ISBN 978-3-540-
41554-1 978-3-540-44541-8. doi: 10.1007/3-540-44541-2_15. URL https:
//doi.org/DOI:10.1007/3-540-44541-2_15.

Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne

Lefebvre. Fast unfolding of communities in large networks. Journal of
Statistical Mechanics: Theory and Experiment, 2008(10):P10008, October
2008. ISSN 1742-5468. doi: 10.1088/1742-5468/2008/10/P10008. URL
https://doi.org/10.1088/1742-5468/2008/10/P10008.

Alain Bretto. Hypergraph Theory. Mathematical Engineering. Springer Inter-

national Publishing, Heidelberg, 2013. ISBN 978-3-319-00079-4 978-3-319-
00080-0. doi: 10.1007/978-3-319-00080-0. URL https://doi.org/10.1007/
978-3-319-00080-0.
Jiajun Bu, Shulong Tan, Chun Chen, Can Wang, Hao Wu, Lijun Zhang, and
Xiaofei He. Music recommendation by unified hypergraph: combining social
media information and music content. In Proceedings of the international
conference on Multimedia - MM ’10, page 391, Firenze, Italy, 2010. ACM
Press. ISBN 978-1-60558-933-6. doi: 10.1145/1873951.1874005. URL https:
//doi.org/10.1145/1873951.1874005.

Csilla Bujtás, Zsolt Tuza, and Vitaly Voloshin. Hypergraph colour-

ing. In Topics in Chromatic Graph Theory, pages 230–254. Cam-
bridge University Press, Cambridge, 2015. ISBN 978-1-139-51979-3.
doi: 10.1017/CBO9781139519793.014. URL https://doi.org/10.1017/
CBO9781139519793.014.

U.V. Catalyurek and C. Aykanat. Hypergraph-partitioning-based decomposi-

tion for parallel sparse-matrix vector multiplication. IEEE Transactions on
Parallel and Distributed Systems, 10(7):673–693, July 1999. ISSN 10459219.
doi: 10.1109/71.780863. URL https://doi.org/10.1109/71.780863.
Cedric Chauve, Murray Patterson, and Ashok Rajaraman. Hypergraph Cov-
ering Problems Motivated by Genome Assembly Questions. In Combi-
natorial Algorithms, volume 8288, pages 428–432. Springer Berlin Heidel-
berg, Berlin, Heidelberg, 2013. ISBN 978-3-642-45277-2 978-3-642-45278-
9. doi: 10.1007/978-3-642-45278-9_37. URL https://doi.org/10.1007/
978-3-642-45278-9_37.

B. Chazelle and J. Friedman. A deterministic view of random sampling and its

use in geometry. In [Proceedings 1988] 29th Annual Symposium on Founda-
tions of Computer Science, pages 539–549, White Plains, NY, USA, 1988.
IEEE. ISBN 978-0-8186-0877-3. doi: 10.1109/SFCS.1988.21970. URL
https://doi.org/10.1109/SFCS.1988.21970.
REFERENCES 31

K.D. Devine, E.G. Boman, R.T. Heaphy, R.H. Bisseling, and U.V. Catalyurek.
Parallel hypergraph partitioning for scientific computing. In Proceedings 20th
IEEE International Parallel & Distributed Processing Symposium, page 10
pp., Rhodes Island, Greece, 2006. IEEE. ISBN 978-1-4244-0054-6. doi: 10.
1109/IPDPS.2006.1639359. URL https://doi.org/10.1109/IPDPS.2006.
1639359.
W. Dörfler and D. A. Waller. A category-theoretical approach to hypergraphs.
Archiv der Mathematik, 34(1):185–192, December 1980. ISSN 0003-889X,
1420-8938. doi: 10.1007/BF01224952. URL https://doi.org/10.1007/
BF01224952.

F. Drewes, H.-J. Kreowski, and A. Habel. Hyperedge replacement graph gram-

mars. In Handbook of Graph Grammars and Computing by Graph Transfor-
mation, pages 95–162. WORLD SCIENTIFIC, February 1997. ISBN 978-
981-02-2884-2 978-981-238-472-0. doi: 10.1142/9789812384720_0002. URL
https://doi.org/10.1142/9789812384720_0002.

Thomas Eschbach, Wolfgang Guenther, and Bernd Becker. Orthogonal Hy-

pergraph Drawing for Improved Visibility. Journal of Graph Algorithms and
Applications, 10(2):141–157, 2006. ISSN 1526-1719. doi: 10.7155/jgaa.00122.
URL https://doi.org/10.7155/jgaa.00122.
Ernesto Estrada and Juan A Rodriguez-Velazquez. Complex networks as hy-
pergraphs. arXiv preprint physics/0505137, 2005.
Yue Gao, Meng Wang, Dacheng Tao, Rongrong Ji, and Qionghai Dai. 3-D
Object Retrieval and Recognition With Hypergraph Analysis. IEEE Trans-
actions on Image Processing, 21(9):4290–4303, September 2012. ISSN 1057-
7149, 1941-0042. doi: 10.1109/TIP.2012.2199502. URL https://doi.org/
10.1109/TIP.2012.2199502.
Michael R Garey and David S Johnson. Computers and intractability, volume 29.
wh freeman New York, 2002.
Reza Ghaemi, Md Nasir Sulaiman, Hamidah Ibrahim, Norwati Mustapha, and
others. A survey: clustering ensembles techniques. World Academy of Science,
Engineering and Technology, 50:636–645, 2009.
Peter Gould and Anthony Gatrell. A structural analysis of a game: The Liver-
pool v Manchester united cup final of 1977. Social Networks, 2(3):253–273,
January 1979. ISSN 03788733. doi: 10.1016/0378-8733(79)90017-0. URL
https://doi.org/10.1016/0378-8733(79)90017-0.

Laura Grigori, Erik G. Boman, Simplice Donfack, and Timothy A. Davis.

Hypergraph-Based Unsymmetric Nested Dissection Ordering for Sparse LU
Factorization. SIAM Journal on Scientific Computing, 32(6):3426–3446, Jan-
uary 2010. ISSN 1064-8275, 1095-7197. doi: 10.1137/080720395. URL
https://doi.org/10.1137/080720395.
REFERENCES 32

Jerrold W Grossman and Patrick DF Ion. On a portion of the well-known

collaboration graph. Congressus Numerantium, pages 129–132, 1995.
András Gyárfás and Gábor N Sárközy. Monochromatic path and cycle partitions
in hypergraphs. the electronic journal of combinatorics, 20(1):18, 2013.

Annegret Habel and Hans-Jörg Kreowski. Some structural aspects of hyper-

graph languages generated by hyperedge replacement. In Franz J. Branden-
burg, Guy Vidal-Naquet, and Martin Wirsing, editors, STACS 87, volume
247, pages 207–219. Springer-Verlag, Berlin/Heidelberg, 1987. ISBN 978-3-
540-17219-2. doi: 10.1007/BFb0039608. URL https://doi.org/10.1007/
BFb0039608.

Allen Hatcher. Algebraic topology. 2005.

Ahmed Isah and Y. Tella. The Concept of Multiset Category. British Jour-
nal of Mathematics & Computer Science, 9(5):427–437, January 2015. ISSN
22310851. doi: 10.9734/BJMCS/2015/18415. URL https://doi.org/10.
9734/bjmcs/2015/18415.
Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, and Mathieu Bas-
tian. ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network
Visualization Designed for the Gephi Software. PLoS ONE, 9(6):e98679,
June 2014. ISSN 1932-6203. doi: 10.1371/journal.pone.0098679. URL
https://dx.plos.org/10.1371/journal.pone.0098679.

Taisong Jin, Jun Yu, Jane You, Kun Zeng, Cuihua Li, and Zhengtao Yu.
Low-rank matrix factorization with multiple Hypergraph regularizer. Pat-
tern Recognition, 48(3):1011–1022, March 2015. ISSN 00313203. doi:
10.1016/j.patcog.2014.09.002. URL https://doi.org/10.1016/j.patcog.
2014.09.002.

D. S. Johnson and H. O. Pollak. Hypergraph planarity and the complexity of

drawing venn diagrams. Journal of Graph Theory, 11(3):309–325, 1987. ISSN
03649024, 10970118. doi: 10.1002/jgt.3190110306. URL http://doi.wiley.
com/10.1002/jgt.3190110306.

Martin Junghans. Visualization of hyperedges in fixed graph layouts. PhD The-

sis, Master\rqs thesis, Brandenburg University of Technology, Cottbus, 2008.
Hiroshi Kajino. Molecular hypergraph grammar with its application to molec-
ular optimization. arXiv preprint arXiv:1809.02745, 2018.
G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph
partitioning: applications in VLSI domain. IEEE Transactions on Very Large
Scale Integration (VLSI) Systems, 7(1):69–79, March 1999. ISSN 1063-8210,
1557-9999. doi: 10.1109/92.748202. URL https://doi.org/10.1109/92.
748202.
REFERENCES 33

George Karypis and Vipin Kumar. Multilevel k-way Hypergraph Partitioning.

VLSI Design, 11(3):285–300, January 2000. ISSN 1065-514X, 1563-5171. doi:
10.1155/2000/19436. URL https://doi.org/10.1155/2000/19436.
Michael Kaufmann, Marc van Kreveld, and Bettina Speckmann. Subdivision
Drawings of Hypergraphs. In David Hutchison, Takeo Kanade, Josef Kittler,
Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Os-
car Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri
Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Ioannis G. Tol-
lis, and Maurizio Patrignani, editors, Graph Drawing, volume 5417, pages
396–407. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-
642-00218-2 978-3-642-00219-9. doi: 10.1007/978-3-642-00219-9_39. URL
https://doi.org/10.1007/978-3-642-00219-9_39.
Andreas Kerren and Ilir Jusufi. A novel radial visualization approach for undi-
rected hypergraphs. Eurographics Association, pages 25–29, 2013.
H.A. Kierstead and V. Rodl. Applications of hypergraph coloring to color-
ing graphs not inducing certain trees. Discrete Mathematics, 150(1-3):187–
193, April 1996. ISSN 0012365X. doi: 10.1016/0012-365X(95)00187-2. URL
https://doi.org/10.1016/0012-365X(95)00187-2.
John Lee. Introduction to topological manifolds, volume 202. Springer Science
& Business Media, 2010.

Chi-Jen Lu. Deterministic hypergraph coloring and its applications. SIAM

Journal on Discrete Mathematics, 18(2):320–331, 2004.
Linyuan Lü, Matúš Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, and
Tao Zhou. Recommender systems. Physics reports, 519(1):1–49, 2012.

Martin H Luerssen and David MW Powers. Graph design by graph grammar

evolution. In 2007 IEEE Congress on Evolutionary Computation, pages 386–
393. IEEE, 2007.
Erkki Mäkinen. How to draw a hypergraph. International Journal of Computer
Mathematics, 34(3-4):177–185, 1990. doi: 10.1080/00207169008803875. URL
https://doi.org/10.1080/00207169008803875.
M. E. J. Newman. Scientific collaboration networks. II. Shortest paths, weighted
networks, and centrality. Physical Review E, 64(1):016132, June 2001a. ISSN
1063-651X, 1095-3787. doi: 10.1103/PhysRevE.64.016132. URL https://
link.aps.org/doi/10.1103/PhysRevE.64.016132.

M. E. J. Newman. Scientific collaboration networks. I. Network construction

and fundamental results. Physical Review E, 64(1):016131, June 2001b. ISSN
1063-651X, 1095-3787. doi: 10.1103/PhysRevE.64.016131. URL https://
doi.org/10.1103/PhysRevE.64.016131.
REFERENCES 34

Alexey Nikolaev. Modeling and analysis of higher-order interactions in collabo-

rative networks. 2016.
Xavier Ouvrard, Jean-Marie Le Goff, and Stéphane Marchand-Maillet. Net-
works of Collaborations: Hypergraph Modeling and Visualisation. arXiv
preprint arXiv:1707.00115, 2017.
David Papa and Igor Markov. Hypergraph Partitioning and Clustering. In
Teofilo Gonzalez, editor, Handbook of Approximation Algorithms and Meta-
heuristics, volume 20073547, pages 61–1–61–19. Chapman and Hall/CRC,
May 2007. ISBN 978-1-58488-550-4 978-1-4200-1074-9. doi: 10.1201/
9781420010749.ch61. URL https://doi.org/10.1201/9781420010749.
ch61.
Jesse Paquette and Taku Tokuyasu. Hypergraph visualization and enrichment
statistics: how the EGAN paradigm facilitates organic discovery from big
data. page 78650E, San Francisco Airport, California, USA, February 2011.
doi: 10.1117/12.890220. URL https://doi.org/10.1117/12.890220.
José J. Ramasco, S. N. Dorogovtsev, and Romualdo Pastor-Satorras. Self-
organization of collaboration networks. Physical Review E, 70(3):036106,
September 2004. ISSN 1539-3755, 1550-2376. doi: 10.1103/PhysRevE.70.
036106. URL https://doi.org/10.1103/PhysRevE.70.036106.
Vsevolod Salnikov, Daniele Cassese, Renaud Lambiotte, and Nick S. Jones.
Co-occurrence simplicial complexes in mathematics: identifying the holes of
knowledge. Applied Network Science, 3(1):37, December 2018. ISSN 2364-
8228. doi: 10.1007/s41109-018-0074-3. URL https://doi.org/10.1007/
s41109-018-0074-3.
P. D. Seymour. On the two-colouring of hypergraphs. The Quarterly Journal
of Mathematics, 25(1):303–311, 1974. ISSN 0033-5606, 1464-3847. doi: 10.
1093/qmath/25.1.303. URL https://doi.org/10.1093/qmath/25.1.303.
John G. Stell. Relations on Hypergraphs. In Relational and Algebraic Meth-
ods in Computer Science, volume 7560, pages 326–341. Springer Berlin Hei-
delberg, Berlin, Heidelberg, 2012. ISBN 978-3-642-33313-2 978-3-642-33314-
9. doi: 10.1007/978-3-642-33314-9_22. URL https://doi.org/10.1007/
978-3-642-33314-9_22.
Carla Taramasco, Jean-Philippe Cointet, and Camille Roth. Academic team
formation as evolving hypergraphs. Scientometrics, 85(3):721–740, December
2010. ISSN 0138-9130, 1588-2861. doi: 10.1007/s11192-010-0226-4. URL
https://doi.org/10.1007/s11192-010-0226-4.
Oleg N Temkin, Andrew V Zeigarnik, and DG Bonchev. Chemical reaction
networks: a graph-theoretical approach. CRC Press, 1996.
John Venn. On the Diagrammatic and Mechanical Representation of Proposi-
tions and Reasonings. 1881.
REFERENCES 35

VI Voloshin. The mixed hypergraphs. Computer Science Journal of Moldova,

1(1):1, 1993.
Vitaly Voloshin. Coloring Mixed Hypergraphs: Theory, Algorithms and Appli-
cations, volume 17 of Fields Institute Monographs. American Mathematical
Society, Providence, Rhode Island, June 2002. ISBN 978-0-8218-2812-0 978-
1-4704-3144-0. doi: 10.1090/fim/017. URL https://doi.org/10.1090/fim/
017.
Yaxiong Wang, Li Zhu, Xueming Qian, and Junwei Han. Joint Hyper-
graph Learning for Tag-Based Image Retrieval. IEEE Transactions on Im-
age Processing, 27(9):4437–4451, September 2018. ISSN 1057-7149, 1941-
0042. doi: 10.1109/TIP.2018.2837219. URL https://doi.org/10.1109/
TIP.2018.2837219.
Stanley Wasserman and Katherine Faust. Social Network Analysis: Methods
and Applications. Cambridge University Press, 1 edition, November 1994.
ISBN 978-0-521-38707-1 978-0-521-38269-4 978-0-511-81547-8. doi: 10.1017/
CBO9780511815478. URL https://doi.org/10.1017/CBO9780511815478.
Wenhui Wu, Sam Kwong, Yu Zhou, Yuheng Jia, and Wei Gao. Nonneg-
ative matrix factorization with mixed hypergraph regularization for com-
munity detection. Information Sciences, 435:263–281, April 2018. ISSN
00200255. doi: 10.1016/j.ins.2018.01.008. URL https://doi.org/10.1016/
j.ins.2018.01.008.
Zihang Xu, Junping Du, Lingfei Ye, and Dan Fan. Multi-feature indexing for
image retrieval based on hypergraph. In 2016 4th International Conference on
Cloud Computing and Intelligence Systems (CCIS), pages 494–500, Beijing,
China, August 2016. IEEE. ISBN 978-1-5090-1256-5. doi: 10.1109/CCIS.
2016.7790309. URL https://doi.org/10.1109/CCIS.2016.7790309.
Wenyin Yang, Guojun Wang, Md Zakirul Alam Bhuiyan, and Kim-Kwang Ray-
mond Choo. Hypergraph partitioning for social networks based on informa-
tion entropy modularity. Journal of Network and Computer Applications, 86:
59–71, May 2017. ISSN 10848045. doi: 10.1016/j.jnca.2016.10.002. URL
https://doi.org/10.1016/j.jnca.2016.10.002.

Alimujiang Yasen and Kazunori Ueda. Name Binding is Easy with Hyper-
graphs. IEICE Transactions on Information and Systems, E101.D(4):1126–
1140, 2018. ISSN 0916-8532, 1745-1361. doi: 10.1587/transinf.2017EDP7257.
URL https://doi.org/10.1587/transinf.2017edp7257.

Yuchi Huang, Qingshan Liu, Fengjun Lv, Yihong Gong, and Dimitris N
Metaxas. Unsupervised Image Categorization by Hypergraph Partition. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 33(6):1266–1273,
June 2011. ISSN 0162-8828, 2160-9292. doi: 10.1109/TPAMI.2011.25. URL
https://doi.org/10.1109/TPAMI.2011.25.
REFERENCES 36

Kun Zeng, Jun Yu, Cuihua Li, Jane You, and Taisong Jin. Image clustering by
hyper-graph regularized non-negative matrix factorization. Neurocomputing,
138:209–217, August 2014. ISSN 09252312. doi: 10.1016/j.neucom.2014.01.
043. URL https://doi.org/10.1016/j.neucom.2014.01.043.
Xiaoyao Zheng, Yonglong Luo, Liping Sun, Xintao Ding, and Ji Zhang. A novel
social network hybrid recommender system based on hypergraph topologic
structure. World Wide Web, 21(4):985–1013, July 2018. ISSN 1386-145X,
1573-1413. doi: 10.1007/s11280-017-0494-5. URL https://doi.org/10.
1007/s11280-017-0494-5.
Denny Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hyper-
graphs: Clustering, classification, and embedding. In Advances in neural
information processing systems, pages 1601–1608, 2007.
Lei Zhu, Jialie Shen, Hai Jin, Ran Zheng, and Liang Xie. Content-Based Visual
Landmark Search via Multimodal Hypergraph Learning. IEEE Transactions
on Cybernetics, 45(12):2756–2769, December 2015. ISSN 2168-2267, 2168-
2275. doi: 10.1109/TCYB.2014.2383389. URL https://doi.org/10.1109/
TCYB.2014.2383389.
Yu Zhu, Ziyu Guan, Shulong Tan, Haifeng Liu, Deng Cai, and Xiaofei He.
Heterogeneous hypergraph embedding for document recommendation. Neu-
rocomputing, 216:150–162, December 2016. ISSN 09252312. doi: 10.1016/j.
neucom.2016.07.030. URL https://linkinghub.elsevier.com/retrieve/
pii/S0925231216307755.
A A Zykov. Hypergraphs. Russian Mathematical Surveys, 29(6):
89–156, December 1974. ISSN 0036-0279, 1468-4829. doi: 10.
1070/RM1974v029n06ABEH001303. URL https://doi.org/10.1070/
RM1974v029n06ABEH001303.