Research on hypergraphs by Austin Benson, Assistant Professor in the Department of Computer Science in the Ann S. Bowers College of Computing and Information Science, is engaged in "How Big Data Carried Graph Theory Into New Dimensions" (Wired Magazine). The article by Stephen Ornes draws mainly from Benson's recent work "Hypergraph Cuts with General Splitting Functions," coauthored with Nate Veldt, former Postdoctoral Associate in the Center for Applied Mathematics at Cornell and currently Assistant Professor at Texas A&M University and Jon Kleinberg, Tisch University Professor of Computer Science and Information Science.
Highlights of Ornes' engagement with Benson's findings include the following passages:
The mathematical language for talking about connections, which usually depends on networks—vertices (dots) and edges (lines connecting them)—has been an invaluable way to model real-world phenomena since at least the 18th century. But a few decades ago, the emergence of giant data sets forced researchers to expand their toolboxes and, at the same time, gave them sprawling sandboxes in which to apply new mathematical insights. Since then, said Josh Grochow, a computer scientist at the University of Colorado, Boulder, there’s been an exciting period of rapid growth as researchers have developed new kinds of network models that can find complex structures and signals in the noise of big data.
Grochow is among a growing chorus of researchers who point out that when it comes to finding connections in big data, graph theory has its limits. A graph represents every relationship as a dyad, or pairwise interaction. However, many complex systems can’t be represented by binary connections alone. Recent progress in the field shows how to move forward. [...]
[G]eneralizing from graphs to hypergraphs quickly gets complicated. One way to illustrate this is to consider the canonical cut problem from graph theory, which asks: Given two distinct nodes on a graph, what’s the minimum number of edges you can cut to completely sever all connections between the two? Many algorithms can readily find the optimal number of cuts for a given graph.
But what about cutting a hypergraph? “There are lots of ways of generalizing this notion of a cut to a hypergraph,” said Austin Benson, a mathematician at Cornell University. But there’s no one clear solution, he said, because a hyperedge could be severed various ways, creating new groups of nodes.
Together with two colleagues, Benson recently tried to formalize all the different ways of splitting up a hypergraph. What they found hinted at a variety of computational complexities: For some situations, the problem was readily solved in polynomial time, which basically means a computer could crunch through solutions in a reasonable time. But for others, the problem was basically unsolvable—it was impossible to know for certain whether a solution existed at all.
“There are still many open questions there,” Benson said. “Some of these impossibility results are interesting because you can’t possibly reduce them to graphs. And on the theory side, if you haven’t reduced it to something you could have found with a graph, it’s showing you that there is something new there.” [...]
Benson’s inconclusive taxi model raises a pervasive question: When do researchers actually need tools like hypergraphs? In many cases, under the right conditions, a hypergraph will deliver the exact same type of predictions and analyses as a graph.
Read more about Benson's research, including his recent NSF CAREER Award.