Как проверить Теорию 6 рукопожатий в БД с миллионами юзеров?
графовая БД

neo4j - самая известная
ArangoDB - вам подойдет
1. Шагать надо с 2 сторон
2. Если не влезаете в память, то шагать стоит в "глубину", а не в ширину. (перебор начиная с самых "любвеобильных") (помня о том, что "попасть" надо не во второго, а в одного из его связей, так проще)
К тому же: 
Шаг 0: 1 человек
Шаг 1: 5000 максимум
Шаг 2: 25000000 максимум
Шаг 3: 40000000 максимум - уперлись

3 запроса, таблички теоретически большие, практически - все это перемалывается без проблем.