Embracing n-ary Relations in Network Science

Abstract

Most network scientists restrict their attention to relations between pairs of things, even though most complex systems have structures and dynamics determined by n-ary relation where n is greater than two. Various examples are given to illustrate this. The basic mathematical structures allowing more than two vertices have existed for more than half a century, including hypergraphs and simplicial complexes. To these can be added hypernetworks which, like multiplex networks, allow many relations to be defined on the vertices. Furthermore, hypersimplices provide an essential formalism for representing multilevel part-whole and taxonomic structures for integrating the dynamics of systems between levels. Graphs, hypergraphs, networks, simplicial complex, multiplex network and hypernetworks form a coherent whole from which, for any particular application, the scientist can select the most suitable.

Supported by the European Dynamics of Multi-Level Complex Systems (DyM-CS) FP7 FET programme, http://cordis.europa.eu/fp7/ict/fet-proactive/dymcs_en.html.

1 Introduction

Given the success of graph and network theory since computers became available to scientists in the nineteen sixties, it is remarkable that the majority of the research done in network science has remained focussed on edges representing binary relations between two vertices. If all relations were binary relations this would be understandable. However, the structure and dynamics of many systems depend on relations between many things.

For example, the participants in a dinner party do not just interact in pairs. Nor do the member of a team or a committee. The members of a choir are not singing pairwise with the others. A great part of the dynamics of social and biological systems involves interactions between many individuals and many things. Surely a science of multidimensional universe should not be constrained to representing it solely through one dimensional objects.

This is not to criticise networks in any way. As will become clear, they are part of a wider story that extends to hypergraphs, simplicial complexes and hypernetworks. It begins with graphs.

In the literature the terminology for graph theory varies considerably. Here, let a graph, G, be defined to be a set, V with elements called vertices and a set, E, of pairs of vertices called edges. Write $G = (V, E)$. Let a and b be vertices and let $\{a,b\}$ be an edge Graphs are usually drawn with dots such as a and b representing vertices and, for example, a line joint a and b to represent the edge $\{a,b\}$. Usually the edges in graphs represent binary relations between the vertices. To go beyond binary relation something else is required.

2 Hypergraphs

Hypergraphs represent an early attempt to allow graph edges to have more than two vertices [7]. Berge writes ‘The idea of looking at a family of sets from this standpoint took shape around 1960. In regarding each set as a “generalised edge” and in calling the family itself a “hypergraph”, the initial idea was to try to extend certain classical results of Graph Theory. ... Next it was noticed that this generalisation often led to simplification; moreover, one single statement ... could unify several theorems on graphs” [8]. In his 1969 paper [7] he gives the following definition. ‘Let $X = \{x_1, x_2, ..., x_n\}$ be a finite set. A hypergraph on X is a family $H= (E_1, E_2, ..., E_m)$ of subsets of X such that

• (1) $E_i \ne \emptyset$         $(i = 1, 2, ..., m)$

• (2) $\bigcup _{i=1}^{m} = X$.

The elements $x_1, x_2, ..., x_m$ are called vertices and the sets $E_1, E_2, ..., E_m$ are the edges of the hypergraph.’ Berge gives the example shown in Fig. 1 where the relationship between the vertices and edges is given as an incidence matrix.

Fig. 1.

The Berge hypergraph

Berge’s method of drawing hypergraphs is a hybrid between graph-theoretic links and loops, and hypergraph-theoretic sets. Figure 2(a) shows the Berge hypergraph drawn entirely as sets. Here the edges corresponding to pairs of vertices are shown as sets, namely $\{ x_1, x_2\}$ and $\{x_5, x_8\}$, and the loop from $x_7$ to itself is draw as a singleton set $\{x_7\}$ which is the edge $E_6$.

Fig. 2.

The dual Berge hypergraphs

Figure 2(a) shows the hypergraph with the columns of the incidence matrix as the edges. The dual hypergraph has sets of edges corresponding to the vertices as shown in Fig. 2(c). Looking along the rows, each vertex is related to a set of edges, for example $x_7$ is related to the set of edges $\{ E_3, E_4, E_6\}$ This is a ‘dual’ edge in the dual hypergraph, as shown in Fig. 2(b).

