Run it: https://met4citizen.github.io/Hypergraph/

Hypergraph Rewriting System able to visualize both single-way and multiway evolutions in 3D.

The app uses 3d Force-Directed Graph for representing graph structures, ThreeJS/WebGL for 3D rendering and d3-force-3d for the force engine.

A hypergraph is a generalization of a regular graph. Whereas an edge typically connects only two nodes, a hyperedge can join any number of nodes. In a Hypergraph Rewriting System some initial hypergraph is transformed incrementally by making a series of updates that follow some abstract rewriting rule.

As an example, consider an abstract rewriting rule (x,x,y)(y,z,u)->(x,v,u)(y,v,z)(v,v,u). Wherever and whenever a subhypergraph having the form of the left-hand side pattern (x,x,y)(y,z,u) is found in the hypergraph, it is replaced with a new subhypergraph having the form of the right-hand side pattern (x,v,u)(y,v,z)(v,v,u) introducing a new node v.

Sometimes matches overlap. For example, when using the previous rule with the initial state (1,1,2)(2,2,3)(3,3,4) there are two overlapping matches (x=1,y=2,z=2,u=3) and (x=2,y=3,z=3,u=4) (critical pair). One way to resolve the conflict is to pick one of the two according to some ordering scheme and ignore the other (single-way evolution). Another approach is to rewrite both by allowing the system to branch (multiway evolution).

As the multiway system branches and diverges (quantum mechanics), the probability of ending up in some particular end state is related to the number of different evolutionary paths to that state (path counting). However, there can also be rules that make branches merge (critical pair completion). This branching and merging makes certain end states more/less likely (constructive/destructive interference). In the end we (observers) are likely to find ourselves in the part of the system in which the branches always merge (confluence) and the system converges (classical mechanics).

For more information about hypergraph rewriting systems and their potential to represent fundamental physics visit The Wolfram Physics Project website. According to their technical documents certain models reproduce key features of both relativity and quantum mechanics.

If you are interested in quantum mechanics and graph theory, you might also want to take a look at my spin-off projects BigraphQM and CliqueVM. For a philosophical take on these ideas see my blog post The Game of Algorithms.

Click RULE to modify the rewriting rule, change its settings, and run the rewriting process.

The system supports several rules separated with a semicolon ; or written on separate lines. The two sides of any one-way rule must be separated with an arrow ->. The separator == can be used as a shortcut for a two-way setup in which both directions (the rule and its inverse) are possible.

Hyperedge patterns can be described by using numbers, characters or words. Several types of parentheses are also supported. For example, a rule [{x,y}{x,z}]->[{x,y}{x,w}{y,w}{z,w}] is considered valid and can be validated and converted to the default number format by clicking Scan.

The system also supports a filter/negation \. As an example, the rule (1)(1,2)\(2)->(1)(1,2)(2) is applied only if there is no unary edge (2). If the branchlike interactions are allowed, the check is made relative to all possible branches of history.

A rule without any right-hand side, such as (1,1,1)(1,1,1), is used as the initial graph. An alternative way to define an initial state is to use some predefined function:

By using options twoway, oneway and/or inverse, each edge produced can be made a two-way edge, sorted or reversed. It is also possible to define some specific branch, or a combination of branches, for the initial state. As an example, (1,1)(1,1)/7, would specify branches 1-3 (the sum of the first three bits 1+2+4). By default, the initial state is set for all the tracked branches.

If the initial state is not specified, the left-hand side pattern of the first rule is used, but with only a single node. For example, a rule (1,2)(1,3)->(1,2)(1,4)(2,4)(3,4) gives an initial state (1,1)(1,1).

The Evolution option defines which kind of evolution is to be simulated:

The Interactions option defines the possible interactions between hyperedges. Any combination of the three possible interactions can be selected.

Other options:

Simulation can be run in three different modes: Space, Time or Phase.

