Hello, > I've created a small version of the web graph. I'm going to apply different > graph algorithms (components, paths, distances,...) to know this graph better > and better for future investigations. It seems that I have two options: > 1. Using the graph algorithm package: > http://components.neo4j.org/neo4j-graph-algo/ > 2. Using the Gremlin and leverage the algorithms of different graph > libraries: > http://wiki.github.com/tinkerpop/gremlin/working-with-jung-algorithms - > > I don't have complete information about the last option. Would you please > familiar us with it? > Let me know if there are any other option (or library other than JUNG) for > this purpose.
If you have a "small version of a web graph," I would just load the graph up in iGraph, JUNG, NetworkX, etc. and make use of all their standard, graph-analysis algorithm implementations---these implementations are blazing fast, in memory, and have been developed by many people for many years. However, if you start to deal with multi-relational graphs---e.g. webpage--href-->webpage, webpage--contains-->image, person--authored-->webpage, then you can't use these packages as they are not meant for multi-relational graphs. See---(at least read the abstract and introduction to understand the problem): http://arxiv.org/abs/0806.2274 What Gremlin is good for is defining abstract paths through a graph---something that Neo4j algorithms package can not handle. Again, I've said in many emails before---Neo4j is a multi-relational graph (as a data model), but unfortunately, the Neo4j graph algorithm and traverser toolkit do not make sufficient use of this fact. As such, they do not allow for fully expressive, multi-relational graph analysis algorithms. However, unfortunately, the way Gremlin is implemented currently, it is not optimized for speed. With it only being in version 0.2.2, its still very much a "work in progress." By version 1.0, Gremlin's core engine will be rewritten to be orders of magnitude faster. On a positive note, what you get with Gremlin is the ability to calculate the near limitless types of PageRanks/geodesics/eigenvectors/etc. that exist within a multi-relational graph---Lets isolate PageRank ---- e.g. PageRank for all webpages that have greater than 10 outgoing edges, the PageRank of al l webpages where my friends are the authors and there are more than 10 images in the webpage, PageRank for all WebPages that are most two degrees away from Google, PageRank over two steps --- not one. When you start dealing with multi-relational graphs you have to deal with "what do you mean by adjacency?" When you deal with the various ways in which two vertices can be related through long, winding, typed paths through the graph, then you have another problem on your hand that is not solved by standard graph analysis toolkits. See the slide show below for more information on Gremlin and its use cases: http://markorodriguez.com/Lectures_files/cnls-gremlin-2010.pdf In short: 1. use an in-memory graph analysis framework for graphs under ~250 (give or take based on your machine) million elements. 2. use Neo4j graph algos if you have a large graph and you don't require multi-relational graph analysis algorithms. 3. use Gremlin if you have a small graph or are doing a local analysis algorithm that requires Turing-complete path descriptions. Take care, Marko. http://markorodriguez.com _______________________________________________ Neo mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
