Open Questions in Multidimensional Multilevel Network Science

Abstract

Network science has made great progress in the study of binary relationships between pairs of elements. Although it has been known for decades that n-ary are ubiquitous in complex systems, progress in this area has been much slower. A condensed account is given of the family of network structures which includes graphs, networks, multilevel networks and multiplex networks for binary relations, and hypergraphs, simplices complexes and hypernetworks for n-ary relations. These structures are naturally integrated in a generalising framework. This family of network structures supports a new theory of multilevel systems where structures at one level become vertices at higher levels through part-whole aggregation interleaved with taxonomic aggregation. Although the structures presented are necessary to understand the dynamics of complex multilevel systems, there are many open questions. These are presented for consideration by the network community.

1 Introduction

Network science has made great progress in the study of binary relationships between pairs of elements. It is now becoming more widely accepted that there is a need to embrace n-ary relations in network science [17]. This paper presents a condensed account of a family of structures able to represent n-ary relations, and the algebraic theory of multilevel systems they support. Although multidimensional network structures are necessary to understand the dynamics of complex multilevel systems, there are many open questions. These are set out in the concluding section for consideration by the network science community.

It will be assumed that the reader is familiar with graphs and networks. Multilayer and multiplex networks provide a formalism for the analysis of networks defined by many different relations [11]. A comprehensive account of multilayer and multiplex networks is given by Boccaletti et al. in [10].

A weakness of conventional network theory is that the notation 〈v, v′〉 does not discriminate between the defining relations. To do this an extra symbol is required. For example, let V represents a set of people, R ₁ the relation ‘is line managed by’ and R ₂ the relation ‘plays golf with’. Then v and v′ may satisfy both relations. Let the notation 〈v, v′; R ₁〉 means v′ is the boss of v. This is different to 〈v, v′; R ₂〉 meaning that v plays golf with v′. This notation has the desirable feature that it naturally allows the definition of algebraic operations on the relations such as 〈v, v′; R ₁ ∧ R ₂〉 which combines the relations R ₁ and R ₂ to form composite relations such as (R ₁ ∧ R ₂) meaning ‘plays golf with the boss’.

2 Hypergraphs and the Galois Lattice

There are many of instances n-ary relations between more than two vertices. For example, consider four people playing bridge. This is a 4-ary relation. n things are related by an n-ary relation if it ceases to hold on removing any them. For example, if one person leaves the bridge game, the game no longer continues normally. The structures at the top of Fig. 1 generalise the structures at the bottom by allowing relations between any number of vertices.

Fig. 1

The natural family of network structures embraces n-ary relations

The French mathematician Claude Berge made an early attempt to generalise relational structure to many vertices through his definition of hypergraphs developed in the 1960s.

Let X = { x ₁, x ₂, …, x _n } be a finite set. A hypergraph on X is a family H = (E ₁, E ₂, …, E _m ) of subsets of X such that

• (1) E _i ≠ ∅ (i = 1, 2, …, m)

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

The elements x ₁, x ₂, …, x _m are called vertices and the sets E ₁, E ₂, …, E _m are the edges of the hypergraph [8, 9].

Let R be a relation between sets A and B. Let a R b mean that a is R-related to b where a ∈ A and b ∈ B. Let R(a) be the set of all b ∈ B that are R-related to a, R(a) = { b | a R b}. Then H _A (B, R) = { R(a) | for all a ∈ A} is a hypergraph. Similarly, let R(b) = { a | a R b}. Then H _B (A, R) = { R(b) | for all b ∈ B} is a also hypergraph.

Given the hypergraph H _A (B, R), let $\mathcal{H}_{A}(B,R)$ be all the sets in H _A (B, R) together with all their intersections. Let $\mathcal{H}_{A}(B,R)$ be called a Galois hypergraph. Similarly, let $\mathcal{H}_{B}(A,R)$ be all the sets in H _B (A, R) together with all their intersections. Then $\mathcal{H}_{A}(B,R)$ and $\mathcal{H}_{B}(A,R)$ are dual Galois hypergraphs.

Proposition.

The sets in the dual Galois hypergraphs $\mathcal{H}_{A}(B,R)$ and $\mathcal{H}_{B}(A,R)$ are in one-to-one correspondence. This is called the Galois connection between the dual hypergraphs.

A proof of this proposition can be found in [18]. The intuition behind the proposition is that there are paired maximal subsets called Galois pairs, A′ ↔ B′ where every member of A′ ⊆ A is R-related to every member of B′ ⊆ B.

