What are the "right" use cases for a graph database?
- Mapping applications. "Find me the shortest path between any two nodes in a connected graph." This would be difficult to solve algorithmically using a RDBMS. In something like Google Maps the "shortest path" isn't necessarily the ultimate goal. You may want the "cheapest" path instead (no toll roads or only 4 lane highways).
- Recommendation generation systems. If you purchase x online, what have others purchased as well and we can display that for upselling purposes.
- Social networking like LinkedIn. How does a person relate to another person? This is another example of a graph.
- Data mining to find the interactions among nodes.
Neo4j is the graph data store I've played with. It uses untyped datatypes and the data is stored much like it would be in a document db...in an ad hoc fasion. Relationships are declared based on the Edges between nodes.