Graph theory is not It is enough.
The mathematical language of talking about connections, usually based on networks — vertices (points) and edges (the lines connecting them) — has been an invaluable way of modeling real-world phenomena since at least the eighteenth century. But a few decades ago, the emergence of giant data sets forced researchers to expand their toolboxes and, at the same time, give them sprawling sandboxes to apply new mathematical insights. He said since then Josh GrouchoA computer scientist at the University of Colorado, Boulder, there was an exciting period of rapid growth as researchers developed new types of network models that could find complex structures and signals in the hype of big data.
Grochow is among a growing group of researchers who point out that when it comes to finding connections in big data, graph theory has its limitations. The graph represents each relationship as a binary or binary interaction. However, many complex systems cannot be represented by binary connections alone. Recent advances in this area show how to move forward.
Consider trying to craft a network model of parenting. Obviously every parent has a connection with a child, but the parenting relationship is not just the sum of the two bonds, as graph theory might represent. The same goes for trying to model a phenomenon like peer pressure.
“There are many axiomatic models. The effect of peer pressure on social dynamics is only recorded if you already have groups in your data” Leonie Neuhauser from RWTH University Aachen in Germany. But binary networks do not capture group effects.
Mathematicians and computer scientists use the term “higher order interactions” to describe these complex ways in which group dynamics, rather than binary connections, can affect individual behaviors. These mathematical phenomena appear in everything from entanglement interactions in quantum mechanics to the path of disease spread through populations. If a pharmacist wants to design a model drug interactionFor example, graph theory might show how two drugs respond to each other—but what about three? Or four?
While tools for exploring these interactions are not new, it is only in recent years that high-dimensional data sets have become an engine of discovery, giving mathematicians and network theorists new ideas. These efforts yielded interesting findings about the limitations of graphs and possibilities for scaling.
“We now know that the network is just a shadow of the thing,” Groucho said. If the data set has a complex underlying structure, modeling it as a graph may reveal only a limited projection of the entire story.
“We’ve come to realize that, from a mathematical perspective, the data structures we used to study things don’t quite fit with what we see in the data,” said the mathematician. Emily Purvin From Pacific Northwest National Laboratory.
This is why mathematicians, computer scientists, and other researchers are increasingly focusing on ways to generalize graph theory – in its many forms – to explore higher-order phenomena. The past few years have brought a flood of proposed ways to describe these interactions, and to verify them mathematically in high-dimensional data sets.
For Purvine, mathematical exploration of high-level interactions is like mapping new dimensions. “Think of the graph as a basis on a two-dimensional plot,” she said. The three-dimensional buildings that can rise can vary greatly. “When you’re at ground level, they look the same, but what you’re building on top is different.”
Enter the graph
The search for those high-dimensional structures is where mathematics becomes especially mysterious and interesting. A higher-order analogue of a graph, for example, is called a high-order graph, and instead of edges, it has “hyper-edges”. These nodes can connect several, which means that they can represent multi-directional (or multi-line) relationships. Instead of a line, a hyperedge may be thought of as a surface, like a tarp piled in three or more places.
That’s fine, but there’s still a lot we don’t know about how these structures relate to their traditional counterparts. Mathematicians are currently learning the rules of graph theory that also apply to high-level interactions, indicating new areas for exploration.
To illustrate the kinds of relationship a hypergraph can extract from a huge data set—and a normal graph cannot—Purvine points to a simple example close to home, scholarly publishing. Imagine two data sets, each containing research papers co-authored by up to three mathematicians; For simplicity, let’s call them A, B, and C. One data set contains six cards, with two cards from each of the three distinct pairs (AB, AC, and BC). The other contains only two papers, each co-authored by the three ABC mathematicians.