The Galois Lattice. Figure 3 shows a set of arches, $A = \{a_1, a_2, a_3, a_4, a_5, a_6, a_7\}$ with each arch made from a subset of the blocks $B = \{ b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8, b_9,$ $b_{10}, b_{11}, b_{12}\}$. Let arch $a_i$ be R-related to block $b_j$ if it contains that block. This bipartite relation can be represented by the incidence matrix shown in Fig. 4. The entry in the $i^\mathrm{{th}}$ row and the $j^\mathrm{{th}}$ column of the matrix is one if $a_i$ is related to $b_j$, and it zero otherwise. Let $E(a_i)$ be the set of blocks related to arch $a_i$. Then:

Fig. 3.

Arches related to the blocks used to construct them

Fig. 4.

Maximal rectangles in the arch-block structure

Apart from these ‘first order’ edges it is interesting to generate ‘higher order’ edges from all their intersections:

Let the set of first order and higher order edges be called the augmented hypergraph for the relation in Fig. 5. The edges of the augmented dual hypergraph can be found in a similar way:

Bringing together the sets in the augmented hypergraphs shows that they can be put is one-to-one correspondence. This is known as the Galois connection and the Galois pairs can be listed as:

In a Galois pair $A' \leftrightarrow B'$ every a in $A'$ is R-related to every b in $B'$. Therefore the rows and columns of the matrix can be rearranged so that all the $a_i$ in $A'$ are contiguous and all the $b_j$ in $B'$ are contiguous, with the corresponding rectangle of entries in the matrix all ones. For example, let $A' = \{a_1, a_2, a_3\}$ and $B' = \{b_3, b_4\}$. Then as shown in Fig. 4 the corresponding rectangle is filled with ones because each of $a_1$, $a_2$ and $a_3$ is related to $b_3$ and $b_4$.

The rectangle corresponding to $A' = \{a_1, a_2, a_3\} \leftrightarrow B' = \{b_3, b_4\}$ is maximal. Two other maximal rectangles are shown in Fig. 4 corresponding to the Galois pairs $\{a_3, a_4\} \leftrightarrow \{b_4, b_5\}$ and $\{ a_5, a_6, a_7\} \leftrightarrow \{b_7, b_8, b_9\}$. The maximal rectangles $A' \leftrightarrow B'$ where $A'$ has just one element or $B'$ has just one element are not shown.

Fig. 5.

The Galois Lattice for the arch-block relation of Fig. 4

The Galois pairs can be arranged as a Galois lattice [13] with upwards set inclusion on the left and downward set inclusion on the right (Fig. 5).

Galois pairs are particularly interesting, since they are sites of relatively high connectivity. However for relations between large sets there can be a combinatorial explosion of Galois pairs making computation difficult. Nonetheless Galois pairs play an important role in hypernetwork theory [17].

Hypergraphs are an excellent first step towards mathematical structure able to represent n-ary relations. However they are essentially set-theoretic and have no orientation. Simplicial complexes provide this.

3 Simplicial Complexes

In the nineteen fifties C.H. Dowker published the paper The homology groups of relations [11] which showed that relations between n things could be represented by multidimensional polyhedra with n vertices, such as those shown in Fig. 6. This idea lay dormant for a quarter of a century until in the nineteen sixties R.H. Atkin introduced the revolutionary idea that social relations could be represented by polyhedra. For example, a business deal between three people can be represented by a triangle, written as $\langle a, b, c \rangle$, the relation of four people playing music together can be represented by a tetrahedron, $\langle a, b, c, d\rangle$, and the relationship between five people working together as a team can be represented by a 5-hedron, $\langle a, b, c, d, e\rangle$. This idea is entirely compatible with network theory since, for example, a relationship between two people having a conversation can be represented by a polyhedron with two vertices, namely a line or an edge, $\langle a, b\rangle$. These ideas first appeared in the article A mathematical approach towards a social science, published in the Essex Review in 1968 [1].

