Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Six Degrees of Kevin Bacon Using Neo4j and Ruby

DZone's Guide to

Six Degrees of Kevin Bacon Using Neo4j and Ruby

· Database Zone
Free Resource

Whether you work in SQL Server Management Studio or Visual Studio, Redgate tools integrate with your existing infrastructure, enabling you to align DevOps for your applications with DevOps for your SQL Server databases. Discover true Database DevOps, brought to you in partnership with Redgate.

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/

It’s easier than you think to extend DevOps practices to SQL Server with Redgate tools. Discover how to introduce true Database DevOps, brought to you in partnership with Redgate

Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}