Cops, robbers and travelling salesman …, what do they have in common? Graph Theory!
Share this on

Cops, robbers and travelling salesman …, what do they have in common? Graph Theory!

Image Source: Guimerà & Sales-Pardo, “Form follows function: the architecture of complex networks,” Molecular Systems Biology 2:42

February 14, 2013

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).

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.

metro_map_header  pralat2_web

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.

Over the last five years Dr. Pralat has written over 70 research papers, some of them appearing in such prestigious journals as Combinatorica and Random Structures and Algorithms. He has worked with 54 co-authors: among them, mathematicians, computer scientists, and social scientists. He draws upon a wide academic background. In Poland, at the University of Lodz and at the Adam Mickiewicz University, he took graduate degrees with a focus on financial mathematics, computer science (theoretical and applied), and random graph theory; he has collaborated in projects with Motorola, Google, Yahoo! Research, Telefonica, and Microsoft Research, and is currently building connections with Facebook.

His work is attracting strong interest. Since his arrival at Ryerson in 2011 he has won an NSERC Discovery Grant, two NSERC Engage Grants, an MPrime Grant, and various internal grants. His Engage Grants (both for 2012) refer to two projects: one with Winston Inc., where he is using aggregated data to improve demand predictions for a taxi service; the other with Mako Invent, where he is developing a series of formulas and algorithms to map a new artificial intelligence rating system online. Ryerson has recently recognized his outstanding contribution with a 2013 Scholarly, Research and Creative (SRC) Activity Award—one of 13 across the entire university.

Dr. Pralat’s wider goal is to build a multidisciplinary research team at Ryerson: members will receive state-of-the-art training in graph theory with applications to real-world complex networks; they will work with industry, and toward innovation. Graduates and post-doctoral fellows will emerge with advanced analytic and programming skills—tailored for a knowledge-driven economy. He sees rapid growth in the need for people who understand the “generative mechanisms” behind our networks; who can bring new insight to our models and structures.

One area of impact is being expanded at Ryerson through the new degree (BSc) in Financial Mathematics. The first cohort will begin in September 2013.

For more information on Dr. Pralat’s research and teaching, you can visit his web page (Department of Mathematics at Ryerson University) and the web site for Graphs@Ryerson, a group of faculty, post-doctoral fellows, and graduate students researching pure and applied graph theory and combinatorics.

metro_map_header  pralat2_web  GAR_2012

Graphs@Ryerson team, 2012

written by Megan O’Connor