Fig. 6.

Simplices can represent relations between two or more things

Polyhedra are the geometric realisation of more abstract objects called simplices. Let V be a set of vertices. An abstract p-simplex is determined by a set of $p+1$ vertices, written as $\langle v_0, v_1, . . . , v_p \rangle$. Simplices are often represented by the symbol $\sigma$.

A simplex $\sigma$ is a face of a simplex $\sigma '$, $\sigma \lesssim \sigma '$, if every vertex of $\sigma$ is also a vertex of $\sigma '$. For example the 2-dimensional simplex $\langle x_1, x_2, x_3 \rangle$ is a triangular face of the tetrahedron representing the 3-dimensional simplex $\langle x_1, x_2, x_3, x_4 \rangle$. A set of simplices with all its faces is called a simplicial complex.

Algebraic Topology. In algebraic topology simplices provide an algebraic way of calculating the topological invariants of spaces. The ideas will be briefly and informally sketched here. Figure 7 shows a complex made up of three triangles with all their faces (lines and vertices). This complex has the topological feature of a hole surrounded by the triangles.

Fig. 7.

A hole in a simplicial complex.

A q-dimension chain is an expression of the form $\Sigma _{i \in I} \, n \,\sigma _i$ where n is a number. The boundary operator, $\partial$, maps a simplex to its boundary according to the rule $\partial \langle x_0, ... , x_p \rangle = \Sigma _{i = 0}^{p} (-1)^{i} \langle x_0, ... , \hat{x_i}, ... , x_p \rangle$, where $\hat{x_i}$ means omit the $i^\mathrm{{th}}$ entry along, counting from zero. For example, $\partial \langle x_1, x_2, x_3 \rangle = \langle x_2, x_3 \rangle - \langle x_1, x_3 \rangle + \langle x_1, x_2 \rangle$. This chain of 1-simplices is called a cycle.

In algebraic topology switching a pair of vertices changes the sign (and orientation) of a simplex, so $- \langle x_1, x_3 \rangle = \langle x_3, x_1 \rangle .$ Thus the cycle can be written as $\langle x_2, x_3 \rangle + \langle x_3, x_1 \rangle + \langle x_1, x_2 \rangle$. In this case it is a bounding cycle because it is a closed loop of 1-simplices that goes round the shaded 2-dimensional triangle. It starts at $\langle x_2 \rangle$ and goes to $\langle x_3 \rangle$ along the oriented edge $\langle x_2, x_3 \rangle$, goes to $x_1$ along the oriented edge $\langle x_3, x_1 \rangle$ and back to close the loop at $x_2$ along the oriented edge $\langle x_3, x_2 \rangle$.

The boundary operator is nilpotent, i.e. when applied twice it gives zero. For example, $\partial ^2 \langle x_1, x_2, x_3 \rangle = \partial \langle x_2, x_3 \rangle - \partial \langle x_1, x_3 \rangle + \partial \langle x_1, x_2 \rangle$ = $\langle x_3 \rangle - \langle x_2\rangle - \langle x_3 \rangle + \langle x_1 \rangle + \langle x_2 \rangle - \langle x_1 \rangle = 0$.

Any chain c with $\partial c = 0$ is defined to be a cycle. Apart from bounding cycles as seen above, there can be non-bounding cycles. For example consider $c = \langle x_2, x_5 \rangle + \langle x_5, x_3 \rangle + \langle x_3, x_2 \rangle$. Then $\partial c = \langle x_5 \rangle - \langle x_2 \rangle + \langle x_3 \rangle - \langle x_5 \rangle + \langle x_2 \rangle - \langle x_3 \rangle = 0$ and c is a cycle. However there is no 2-dimensional chain $c'$ with $\partial c' = c$ so c is a non-bounding cycle. In general, non-bounding cycles correspond to holes, in this case exactly the hole bounded by c.

Atkin’s Q-analysis. In the early seventies Atkin and coworkers investigated the topological properties of relations in the context of town planning. Atkin suggested a new kind of connectivity based on the shared faces of social polyhedra [3–5].

