Due to the growing need to process large graph and network datasets created by modern applications, recent years have witnessed a surging interest in developing big graph platforms. Tens of such big graph systems have already been developed, but there lacks a systematic categorization and comparison of these systems. This article provides a timely and comprehensive survey of existing big graph systems, and summarizes their key ideas and technical contributions from various aspects. In addition to the popular vertex-centric systems which espouse a think-like-a-vertex paradigm for developing parallel graph applications, this survey also covers other programming and computation models, contrasts those against each other, and provides a vision for the future research on big graph analytics platforms. This survey aims to help readers get a systematic picture of the landscape of recent big graph systems, focusing not just on the systems themselves, but also on the key innovations and design philosophies underlying them.

We propose GraphD, an out-of-core Pregel-like system targeting efficient big graph processing with a small cluster of commodity PCs connected by Gigabit Ethernet, an environment affordable to most users. This is in contrast to some recent efforts for out-of-core graph computation with specialized hardware. In our setting, a vertex-centric program is often data-intensive, since the CPU cost of calculating a message value is negligible compared with the network cost of transmitting that message. As a result, network bandwidth is usually the bottleneck, and out-of-core execution would not sacrifice performance if disk IO overhead can be hidden by message transmission, which is achieved by GraphD through the parallelism of computation and communication. GraphD streams edge and message data on local disks, and thus consumes negligible memory space. For a broad class of Pregel algorithms where message combiner is applicable, GraphD completely eliminates the need of any expensive external-memory join or group-by, which is required by existing systems such as Pregelix and Chaos. Extensive experiments show that GraphD beats existing out-of-core systems by orders of magnitude, and achieves comparable performance to in-memory systems running with adequate memory.

Recovering low-rank matrices from incomplete observations is a fundamental problem with many applications, especially in recommender systems. In theory, under certain conditions, this problem can be solved by convex or non-convex relaxation. However, most existing provable algorithms suffer from superlinear per-iteration cost, which severely limits their applicability to large-scale problems. In this paper, we propose a novel fuzzy double trace norm minimization (DTNM) method for recommender systems. We first present a tractable DTNM model, in which we can integrate both the user social relationship and the user reputation information using a fuzzy weighting way and coupling fuzzy matrix factorization. In essence, our model is a Schatten-1/2 quasi-norm minimization problem. Moreover, we develop two efficient augmented Lagrangian algorithms to solve the proposed problems, and prove the convergence of our algorithms. Finally, we investigate the empirical recoverability properties of our model and its advantage over classical trace norm. Extensive experimental results on both synthetic and real-world data sets verified both the efficiency and effectiveness of our method compared with the state-of-the-art algorithms.