The Mont Blanc of Twitter: Identifying Hierarchies of Outstanding Peaks in Social Networks

The visualization of social networks is often hindered by their size as such networks often consist of thousands of vertices and edges. Hence, it is of major interest to derive compact structures that represent important connections of the original network. In order to do so, we transfer concepts from the realm of orometry to graphs. These concepts are originally designed to identify outstanding mountain peaks and to provide a small set of key points and relationships between them that are representative for the complete mountain landscape. With the adoption to social networks, it is possible to derive family trees of important vertices and thus to represent key connections between them. Our approach consist of two steps. We first use a novel method for discarding edges that stand for weak connections. This is done such that the connectivity of the network is preserved. Then, we identify the important peaks in the network and the key saddles, i.e., the lower points that connect them. This gives us a compact network that displays which peaks are connected through which saddles. Additionally, a natural hierarchy on the peaks arises by the question which higher peak comes after the saddle, yielding to chains of peaks with increasing heights. This line parent hierarchy provides the means for a completely new navigation paradigm between important vertices. Our experiments on Twitter users and academic collaboration networks show that networks with hundreds or thousands of edges can be condensed to a small set of vertices and key connections.Comment: 12 pages, 8 figure