Big Data, Graph Theory and Beyond: The Complexity of Data Interrelationships

Graph Theory provides mathematical structure for analyzing connections, relationships, and the strengths of those bonds.

Google’s PageRank algorithm introduced twenty years ago is an example of a successful application of graph theory. The original Google PageRank algorithm looked at which pages on the internet link to a specific web page and weights those connections based on the authoritativeness of the linking site, and from that, scores the importance of the web page. That’s basically how Google Search continues to work today, but the success of PageRank led to many people trying to ‘game’ the system in order to achieve high SEO rankings and over the years has caused the algorithm and the criteria for how to weight relationships to change.

Graph theory provides a framework for querying relationships in order to find solutions to problems related to optimization, arrangement, matching, and networking. Examples of graph problems are all around us and can be found in physical, biological and social disciplines, not to mention healthcare, retail, finance, gaming, and other fields.

Some examples of graph theory include:

• GPS navigation paths
• Contact communities, like with LinkedIn, Twitter, or COVID19 exposures
• Molecules and atoms in chemistry

PageRank and contact information are pretty straightforward, but real data can get messy and other parameters and subrelationships can be thrown in to mix things up even more. When really huge Big Data sets are studies, the interactions between data can become incredibly complex.

As greater complexity is added to the problem set, people are talking about ‘hypergraphs’.

Emilie Purvine, computational mathematician at the Pacific Northwest National Laboratory, said that “think about a graph as a foundation on a two-dimensional plot of land. When you’re down at ground level, they look the same, but what you construct on top is different. That’s the kind of power we’re seeing from hypergraphs, to go above and beyond graphs.”

And there is likely more theory that goes beyond hypergraphs. Austin Benson, a mathematician at Cornell University, said that “there are still many open questions there. 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.”