Searching for a Common Ancestor
There is a common interview prep question that goes by “the most recent common ancestor” (MRCA) problem. The question is usually stated like this: Given two arbitrary nodes in a binary tree, find a common ancestor node between the two nodes (a node is a common ancestor if there exists paths starting from the node and down to both of the two initial nodes). Though this question has a simple O(log(n)) solution, there is another greater question that can be built off of the original question which is not quite as trivial: If we were to draw a family tree for every human being on this earth, how far back in this tree must we go to find a common ancestor for all(~100%) human beings?
A study conducted by researchers from MIT and Yale provides some insight into solving the problem through two approaches: a purely probabilistic model involving a starting population and random mating across some fixed time. The team also made a more elaborate model “designed to capture historical population dynamics in a more realistic way” and they “analysed computationally through Monte Carlo simulations” to reach an astounding conclusion: from the results of simulation it is highly probable that the MRCA of all human beings on the planet right now lived just a few thousand years ago.
We now take a step back and observe what is going on. As we have learned in class, in a complex network of interconnected people (ie. a graph, which a family tree will become if you give it enough instances due to mating between differing levels/generations, mating between nth cousins etc.), it is often the case that two arbitrary nodes are connected through a much shorter path relative to the number of nodes included. We can see this phenomena in graphs with the 6 degrees of Kevin Bacon game, nth connections between Linkedin profiles, etc. Although a family graph may not be as evenly connected as a social network graph (due to restrictive conditions for direct connections between nodes such as temporal, geographical, and social constraints) if we consider migrations of different groups observed during the appropriate time periods across the globe, the most recent common ancestor can be found much closer than ln(n)/log(2) (ie. log base 2 of n). This result may sound astounding at first but from lessons learned in class we see that this is in fact a nature of complex network structures such as the family graph.
Source:
http://www.nature.com/nature/journal/v431/n7008/full/nature02842.html