Sign In

Communications of the ACM

Contributed articles

Parallel Graph Analytics

Internet routing paths, visualization

Visualization of the routing paths of the Internet.

Credit: Barrett Lyon / The Opte Project

The study of graphs began in the 18th century with Euler's work on the "Bridges of Königsberg" problem, but it is only since the creation of the Web two decades ago that large-scale parallel computers have been used to study graph properties. Today, this field, known as "parallel graph analytics," touches all our lives, even if we are not aware of it. When we use a Web search engine or get a friend recommendation on Facebook, graph analytics is at work behind the scenes. Companies like Amazon and Netflix use parallel graph analytics to find patterns of purchases by their customers, enabling them to make targeted product recommendations. And intelligence agencies use parallel graph analytics to find key players, called "centralities," in terrorist networks.

Back to Top

Key Insights


Using computers to study graph properties is not new; 40 years ago, in 1976, mathematicians Kenneth Appel and Wolfgang Haken ran a FORTRAN program for 1,200 hours to prove the four-color theorem for planar graphs.a Today, we are interested in studying not only the mathematical properties of different kinds of graphs (such as planar graphs) but also in computing and exploiting properties of particular graphs that arise from big datasets. There are three main challenges in performing computations on these graphs—large graph sizes, diversity in graph structure, and the complex patterns of parallelism in graph analytics applications. Most current parallel abstractions and implementations fail to provide solutions for at least one of them.


CACM Administrator

An online appendix for this article entitled "Research Directions" may be found under the Source Materials tab in the ACM Digital Library at, or at
--CACM Administrator

Displaying 1 comment

Log in to Read the Full Article

Sign In

Sign in using your ACM Web Account username and password to access premium content if you are an ACM member, Communications subscriber or Digital Library subscriber.

Need Access?

Please select one of the options below for access to premium content and features.

Create a Web Account

If you are already an ACM member, Communications subscriber, or Digital Library subscriber, please set up a web account to access premium content on this site.

Join the ACM

Become a member to take full advantage of ACM's outstanding computing information resources, networking opportunities, and other benefits.

Subscribe to Communications of the ACM Magazine

Get full access to 50+ years of CACM content and receive the print version of the magazine monthly.

Purchase the Article

Non-members can purchase this article or a copy of the magazine in which it appears.
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account