Fig. 8.

q-connected polyhedra

Two simplices are q-near if they share a q-dimensional face. Two simplices are q-connected if there is a chain of pairwise q-near simplices between them. The tetrahedra $\sigma$ and $\sigma '$ are 1-near in Fig. 8(a) because they share an edge, or 1-dimensional face. In Fig. 8(b) the tetrahedra $\sigma _1$ and $\sigma _4$ are 1-connected, since $\sigma _1$ is 1-near $\sigma _2$, $\sigma _2$ is 1-near $\sigma _3$, and $\sigma _3$ is 1-near $\sigma _4$. A Q-analysis determines classes of q-connected components, sets of simplices that are all q-connected. An early application of Q-analysis studied land uses in Colchester [6].

Backcloth and Traffic. The vertices and edges of networks often have numbers associated with them. For example in a social network the vertices may be associated with the amount of money a person has and the edges may be associated with how much money passes between pairs of people. In electrical networks the vertices have voltage associated with them and the edges have current. Although the network’s voltages and currents may change, the network itself does not. Similarly in a road network the daily traffic flows may vary but usually the network infrastructure does not. The same holds for simplicial complexes when there are patterns of numbers across the vertices and the simplices. The numbers may change when the underlying simplicial complex does not.

Atkin suggested that the relatively unchanging network or simplicial complex structure be called a backcloth and that the numbers be called the traffic of activity on the backcloth. As an example, the airline network acts as a backcloth to the traffic of airline passengers. The term backcloth comes from the scenery painted on large canvas sheets used in theatres as a static backdrop behind the actors.

Atkin first used simplicial complexes to characterise a wide variety of phenomena in physics by his Cocycle Law that the space-time backcloth supporting many physical phenomena has no holes. His conceptual leap “from cohomology in physics to q-connectivity in social science” was published in 1972 [2].

Flows and ${\varvec{q}}$ -transmission as Multidimensional Percolation. Networks are excellent for representing and calculating the dynamics of flows, from electricity to oil to cars and sentiments. Simplicial complexes are multidimensional networks and they too can carry equally diverse traffic flows. Generally the q-connectivity of the underlying backcloth constraints the dynamics of the flows. This has been called q-transmission and has been described as a multidimensional analogue analogue to percolation in networks [17].

Example: Road Accidents. A study of road accidents illustrates the combinatorial nature of simplices [17]. Drivers who had been involved in accidents were interviewed to find out the possible causes. The telephone interviews were unstructured with the interviewer eliciting the causes from the interviewees, e.g. interviewees would often would volunteer that they were going too fast for the conditions. Some typical examples of the 57 reported accident simplices are:

$\langle$mechanical failure, need to stop, lack anticipation, stress; $R_1\rangle$

$\langle$carelessness, unexpected manoeuvre; $R_8\rangle$

$\langle$change in road layout, poor signposting, bad visibility; $R_{16}\rangle$

$\langle$speed, lack of concentration; $R_{23}\rangle$

$\langle$inexperienced driver, car in wrong position; $R_{31}\rangle$

$\langle$poor visibility, lack of caution, road wet; $R_{23}\rangle$

$\langle$not paying attention, to near/too fast, brakes poor, unexpected manoeuvre; $R_{51}\rangle$

$\langle$narrow road, speed $R_{53}\rangle$

These combinations of causes were expressed in everyday language. The data was analysed according to the classes:

Like hypergraphs, simplicial complex also have Galois pairs:

Fig. 9.

Frequencies of occurrences of accident factors

