Java Network / Graph / Data Mining Алгоритм «Арсенал» на Neo4j: Часть 2

Изучение социальных сетей восходит, по крайней мере, к древним грекам, но сегодня мы не вернемся так далеко … только к 1977 году. Человек по имени Уэйн Захари записал взаимодействия клуба каратэ в университете в течение 2 лет. За это время возник конфликт между администратором и инструктором, а клуб распался на две части. Оказывается, вы можете предсказать, к какому клубу будет принадлежать каждый член, построив график их взвешенных отношений и разделив его по минимальному разрезу .

Мы работаем с Neo4j , и вы все знаете, что Neo знает кунг-фу , поэтому мы сделаем что-то немного другое. Плюс, смотреть на кластер из двух узлов — это немного неубедительно … давайте пойдем дальше. Мы собираемся использовать Neo4j с файлами JUNG, уже находящимися в каталоге lib. Обратитесь к JUNG в Neo4j — Часть 1, если вам нужна помощь в этом. Давайте создадим наш график:

def create_graph
  neo = Neography::Rest.new
  graph_exists = neo.get_node_properties(1)
  return if graph_exists && graph_exists['name']

  names = %w[Aaron Achyuta Adam Adel Agam Alex Allison Amit Andreas Andrey 
             Andy Anne Barry Ben Bill Bob Brian Bruce Chris Corey 
             Dan Dave Dean Denis Eli Eric Esteban Ezl Fawad Gabriel 
             James Jason Jeff Jennifer Jim Jon Joe John Jonathan Justin 
             Kim Kiril LeRoy Lester Mark Max Maykel Michael Musannif Neil]

  commands = names.map{ |n| [:create_node, {"name" => n}]}

  names.each_index do |from| 
    commands << [:add_node_to_index, "nodes_index", "type", "User", "{#{from}}"]
    connected = []

    # create clustered relationships
    members = 5.times.collect{|x| x * 10 + (from % 10)}
    members.delete(from)
    rels = 1 + rand(4)
    rels.times do |x|
      to = members[x]
      connected << to
      commands << create_rel(from, to) unless to == from
    end    

    # create random relationships
    rels = 1 + rand(4)
    rels.times do |x|
      to = rand(names.size)
      commands << create_rel(from, to) unless (to == from) || connected.include?(to)
    end    
   end
   batch_result = neo.batch *commands
end

Я снова использую первые 50 имен из группы Graph DataBase — Chicago Meet-Up . Вы уже видели, как я делаю это один или два раза, поэтому я не буду подробно останавливаться на этом, но, как вы можете видеть выше, я заставляю небольшие группы отношений существовать вместе со случайными отношениями. Наши отношения имеют свойство weight, поэтому метод create_rel выглядит так:

def create_rel(x,y,z= 1 + rand(10))
  [:create_relationship, "knows", "{#{x}}", "{#{y}}", {:weight => z}]
end

Наша визуализация предполагает получение списка узлов, уже входящих в группы, и списка отношений, которые включают его силу. Объект JSON выглядит так:

{"nodes":[{"name":"Myriel","group":1},
          {"name":"Napoleon","group":1},
          {"name":"Mlle.Baptistine","group":2}],
 "links":[{"source":1,"target":0,"value":1},
          {"source":2,"target":0,"value":8},
          {"source":3,"target":0,"value":10}]
}

Получить наши узлы довольно просто, мы будем использовать Gremlin, чтобы получить все, кроме корневого узла.

def get_nodes
  neo = Neography::Rest.new
  neo.execute_script("g.V.filter{it.id != 0}.transform{[it.id,it.name]}")
end 

Установить отношения довольно легко, чтобы их изменить, мы будем использовать Cypher.

def get_relationships
  neo = Neography::Rest.new
  cypher_query =  " START a = node:nodes_index(type='User')"
  cypher_query << " MATCH a-[r:knows]-b"
  cypher_query << " RETURN ID(a), ID(b), r.weight"
  neo.execute_query(cypher_query)["data"]
end 

Теперь самое интересное. Чтобы получить наши кластеры, мы будем использовать класс кластера напряжения. Мы не хотим, чтобы корневой узел мешал, поэтому мы создадим подграф, используя TinkerGraph, который исключает его (вы могли бы сделать что-то похожее на кластер, только небольшую часть большего графа). Затем мы передаем этот график в GraphJung и настраиваем наш VoltageClusterer, чтобы попытаться получить 10 кластеров для нас.

def get_voltage_clusters
  neo = Neography::Rest.new
  lg = neo.execute_script("import edu.uci.ics.jung.algorithms.cluster.VoltageClusterer;
                            to = new TinkerGraph();
                            g.V.filter{it.id != 0}.sideEffect{toVertex = to.addVertex(it.getId()); 
                                           ElementHelper.copyProperties(it, toVertex);
                            }.iterate();   
                            g.E.sideEffect{toEdge = to.addEdge(it.getId(), 
                                                    to.v(it.getOutVertex().getId()), 
                                                    to.v(it.getInVertex().getId()),
                                                    it.getLabel());
                                            ElementHelper.copyProperties(it, toEdge);
                            }.iterate();
                            vc = new VoltageClusterer(new GraphJung(to), 10);
                            vc.cluster(10).id;
                            ")
end

Затем мы можем собрать все это вместе для создания этого объекта JSON.

get '/cluster' do
  clusters = Hash.new
  get_voltage_clusters.each_with_index {|item, index| item.each{|i| clusters[i.to_i] = index + 1} }
  nodes = get_nodes.map{|n| {"name" => n[1], "group" => clusters[n[0]]}}
  relationships = get_relationships.map{|r| {"source" => r[0] - 1, "target" => r[1] - 1, "value" => r[2]} }
  {:nodes => nodes, :links => relationships}.to_json
end	

Наша визуализация была сделана Майком Босток с D3.js . Как всегда, код на Github . Нажмите на изображение ниже, чтобы увидеть живой пример на Heroku .

Примечание. В версии Heroku используется предварительно созданный файл JSON.