Algorithm to drastically speed up mapping of Internet

8 January 2014
By Edd Gent
Mobile version
Share |
The increasing complexity of networks in the modern world has put limitations on the usefulness of traditional

The increasing complexity of networks in the modern world has put limitations on the usefulness of traditional "max flow" algorithms

A new theoretical algorithm could vastly simplify methods for finding the most efficient route across complex networks like the Internet.

Mathematicians and computer scientists have wrestled with problems such as finding the most efficient way to transport items across networks like highway systems or the Internet for decades, traditionally using a maximum-flow algorithm, also known as "max flow".

In a max-flow algorithm the  network is represented as a graph with a series of nodes, known as vertices, and connecting lines between them, called edges, which each have a maximum capacity — just like roads or fibre-optic cables.

These algorithms attempt to find the most efficient way to send goods from one node in the graph to another, without exceeding the capacity constraints.

But as the size of networks like the Internet has grown exponentially it has become prohibitively time-consuming to solve these problems using traditional computing techniques, according to Jonathan Kelner, an associate professor of applied mathematics at MIT and a member of MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL).

In response, Kelner and his team have created a new theoretical algorithm that can dramatically reduce the number of operations needed to solve the max-flow problem, making it possible to tackle even huge networks like the Internet or the human genome.

"There has recently been an explosion in the sizes of graphs being studied," Kelner said. "For example, if you wanted to route traffic on the Internet, study all the connections on Facebook, or analyse genomic data, you could easily end up with graphs with millions, billions or even trillions of edges."

In a paper to be presented at the ACM-SIAM Symposium on Discrete Algorithms in the USA this week, Kelner and his colleague Lorenzo Orecchia, an applied mathematics instructor, alongside graduate students Yin Tat Lee and Aaron Sidford, describe how have abandoned the methods of previous max-flow algorithms, which have come at the problem one edge, or path, at a time.

"Many previous algorithms would find a path from point A to point B, send some flow along it, and then say, 'Given what I've already done, can I find another path along which I can send more?' When one needs to send flow simultaneously along many different paths, this leads to an intrinsic limitation on the speed of the algorithm," said Kelner.

But in 2011 Kelner, CSAIL graduate student Aleksander Madry, mathematics undergraduate Paul Christiano, and colleagues at Yale University and the University of Southern California developed a technique to analyse all of the paths simultaneously by viewing the graph as a collection of electrical resistors.

The researchers imagined connecting a battery to node A and a ground to node B, and allowing the current to flow through the network.

"Electrical current doesn't pick just one path, it will send a little bit of current over every resistor on the network," Kelner said. "So it probes the whole graph globally, studying many paths at the same time."

This breakthrough allowed the new algorithm to solve the max-flow problem substantially faster than previous attempts, and now the MIT team has developed a technique to reduce the running time even further, making it possible to analyse even gigantic networks, Kelner says.

Unlike previous algorithms, which have viewed all the paths within a graph as equals, the new technique identifies those routes that create a bottleneck within the network. The team's algorithm divides each graph into clusters of well-connected nodes, and the paths between them that create bottlenecks, Kelner says.

"Our algorithm figures out which parts of the graph can easily route what they need to, and which parts are the bottlenecks,” he says. “This allows you to focus on the problem areas and the high-level structure, instead of spending a lot of time making unimportant decisions, which means you can use your time a lot more efficiently.”

The result is an almost linear algorithm, Kelner says, meaning the amount of time it takes to solve a problem is very close to being directly proportional to the number of nodes on the network.

So if the number of nodes on the graph is multiplied by 10, the amount of time would be multiplied by something very close to 10, as opposed to being multiplied by 100 or 1,000, he says.

"This means that it scales essentially as well as you could hope for with the size of the input," he added.

Latest Issue

E&T cover image 1606

"Where would Frankenstein and his creative mind fit into today's workplace? Should we fear technological developments or embrace them?"

