[Neo4j] Scaling Characteristics of Centrality Algorithms
Rushan
rushan.chen at gmail.com
Fri Jul 23 02:11:45 CEST 2010
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();
}
More information about the User
mailing list