Distributed (in-memory) graph processing with Akka by Adelbert Chang.
From the post:
Graphs have always been an interesting structure to study in both mathematics and computer science (among other fields), and have become even more interesting in the context of online social networks such as Facebook and Twitter, whose underlying network structures are nicely represented by graphs.
These graphs are typically “big”, even when sub-graphed by things such as location or school. With “big” graphs comes the desire to extract meaningful information from these graphs. In the age of multi-core CPU’s and distributed computing, concurrent processing of graphs proves to be an important topic.
Luckily, many graph analysis algorithms are trivially parallelizable. One example that comes to mind is all-pairs shortest path. In the case of an undirected, unweighted graph, we can consider each vertex individually, and do a full BFS from each vertex.
In this post I detail a general framework for distributed graph processing. I do not use any particular graph library, so my graph class will simply be called Graph. Popular graph libraries for Scala can be found in Twitter’s Cassovary project or the Graph for Scala project.
I will also make use of Derek Wyatt’s submission to the Akka Summer of Blog—”Balancing Workloads Across Nodes with Akka 2“—which provides a nice and simple implementation of a BalancingDispatcher in the context of distributed processing.
If you like Akka, graphs, or both, you will enjoy this post.