Figure 9 gives a graphical summary of the Galois pairs and the numbers accidents associated with the simplices. The interviewees were asked to rate the importance of the factors on a five-point low-high scale. For example, $\sigma$(Accident-2) = $\langle$D1–Stress(5), D2–Careless(3), D13–Unfamiliar road(5), D15–Mistaken priority(5), R1–Difficult config(5), R2–Poor visibility(3), R3–Poor signposting(5)$\rangle$, and $\sigma$(Accident–2) = $\langle$D1–Stress(5), D2–Careless(4), D6–Alcohol(1), D7–Tired(5), D13–Unfamiliar road(3), D15–Speed(3) R2–Poor visibility(2)$\rangle$. Let $\mu (v_i)$ be the weighting given to accident factor $v_i$, $\mu (v_i)$. A value on the whole simplex, the fuzzy conjunction, can be defined as $\mu \sigma =$ min$\{ \mu (v_i) \, | \, v_i \lesssim \sigma \}$. Then for a fuzzy value of 3, $\sigma$(Accident-2) and $\sigma$(Accident-3) share the face $\langle$D1-Stress, D2-Careless, D13-Unfamiliar road$\rangle$, and they are 3-fuzzy 2-near.

4 Hypernetworks

Figure 10(a) shows the lines $\ell _1, ... , \ell _{16}$ arranged in a circle by the relation $R_1$. The resulting structure $\langle \ell _1, ... , \ell _{16}; R_1 \rangle$ has the emergent property that most people see a white disk at the centre of the lines, the so-called sun illusion. Figure 10(b) shows the same set of lines assembled under a different relation, $R_2$. Now there is no disk but a rectangle shape emerges. This example illustrates that the same ordered set of elements can be the subject of more than one relation, and that the simplex notation $\langle \ell _1, ... , \ell _{16} \rangle$ cannot discriminate these very different cases.

Fig. 10.

The lines $\ell _1, ... , \ell _{16}$ organised by two different relations, $R_1$ and $R_2$

In order to do this another symbol is necessary to represent the relation. We write $R_1: \langle \ell _1, ... , \ell _{16} \rangle \rightarrow \langle \ell _1, ... , \ell _{16} ; R_1 \rangle$ and $R_2: \langle \ell _1, ... , \ell _{16} \rangle \rightarrow \langle \ell _1, ... , \ell _{16} ; R_2 \rangle$. Let $\sigma _1$ represent the sun configuration and $\sigma _2$ represent the rectangle configuration. Then $\sigma _1$ and $\sigma _2$ are examples of relational simplices, or hypersimplices. Now the notation enables $\sigma _1$ to be discriminated from $\sigma _2$, since $\sigma _1 \ne \sigma _2$.

In general a hypernetwork is defined to be any collection of hypersimplices. This definition is deliberately undemanding, so that almost anything can be a hypersimplex, and any collection of hypersimplices can be a hypernetwork.

Fig. 11.

Chemical isomers as relational simplices

Example: Chemical Molecules. Chemical molecules illustrate the idea of hypersimplices. For example, propanol assembles three carbon atoms with eight hydrogen atoms and one oxygen atom, written as C$_3$H$_8$O or C$_3$H$_7$OH. Figure 11 shows the atoms of propanol arranged in a variety of ways. The first two show the isomers n-propyl alcohol and isopropyl alcohol. The oxygen atom is attached to an end carbon in the first isomer and to the centre carbon in the second, but the C-O-H hydroxyl group substructure is common to both. The rightmost isomer of C$_3$H$_8$O, methoxyethane, has the oxygen atom connected to two carbon atoms and there is no C-O-H substructure. This makes it an ether, methyl-ethyl-ether, rather than an alcohol. Thus the relational simplices of the isomers have the same vertices, but the assembly relations are different. n-propyl alcohol and isopropyl alcohol share the hydroxyl group substructure C-O-H and are similar, but methyl-ethyl-ether does not and has different properties. Thus

$\langle$ C, C, C, H, H, H, H, H, H, H, H, O ; $R\,_{n-\mathrm{{propyl alcohol}}} \rangle \;\;\;\;\; \ne$

]

$\langle$ C, C, C, H, H, H, H, H, H, H, H, O ; $R\,_\mathrm{{isopropyl alcohol}} \rangle \;\;\;\;\;\ne$

$\langle$ C, C, C, H, H, H, H, H, H, H, H, O ; $R\,_\mathrm{{methyl-ethyl-ether}} \rangle$

