Distributed Algorithms for k-Truss Decomposition
Date Issued
2014
Date
2014
Author(s)
Chen, Pei-Ling
Abstract
k-truss, a type of cohesive subgraphs of a network, is an important measure
for a social network graph. However, with the emergence of large online
social networks, the running time of the traditional batch algorithms for
k-truss decomposition is usually prohibitively long on such a graph with billions
of edges and millions of vertices. Moreover, the size of a graph becomes
too large to load into the main memory of a single machine. Currently, cloud
computing has become an imperative way to process the big data. Thus, our
aim is to design a scalable algorithm of k-truss decomposition in the scenario
of cloud computing. In this thesis, we first improve the existing distributed
k-truss decomposition in the MapReduce framework. We then propose a series
of theoretical basis for k-truss and use them to design an algorithm based
on graph-parallel abstractions. Our experiment results show that our method
in the graph-parallel abstraction significantly outperforms the methods based
on MapReduce in terms of running time and disk usage.
Subjects
k叢集
平行運算
社群網路
大數據
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R01942069-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):81737c6522fbe5d7f0a8e44f71596ca6