Emergence of hierarchy in directed online social networks

Social hierarchy and stratification among humans is a well studied concept in sociology. The popularity of online social networks presents an opportunity to study social hierarchy for different types of people, and at different scales. We conjecture that people form connections in social network based on their perceived social hierarchy; as a result, the edge directions in directed social networks can be leveraged to infer hierarchy. In this paper, we define a measure of hierarchy in a directed social network, and present an efficient algorithm to compute this measure. We validate our measure using ground truths including Wikipedia notability score. We use this measure to study hierarchy in several directed online social networks including Twitter, Delicious, Flickr, and curated lists of several types of people based on different occupations, and different organizations. Our experiments how hierarchy emerges as the networks grows on different online social networks. We show that the degree of stratification in a network is bounded and does not increase after the graph has become large.Technical report DCS-TR-67