Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Short and Sweet

New technique for solving “graph Laplacians” makes it easier to tackle a wide array of practical problems

In computer science, a huge range of problems can be represented as “graphs”—mathematical abstractions consisting of nodes, depicted as circles, connected by edges, depicted as line segments. The nodes can represent almost anything—routers in a communication network, airline flights, movie titles.

Analyzing such graphs—finding a route through a communications network, or predicting a Netflix subscriber’s movie preferences—often requires something called a graph Laplacian, which is a big grid of numbers (a matrix) representing the strength of the connections between nodes. Each row of the grid can also be treated as a separate equation using the same variables; solving the Laplacian means solving all the equations simultaneously.

For years the best algorithms for solving graph Laplacians had an execution time that increased exponentially with the number of variables, but a paper published in 2004 presented the first of several “nearly linear time” algorithms. In June, at the ACM Symposium on the Theory of Computing, MIT researchers will present a new algorithm that’s drastically simpler than its predecessors.

May/June MIT News cover
This story is part of the May/June 2013 Issue of the MIT News Magazine
See the rest of the issue
Subscribe

“The 2004 paper required fundamental innovations in multiple branches of mathematics and computer science, but it ended up being split into three papers that I think were 130 pages in aggregate,” says Jonathan Kelner, an associate professor of applied mathematics, who led the new research. “We were able to replace it with something that would fit on a blackboard.”

One way to think about graph Laplacians is to imagine the graph as an electrical circuit and the edges as resistors; solving the Laplacian tells you how much current would flow between any two points in the graph.

The MIT algorithm’s first step is to find a “spanning tree” for the graph. A tree is a graph that has no closed loops; a spanning tree is one that touches all of a graph’s nodes.

The algorithm then adds back just one of the graph’s missing edges, creating a loop. On the circuit analogy, the net voltage around the loop must be zero, so the algorithm plugs in values for current flow that balance the loop. Then it adds back another missing edge and rebalances.

Remarkably, this simple, repetitive process converges on the solution of the graph Laplacian. Demonstrating that convergence didn’t require any sophisticated mathematics: “Once you find the right way of thinking about the problem, everything just falls into place,” Kelner explains.

Become an MIT Technology Review Insider for in-depth analysis and unparalleled perspective.

Subscribe today
Next in MIT News
Want more award-winning journalism? Subscribe to Insider Basic.
  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning print magazine, unlimited online access plus The Download with the top tech stories delivered daily to your inbox.

    See details+

    Print Magazine (6 bi-monthly issues)

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

/3
You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.