The Vertex Removal Test for ${\varvec{n}}$ -ary Relations. The essential feature of a polyhedron is that it ceases to exist if any of the vertices are removed. For example, consider a cyclist represented as the combination $\langle$rider, bicycle; $R_\mathrm{{riding}} \rangle$. Remove either the man or the bicycle and what is left ceases to be a cyclist. Removing a vertex is like sticking a pin in a balloon, causing the structure to collapse and whatever is left is not the whole simplex. Remove any vertex from $\langle$gin, tonic, ice, lemon; $R_\mathrm{{mixed}} \rangle$ and it ceases to be the perfect gin and tonic. Generalising edges to polyhedra allows a distinction to be made between the parts of things represented by vertices, and wholes represented by hypersimplices. Using this test it is easy to find many examples of n-ary relations, e.g. a path with n edges in a network forms a hypersimplex - remove an edge and the path ceases to exist; four bridge players form a hypersimplex - remove one and the game collapses; and a car and its wheels are 5-ary related - without any of them it won’t work.

Fig. 12.

Remove a vertex and the simplex ceases to exist.

5 Hypernetworks and Multilevel Structure

Hypersimplices enable the definition of multilevel part-whole structures, e.g. the four blocks assembled by the 4-ary relation R to form an arch in Fig. 13. Here the whole has the emergent property of a gap not possessed by any of its parts. If the parts exist in the system at an arbitrary Level N then the whole exists at a higher level, here shown as Level N+1. Thus assembly relations provide an immutable upwards arrow for the definition of multilevel structure.

Fig. 13.

The fundamental part-whole diagram of multilevel aggregation

Part-whole aggregations are interleaved with taxonomic aggregations, as shown in Fig. 14. The aggregation between Level N and Level N+1 combines graphical parts to form faces. The aggregation between Level N+1 and Level N+2 establishes classes of faces in a taxonomy. Such aggregations depend on the purpose of the taxonomy. For example, there is no class of ‘frowny’ faces because, for the purpose here, it is not required. Note that part-whole aggregation require all the parts. In contrast taxonomic aggregations require just one example to aggregate. For example, the round smiley face is sufficient for there to be a smiley face, irrespective of whether or not there is a square smiley face.

Fig. 14.

Part-whole and taxonomic aggregation

6 Embracing n-ary Relations in Network Science

Despite the mathematics literature on multi-vertex relational structure dating back at least to the 1950s, and despite the efforts of visionaries such as Berge and Atkin in the 1960s, today many scientists still shy away from relations between more than two things. It is all the more remarkable because graph theorists have known about this mathematics but not adopted it, e.g. in his classic book on graph theory, Harary [14] quotes Veblen’s 1922 book [19] as a source for his definition of simplicial complex but, frustratingly, notes in passing that a graph is a one-dimensional simplicial complex, even though Veblen explicitly considers two-dimensional simplicies in the second chapter of his book. In contrast, computer science recognises the importance of n-ary relations, e.g. Codd [9] uses them in his seminal paper on relational data structures, and the WC3 consortium defines their use in the semantic web [15].

Fig. 15.

The natural family of network structures embraces n-ary relations

It is unfortunate that network scientists should neglect n-ary relations since they are part of a natural family of network structures (Fig. 15). Assuming appropriate definitions, providing orientation makes a non-oriented graph into a network, and allowing pairs of vertices to support many relations makes multiplex networks. Vertically, allowing edges to have many vertices generalises graphs to hypergraphs, allowing oriented edges to have many vertices generalises networks to simplicial complexes, and allowing oriented edges supporting many relations to have many vertices generalises multiplex networks to hypernetworks. Horizontally, orienting the edges of hypergraphs creates simplicial families and complexes, and allowing a simplex to support many relations creates hypernetworks. Thus the diagram in Fig. 15 commutes and these structures form a natural family by adding structure from top left to bottom right.

Hopefully this paper will stimulate more interest in n-ary relations in network science:

• many systems involve n-ary relations – ignoring this misrepresents them

• n-ary relations are essential for representing part-whole structures and related dynamics in multilevel systems

• there is a rich and coherent mathematical theory for n-ary relations - with many remaining challenges and opportunities for the network community.