bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.

One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is $k$ and the average branching factor in the network is $p$ then we explore $O(p^k/2^)$ nodes instead of $O(p^k^)$ nodes.

The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.
One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet.  This way we only go through $O(p^k/2^)$ nodes.

This approach works well on both path finding problems on explicit graphs and on implicit state graphs like ones in games.