How many knows relationships do you have per person?
I think you should also check your configuration, 4GB of RAM is a bit on the low side, you might end up using swap all the time.
You should have enough non-heap RAM for some decent memory mapping of your store-files
And enough heap for sensible high level caches (e.g. 4G-8G HEAP)
So in total a machine with 16-32G heap would make more sense.
Also Upgrade to Neo4j 2.0 to have a stable baseline.
And if you add many friends at once I would do all those rel-checks at once too, so instead of iterating over all rels 100 times and checking them against a single person.
You iterate over them once and remove already existing friends from a hashset.
something like:
Set<Node> filterNewFriends(Set<Node> potentialFriends, Node underlyingNode) {
for (Relationship rel : underlyingNode.getRelationships(Direction.OUTGOING,KNOW)) {
potentialFriends.remove(rel.getEndNode());
}
return potentialFriends;
}
and then only create relationships to all those friends that have been returned.