HyperG-package {HyperG}

Hypergraphs in R

Description

Implements various tools for storing and analyzing hypergraphs. Handles basic undirected, unweighted hypergraphs, and various ways of creating hypergraphs from a number of representations, and converting between graphs and hypergraphs.

Details

A hypergraph is implemented as a list containing (for now) a single element, M, corresponding to the incidence matrix. It is an S3 object with class hypergraph and a plot method, summary and print methods. The package uses a sparse representation (from the Matrix package), so in principle it should allow for very large hypergraphs, although to date only relatively small hypergraphs have been investigated.

Index of help topics:

H2                      Two sections of a hypergraph.
HyperG-package          Hypergraphs in R
as.bipartite            Hypergraph as a bipartite graph.
as.hypergraph           Convert between hypergraphs and graphs.
ase                     Adjacency spectral embedding.
clique_hypergraph       Clique Hypergraph
cluster_spectral        Spectral Graph Clustering
dual_hypergraph         Dual hypergraph.
epsilon_hypergraph      Epsilon-Ball Hypergraph
equivalent.hypergraphs
                        Equivalent Hypergraphs
has.helly               Helly Property
has.isolates            Test for loops, isolates and empty hyper-edges.
hdegree                 Degrees of a hypergraph.
horder                  The number of vertices, edges and statistics of
                        the hypergraph.
hrank                   Rank of a hypergraph.
hypergraph.add.edges    Add edges or vertices to a hypergraph.
hypergraph.complement   The complement of a hypergraph.
hypergraph.delete.edges
                        Delete edges or vertices of a hypergraph.
hypergraph.entropy      Hypergraph Entropy
hypergraph.is.connected
                        Is the hypergraph connected?
hypergraph.union        Unions and intersections of hypergraphs.
hypergraph_as_adjacency_matrix
                        Adjacency Matrix of a Hypergraph.
hypergraph_as_edgelist
                        Convert between hypergraphs and graphs.
hypergraph_from_incidence_matrix
                        Hypergraph construction.
hypergraph_from_literal
                        Hypergraph from literal.
hypergraph_laplacian_matrix
                        Laplacian Matrix
incidence_matrix        Graph Incidence Matrix.
induced_hypergraph      Induced hypergraph.
is.conformal            Conformal Hypergraphs
is.empty.hypergraph     Is the hypergraph empty.
is.hypergraph           Is an object a hypergraph?
is.hypertree            Test for hypertree.
is.simple               Is a hypergraph simple/linear?
is.star                 Is a hypergraph a star?
is.tree                 Test if a graph is a tree or a forest.
kCores                  K-Cores
knn_hypergraph          K-Nearest Neighbor Hypergraph.
line.graph              Line Graph
make_empty_hypergraph   Empty hypergraph.
pendant                 Pendant Vertices
plot.hypergraph         Plot a hypergraph.
print.hypergraph        Print a hypergraph to the console.
reduce.hypergraph       Remove redundant hyperedges and isolated
                        vertices.
remove.redundant.vertices
                        Remove redundant vertices.
reorder_vertices        Reorder the vertices of a hypergraph.
sample_geom_hypergraph
                        Construct a hypergraph from a random collection
                        of points.
sample_gnp_hypergraph   Erdos-Renyi hypergraphs.
sample_k_uniform_hypergraph
                        Random k-uniform and k-regular hypergraphs.
sample_sbm_hypergraph   Sample from a stochastic block model.
subtree.hypergraph      Subtree Hypergraph.
summary.hypergraph      Print a summary of the hypergraph to the
                        console.

Introduction

A graph is a set of vertices, V, and a set of egdes, E, each of which contains two vertices (or a single vertex, if self-loops are allowed). A hypergraph is a generalization of this, in which more than two vertices can be in a single hyper-edge. Multi-graphs are graphs in which E is not a set, but rather allows for duplicate edges. Hypergraphs are allowed to have duplicate hyper-edges.

This package is a simple implementation of hypergraphs built around the incidence matrix – a binary matrix in which the rows correspond to the hyper-edges, the columns to vertices, and a 1 in position (i,j) indicates that the vertex j is in the ith hyper-edge. There is currently no support for directed or weighted hypergraphs.

Various methods of manipulating hypergraphs, such as adding and removing edges and vertices are implemented, and for small hypergraphs the igraph package plot routine is used to plot the hypergraph and its hyper-edges. For hypergraphs with more than a few dozen vertices, it is recommended that the plot function be called with mark.groups=NULL. See igraph.plotting for more information.

There are utilities in this package for removing loops, duplicate hyper-edges, empty hyper-edges, and isolated vertices (ones that are not contained in any hyper-edge). Also, there is a function, reduce.hypergraph, which reduces the hypergraph down to its largest hyper-edges – that is, it removes hyper-edges that are subsets of other hyper-edges. It also has other ways to reduce the hypergraph, see the corresponding manual page.

There are also utilities for extracting information from the hypergraph. For example, simple statistics such as the number of vertices, hyper-edges, degrees of vertices, number of nodes per hyper-edge. Also global properties such as whether it is connected, if it has the Helly property or is conformal (see the manual pages for has.helly and is.conformal for more information on these topics).

Note

Some effort has been taken to avoid masking or redefining functions from the igraph package. While this results in awkward function names ("hypergraph" nearly everywhere) it does reduce the chances of hard-to-diagnose errors. I am considering adding aliases that replace "hypergraph" with "hg" or some such, but I'm not sure this is helpful. The two functions that are masked, is.simple and line.graph, first check whether their argument is an igraph graph, and if so calls the corresponding igraph function.

Author(s)

David J. Marchette

Maintainer: David J. Marchette <[e-mail]>

References

Bretto, Alain, Hypergraph theory, An introduction. Springer, 2013.

Voloshin, Vitaly I. Introduction to graph and hypergraph theory. Nova Science Publ., 2009.

See Also

igraph.

Examples

h <- hypergraph_from_edgelist(list(1:2,2:5,3:7,c(1,3,5,7,9)))
hsize(h)
## 4
horder(h)
## 9