Six Degrees of Kevin Bacon Using Neo4j and Ruby
Join the DZone community and get the full member experience.
Join For Freepreviously 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/
Opinions expressed by DZone contributors are their own.
Comments