At Ryerson University in Toronto, mathematical researchers are exploiting the graph, taking graph theory in real world applications to explore networks of data.
What do cops, robbers, and travelling salesmen have in common? They belong to the language of graph theory.
Graph theory is a fast-emerging field that impacts our daily lives: how we use the Internet; the development of new drugs; how a city supplies power; a taxi’s response to our call. A simple graph can consist of a few nodes and lines (or edges). Algorithms are created to move along a graph by the most efficient route (hence the reference to “cops and robbers”: a particular kind of graph pursuit).
Image Source: Guimerà & Sales-Pardo, “Form follows function: the architecture of complex networks,” Molecular Systems Biology 2:42
Yet it’s not simply a game, or a single topic. The modelling and searching of complex networks is a multidisciplinary field—often complicated (or illuminated) by human behaviour.
One of Ryerson’s newest mathematicians, Dr. Pawel Pralat, is helping to advance this area. His main research focuses on graph theory with applications to real-world self-organizing networks; on both modelling and searching. In October, he co-organized the 2012 Banff conference: GRAph Searching, Theory and Applications. In April 2013, Ryerson will be hosting the
2nd Graph Searching in Canada (GRASCan) Workshop. In December 2013, Dr. Pralat and Ryerson mathematics chair Dr. Anthony Bonato will be co-organizing a
Workshop for Algorithms and Models for the Web Graph with Harvard University’s Dr. Michael Mitzenmacher. Dr. Bonato recently co-authored a book titled The Game of Cops and Robbers on Graphs (2011) with Dr. Richard Nowakowski from Dalhousie University.
Interest in graph theory is rising in Canada and around the world due to the increase in applications. Just think of the media stir earlier this year when Facebook announced “Graph Search,” a function that gives users the ability to search for people in Toronto who like Tafelmusik, read spy novels, and own a border collie (other examples are less benign); people may be questioning the ethics of this search capability, but no one doubts that the potential, for good or ill, is vast. Graph Search draws on expertise in graph theory, data mining, statistics, and modelling—topics Dr. Pralat and others are exploring at Ryerson.
Graphs also enable mathematicians to study how people use such networks. Before Dr. Pralat came to Ryerson, he took part in a project that revealed a tendency for people to communicate with those who share similar beliefs or ways of looking at the world—which complicates our idea of the Internet as a level ground. Organization, social and otherwise, happens all the time. Dr. Pralat’s development of the idea of “segregation in evolving social networks” was published in the Proceedings of the National Academy of Sciences to high acclaim among social scientists in 2011.
But social media is not the only graph use: complex networks now offer the ability to search a database of 3D molecular models, which is transforming pharmaceutical development; our traffic systems are increasingly sophisticated, from bus routes to hand-held GPS; power grids are coping with more points and sources than ever before. Think, too, of the variables in modern financial systems.
One key feature in many such networks is that they are self-organizing and decentralized. As such, they are forever changing—often in ways or degrees that we can’t entirely predict.
It is crucial that we learn more about their (and our) behaviour. Dr. Pralat’s own research program focuses on the modelling and searching of such networks, and reflects the interdisciplinary nature of the field. Related areas of research include game theory, logic, probabilistic analysis, motion planning, and distributed computing.
Read the full article.
Keywords: Dr. Pawel Pralat • Graph Theory
