Six Degrees of Kevin Bacon Using Neo4j and Ruby

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

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.

Source: http://maxdemarzi.com/2012/01/05/how-youre-connected-to-kevin-bacon/