Clustered Embedding of Massive Social Networks

Abstract — The explosive growth of social networks has created numerous exciting research opportunities. A central concept in the analysis of social networks is a proximity measure, which captures the closeness or similarity between nodes in the network. Despite much research on proximity measures, there is a lack of techniques to efficiently and accurately compute proximity measures for large-scale social networks. In this paper, we embed the original massive social graph into a much smaller graph, using a novel dimension-ality reduction technique termed Clustered Spectral Graph Embed-ding. We show that the embedded graph captures the essential clus-tering and spectral structure of the original graph and allow a wide range of analysis to be performed on massive social graphs. Ap-plying the clustered embedding to proximity measurement of so-cial networks, we develop accurate, scalable, and flexible solutions to three important social network analysis tasks: proximity estima-tion, missing link inference, and link prediction. We demonstrate the effectiveness of our solutions to the tasks in the context of large real-world social network datasets: Flickr, LiveJournal, and My-Space with up to 2 million nodes and 90 million links