Movebank · 2016 · 17 citations · 29 references
ComputingComputer ScienceBig Data AnalyticsComputational BiologyGenomic Data AnalysisGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryScalable Algorithm DesignCorrelationGraph SimilarityScalabilityScalable Graph AlgorithmsShotgun SequencingSystem Scalability
Enterprises and researchers often have datasets that can be represented as graphs (e.g. social networks). The owner of a large graph may want to scale it down to a smaller version, e.g. for application development. On the other hand, the owner of a small graph may want to scale it up to a larger version, e.g. to test system scalability. This paper investigates the Graph Scaling Problem (GSP): Given a directed graph G and positive integers n and m, generate a similar directed graph G with n nodes and m edges. This paper presents a graph scaling algorithm Gscaler for GSP. Analogous to DNA shotgun sequencing, Gscaler, decomposes G into small pieces, scales them, then uses the scaled pieces to construct G. This construction is based on the indegree/outdegree correlation of nodes and edges. Extensive tests with real graphs show that Gscaler is scalable and, for many graph properties, it generates a G that has greater similarity to G than other state-of-the-art solutions, like Stochastic Kronecker Graph and UpSizeR.
29
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Equation of State Calculations by Fast Computing Machines
N. Metropolis, Arianna W. Rosenbluth, M. N. Rosenbluth et al. · The Journal of Chemical Physics · 1953 · 37.1K citations
Emergence of Scaling in Random Networks
Albert-Ĺaszló Barabási, Réka Albert · Science · 1999 · 36.4K citations · Full text
Statistical mechanics of complex networks
Réka Albert, Albert-Ĺaszló Barabási · Reviews of Modern Physics · 2002 · 20.6K citations · Full text
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations