Статьи

Шесть градусов Кевина Бэкона с использованием Neo4j и Ruby

Январь 8, 2019

Ранее я показал вам, как настроить Neo4j для работы с Ruby и как найти рекомендуемых друзей в социальной сети. Как насчет того, чтобы узнать, как вы подключены к кому-то за пределами сети друзей? Вы помните концепцию шести степеней разделения ? Нет, как насчет шести градусов Кевина Бэкона ?

Рекламный ролик кредитной карты объясняет, как это работает:

Актер Кевин Бэкон хочет выписать чек, чтобы купить книгу, но клерк спрашивает его удостоверение личности, которого у него нет. Он уходит и возвращается с группой людей, затем говорит клерку: «Хорошо, я был в фильме с дополнительной, Юнис, чей парикмахер Уэйн посещал воскресную школу с отцом О’Ниллом, который играет в ракетбол с доктором Санджай, который недавно удалил приложение Кима, который бросил тебя на втором курсе. Итак, вы видите, мы практически братья.


Возможно, вы не голливудский актер, но если вы использовали сайт социальной сети Linked In, вы увидели эту функцию в их окне «Как вы подключились». Итак, как мы можем сделать это с Ruby и 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

В этой функции мы даем Neo4j два узла и просим его выяснить, как они связаны через дружбу до глубины 4 (этого достаточно для нашего примера). Затем мы получаем свойство name этих узлов.

Мы использовали алгоритм «allSimplePaths», чтобы найти все способы их соединения, но если вы хотите выиграть раунд из шести степеней Кевина Бэкона, вам просто нужно найти кратчайший путь.

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 есть несколько графических алгоритмов , посмотрите на них в документации.

Это не слишком сложно, но если вы хотите немного сахара, то вы идете:

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

Незначительное изменение последней части, чтобы получить только кратчайший путь:

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

 Вы можете взглянуть на различные функции пути в Neography, чтобы получить разные результаты.

Найдите меня и многих других поклонников графиков в Neo4j Google Group .

Источник: http://maxdemarzi.com/2012/01/05/how-youre-connected-to-kevin-bacon/

40
Share: