‘Well, some go this way, some go that way. But as for me, myself, personally, I prefer the short-cut.’ – The Cheshire Cat
Every morning we wake to a deafening barrage of choice, decisions that crackle and branch to more choices and more decisions that daunt enumeration. How can we tally the untaken roads of a day, or quantify the chains of action that we might just as easily have been nudged into treading? What is the mathematics that controls the probabilities of where an initial system, governed by a complicated set of allowable connections, ends up at the end of a day or a century?
These are the concerns of graph theory, an enchanting branch of mathematics charged with investigating how massively interlinked systems of points behave, and what to expect when you head out on a random journey from one of those points. And few people since Paul Erdös have wielded that mathematics, and enhanced its connections with other parts of existence from manifold theory to the connectivity of the Entire Internet, as Fan Chung (b. 1949).
She is such a Maths Person, so wrapped up at every moment of the day in solving new problems and fine-tuning old solutions, that I would not remotely be surprised to learn that she was immaculately conceived by mathematically inclined midi-chlorians. That, I am sad to say, is not the case. She was, in fact, born in Taiwan to a family who encouraged her, against tradition, to pursue a life of science and in particular, given a certain lack of manual finesse when young, a life of calculation where she had to handle nothing more fragile (or explosive) than a pen and a sheet of paper.
Chung went to National Taiwan University and was drawn to the allure of combinatorics, the branch of mathematics that, broadly speaking, asks questions about the number of ways that a given event can happen. How many ways are there to arrange eight books on a shelf? How many different licence plates can you make if the first three positions are digits, the last three are letters, and no repetition is allowed? What is the maximum number of possible distances between n points in a plane?
That attraction was fostered by Herbert Wilf at the University of Pennsylvania, where Chung studied after graduating from NTU in 1970. Her score on the university’s qualifying exams was so much higher than that of any other student he decided to snatch her up and make her into one of his combinatoric warriors. He lent her a book that contained a chapter on Ramsey theory so charming and enticing that it was his standard text for hooking promising students into the field. She came back in a week not only having read and understood the work, but having found a spot that could be improved. ‘In just one week,’ he recalled, ‘from a cold start, she had a major result in Ramsey theory. I told her that she had just done two-thirds of a doctoral dissertation.’
It was the first step in a string of triumphs that would encompass hundreds of papers producing important results in half a dozen different fields of mathematics, none of which will make the least bit of sense without at least a few words about what graph theory is all about.
First of all, it is not about graphs. Well, not graphs as we know them from school, with their curvy parabolas and pointy absolute value functions jauntily marching about in the space created by the x and y axes. A graph G(v,e) is simply made up of v vertices connected by e edges. Here’s an exquisite, some might say artisanal, drawing of a random G(4,5) graph, for example, which was not at all drawn on the back of an envelope:
In practical life, you can think of the points as oil reserves connected by pipelines, or websites connected by links, or people connected through a social network, at which point seemingly abstract questions in graph theory such as, ‘What is the minimum number of points we need to remove to cut the graph into two disconnected pieces?’ or, ‘If we let a set of free agents wander this graph, is there a stable final configuration, and how fast do we get to it?’ become multi-billion dollar questions pushing the future of global commerce and information technology.
One of the areas that highlights all of the different areas of mathematics that Chung brings to her research on combinatorics and graph theory involves questions of random walks along a graph. Put simply, if you put a number of people at the different vertices of a graph and let them walk from vertex to vertex however they want, is there a stable configuration that they’ll eventually end up at, and how long will it take them to reach it? Stated another way, if each of the vertices is a web page, and people randomly click on links, is all the clicking going to settle into some stable number of people we expect to be, at any given moment, on any given site?
Let’s do it, then! Suppose we have our G(4,5) graph above and we put one person at each corner, then let each of them randomly choose an edge to walk along towards another corner. So, the person at corner 1 can walk to corner 2 or 3, but the person at corner 3 can walk to corners 1, 2, or 4. The initial configuration can be expressed as follows (i.e. with just one person at each vertex):
Now, we need to make a matrix that expresses the probability that a person will choose to go from corner i to corner j. It is called a transformation matrix, and here it is!
We have 1/2 as the entry in the 2nd column of the 1st row because a person at vertex 1 has a 1/2 chance of going to vertex 2. But the 1st column entry of row 3 is a 1/3 because, from vertex 3, I have three choices of where to go so the chance of going to vertex 1 is just 1/3. So, to figure out how everything ends up after everybody’s first random choice, we just have to multiply the original configuration matrix by the probability matrix to get the new configuration:
After one decision we see that people are starting to group up around vertices 2 and 3, which is what we’d expect, since there are three roads to each of those vertices but only two roads to vertices 1 and 4. Now, to see what happens with the next random move, we just need to multiply our new distribution of people by our old friend the transformation matrix, which thankfully never changes!
The question, then, of ‘Does it settle down?’ can be answered by just continuously multiplying by the transformation matrix until the numbers stop significantly changing. Try it at home and you should get (.8 1.2 1.2 .8) as your stable configuration. If we had a hundred people at each corner, then, we’d expect the stable state to have 80 each at corners 1 and 4, and 120 each at 2 and 3. That’s fine, but it doesn’t answer questions like, ‘How quickly does the system achieve this stable state?’ It makes rather a big difference if it will settle to these proportions after thirty choices or after 30 million, especially if this graph models something physical.
Enter eigenvalues. This is where the ‘spectral’ in Spectral Graph Theory comes from. It is a rather alarming word for a really simple idea. Sometimes, when you multiply a matrix by a one-column matrix, the result is just a multiple of that one-column matrix. The multiple is called the eigenvalue and the one-column matrix is called the eigenvector. A matrix’s eigenvalues carry with them massive amounts of information about the matrix they come from and, therefore, when that matrix represents a physical model, about the physical situation it represents.
We’re interested in the eigenvalues of a matrix called the Laplacian which is actually relatively easily built:
- Put 1’s along the main diagonal.
- For the entry in row i, column j, put a zero if vertex i and j aren’t connected by an edge, and put -1/√(didj) if they are, where di and dj just represent the number of edges coming out of vertices i and j. For those playing along at home, our graph from above would have the following Laplacian matrix:
The Laplacian, yo!!
Find out the eigenvalues of THAT matrix, and it turns out you find out a lot about how quickly the graph converges to its stable state. Now, that all looks simple – an incredibly clever use of methods you learned in your pre-calculus class or undergraduate linear algebra course – but that is because we’re dealing with one given case with a very small number of vertices. It is when you start saying general things about systems of n vertices and e edges that life gets interesting, and it is precisely those questions that Fan Chung has been shedding light on for the better part of five decades now, creating solutions for general values of n that have allowed us to gain insight into the comings and goings of massively complicated systems like website connectivity on the Internet or the chains linking members of a biological network.
How do you deal with random paths when the different edges have different weights? How does giving each edge a direction (i.e. you can only go from site A to site B, never site B to site A) mess with the ability of a system to settle down? First at the University of Pennsylvania then, throughout the 1970s and 1980s, as a researcher and manager at Bell Laboratories and its splinter company, Bell Communications Research, Fan Chung has tackled the intersection of abstract graph theory and complex real-life applications by collaborating with mathematicians in far-flung fields, to bring unlikely approaches to solve sticky problems. She describes mathematicians as falling into the category of either Theory Makers or Problem Solvers, and places herself firmly in the second category, as someone who thinks about maths every waking moment, getting better answers to old questions and finding ways to apply several disciplines’ worth of wisdom to answer the questions posed by the exploding world of Big Connectivity.
And the maths and the life keep rolling on. She has had two children, working until the very last moment while pregnant with each and even continuing her research at home when she took a few weeks’ personal vacation after the births. Her husband is a mathematician in the same field, and their joint passion for constant research draws them together in investigation, rather than pushing them apart in competition. Where other couples have a massive television sprawled along a wall of the living room, they have a giant whiteboard where they solve problems together, their work, their passion, their hobby all concentrated on the same intellectual object.
It is, by all objective standards, a magnificent way to spend a life with another human.
Today, Fan Chung’s research continues at UCSD, where she has been a professor since 1998, and as the editor-in-chief of Internet Mathematics since 2003. She manages the ‘bigness’ of the virtual world we have placed ourselves in, using the massive power of graph theory to find how tribal online communities work in isolation, how they interact with the larger picture, and what the effects might be should they be suddenly expunged, while documenting the growing disparity between high-volume, high-connectivity sites and the small competitors treading water ever more feebly in their wake.
Maths might be pretty, but it is rarely kind.
FURTHER READING:
Chung has two books out, Spectral Graph Theory and Erdös on Graphs, both of which are pretty easy to find, but I think are probably too daunting for most. Better to start with Bela Bollobas’s Extremal Graph Theory and work your way up, supplementing it with the fantastic resources that Chung has on her website, including her lecture notes which clarified beautifully a number of points that I had been struggling with when trying to grasp the intersection of spectra with graphs.
Comments