Lowell Trott, one of the theory students here at UCI, successfully defended his thesis yesterday. Lowell's Ph.D. advisor is Mike Goodrich, but I've also worked with him on several publications related to both social networks and road networks. (Although the vertices in road networks are not people, the networks still come from a social structure.) Specifically, he:
Showed that road networks have the property that any line of sight crosses only a small number of roads, both empirically and in a mathematical model of these networks based on circle packings;
Developed data structures for taking a census of different kinds of small subgraphs in a social network, with efficiency bounded by a parameter that is small for real-world networks;
Showed how greedy routing can be used by actors in a social network using estimates of the distance to a destination based on shared characteristics rather than geometric coordinates; and
Used gravitational forces to move the more important vertices in a social network towards the center of its drawing, also providing more compact graph layouts that allow the size of individual features to be larger relative to the overall layout area.
My understanding is that he has accepted a position at Google, starting in the fall. Congratulations, Lowell!
Thank you for sharing it through arxiv! These papers look quite interesting! I am especially eager to read the first one, with an application to the US roads. :)