Proposition.

There is an order relation on the set of Galois pairs with an associated Galois Lattice

Let A′ ↔ B′ and A″ ↔ B″ be Galois pairs. Then A′ ⊆ A″ if and only if B′ ⊇ B″. Let $\lesssim$ be defined as A′ ↔ B′ $\lesssim$ A″ ↔ B″ if A′ ⊆ A″. Then $\lesssim$ is an order relation with an associated lattice structure. This is called the Galois Lattice for the relation R between A and B. More details of the Galois connection and Galois Lattice can be found in [13, 14, 16, 18].

3 Simplicial Complexes and Q-Analysis

Hypergraphs have the great advantage that they are simple set-theoretic structures and this makes it easy to prove the existence of the Galois connection and Galois Lattice. However set theory is too weak for most applications because the elements are not ordered. For example, {R, E, P, A, I, R} = {R, A, P, I, E, R} so the words ‘repair’ and ‘rapier’ cannot be discriminated by the sets of their letters—the order of the letters is also required.

At the same time that Berge was developing his theory of hypergraphs, the British mathematician Ron Atkin was developing his theory of Q-analysis based on simplicial complexes and algebraic topology [1–6].

Let V be a set of elements called vertices. An abstract p -dimensional simplex 〈x ₀, x ₁, …, x _p 〉 is an ordered set of p + 1 vertices. A simplex 〈x ₀ ^′, x ₁ ^′, …, x _q ^′〉 is a q-dimensional face of the simplex 〈x ₀, x ₁, …, x _p 〉 iff {x ₀ ^′, x ₁ ^′, …, x _q ^′} ⊆ { x ₀, x ₁, …, x _p }. A set of simplices is called a simplicial family. A set of simplices with all its faces is called a simplicial complex.

In algebraic topology it is common to use the symbol σ to represent simplices, and this convention will be used here. Simplices have a geometric realisation as p-dimensional polyhedra, as shown in Fig. 2.

Fig. 2

Simplices can represent relations between two or more things. (a ) Line 1-dimensional. (b ) Triangle 2-dimensional. (c ) Tetrahedron 3-dimensional. (d ) 5-hedron 4-dimensional

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 σ and σ′ are 1-near in Fig. 3a because they share a 1-dimensional face. In Fig. 3b σ ₁ and σ ₄ are 1-connected, since σ ₁ is 1-near σ ₂, σ ₂ is 1-near σ ₃, and σ ₃ is 1-near σ ₄.

Fig. 3

q-connected polyhedra. (a ) σ and σ′ are 1-near. (b ) σ ₁ and σ ₄ are 1-connected

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].

4 Backcloth, Traffic and Multidimensional Percolation

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 [1, 12].

Networks are excellent for representing and calculating the dynamics of flows, including electricity, fluids, vehicles 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 to percolation in networks [15, 16].

5 Hypernetworks

Although simplicial complex are a step forward in representing n-ary relations they too have their limitations, as illustrated in Fig. 4. Here the lines ℓ ₁, …, ℓ ₁₆ are arranged in a circle by the relation R ₁. The resulting structure 〈ℓ ₁, …, ℓ ₁₆; R ₁〉 has the emergent property that most people see a white disk at the centre of the lines, the so-called sun illusion. Figure 4b shows the same set of lines assembled under a different relation, R ₂. 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 〈ℓ ₁, …, ℓ ₁₆〉 cannot discriminate these very different cases.

Fig. 4

The lines ℓ ₁, …, ℓ ₁₆ organised by two different relations, R ₁ and R ₂. (a ) The sun illusion σ ₁ = 〈ℓ ₁, …, ℓ ₁₆; R ₁〉. (b ) The rectangle illusion σ ₂ = 〈ℓ ₁, …, ℓ ₁₆; R ₂〉

In order to do this another symbol is necessary to represent the relation. We write R ₁: 〈ℓ ₁, …, ℓ ₁₆〉 → 〈ℓ ₁, …, ℓ ₁₆; R ₁〉 and R ₂: 〈ℓ ₁, …, ℓ ₁₆〉 → 〈ℓ ₁, …, ℓ ₁₆; R ₂〉. Let σ ₁ represent the sun configuration and σ ₂ represent the rectangle configuration. Then σ ₁ and σ ₂ are examples of relational simplices, or hypersimplices. Now the notation enables σ ₁ to be discriminated from σ ₂, since σ ₁ ≠ σ ₂.

As another example, propanol assembles three carbon atoms with eight hydrogen atoms and one oxygen atom, written as C₃H₈O or C₃H₇OH. Figure 5 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₃H₈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

Fig. 5

Chemical isomers as relational simplices. (a ) n-propyl alcohol. (b ) Isopropyl alcohol. (c ) Methyl-ethyl-ether

• 〈 C, C, C, H, H, H, H, H, H, H, H, O ; R  _{n−propyl alcohol}〉      ≠

• 〈 C, C, C, H, H, H, H, H, H, H, H, O ; R _{isopropyl alcohol}〉      ≠

• 〈 C, C, C, H, H, H, H, H, H, H, H, O ; R _{methyl-ethyl-ether}〉

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. Hypersimplices can act as backcloth structure carrying a traffic of numbers on their vertices and on their faces.

6 The Vertex Removal Test for 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 〈rider, bicycle; R _riding〉. Remove either the man or the bicycle and what is left ceases to be a cyclist. Remove any vertex from 〈gin, tonic, ice, lemon; R _mixed〉 and it ceases to be the perfect gin and tonic (Fig. 6). 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. 6

Remove a vertex and the simplex ceases to exist. (a ) Remove a vertex and the cyclist simplex ceases to exist. (b ) Remove a vertex and the perfect gin and tonic ceases to exist

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

The fundamental part-whole diagram of multilevel aggregation

Part-whole aggregations are interleaved with taxonomic aggregations, as shown in Fig. 8. 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 aggregations 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. 8

Part-whole and taxonomic aggregation

8 The Multilevel Fragment-Recombine Operator

When dealing with multilevel systems it would be useful to have a single symbol to represent the very complicated multilevel cone structures illustrated in Fig. 9a. One possibility is to enclose them by triangle. This representation allows a subsystem to be represented by a triangle within a triangle as shown in Fig. 9b. Since the intersection of two triangles is also a triangle, this representation is convenient to denote the intersection of two multilevel systems, as shown in Fig. 9c.

Fig. 9

Multilevel operations on multilevel triangles. (a ) A multilevel triangle. (b ) Subsystem. (c ) Intersection

This representation suggests an exciting new possibility for multilevel complex systems. To be more concrete consider a narrative as a multilevel structure made of words, phrases, paragraphs and complete stories. Narratives are very important in policy and very important for the development of a theory of complex social systems.

For example, Europe is grappling with many narratives associated with migrants, and these narratives work at the level of the plight of individual people, through to more aggregate structures such as people traffickers’ boats to more aggregate structures such as countries and their policies. The narratives include political and economic aspects at many level of aggregation. Let this multilevel narrative be called N _Migration as shown top-left in Fig. 10. Let △ _Mi be the state of the narrative at time t _i .

Fig. 10

Multilevel fragment-recombine operators

Alongside the strong migration narrative in the UK there are others, e.g. the unemployment narrative, N _Unemployment, shown bottom-left in Fig. 10.

Both these narratives evolve in time, with information and invention being added or lost as the meanings of the narrative evolve. Figure 10 shows these narratives evolving independently until they crash into each other at time t ₅. The combinatorial dynamics of such a crash is not well understood, but it involves parts of the two multilevel systems interacting and each of the multilevel narratives fragmenting before they recombine to form new composite narratives, e.g. $N_{\mbox{migrants$\_$are$\_$taking$\_$our$\_$jobs}}$. Let the fragment-recombine operator of multilevel systems, ⋆, be defined as

where and are multilevel systems before they crash and is the multilevel system after. There are many open questions associated with this.

9 Open Questions in Multidimensional Network Science

Open Question 1

How are the dynamics of systems constrained by the q-connectivity structure of the backcloth? What are the mechanisms for q-percolation?

This question concerns the dynamics of system traffic, i.e. the patterns of numbers across the vertices and hypersimplices. The numbers on one hypersimplex can directly influence the numbers on another through their shared face. For example, consider two routes through a road traffic system. The routes can be considered to be structured sets of road segments, R _i  = 〈s ₀, s ₁, …, s _n ; R _route〉. The more segments that two routes share, the more their traffic will interact, with the vehicles slowing each down. Thus the more highly connected the routes, the greater the impact they have on each other.

Open Question 2

What are the processes of hypersimplex formation and loss?

