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.

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.

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.

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