# Explained: Graphs

##### December 17, 2012 by Larry Hardesty, Massachusetts Institute of Technology

When most people hear the word "graph," an image springs to mind: a pair of perpendicular lines overlaid with a line, a curve, or bars of different heights.

But when use the term, they often have something very different in mind. The most familiar example of a , in the computer-science sense, may be a network diagram, with computers or depicted as circles and the connections between them depicted as line segments. But graphs can represent all kinds of things, from of decisions to relationships between data in a database, and they play a crucial role in a huge number of algorithms.

Technically, a graph consists of two fundamental elements: nodes (or vertices, usually depicted as circles) and edges (usually depicted as lines connecting nodes). Often, in computer science, the edges are "weighted": Associated with each edge is a number that indicates the ease or difficulty of traversing it. The weight of an edge could, for instance, represent the bandwidth of a wired connection in a network, or it could represent the cost—in money, or something else—in moving from one step to the next in some process.

Mathematicians have developed a handful of standard techniques for describing graphs: The weights of edges, for instance, can be depicted in a big table that maps every node against every other. In computer science, the challenge posed by graphs generally lies in their analysis, not their representation. Sometimes that analysis requires careful consideration of the data represented by each node. Other times, the point of graphic analysis is precisely to abstract away from the data: The useful information is some general property of the network as a whole.

A glance at some recent MIT News articles provides, to coin a phrase, graphic evidence of the importance of graphs. Last month, MIT professor of mathematics Peter Shor, his former student Ramis Movassagh and their colleagues published a paper demonstrating properties of physical systems that could make them useful for quantum computing. Their proof relied, in part, on graphs whose nodes represented the quantum states of physical systems; edges connected states that could be reached from each other with no change in energy. There, the crucial revelation was that the graph was highly connected: There were no bottlenecks that transitions between states had to traverse.

An August paper by Alvin Cheung, a graduate student in the Department of Electrical Engineering and Computer Science; his advisor, professor of computer science and engineering Sam Madden; and colleagues at Cornell University describes an algorithm that uses graphs to represent discrete instructions in computer programs. Like Shor and Movassagh, Cheung and Madden were looking at edges, not nodes. But unlike Shor and Movassagh, they were using a weighted graph, where the edges depicted the amount of data that each new instruction inherited from the last. Cheung and Madden's algorithm automatically splits a computer program up so that it can run on multiple servers; by identifying edges with low weights, it minimizes the data that has to pass between servers, improving efficiency.

Finally, in another paper that appeared last month, Daniela Rus, a professor of computer science and engineering and director of MIT's Computer Science and Artificial Intelligence Laboratory, her postdoc Dan Feldman, and Cynthia Sung, a graduate student in her group, described an algorithm that uses a particular type of graph called a tree. There, the interest was all in the nodes, not the edges. The most familiar example of a tree may be a family-tree diagram, which has a single node at the top and fans out at successive layers of depth. In the Rus group's , the bottom layer of the tree represented raw GPS data, and all the other nodes represented compressed versions of the data contained in the nodes beneath them.

That's just a few recent examples. Many algorithms model decision problems as graphs: For instance, a chess-playing algorithm might treat a game of chess as a tree in which each node represents a state of the board, and the nodes beneath it represent possible moves. Others use weighted graphs to depict the strength of the correlations between data points in a database. Some major advances in involve problems that are specified using graphs in the first place, such as the "max-flow" problem, which is at the heart of a huge range of logistical analyses. And that's to say nothing of perhaps the most intuitive use of graphs, in the analysis of communication networks.

## Related Stories

#### More-efficient computation: Finding local solutions to overwhelmingly complex problems

March 31, 2011

At a time when the Internet puts an untold amount of information at anyone’s fingertips, and automated scientific experiments churn out data faster than researchers can keep up with it, and communications networks can ...

#### Fundamental algorithm gets first improvement in 10 years

September 27, 2010

The maximum-flow problem, or max flow, is one of the most basic problems in computer science: First solved during preparations for the Berlin airlift, it’s a component of many logistical problems and a staple of introductory ...

#### Making Web applications more efficient

August 31, 2012

Most major websites these days maintain huge databases: Shopping sites have databases of inventory and customer ratings, travel sites have databases of seat availability on flights, and social-networking sites have databases ...

February 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information could help ...

#### Who's the most influential in a social graph? New software recognizes key influencers faster than ever

September 7, 2012

(Phys.org)—At an airport, many people are essential for planes to take off. Gate staffs, refueling crews, flight attendants and pilots are in constant communication with each other as they perform required tasks. But it's ...

#### A new kind of counting: Scientists develop computer algorithm to solve previously unsolvable counting problems

February 11, 2009

(PhysOrg.com) -- How many different sudokus are there? How many different ways are there to color in the countries on a map? And how do atoms behave in a solid? Researchers at the Max Planck Institute for Dynamics and Self-Organization ...

## Recommended for you

#### Researchers develop more efficient conversion method for solar energy

January 16, 2018

Researchers at the University of Twente's MESA+ Institute for Nanotechnology have made significant efficiency improvements to the technology used to generate solar fuels. This involves the direct conversion of energy from ...

#### Intel underfoot: Floor sensors rise as retail data source

January 15, 2018

The next phase in data collection is right under your feet.

#### Cryptocurrency rivals snap at Bitcoin's heels

January 14, 2018

Bitcoin may be the most famous cryptocurrency but, despite a dizzying rise, it's not the most lucrative one and far from alone in a universe that counts 1,400 rivals, and counting.

#### Top takeaways from Consumers Electronics Show

January 13, 2018

The 2018 Consumer Electronics Show, which concluded Friday in Las Vegas, drew some 4,000 exhibitors from dozens of countries and more than 170,000 attendees, showcased some of the latest from the technology world.

#### Finnish firm detects new Intel security flaw

January 12, 2018

A new security flaw has been found in Intel hardware which could enable hackers to access corporate laptops remotely, Finnish cybersecurity specialist F-Secure said on Friday.