1. A computer-implemented method of partitioning a graph database, wherein the graph database includes nodes connected to one another, comprising: determining a node type indicating a type of node that is to be used as mapped nodes; and upon receiving a new node, placing the new node in a partition according to one or more property values associated with the new node if it is a mapped node, and placing the new node in a partition according to at least one of: its number of connections to other nodes, depth of its connections to other nodes, and attributes of the other nodes to which the new node will be connected if the new node is not a mapped node.