3 ms·
Facebook Graph Theory
- espeed 15y agoYou can write these type of algorithms easily with a graph-programming language like Gremlin (https://github.com/tinkerpop/gremlin/wiki https://github.com/tinkerpop/gremlin/wiki): g = new Neo4jGraph('/tmp/neo4j') // calculate basic collaborative filtering for vertex 1 m = [:] g.v(1).out('likes').in('likes').out('likes').groupCount(m) m.sort{a,b -> a.value <=> b.value} // calculate the primary eigenvector (eigenvector centrality) of a graph m = [:]; c = 0; g.V.out.groupCount(m).loop(2){c++ < 1000} m.sort{a,b -> a.value <=> b.value} When a user signs in with Facebook or Twitter, you can load their friends and followers into a graph database such as Neo4j and then use Gremlin to run these type of social-graph algorithms. Graph DBs are fast in general because there is no external index lookup during traversals (the index containing adjacent nodes are located within the node). Pair that with local-rank (http://markorodriguez.com/2011/03/30/global-vs-local-graph-ranking/ http://markorodriguez.com/2011/03/30/global-vs-local-graph-r...), and you can do real-time ranking and analysis.
- brent 15y agoThis blog post seems to be copied from http://20bits.com/articles/graph-theory-part-iii-facebook/ http://20bits.com/articles/graph-theory-part-iii-facebook/ without any attribution. It was also posted on yc only two weeks ago (see http://news.ycombinator.com/item?id=2912073 http://news.ycombinator.com/item?id=2912073 for commentary).