@DeathByVisualStudio: I suspect people who use Facebook will simply search using natural language queries. There will be a search box and a "search" button...

There's some great information about graph databases, graph traversal and a little graph theory here: http://channel9.msdn.com/Shows/Going+Deep/YOW-2012-Marko-Rodriguez-Graph-Systems-and-Databases

Granny won't tell herself "I'm going to do a graph traversal over my Facebook graph data". She'll simply just search for something.....

C