graph-analysis-graphx(Scala)

%md

## Graph Analysis with GraphX

In this notebook we'll go over basic graph analysis using the GraphX API. The goal of this notebook is to show you how to use the GraphX API to perform graph analysis. We're going to be doing this with publicly available bike data from [the Bay Area Bike Share portal](http://www.bayareabikeshare.com/open-data). We're going to be specifically analyzing the second year of data.

**Note: ** GraphX computation is only supported using the Scala and RDD APIs.

#### Graph Theory and Graph Processing

Graph processing is important aspect of analysis that applies to a lot of use cases. Fundamentally graph theory and processing are about defining relationships between different nodes and edges. Nodes or vertices are the units while edges are the relationships that are defined between those. This works great for social network analysis and running algorithms like [PageRank](https://en.wikipedia.org/wiki/PageRank) to better understand and weigh relationships.

Some business use cases could be to look at central people in social networks [who is most popular in a group of friends], importance of papers in bibliographic networks [which papers are most referenced], and of course ranking web pages!

#### Graphs and Bike Trip Data

As mentioned, in this example we'll be using bay area bike share data. This data is free for use by the public on the website linked above. The way we're going to orient our analysis is by making every vertex a station and each trip will become an edge connecting two stations. This creates a *directed* graph.

**Further Reference:**

* [Graph Theory on Wikipedia](https://en.wikipedia.org/wiki/Graph_theory)

* [PageRank on Wikipedia](https://en.wikipedia.org/wiki/PageRank)

#### **Table of Contents**

* **Setup & Data**

* **Imports**

* **Building the Graph**

* **PageRank**

* **Trips from Station to Station**

* **In Degrees and Out Degrees**

%md ### Create DataFrames

%md It can often times be helpful to look at the exact schema to ensure that you have the right types associated with the right columns. In this case we haven't done any manipulation so we won't have anything besides `string`.

%md 

### Imports

We're going to need to import several things before we can continue. Because GraphX is built on the RDD API, we're going to need to create some RDDs. We'll also import everything from GraphX for simplified access.

%md

### Build the Graph

Now that we've imported our data, we're going to need to build our graph. To do so we're going to do two things. We are going to build the structure of the vertices (or nodes) and we're going to build the structure of the edges.

%md

Now we can create our set of vertices and attach a bit of metadata to each of them, which in this case is the actual name of the station.

%md Now we can create the trip edges from all of our individual rides. We'll get the station values, then just add a dummy value of 1.

%md Now we can build our graph. You'll notice below that I make a default station. This is for any edges that don't actually point to one of our vertices, imagine some sort of collection error, or a station that has gone out of service. It's worth understanding and analyzing the data collection process (or historical collection process) to better understand whether or not this merits more thought when applied to your own data.

I'm also going to cache our graph for faster access.

%md 

Now that we're all set up and have computed some basic statistics, let's run some algorithms!

## PageRank

GraphX includes a number of built-in algorithms to leverage. [PageRank](https://en.wikipedia.org/wiki/PageRank) is one of the more popular ones popularized by the Google Search Engine and created by Larry Page. To quote Wikipedia:

> PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.

What's awesome about this concept is that it readily applies to any graph type structure be them web pages or bike stations. Let's go ahead and run PageRank on our data, we can either run it for a set number of iterations or until convergence. Passing an Integer into `pageRank` will run for a set number of iterations while a Double will run until convergence.

%md We can see above that the Caltrain stations seem to be significant! This makes sense as these are natural connectors and likely one of the most popular uses of these bike share programs to get you from A to B in a way that you don't need a car!

%md

## Trips From Station to Station

One question you might ask is what are the most common destinations in the dataset from location to location. We can do this by performing a grouping operator and adding the edge counts together. This will yield a new graph except each edge will now be the sum of all of the semantically same edges. Think about it this way: we have a number of trips that are the exact same from station A to station B, we just want to count those up!

In the below query you'll see that we're going to grab the station to station trips that are most common and print out the top 10.

%md 

## In Degrees and Out Degrees

Remember that in this instance we've got a directed graph. That means that our trips our directional - from one location to another. Therefore we get access to a wealth of analysis that we can use. We can find the number of trips that go into a specific station and leave from a specific station.

Naturally we can sort this information and find the stations with lots of inbound and outbound trips! Check out this definition of [Vertex Degrees](http://mathworld.wolfram.com/VertexDegree.html) for more information.

Now that we've defined that process, let's go ahead and find the stations that have lots of inbound and outbound traffic.

%md One interesting follow up question we could ask is what is the station with the highest ratio of in degrees but fewest out degrees. As in, what station acts as almost a pure trip sink. A station where trips end at but rarely start from.

%md 

We can do something similar by getting the stations with the lowest in degrees to out degrees ratios, meaning that trips start from that station but don't end there as often. This is essentially the opposite of what we have above.