http://www.iop.org/EJ/article/1367-2630/11/6/063019/njp9_6_063019.html

Border detection in complex networks

Bruno A N Travençolo, Matheus Palhares Viana, and Luciano da Fontoura Costa

The open-access New Journal of Physics has a paper on detecting the interior and exterior nodes of a complex graph using a concept called "diversity entropy". Diversity entropy measures how many different walks of a particular length can reach other nodes in the network. Since exterior nodes of a graph will have fewer options to reach other nodes, the diversity entropy measure can identify them.  The illustration below shows the concept quite succinctly.

The large unstructured graph is the most important data structure in the world today (hint, think social networks, or the Internet itself). The diversity entropy measurement is potentially a breakthrough analysis tool; it offers an extraordinarily interesting way to partition a graph as a precursor to other hard analyses such as cycle detection.