Max De Marzi, is a seasoned web developer. He started building websites in 1996 and has worked with Ruby on Rails since 2006. The web forced Max to wear many hats and master a wide range of technologies. He can be a system admin, database developer, graphic designer, back-end engineer and data scientist in the course of one afternoon. Max is a graph database enthusiast. He built the Neography Ruby Gem, a rest api wrapper to the Neo4j Graph Database. He is addicted to learning new things, loves a challenge and finding pragmatic solutions. Max is very easy to work with, focuses under pressure and has the patience of a rock. Max is a DZone MVB and is not an employee of DZone and has posted 60 posts at DZone. You can read more from them at their website. View Full User Profile

Six Degrees of Kevin Bacon Using Neo4j and Ruby

02.21.2012
| 5547 views |
  • submit to reddit

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/

Published at DZone with permission of Max De Marzi, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)