Clustered Embedding of Massive Social Networks
2012 (English)In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2012, , 27 p.331-342 p.Conference paper (Other academic)
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 a social network. Despite much research on proximity measures, there is a lack of techniques to eciently and accurately compute proximity measures for large-scale social networks. In this paper, we develop a novel dimensionality reduction technique, called clustered spectral graph embedding, to embed the graphs adjacency matrix into a much smaller matrix. The embedded matrix together with the embedding subspaces capture the essential clustering and spectral structure of the original graph and allows a wide range of analysis tasks to be performed in an ecient and accurate fashion. To evaluate our technique, we use three large real-world social network datasets: Flickr, LiveJournal and MySpace, with up to 2 million nodes and 90 million links. Our results clearly demonstrate the accuracy, scalability and exibility of our approach in the context of three importantsocial network analysis tasks: proximity estimation, missing link inference, and link prediction.
Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2012. , 27 p.331-342 p.
, ACM SIGMETRICS Performance Evaluation Review, ISSN 0163-5999 ; Vol. 40, Iss.1
Other Computer and Information Science
IdentifiersURN: urn:nbn:se:liu:diva-86053DOI: 10.1145/2254756.2254796ISBN: 978-1-4503-1097-0OAI: oai:DiVA.org:liu-86053DiVA: diva2:574698
the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, June 11-15, London, UK