The Barabási-Albert(BA) model plays an important role in many domains since it can generate a scale-free graph having the degree exponents that real graphs have. However, due to the dependency among the edges generated at different time steps, the exact generation methods support only a single thread, and the parallel generation methods generate a graph only approximately. There is no method that can generate a large-scale graph following the BA model strictly using multiple threads. We propose a fast, exact, and scalable graph generation method called LineageBA that solves the above issue. We propose the concept of lineage relationship for reducing memory usage significantly and the detection of hash collisions for parallelizing the graph generation. Through extensive experiments, we have shown that LineageBA significantly outperforms the state-of-the-art BA graph generation methods and easily generates 2.5 trillion edges within four hours using a small cluster of PCs.

Nowadays, many researchers and industry groups often suffer from the lack of a variety of large-scale real graphs. Although a lot of synthetic graph generation methods,(or models) such as RMAT and BA have been developed, their output graphs tend to be quite different from real-world graphs in terms of graph properties. There are a few graph upscaling methods such as Gscaler, they still fail to preserve important properties of the original graph and fail to upscale due to out of memory or too long runtime. In this paper, we propose a novel graph upscaling method called EvoGraph that can upscale the original graph with preserving its properties regardless of a scale factor. It determines and attaches new edges to the real graph using the preferential attachment mechanism in an effective and efficient way. Through extensive experiments, we have demonstrated that EvoGraph significantly outperforms the state-of-the-art graph upscaling method Gscaler in terms of preserving graph properties and performance measures such as runtime, memory usage, and scalability.

As many applications encounter exponential growth in graph sizes, a fast and scalable graph generator has become more important than ever before due to lack of large-scale realistic graphs for evaluating the performance of graph processing methods. Although there have been proposed a number of methods to generate synthetic graphs, they are not very efficient in terms of space and time complexities, and so, cannot generate even trillion-scale graphs using a moderate size cluster of commodity machines. Here, we propose an efficient and scalable disk-based graph generator, TrillionG that can generate massive graphs in a short time only using a small amount of memory. It can generate a graph of a trillion edges following the RMAT or Kronecker models within two hours only using 10 PCs. We first generalize existing graph generation models to the scope-based generation model, where RMAT and Kronecker correspond to two extremes. Then, we propose a new graph generation model called the recursive vector model, which compromises two extremes, and so, solves the space and time complexity problems existing in RMAT and Kronecker. We also extend the recursive vector model so as to generate a semantically richer graph database. Through extensive experiments, we have demonstrated that TrillionG outperforms the state-of-the-art graph generators by up to orders of magnitude.

Computing connected components (CC) is a core operation on graph data. Since billion-scale graphs cannot be resident in memory of a single machine, there have been proposed a number of distributed graph processing methods. The representative ones for CC are Hash-To-Min and PowerGraph. Hash-To-Min focuses on minimizing the number of MapReduce rounds, but is still slower than in-memory methods, PowerGraph is a fast and general in-memory graph method, but requires a lot of machines for handling billion-scale graphs. We propose an ultra-fast parallel method DSP-CC, using only a single PC that exploits secondary storage like a PCI-E SSD for handling billion-scale graphs. It can compute connected components I/O efficiently using only a limited size of memory. Our experimental results show that DSP-CC significantly outperforms the representative methods including Hash-To-Min and PowerGraph.

A fast and scalable graph processing method becomes increasingly important as graphs become popular in a wide range of applications and their sizes are growing rapidly. Most of distributed graph processing methods require a lot of machines equipped with a total of thousands of CPU cores and a few terabyte main memory for handling billion-scale graphs. Meanwhile, GPUs could be a promising direction toward fast processing of large-scale graphs by exploiting thousands of GPU cores. All of the existing methods using GPUs, however, fail to process large-scale graphs that do not fit in main memory of a single machine. Here, we propose a fast and scalable graph processing method GTS that handles even RMAT32 (64 billion edges) very efficiently only by using a single machine. The proposed method stores graphs in PCI-E SSDs and executes a graph algorithm using thousands of GPU cores while streaming topology data of graphs to GPUs via PCI-E interface. GTS is fast due to no communication overhead and scalable due to no data duplication from graph partitioning among machines. Through extensive experiments, we show that GTS consistently and significantly outperforms the major distributed graph processing methods, GraphX, Giraph, and PowerGraph, and the state-of-the-art GPU-based method TOTEM.

Computing connected components is a core operation on graph data. Since billion-scale graphs cannot be resident in memory of a single server, several approaches based on distributed machines have recently been proposed. The representative methods are$\mathsf{Hash\hbox{-}To\hbox{-}Min}$and$\mathsf{PowerGraph}$.$\mathsf{Hash\hbox{-}To\hbox{-}Min}$is the state-of-the artdisk-baseddistributed method which minimizes the number of MapReduce rounds.$\mathsf{PowerGraph}$is the-state-of-the-artin-memorydistributed system, which is typically faster than the disk-based distributed one, however, requires a lot of machines for handling billion-scale graphs. In this paper, we propose an I/O efficient parallel algorithm for billion-scale graphs in a single PC. We first propose theDisk-based Sequential access-oriented Parallel processing(DSP) model that exploits sequential disk access in terms of disk I/Os and parallel processing in terms of computation. We then propose an ultra-fast disk-based parallel algorithm for computing connected components,$\mathsf{DSP\hbox{-}CC}$, which largely improves the performance through sequential disk scan andpage-level cache-conscious parallel processing. Extensive experimental results show that$\mathsf{DSP\hbox{-}CC}$1) computes connected components in billion-scale graphs using the limited memory size whereas in-memory algorithms can only support medium-sized graphs with the same memory size, and 2) significantly outperforms all distributed competitors as well as a representative disk-based parallel method.