Sökning: WFRF:(Lee Jiyoung)
> (2012) >
Parallel clustered ...
Parallel clustered low-rank approximation of graphs and its application to link prediction
-
- Sui, Xin (författare)
- University of Texas at Austin, USA
-
- Lee, Tsung-Hsien (författare)
- University of Texas at Austin, USA
-
- Whang, Joyce Jiyoung (författare)
- University of Texas at Austin, USA
-
visa fler...
-
- Savas, Berkant, 1977- (författare)
- Linköpings universitet,Beräkningsvetenskap,Tekniska högskolan
-
- Jain, Saral (författare)
- University of Texas at Austin, USA
-
- Pingali, Keshav (författare)
- University of Texas at Austin, USA
-
- Dhillon, Inderjit S. (författare)
- University of Texas at Austin, USA
-
visa färre...
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2012
- 2012
- Engelska.
-
Ingår i: Proceedings of the International Workshop on Languages and Compilers for Parallel Computing. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783642376573 - 9783642376580 ; , s. 76-95
- Relaterad länk:
-
http://www.cs.utexas...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Social network analysis has become a major research area that has impact in diverse applications ranging from search engines to product recommendation systems. A major problem in implementing social network analysis algorithms is the sheer size of many social networks, for example, the Facebook graph has more than 900 million vertices and even small networks may have tens of millions of vertices. One solution to dealing with these large graphs is dimensionality reduction using spectral or SVD analysis of the adjacency matrix of the network, but these global techniques do not necessarily take into account local structures or clusters of the network that are critical in network analysis. A more promising approach is clustered low-rank approximation: instead of computing a global low-rank approximation, the adjacency matrix is first clustered, and then a low-rank approximation of each cluster (i.e., diagonal block) is computed. The resulting algorithm is challenging to parallelize not only because of the large size of the data sets in social network analysis, but also because it requires computing with very diverse data structures ranging from extremely sparse matrices to dense matrices. In this paper, we describe the first parallel implementation of a clustered low-rank approximation algorithm for large social network graphs, and use it to perform link prediction in parallel. Experimental results show that this implementation scales well on large distributed-memory machines; for example, on a Twitter graph with roughly 11 million vertices and 63 million edges, our implementation scales by a factor of 86 on 128 processes and takes less than 2300 seconds, while on a much larger Twitter graph with 41 million vertices and 1.2 billion edges, our implementation scales by a factor of 203 on 256 processes with a running time about 4800 seconds.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- vet (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas