How you’re connected to Kevin Bacon

Previously I showed you how to get Neo4j up and running with Ruby and how to find recommended friends on a social network. What about finding out how you are connected to someone outside of your friends of friends network? Do you remember the concept of six degrees of separation? No, how about six degrees of Kevin Bacon?

A credit card commercial explains how this works:

The actor, Kevin Bacon wants to write a check to buy a book, but the clerk asks for his ID, which he does not have. He leaves and returns with a group of people, then says to the clerk, “Okay, I was in a movie with an extra, Eunice, whose hairdresser, Wayne, attended Sunday school with Father O’Neill, who plays racquetball with Dr. Sanjay, who recently removed the appendix of Kim, who dumped you sophomore year. So you see, we’re practically brothers.”


You may not be a Hollywood actor, but if you’ve used the social network site Linked In, you’ve seen this feature in their “How you’re connected to” window. So how can we do this with Ruby and Neo4j?

require 'rubygems'
require 'neography'

@neo = Neography::Rest.new

def create_person(name)
  @neo.create_node("name" => name)
end

def make_mutual_friends(node1, node2)
  @neo.create_relationship("friends", node1, node2)
  @neo.create_relationship("friends", node2, node1)
end

def degrees_of_separation(start_node, destination_node)
  paths =  @neo.get_paths(start_node, 
                          destination_node, 
                          {"type"=> "friends", "direction" => "in"},
                          depth=4, 
                          algorithm="allSimplePaths")
  paths.each do |p|
   p["names"] = p["nodes"].collect { |node| 
     @neo.get_node_properties(node, "name")["name"] }
  end
end

johnathan = create_person('Johnathan')
mark      = create_person('Mark')
phil      = create_person('Phil')
mary      = create_person('Mary')

make_mutual_friends(johnathan, mark)
make_mutual_friends(mark, phil)
make_mutual_friends(phil, mary)
make_mutual_friends(mark, mary)

degrees_of_separation(johnathan, mary).each do |path|
  puts "#{(path["names"].size - 1 )} degrees: " + path["names"].join(' => friends => ')
end

# RESULT
# 3 degrees: Johnathan => friends => Mark => friends => Phil => friends => Mary
# 2 degrees: Johnathan => friends => Mark => friends => Mary

A lot of the code above we saw already, so let’s take a look at what’s new:

def degrees_of_separation(start_node, destination_node)
  paths =  @neo.get_paths(start_node, 
                          destination_node, 
                          {"type"=> "friends", "direction" => "in"},
                          depth=4, 
                          algorithm="allSimplePaths")
  paths.each do |p|
   p["names"] = p["nodes"].collect { |node| 
     @neo.get_node_properties(node, "name")["name"] }
  end
end

In this function we give Neo4j two nodes and ask it to figure out how they are connected via friendships up to a depth of 4 (which is enough for our example). We then get the name property of those nodes.

We used the algorithm “allSimplePaths” to find all the ways they are connected, but if you want to win a round of Six Degrees of Kevin Bacon, you just need to find the shortest path.

def degrees_of_separation(start_node, destination_node)
  paths =  @neo.get_paths(start_node, 
                          destination_node, 
                          {"type"=> "friends", "direction" => "in"},
                          depth=4, 
                          algorithm="shortestPath")
  paths.each do |p|
   p["names"] = p["nodes"].collect { |node| 
     @neo.get_node_properties(node, "name")["name"] }
  end
end

# RESULT
# 2 degrees: Johnathan => friends => Mark => friends => Mary

Neo4j has a few graph algorithms baked in, take a look at them in the documentation.

It’s not too complicated, but if you want some sugar here you go:

require 'rubygems'
require 'neography'

def create_person(name)
  Neography::Node.create("name" => name)
end

johnathan = create_person('Johnathan')
mark      = create_person('Mark')
phil      = create_person('Phil')
mary      = create_person('Mary')

johnathan.both(:friends) << mark
mark.both(:friends) << phil
phil.both(:friends) << mary
mark.both(:friends) << mary

johnathan.all_simple_paths_to(mary).incoming(:friends).depth(4).nodes.each 
do |path|
  puts "#{(path.size - 1 )} degrees: " + path.map{|n| n.name }.join(' => friends => ')
end
# RESULT
# 3 degrees: Johnathan => friends => Mark => friends => Phil => friends => Mary
# 2 degrees: Johnathan => friends => Mark => friends => Mary

A minor change the last part to get just the shortest path:

johnathan.shortest_path_to(mary).incoming(:friends).depth(4).nodes.each 
do |path|
  puts "#{(path.size - 1 )} degrees: " + path.map{|n| n.name }.join(' => friends => ')
end
# RESULT
# 2 degrees: Johnathan => friends => Mark => friends => Mary

You can take a look at the different path functions in Neography to get different results.

Find me and many other graph aficionados at the Neo4j Google Group.

Tagged , , ,

5 thoughts on “How you’re connected to Kevin Bacon

  1. [...] Gremlin is a domain specific language for traversing property graphs. Neo4j is one of the databases that can speak the gremlin language, and as promised I’ll show you how you can use it to implement friend recommendations as well as degrees of separation. [...]

  2. [...] Cypher is the query language of Neo4j, and as promised I’ll show you how you can use it to implement friend recommendations as well as degrees of separation. [...]

  3. [...] this post we saw how to traverse the graph using the Traversal Framework directly. In upcoming posts, I’ll show you two more ways to traverse the graph via Gremlin and Cypher as well as many [...]

  4. [...] learned how to get Neo4j up and running with Neography, how to find friends of friends and degrees of separation with the Neo4j REST API and a little bit of the Gremlin and Cypher languages. However, all [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,577 other followers

%d bloggers like this: