Граф

Теория графов изобретена Леонардом Эйлером ...
в ходе решения задачи о 7 мостах в Кёнигсберге...
и представлена в Петербуржской Академии 26 августа 1735-го года.

Типы графов

Множественный, нагруженный, с поименованными вершинами, с поименованными ребрами, атрибутированные вершины и ребра, направленный и ненаправленный, связанный, хипер-граф, дерево, циклический и ациклический, планарный etc ...

Граф дорог, нагруженный времен на отрезках

Граф дорог: путешествие

Социальная сеть aka stay in touch ...

Facebook, Twitter, LinkedIn, ВКонтакте, Одноклассники етс етс ...

Граф: ноды - люди (компании), ребра - "дружу", "служу", "работаю", "смотрю", "читаю" ...

Алгоритмы - рекомендации:
* А не хочешь ли дружить с Петей, ибо с ним дружит твой друг Вася ...
* Люди твоего семейного положения, возраста и достатка ... любят смотреть рекламу о машинах ...

Теория шести рукопожатий

Twitter: 3.43 / Facebook: 4.74 (source:Six degrees of separation)

Компьютерная сеть aka The Net ...

Интернет сам по себе - компьютеры, свитчи, таблицы маршрутизации, пользователи ... сайти и линки сайтов

Алгоритм PageRank и индекс цитирования сайтов

Новые термины: Internet of Things / Web of Things

Интересная презентация: Using A Graph Database To Power The “Web of Things” by Rick Bullotta and Emil Eifrem

Трансформации типов графов

Хранение графов: в реляционной базе

Хранение графов: в JSON / документной базе

Хранение графов: в xml

GraphDB: определение

Если графы можно хранить в любой базе, зачем термин graph db?

"Официального" определения не существует.

@twarko определяет это как: Граф база - это любое хранилище, реализующее "смежность" без использования индексов (index-free adjacency).

• Каждый элемент (ребро, вершина) напрямую знает о связанных элементах
• Не требуется o(ln(n)) поиск по индексу
• Если граф связан - это атомарная структура данных

Граф ДБ - можно рассматривать как распределенный индекс, когда в каждом элементе живет свой, маленький, кусочек индекса.

Граф ДБ - это о "локальных" вычислениях. Т.е. когда результат определяется "окрестностями" точки. "Глобальное вычисление" - плохо, нужно будет ходить по всем-всем точкам.

Neo4j: NOSQL for the Enterprise

http://neo4j.org/ / wikipedia:Neo4j

Neo4j is a high-performance, NOSQL graph database with all the features of a mature and robust database.

"embedded, disk-based, fully transactional Java persistence engine that stores data structured in graphs rather than in tables"

“For anything with multiple relationships, multiple connections, Neo4j absolutely ROCKS!”
Werner Vogels, CTO of Amazon

http://neotechnology.com / Menlo Park, CA 94025 / 19 Malmo, Sweden

Несколько раз получали венчурный капитал, сейчас 25 человек в 5 странах етс ...

Люди:

Emil Eifrém, CEO @emileifrem

Peter Neubauer, VP Product Management @peterneubauer

Marko A. Rodriguez, Advisor http://markorodriguez.com / @twarko

Tinkerpop / http://tinkerpop.com

Open source software products in the graph space.

Blueprints: набор API ( a-la JDBC но для Graph DB :) ) - реализации

Gremlin: язык обхода графов, работает со всеми базами у которых есть blueprints обертка

Rexter: превращаем BluePrints базу в REST server (http://localhost:8182/graphs/tinkergraph/vertices/1)

Pipes: библиотека для конструирования процессов обработки

Furnace: библиотека алгоритмов над графами

Frames: java object - graph bridge (ORM для графов)

gremlin> t = new TinkerGraph('/tmp/tinker');
==> tinkergraph[vertices:0 edges:0 directory:/tmp/tinker]
gremlin> t.addVertex(0)
==> v[0]
gremlin> t.v(0).setProperty("name","mongo")
==> 
gremlin> t.v(0).setProperty("age", 5 ) 
==> 
gremlin> t.v(0).map
==> name=mongo
==> age=5
gremlin> t.addVertex(1)
==> v[1]
gremlin> t.v(1).setProperty("name", "pulser" )
==> 
gremlin> t.addEdge(0, t.v(1), t.v(0), "uses")
==> e[0][1-uses->0]
gremlin> t.v(1).out
==> v[0]
gremlin> t.v(1).in
gremlin> t.v(1).outE
==> e[0][1-uses->0]

gremlin> t = TinkerGraphFactory.createTinkerGraph()
==> tinkergraph[vertices:6 edges:6]

gremlin> t.V.name
==> lop
==> vadas
==> marko ...
gremlin> t.E
==> e[10][4-created->5]
==> e[7][1-knows->2]
==> e[9][1-created->3] ...
gremlin> v = t.v(1)
==> v[1]
gremlin> v.out
==> v[2]
==> v[3]
==> v[4]
gremlin> v.outE
==> e[7][1-knows->2]
==> e[9][1-created->3]
==> e[8][1-knows->4]
gremlin> v.out.name
==> vadas
==> lop
==> josh
gremlin> v.out('knows').name
==> vadas
==> josh
gremlin> v.out('knows').filter{it.age > 30}.out('created').name
==> ripple
==> lop 

Хочу данных!

thru http://markorodriguez.com

MovieLens Data Sets Aug 2011

• MovieLens 100k - Consists of 100,000 ratings from 1000 users on 1700 movies.
• MovieLens 1M - Consists of 1 million ratings from 6000 users on 4000 movies.
• MovieLens 10M - Consists of 10 million ratings and 100,000 tag applications applied to 10,000 movies by 72,000 users.

HetRec 2011 Data Sets May 2011

• Delicious bookmark data (105,000 bookmarks from 1867 users)
• Last.fm music artist data (92,800 artist listening records from 1892 users)
• MovieLens rating data with IMDb and Rotten Tomatoes links (86,000 ratings from 2113 users)

MovieLens

==> movies.dat <==
MovieID::Title::Genres
1::Toy Story (1995)::Animation|Children's|Comedy
2::Jumanji (1995)::Adventure|Children's|Fantasy

==> ratings.dat <==
UserID::MovieID::Rating::Timestamp
1::1193::5::978300760
1::661::3::978302109

==> users.dat <==
UserID::Gender::Age::Occupation::Zip-code
1::F::1::10::48067
2::M::56::16::70072

wc -l *.dat
    3883 movies.dat
 1000209 ratings.dat
    6040 users.dat
 1010132 total

Разделитель ::

imdb данные

pulser$ wc -l *.dat
  231743 movie_actors.dat
   10198 movie_countries.dat
   10156 movie_directors.dat
   20810 movie_genres.dat
   49168 movie_locations.dat
   51796 movie_tags.dat
   10198 movies.dat
   13223 tags.dat
  855599 user_ratedmovies-timestamps.dat
  855599 user_ratedmovies.dat
   47958 user_taggedmovies-timestamps.dat
   47958 user_taggedmovies.dat
 2204406 total
head -n 5 movies.dat | awk 'BEGIN{FS="[\t]"} {print $1,$2,$3;}'
id title imdbID
1 Toy story 0114709
2 Jumanji 0113497
3 Grumpy Old Men 0107050
4 Waiting to Exhale 0114885
head -n 5 movie_actors.dat 
movieID actorID actorName   ranking
1   annie_potts Annie Potts 10
1   bill_farmer Bill Farmer 20
1   don_rickles Don Rickles 3
1   erik_von_detten Erik von Detten 13 

Создаем новую базу neo4j

Парсим входные файлы

"Гуляем" по данным

Надо еще подготовить уникальный список актеров:

iconv -f ISO-8859-1 -t utf8 movie_actors.dat 
    | awk ' BEGIN{FS="[\t]";OFS="\t"} { print $2,$3; }' 
    | sort 
    | uniq > mine_actors.dat

head mine_actors.dat 
1000057-don_adams   Don Adams
10000635-joel_michaely  Joel Michaely
10000643-john_hensley   John Hensley

NB: neo4j не дает назначить id вершинам, так что нужен "маппинг" из id файлов в ноды...

создаем проект в IDEA
прописываем библиотеки из 
  /usr/local/Cellar/neo4j/community-1.5/libexec/lib/

geronimo-jta_1.1_spec-1.1.1.jar
lucene-core-3.1.0.jar
neo4j-community-1.5.jar
neo4j-cypher-1.5.jar
neo4j-graph-algo-1.5.jar
neo4j-graph-matching-1.5.jar
neo4j-jmx-1.5.jar
neo4j-kernel-1.5.jar
neo4j-lucene-index-1.5.jar
neo4j-shell-1.5.jar
neo4j-udc-1.5.jar
org.apache.servicemix.bundles.jline-0.9.94_1.jar
scala-library-2.9.0-1.jar
server-api-1.5.jar

public class Loader2 extends TestCase {

    private static final Logger log = Logger.getLogger(Loader2.class);
    
    public static final Pattern TAB_SPLITTER = Pattern.compile("\t");
    public static final Pattern SPLIT_COMMA = Pattern.compile(":");

    EmbeddedGraphDatabase graphDb = null;
    Transaction transaction = null;

    public void setUp() throws Exception {
        super.setUp();
        if (graphDb == null) {
            graphDb = new EmbeddedGraphDatabase("/Users/pulser/neo4j/imdb/graph.db");
            transaction = graphDb.beginTx();
        }
    }

    protected void tearDown() throws Exception {
        transaction.success();
        transaction.finish();
        graphDb.shutdown();
        super.tearDown();
    }

public void testLoadActors() throws Exception {
  final Fu<String, Void> callable = new Fu<String, Void>() {
    public Void apply(final String line) {
      try {
        final String[] parts = TAB_SPLITTER.split(line);
        if (parts.length != 2) {
            return null;
        }

        final String code = parts[0];
        final String name = parts[1];

        final Node v = graphDb.createNode();
        v.setProperty("code", "actor:" + code);
        v.setProperty("name", name);

        return null;
      } catch (Exception e) {
        System.out.print("." + line + ".");
        throw new RuntimeException(e);
      }
    }
  };
  load(false, "mine_actors.dat", callable);
}

public void testLoadRelations() throws Exception {

  final Pair<Map<String, Long>, Map<Long, Long>> p = loadMapping();
  final Map<String, Long> actors = p.first;
  final Map<Long, Long> movies = p.second;

  load(true, "movie_actors.dat", new Fu<String, Void>() {
    public Void apply(final String line) {
      final String[] parts = TAB_SPLITTER.split(line);
      if (parts.length != 4) {
          return null;
      }
      final long movie = Long.valueOf(parts[0]);
      final String actorCode = parts[1];
      // parts[2]
      final String rank = parts[3];
      try {
        final Node movieNode = graphDb.getNodeById(movies.get(movie));
        final Node actorNode = graphDb.getNodeById(actors.get(actorCode));
        final Relationship edge = movieNode
            .createRelationshipTo(actorNode, RelTypes.STARRED_BY);
        edge.setProperty("rank", rank);
      } catch (Exception e) {
        log.error(e.getMessage() + " for " + line);
      }

      return null;
    }
  }); }

public void testSearch() throws Exception {
  for (final Node node : graphDb.getAllNodes()) {
    if (node.hasProperty("name")) {
      final String name = node.getProperty("name").toString();
      if (name.contains("Clooney")) {
          System.out.println(node.getId() + " name = " + name);
      }
    } } }

Теперь подсунем новую базу серверу ...

pulser$ cp -r ~/neo4j/imdb/graph.db .

И запустим сервер ...

neo4j start 
open http://localhost:7474/

gremlin> c = g.v(33317)
==> v[33317]
gremlin> c.name
==> George Clooney
gremlin> c.in.out.filter({it.name == 'Brad Pitt'})
==> v[13191]
==> v[13191]
==> v[13191]
==> v[13191]
gremlin> c.in.out.filter({it.name == 'Brad Pitt'}).back(2).title
==> Burn After Reading
==> Ocean's Thirteen
==> Ocean's Twelve
==> Ocean's Thirteen
==> Burn After Reading
==> Ocean's Eleven
==> Ocean's Eleven

Литература

https://github.com/tinkerpop - документация по Tinkerpop продуктам

http://neo4j.org/learn/ - документация и туториалы по Neo4j

Writings и Lectures by Marko Rodriguez

Интернет университет: Введение в теорию графов

Твиттер по hash-tag #neo4j

InfoQ.com по neo4j

DZone NoSQL microzone

Итого

Теория графов вышла из "математическая" абстракция в нашу жизнь.

Вычисления в графах ориентированы на "локальность".

Специальный базы созданы и доступны для работы с графами.

В свободном доступе есть массивы данных для игры с алгоритмами.

Создать программу для работы с Neo4j можно за несколько часов.