• In Space mode the system shows the evolution of the spatial hypergraph. According to the Wolfram Model, the spatial hypergraph represents a spacelike state of the universe with nodes as "atoms of space".
• In Time mode the system builds up the transitive reduction of the causal graph. In this view nodes represent updating events and directed edges their causal relations. According to the Wolfram Model, the flux of causal edges through spacelike and timelike hypersurfaces is related to energy and momentum respectively.
• In Phase mode the hyper-dimensional multiway space is projected in 3D by using Hamming distances and k-NN algorithm (see Appendix A: Coordinatization of Local Multiway System by using Hyper-dimensional Vectors). According to Wolfram Model, positions in so-called "branchial" space are related to quantum phase.

Media buttons let you reset the mode, start/pause the simulation and skip to the end. Whenever the system has branches, the first four branches can be shown separately or in any combination. If Past is selected, the full history of the local multiway system is shown in space mode. By default only the leaf edges of the system are visible.

The two sliders change the visual appearance of the graph by tuning the parameters of the underlying force engine. Note: Changing the viewpoint or the forces do not in any way change the multiway system itself only how it is visualized on the screen.

Subhypergraphs can be highlighted by clicking RED/BLUE and using one or more of the following commands:

The node parameters can be specified with identifiers you can find by hovering the mouse pointer over nodes. It is also possible to use variables x and y. To set variable x click on any node and to set y use right click.

Click GRAD to visualize predefined scalar fields. Relative intensity of the field is represented by different hues of colour from light blue (lowest) to green to yellow (mid) to orange to red (highest). Field values are calculated for each edge and the colours of the vertices represent the mean of their edges.

The value range can be limited by giving lower and higher limits as parameters. For example, branch(2,4) shows branches 2-4. A limit can also be given as a percentage. For example, energy(50%,100%) highlights only upper half of the full range.

The aim of this project has been to learn some basic concepts and ideas related to hypergraphs and hypergraph rewriting. Whereas the Wolfram physics project has been a great inspiration, this project is not directly associated with it, doesn't use any code from it, and doesn't claim to be compatible with the Wolfram Model.

As a historical note, the idea of "atoms of space" is not a new one. It already appears in the old Greek tradition of atomism (atomos, "uncuttable") started by Democritus (ca. 460–370 BCE). In the Hellenistic period the idea was revived by Epicurus (341–270 BCE) and put in a poetic form by Lucretius (ca. 99–55 BCE). Unfortunately, starting from the Early Middle Ages, atomism was mostly forgotten in the Western world until Lucretius' De Rerum Natura and other atomist teachings were rediscovered in the 14th century.

“The atoms come together in different order and position, like letters, which, though they are few, yet, by being placed together in different ways, produce innumerable words.” -- Epicurus (according to Lactantius)

The following procedure utilizes Pentti Kanerva's work on Hyperdimensional computing [1]. HDC is based on the fact that in hyperdimensional space (>10,000-D) a randomly chosen vector (hypervector) is quasi-orthogonal to all previously generated hypervectors.

• For each rewriting rule, generate a random 10,240-dimensional dense bipolar {-1,1} seed vector.

• Let the coordinate of the initial event in a local multiway system be a randomly generated 10,240-dimensional dense bipolar {-1,1} vector.

• Let the coordinate of each new token/event be the sum of its parents' coordinates so that the 'sum' is the element-wise majority with random bipolar values for ties.

• Whenever the parents are timelike/branchlike separated, instead of summing up their own coordinates, use the coordinates of their lowest common ancestors.

• Whenever there is a new branch so that two or more events use an overlapping set of tokens, separate the events in orthogonal branches by adding random hypervectors to their previously calculated coordinates.

• The distance between the coordinates of any two tokens/events is the Hamming distance between their hypervectors. If the distance is close to 1/2 of the used dimension, the two hypervectors are quasi-orthogonal.

The local multiway coordinates can be projected into some lower dimension by first calculating the distance matrix and then doing multidimensional scaling. Al alternative way to do the projection is to build a graph in which each node represents a group of close-by tokens/events. These groups can then be connected to their 1-3 nearest neighbours by using a k-NN algorithm.

[1] Kanerva, P. (2019). Computing with High-Dimensional Vectors. IEEE Design & Test, 36(3):7–14.