Chapter 11. Graph Processing Using GraphX

This chapter will cover how we can do graph processing using GraphX, Spark's graph processing library.

The chapter is divided into the following recipes:

• Fundamental operations on graphs

• Using PageRank

• Finding connected components

• Performing neighborhood aggregation

Introduction

Graph analysis is much more commonplace in our life than we think. To take the most common example, when we ask a GPS to find the shortest route to a destination, it uses a graph-processing algorithm.

Let's start by understanding graphs. A graph is a representation of a set of vertices where some pairs of vertices are connected by edges. When these edges move from one direction to another, it's called a directed graph or digraph.

GraphX is the Spark API for graph processing. It provides a wrapper around an RDD called resilient distributed property graph. The property graph is a directed multigraph with properties attached to each vertex and edge.

There are two types of graphs—directed graphs (digraphs) and regular graphs. Directed graphs have edges that run in one direction, for example, from vertex A to vertex B. Twitter follower is a good example of a digraph. If John is David's Twitter follower, it does not mean that David is John's follower. On the other hand, Facebook is...

Fundamental operations on graphs

In this recipe, we will learn how to create graphs and do basic operations on them.

Getting ready

As a starting example, we will have three vertices, each representing the city center of three cities in California—Santa Clara, Fremont, and San Francisco. The following is the distance between these cities:

Source	Destination	Distance (miles)
Santa Clara, CA	Fremont, CA	20
Fremont, CA	San Francisco, CA	44
San Francisco, CA	Santa Clara, CA	53

How to do it…

1. Import the GraphX-related classes:

   scala> import org.apache.spark.graphx._
   scala> import org.apache.spark.rdd.RDD
   

2. Load the vertex data in an array:

   scala> val vertices = Array((1L, ("Santa Clara","CA")),(2L, ("Fremont","CA")),(3L, ("San Francisco","CA")))
   

3. Load the array of vertices into the RDD of vertices:

   scala> val vrdd = sc.parallelize(vertices)
   

4. Load the edge data in an array:

   scala> val edges = Array(Edge(1L,2L,20),Edge(2L,3L,44),Edge(3L,1L,53))
   

5. Load the data into the RDD of edges...

Using PageRank

PageRank measures the importance of each vertex in a graph. PageRank was started by Google's founders, who used the theory that the most important pages on the Internet are the pages with the most links leading to them. PageRank also looks at the importance of a page leading to the target page. So, if a given web page has incoming links from higher rank pages, it will be ranked higher.

Getting ready

We are going to use Wikipedia page link data to calculate page rank. Wikipedia publishes its data in the form of a database dump. We are going to use link data from http://haselgrove.id.au/wikipedia.htm, which has the data in two files:

• links-simple-sorted.txt

• titles-sorted.txt

I have put both of them on Amazon S3 at s3n://com.infoobjects.wiki/links and s3n://com.infoobjects.wiki/nodes. Since the data size is larger, it is recommended that you run it on either Amazon EC2 or your local cluster. Sandbox may be very slow.

You can load the files to hdfs using the following commands:

$ hdfs...

Finding connected components

A connected component is a subgraph (a graph whose vertices are a subset of the vertex set of the original graph and whose edges are a subset of the edge set of the original graph) in which any two vertices are connected to each other by an edge or a series of edges.

An easy way to understand it would be by taking a look at the road network graph of Hawaii. This state has numerous islands, which are not connected by roads. Within each island, most roads will be connected to each other. The goal of finding the connected components is to find these clusters.

The connected components algorithm labels each connected component of the graph with the ID of its lowest-numbered vertex.

Getting ready

We will build a small graph here for the clusters we know and use connected components to segregate them. Let's look at the following data:

Follower	Followee
John	Pat
Pat	Dave
Gary	Chris
Chris	Bill

The preceding data is a simple one with six vertices and two clusters...

Performing neighborhood aggregation

GraphX does most of the computation by isolating each vertex and its neighbors. It makes it easier to process the massive graph data on distributed systems. This makes the neighborhood operations very important. GraphX has a mechanism to do it at each neighborhood level in the form of the aggregateMessages method. It does it in two steps:

1. In the first step (first function of the method), messages are send to the destination vertex or source vertex (similar to the Map function in MapReduce).

2. In the second step (second function of the method), aggregation is done on these messages (similar to the Reduce function in MapReduce).

Getting ready

Let's build a small dataset of the followers:

Follower	Followee
John	Barack
Pat	Barack
Gary	Barack
Chris	Mitt
Rob	Mitt

Our goal is to find out how many followers each node has. Let's load this data in the form of two files: nodes.csv and edges.csv.

The following is the content of nodes.csv:

1,Barack
2,John
3,Pat...

The rest of the chapter is locked

Unlock this book and the full library FREE for 7 days

Get unlimited access to 7000+ expert-authored eBooks and videos courses covering every tech area you can think of

Renews at $15.99/month. Cancel anytime

Start free trial

Previous Chapter

Chapter 17 of 19

Next Chapter

Using PageRank

PageRank measures the importance of each vertex in a graph. PageRank was started by Google's founders, who used the theory that the most important pages on the Internet are the pages with the most links leading to them. PageRank also looks at the importance of a page leading to the target page. So, if a given web page has incoming links from higher rank pages, it will be ranked higher.

Getting ready

We are going to use Wikipedia page link data to calculate page rank. Wikipedia publishes its data in the form of a database dump. We are going to use link data from http://haselgrove.id.au/wikipedia.htm, which has the data in two files:

• links-simple-sorted.txt

• titles-sorted.txt

I have put both of them on Amazon S3 at s3n://com.infoobjects.wiki/links and s3n://com.infoobjects.wiki/nodes. Since the data size is larger, it is recommended that you run it on either Amazon EC2 or your local cluster. Sandbox may be very slow.

You can load the files to hdfs using the following commands:

$ hdfs...

Finding connected components

A connected component is a subgraph (a graph whose vertices are a subset of the vertex set of the original graph and whose edges are a subset of the edge set of the original graph) in which any two vertices are connected to each other by an edge or a series of edges.

An easy way to understand it would be by taking a look at the road network graph of Hawaii. This state has numerous islands, which are not connected by roads. Within each island, most roads will be connected to each other. The goal of finding the connected components is to find these clusters.

The connected components algorithm labels each connected component of the graph with the ID of its lowest-numbered vertex.

Getting ready

We will build a small graph here for the clusters we know and use connected components to segregate them. Let's look at the following data:

Follower	Followee
John	Pat
Pat	Dave
Gary	Chris
Chris	Bill

The preceding data is a simple one with six vertices and two clusters...

Performing neighborhood aggregation

GraphX does most of the computation by isolating each vertex and its neighbors. It makes it easier to process the massive graph data on distributed systems. This makes the neighborhood operations very important. GraphX has a mechanism to do it at each neighborhood level in the form of the aggregateMessages method. It does it in two steps:

1. In the first step (first function of the method), messages are send to the destination vertex or source vertex (similar to the Map function in MapReduce).

2. In the second step (second function of the method), aggregation is done on these messages (similar to the Reduce function in MapReduce).

Getting ready

Let's build a small dataset of the followers:

Follower	Followee
John	Barack
Pat	Barack
Gary	Barack
Chris	Mitt
Rob	Mitt

Our goal is to find out how many followers each node has. Let's load this data in the form of two files: nodes.csv and edges.csv.

The following is the content of nodes.csv:

1,Barack
2,John
3,Pat...

The rest of the chapter is locked

Unlock this book and the full library FREE for 7 days

Get unlimited access to 7000+ expert-authored eBooks and videos courses covering every tech area you can think of

Renews at $15.99/month. Cancel anytime

Start free trial

Previous Chapter

Chapter 17 of 19

Next Chapter

Performing neighborhood aggregation

GraphX does most of the computation by isolating each vertex and its neighbors. It makes it easier to process the massive graph data on distributed systems. This makes the neighborhood operations very important. GraphX has a mechanism to do it at each neighborhood level in the form of the aggregateMessages method. It does it in two steps:

1. In the first step (first function of the method), messages are send to the destination vertex or source vertex (similar to the Map function in MapReduce).

2. In the second step (second function of the method), aggregation is done on these messages (similar to the Reduce function in MapReduce).

Getting ready

Let's build a small dataset of the followers:

Follower	Followee
John	Barack
Pat	Barack
Gary	Barack
Chris	Mitt
Rob	Mitt

Our goal is to find out how many followers each node has. Let's load this data in the form of two files: nodes.csv and edges.csv.

The following is the content of nodes.csv:

1,Barack
2,John
3,Pat...

The rest of the chapter is locked