E&T jobs

  • Maritime Engineering Opportunities

    Defence Equipment & Support (DE&S)
    • Bristol
    • £30,424 - £35,285

    You will be working alongside a team of people who are immensely proud of what they do in providing the best possible service to our Armed Forces

    • Recruiter: Defence Equipment & Support (DE&S)

    Apply for this job

  • Engineering Manager

    BAE Systems
    • Hampshire, England, Portsmouth
    • Competitive package

    Would you like to play a vital role in managing and implementing the correct governance in order to enable BAE Systems to provide assurance and integrity of supply chain data? We currently have a vacancy for an Engineering Manager - Product Integrity

    • Recruiter: BAE Systems

    Apply for this job

  • Consultant Engineer - Test

    BAE Systems
    • Farnborough, Hampshire, England
    • Negotiable

    Consultant Engineer - Test Would you like to be a lead within an exciting team working on one of the UK's largest defence projects? We currently have a vacancy for a Consultant Engineer - Test at our site in Ash Vale. As a Consultant Engineer - Test, you

    • Recruiter: BAE Systems

    Apply for this job

  • Structural Designer

    BAE Systems
    • England, Barrow-In-Furness, Cumbria
    • Negotiable

    Structural Designer BAE Systems is looking to recruit multiple Structural Designers to join our Maritime Submarines unit to be based in our site in Barrow-in-Furness, as the Trident Replacement Programme progresses towards the start of the build stage in

    • Recruiter: BAE Systems

    Apply for this job

  • Mechanical Design Engineer

    BAE Systems
    • England, Hampshire, Portsmouth
    • Negotiable

    Mechanical Design Engineer Would you like to work in an interesting and challenging role with the chance to gain exposure to a number of maritime projects? We currently have a vacancy for a Mechanical Design Engineer at our site in Portsmouth. As a Design

    • Recruiter: BAE Systems

    Apply for this job

  • Operations Manager

    BAE Systems
    • England, Barrow-In-Furness, Cumbria
    • Negotiable

    Operations Manager We currently have an opportunity for an Operations Manager to join our Maritime - Submarines business area at our Barrow-In-Furness site. As the Operations Manager you will work within a Construction or Manufacturing Facility and be res

    • Recruiter: BAE Systems

    Apply for this job

  • Principal Chemist

    BAE Systems
    • Barrow-In-Furness, Cumbria, England
    • Negotiable

    Principal Chemist Would you like to play a key role in the safety and assurance of submarines for the Royal Navy? We currently have a vacancy for a Principal Chemist at our site in Barrow-in-Furness. As a Principal Chemist, you will be carrying out a rang

    • Recruiter: BAE Systems

    Apply for this job

  • Software Engineer

    BAE Systems
    • England, Hampshire, Portsmouth
    • Competitive package

    As a Software Engineer, you will be investigating how technology and data can be used to optimise the services we provide to our clients, including the Royal Navy, and will include unique pieces of equipment at the forefront of innovation.

    • Recruiter: BAE Systems

    Apply for this job

  • Principal Control Systems Engineer

    BAE Systems
    • England, Cumbria, Barrow-In-Furness
    • Competitive package

    As a Principal Engineer you will be responsible for the design and integration of control systems at a safety integrity level (SIL) 3. This will include requirements management, system design, and integration into the wider platform.

    • Recruiter: BAE Systems

    Apply for this job

  • Ship Refit Operations Manager

    BAE Systems
    • Jubail, Saudi Arabia
    • Negotiable

    Ship Refit Operations Manager Would you like to work with some of the largest defence projects in the world, with the chance to deploy on a contract basis to Jubail, Saudi Arabia with increased allowances? An exciting opportunity has arisen to join BAE Sy

    • Recruiter: BAE Systems

    Apply for this job

More jobs ▶

Subscribe

Choose the way you would like to access the latest news and developments in your field.

Subscribe to E&T