[Neo4j] Scaling Characteristics of Centrality Algorithms

[Rushan]

Hi,

I am experimenting with noe4j for some classicla graph algorithms such
as shortest path and centrality.

The component page for graph-alo-0.6 does mention that centrality
algorithms cannot scale to very large graphs. Judging from what is
being discussed in this list, a 78K node(and about 75K edges of the
same connection type) graph is probably not on the large side.
However, I am seeing some uncharacteristic(relative to algorithm
complexity) performance degradation. Some numbers below

#Nodes, # Edges, Betweenness Computation Time(sec)
20190, 19410, 7
29652, 38173, 19
59372, 57064, 75
78219, 75369, 1402

The betweenness is computed based on single source BFS. However, the
result above scales a lot worse than what I would expect from BFS. At
1402 second(23 min), the largest graph (which is less than 2x the one
smaller than that) is almost 20 times slower.

This graph has almost equal number of nodes and edges.i.e. a graph
with may small trees. Could this have an adverse effect?

Any suggestions on how to program this for graphs larger than 100K nodes?

Thanks!

Rushan

Machine info, JVM, properties and code excerpt below.

Machine
CentOS 5.4 64 bit, 72G Ram Quad-Core Intel® Xeon®

JVM
-d64 -server -Xms512m -Xmx3000m -XX:NewRatio=2 -XX:+UseConcMarkSweepGC
-XX:PermSize=128m -XX:MaxPermSize=512m

Neo4j Properties
neostore.nodestore.db.mapped_memory=25M
neostore.relationshipstore.db.mapped_memory=100M
neostore.propertystore.db.mapped_memory=10M
neostore.propertystore.db.strings.mapped_memory=1M
neostore.propertystore.db.arrays.mapped_memory=20M
use_adaptive_cache=YES

Code Excerpt
		SingleSourceShortestPath<Integer> singleSourceShortestPath = new
	    	        SingleSourceShortestPathBFS(null, Direction.BOTH,
ConnectionType.X);
		betweennessCentrality = new
BetweennessCentrality<Integer>(singleSourceShortestPath, targetNodes);
		Transaction tx = embeddedDB.beginTx();
		try {
                        ... ...
			betweennessCentrality.reset();			
			betweennessCentrality.calculate();
                        ... ...
		} finally {
			tx.finish();
		}