This question is a generalised version of the question as to how links form in networks. One answer to this for networks is the Barabási’s preferential attachment mechanism [7]. A necessary condition for a hypersimplex to form is that all its vertices are present. For the vertices to become n-ary related may require a process in time involving a sequence of other p-ary relations. For example, for n people to form a well-functioning team involves a process in which they learn to work together. In the case the process may change the vertices. For example, some members of the team may be trained in order to acquire necessary skills.

Open Question 3

What is the nature of multilevel backcloth-traffic dynamics?

This question combines the first and second questions in the context of multi-level interactions. Bottom-up the traffic or patterns of numbers aggregate over the multilevel backcloth. In general more aggregate numbers get larger and more predictable in time. Furthermore, aggregation bottom-up tends to convert lower level structures into numbers. For example, company taxation results in a time series of numbers at the national level, where the details of companies and their activities are not explicit. Similarly there are issues of how numbers are distributed top-down over multilevel systems. The challenge is to understand how bottom-up and top-down dynamics interact across multilevel systems.

Another aspect of this question concerns the formation of multilevel structure, and the processes by which top-down decisions enable or require the creation of lower level structures. For example a company may decide to invest in a new factory. This requires information traffic to flow across higher management level resulting in top-down flows of resources to create the lower level structure. Generally the rationale for this is that the new lower structure will create new resources that will flow up the structure to enhance the company’s profits.

When modelling systems it is always the case that some things are included and some are left out. This includes deciding that some level is the lowest necessary to model a multilevel system. The dynamics of a multilevel system are said to be information complete at Level N if modelling their behaviour requires no information from Level N-k for k ≥ 1. Thus Open Question 3 includes how to decide the level at which a system is information complete. For example, until recently, economic systems were modelled at the meso level of the ‘representative agent’. Today it is increasing realised that many social system are information-complete only at the level of the individual person. For example, the behaviour of road traffic system emerges from the decisions of individual driver agents and increasingly they are modelled at this level by agent-based simulations using the disaggregate data of synthetic micro populations.

Open Question 4

What new algebraic operations can be defined between hypersimplices?

The generality of this question is given by the expression

where . The challenge is to determine the nature of the operators and .

This question has its origins in the simple question “what is the intersection of two hypersimplices?” An obvious but unsatisfactory answer is given by

$$\displaystyle{\langle x_{1},x_{2},\ldots,x_{n};R_{1}\rangle \cap \langle y_{1},y_{2},\ldots,y_{p'};R_{2}\rangle \stackrel{?}{=}\langle z_{1},z_{2},\ldots,z_{q};R_{1} \wedge R_{2}\rangle,}$$

where {z ₁, z ₂, …, z _q } = { x ₁, x ₂, …, x _p } ∩{ y ₁, y ₂, …, y _p′}.

The problem here is that R ₁ is defined on all the vertices x ₁, x ₂, …, x _p and R ₂ is defined on all the vertices y ₁, y ₂, …, y _p′ but, as written, their conjunction is defined on {x ₁, x ₂, …, x _p } ∩{ y ₁, y ₂, …, y _p′}. Another possibility is to write

$$\displaystyle{\langle x_{1},x_{2},\ldots,x_{n};R_{1}\rangle \cap \langle y_{1},y_{2},\ldots,y_{p'};R_{2}\rangle \stackrel{?}{=}\langle z_{1},z_{2},\ldots,z_{q};R_{1} \wedge R_{2}\rangle,}$$

where {z ₁, z ₂, …, z _q } = { x ₁, x ₂, …, x _p } ∪{ y ₁, y ₂, …, y _p′}.

To investigate this question further consider two multiplex network edges, 〈x ₁, x ₂; R〉 and 〈y ₁, y ₂; R′〉

Of these, the first and second are not problematic, the former being an empty intersection and the latter being the conjunction of the relations. But how should the and operations be defined?

Suppose . This means that is defined on a single vertex. It is perhaps more promising to suppose that ?

Open Question 5

What is the nature of the multilevel fragment-recombine operator ⋆: (△₁, △₂, …) → △₁ ⋆ △₂ ⋆ … for multilevel systems.

It may be easiest to answer by thinking ahead to how the ⋆ operation could be implemented. In practice it is assumed that the multilevel systems are explicitly represented in multilevel data structures based on the algebra sketched in this paper. Then the question becomes how hypersimplices at compatible levels behave when they crash into each other. Presumably there are various and operations to deconstruct and recombine the hypersimplices. The nature of these is a major challenge for multilevel multidimensional network science.