Graph Generators: State of the Art and Open Challenges

As we can see, the biggest set of available generators can be found in the Semantic Web application domain, probably due to its recent popularity and a number of research groups dealing with this topic. None of these generators is natively implemented in a distributed manner and thus primarily generating output at the Big Data scale. On the other hand, the Linked Open Data (LOD) is expected to be large in general; however, this is the case of the whole LOD Cloud⁴⁴4https://lod-cloud.net/, but not necessarily of the particular data sets forming it.

The second large group of generators also corresponds to a popular application domain – social networks. In this case the size of the output graph is important if we require realistic features of the result. However, surprisingly many of the proposals do not provide an implementation at all and amongst the others there is a high percentage of those that are not highly scalable.

In case of the other application-specific domains the amount of generators is relatively small. As we will show in Section 2.2, the situation is not so critical. Some of the application-specific generators can be re-used also in other application domains or the general graph generators can be used.

Considering the output format of the data, as expected, the generators produce data in a standard format (e.g., RDF) or in a reasonable graph-related form (e.g., edge list).

If we consider the features of the particular domain of the generators, in most cases it is expectably fixed, i.e., it is pre-defined (describing, e.g., a social network) and cannot be modified. It is the simplest option, but it does mean that the generator is simple too – it can still focus on other complex aspects of the output. While the schema-driven approaches enable to influence the target domain using a user-supplied schema, there also exist approaches where the domain is extracted from sample data. The particular target (in case of fixed) or sample (in case of schema-driven or extracted) domains do not provide very rich areas. They either correspond to the respective application domains (like in the case of social networks), or they are based on well-known and commonly used data sets (such as, e.g., DBLP [team (2016)] or DBpedia [Bizer et al. (2009)]). Except for general graphs without any domain, in all other cases we can find a flexible representative with schema-driven/pattern-driven domain or a domain extracted from sample data.

In the case of operations, most commonly the respective generators are accompanied with a set of fixed read operations or sequences of operations (query mixes) representing typical behavior of a user. In some cases this aspect is more flexible – either query templates are used or the operations are generated, e.g., in order to access most of the data in the generated graph. On the other hand, update operations are provided only in a small amount of cases. As we will discuss in Section 4.6, the more general problem of evolving graphs is still an open issue.

A natural feature of the generators is to provide as realistic graphs as possible. Hence, most of them focus not only on the structure of the output graph, but also the properties. For the purpose of generating graphs with near real-world characteristics various distributions are used, such as power-law, Zipfian etc. Especially interesting are distributions extracted from real-wold data (such as, e.g., Facebook in case of the social network domain).

Barabasi and Albert [Barabasi and Albert (1999)] introduced a graph generation model that relies on two main mechanisms. The first mechanism is continuously expanding the graphs by adding new vertices. The second mechanism is to preferentially attach the new vertices to the nodes/regions that are already well connected. So, in this approach, the generation of large graphs is governed by standard, robust self-organizing mechanisms that go beyond the characteristics of individual applications.

R-MAT (Recursive Matrix) is a procedural synthetic graph generator which is designed to generate power-law degree distributions [Chakrabarti et al. (2004)]. The generator is recursive and employs a fairly small number of parameters. In principle, the strategy of this generator is to achieve simple means to produce graphs whose properties correspond to properties of the real-world graphs. In particular, the design goal of R-MAT is to produce graphs which mimics the degree distributions, imitate a community structure and have a small diameter. R-MAT can generate weighted, directed and bipartite graphs.

The HPC Scalable Graph Analysis Benchmark [GraphAnalysis.org (2009), Bader and Madduri (2005)] consists of a weighted, directed graph that has a power-law distribution and four related analysis techniques (namely graph construction, graph extraction with BFS, classification of large vertex sets, and graph analysis with betweenness centrality). The generator has the following parameters: the number of nodes, the number of edges, and maximum weight of an edge. It outputs a list of tuples containing identifiers of vertices of an edge (with the direction from the first one to the second one) and weights (positive integers with a uniform random distribution) assigned to the edges of the multigraph. The algorithm of the generator is based on R-MAT.

For the purpose of testing the scalability of an indexing technique called FG-index [Cheng et al. (2007)] on the size of the database of graphs, their average size and average density, the authors have also implemented a synthetic generator called GraphGen⁵⁵5https://www.cse.ust.hk/graphgen/. It relies on data generation code for associations and sequential patterns provided by IBM⁶⁶6From 1996, no longer available at http://www.almaden.ibm.com/cs/projects/iis/hdb/Projects/datamining/mining.shtml. GraphGen yields a collection of undirected, labeled and connected graphs. It addresses the performance evaluation of frequent subgraph mining algorithms and graph query processing algorithms. The result is represented as a list of graphs, each consisting of a list of nodes along with a list of edges.

BTER (Block Two-Level Erdös-Rény) [Kolda et al. (2014)] is a graph generator based on the creation of multiple Erdös-Rény graphs with different connection probabilities of which they are connected randomly between them. As the main feature, BTER is able to reproduce input degree distributions and average clustering coefficient per degree values. The generator starts by grouping the vertices by degree $d$, and forming groups of size $d+1$ of nodes with degree $d$. Then, these groups are assigned an internal edge probability in order to match the observed average clustering coefficient of the nodes of such degree. Based on this probability, for each node, the excess degree (i.e, the degree that in expectation will not be realized internally in the group) is computed and used to connect nodes from different groups at random. The authors report that BTER is able to generate graphs with billions of edges.

Darwini [Edunov et al. (2016)] is an extension of BTER designed to run on Vertex Centric computing frameworks like Pregel [Malewicz et al. (2010)] or Apache Giraph [Ching et al. (2015)], with the additional feature that it is more accurate when reproducing the clustering coefficient of the input graph. Instead of just focusing on the average clustering coefficient for each degree, Darwini is able to model the clustering coefficient distribution per degree. It achieves this by gathering the nodes of the graph into buckets based on the expected number of closed triangles that they need to close in order to attain the expected clustering coefficient. The latter is sampled from the input distributions. Then, the vertices in each bucket are connected randomly with a probability that would produce the expected desired number of triangles for each bucket. Then, as in BTER, the excess degree is used to connect the different buckets. The authors report that Darwini is able to generate graphs with billions and even trillions of edges.

The Random Typing Generator (RTG) [Akoglu and Faloutsos (2009)] aims at generating realistic graphs. In particular, it outputs (un)weighted, (un)directed, as well as uni/bipartite graphs, whereas the realism of the output is ensured by 11 laws (e.g., densification power law, weight power law, small and shrinking diameter, community structure, etc.) known to be typically exhibited by real-world graphs. On input it requires 4 parameters ($k$, $q$, $W$, and $\beta$) that correspond to the core Miller’s observation [Miller (1957)] that a random process (namely, having a keyboard with $k$ characters and a space, the process of random typing of $W$ words, where the probability of hitting a space is $q$ and the probability of hitting any other characters is $(1-q)/k$) leads to Zipf-like power laws (of the resulting words) plus in addition (using imbalance factor $\beta$) ensure homophily and community structure. RTG is based on the idea creating an edge between pairs of consecutive words.

Paper [Ammar and Özsu (2013)] further extends this idea mainly in the direction of simplification of specifying of the parameters. Instead of Miller’s parameters that are not much associated with graphs, the authors prove and exploit their relationship with size and density of the target graph.

In general, existing general graph generators produce graphs with the following properties: skewed degree distribution (e.g., power law), small diameter, a large largest connected component, large clustering coefficient, and some degree of community structure. Degree distribution can be typically configured while other properties are just a result of the generation process and cannot be controlled by any means. This is not the case in the work of BTER and Darwini, which besides the degree distribution, they also allow tuning of the clustering coefficient. However, some use cases demand for more control on the characteristics of the generated graphs. This is the case, for example, of benchmarking, where the underlying graph structure has direct implications to the performance of the graph algorithms to run. For this reason, the design of graph generators with the capability of fine tuning the characteristics of the generated graphs still remains as an open challenge. The questions that remain are what characteristics to tune and which are the algorithms that depend on such characteristics.

The use-case driven Lehigh University Benchmark (LUBM)⁷⁷7http://swat.cse.lehigh.edu/projects/lubm/ considers the university domain. The ontology defines 43 classes and 32 properties [Guo et al. (2005)]. In addition, 14 test queries are provided in the LUBM benchmark. In particular, the benchmark focuses on extensional queries, i.e., queries which target the particular data instances of the ontology, as an opposite to intentional queries, i.e., queries which target properties and classes of the ontology. The Univ-Bench Artificial (UBA) data generator features repeatable and random data generation (exploiting classical linear congruential generator, LCG, of numbers). In particular, the data which is produced by the generator are assigned zero-based indexes (i.e., University0, University1 etc.), thus they are reproducible at any time with the same indexes. The generator naturally allows to specify a seed for random number generation, along with the starting index and the desired number of universities.

An extension of LUBM, the Lehigh BibTeX Benchmark (LBBM) [Wang et al. (2005)], enables generating synthetic data for different ontologies. The data generation process is managed through two main phases: (1) the property-discovery phase, and (2) the data generation phase. LBBM provides a probabilistic model that can emulate the discovered properties of the data of a particular domain and generate synthetic data exhibiting similar properties. Synthetic data are generated using a Monte Carlo algorithm. The approach is demonstrated on the Lehigh University BibTeX ontology which consists of 28 classes along with 80 properties. The LUBM benchmark includes 12 test queries that were designed for the benchmark data. Another extension of LUBM, the University Ontology Benchmark (UOBM)⁸⁸8https://www.cs.ox.ac.uk/isg/tools/UOBMGenerator/, focuses on two aspects: (1) usage of all constructs of OWL Lite and OWL DL [W3C (2004)] and (2) lack of necessary links between the generated data which thus form isolated graphs [Ma et al. (2006)]. In the former case the original ontology is replaced by the two types of extended versions from which the user can choose. In the latter case cross-university and cross-department links are added to create a more complex graph.

Ferrara et al. [Ferrara et al. (2008)] proposed the ISLab Instance Matching Benchmark (IIMB)⁹⁹9http://www.ics.forth.gr/isl/BenchmarksTutorial/ for the problem of instance matching. For any two objects $o_{1}$ and $o_{2}$ adhering to different ontologies or to the same ontology, instance matching is specified in the form of a function $Om(o_{1},o_{2})\rightarrow\{0,1\}$, where $o_{1}$ and $o_{2}$ are linked to the same real-world object (in which case the function maps to $1$) or $o_{1}$ and $o_{2}$ are representing different objects (in which case the function maps to $0$). It targets the domain of movie data which contains 15 named classes, along with 5 objects and 13 datatypes. The data are extracted from IMDb¹⁰¹⁰10http://www.imdb.com/. The data generator corresponds to a data modifier which simulates differences between the data. In particular it involves data value differences (such as typographical errors or usage of different standard formats, e.g., for names), structural heterogeneity (represented by different levels of depth for properties, diverse aggregation criteria for properties, or missing values specification) and logical heterogeneity (such as, e.g., instantiation on disjoint classes or various subclasses of the same superclass).

The Berlin SPARQL Benchmark (BSBM)¹¹¹¹11http://wifo5-03.informatik.uni-mannheim.de/bizer/berlinsparqlbenchmark/, is centered around an e-commerce application domain with object types such as Customer, Vendor, Product and Offer in addition to the relationship among them [Bizer and Schultz (2009)]. The benchmark provides a workload that has 12 queries with 2 types of query workloads (i.e., 2 sequences of the 12 queries) emulating the navigation pattern and search of a consumer seeking a product. The data generator is capable of producing arbitrarily scalable datasets by controlling the number of products ($n$) as a scale factor. The scale factor also impacts other data characteristics, such as, e.g., the depth of type hierarchy of products, branching factor, the number of product features, etc. BSBM can output two representations, i.e. an RDF representation along with a relational representation. Thus, BSBM also defines an SQL [ISO (2008)] representation of the queries. This allows comparison of SPARQL [Prud’hommeaux and Seaborne (2008)] results to be compared against the performance of traditional RDBMSs.

The SP²Bench¹²¹²12http://dbis.informatik.uni-freiburg.de/forschung/projekte/SP2B/ is a language-specific benchmark [Schmidt et al. (2010)] which is based on the DBLP dataset. The generated datasets follow the key characteristics of the original DBLP dataset. In particular, the data mimics the correlations between entities. All random functions of the generator use a fixed seed that ensures that the data generation process is deterministic. SP²Bench is accompanied by 12 queries covering the various types of operators such as RDF access paths in addition to typical RDF constructs.

DBpedia SPARQL Benchmark (DBPSB)¹³¹³13http://aksw.org/Projects/DBPSB.html proposed at the University of Leipzig has been designed using workloads that have been generated by applications and humans [Morsey et al. (2011), Morsey et al. (2012)]. In addition, the authors argue that benchmarks like LUBM, BSBM, or SP²Bench resemble relational database benchmarks involving relational-like data which is structured using a small amount of homogeneous classes, whereas, in reality, RDF datasets are tending to be more heterogeneous. For example, DBpedia 3.6 consists of 289,016 classes, whereas 275 of them are defined based on the DBpedia ontology. In addition, in property values different data types as well as references to objects of the various types are used. Hence, they presented a universal SPARQL benchmark generation approach which uses a flexible data production mechanism that mimics the input data source. This dataset generation process begins using an input dataset; then multiple datasets with different sizes are generated by duplicating all the RDF triples with changing their namespaces. For generating smaller datasets, an adequate selection of all triples is selected randomly or using a sampling mechanism over the various classes in the dataset. The methodology is applied on the DBpedia SPARQL endpoint and a set of 25 templates of SPARQL queries is derived to cover frequent SPARQL features.

The Linked Open Data Integration Benchmark (LODIB)¹⁴¹⁴14http://lodib.wbsg.de/ has been designed with the aim of reflecting the real-world heterogeneities that exist on the Web of Data in order to enable testing of Linked Data translation systems [Rivero et al. (2012)]. It provides a catalogue of 15 data translation patterns (e.g., rename class, remove language tag etc.), each of which is a common data translation problem in the context of Linked Data. The benchmark provides a data generator that produces three different synthetic data sets that need to be translated by the system under test into a single target vocabulary. They reflect the pattern distribution in analyzed 84 data translation examples from the LOD Cloud. The data sets reflect the same e-commerce scenario used for BSBM.

The Geographica benchmark¹⁵¹⁵15http://geographica.di.uoa.gr/ has been designed to target the area of geospatial data [Garbis et al. (2013)] and respective SPARQL extensions GeoSPARQL [Battle and Kolas (2012)] and stSPARQL [Koubarakis and Kyzirakos (2010)]. The benchmark involves a real-world workload that uses openly available datasets that cover various geometry elements (such as, e.g., lines, points, polygons, etc.) and a synthetic workload. In the former case there is a (1) a micro benchmark that evaluates primitive spatial functions (involving 29 queries) and (2) macro benchmark that tests the performance of RDF engines in various application scenarios such as map exploring and search (consisting of 11 queries). In the latter case of a synthetic workload the generator produces synthetic datasets of different sizes that corresponds to an ontology based on OpenStreetMap and instantiates query templates. The generated SPARQL query workload is corresponding to spatial joins and selection using 2 query templates.

The Waterloo SPARQL Diversity Test Suite (WatDiv)¹⁶¹⁶16http://dsg.uwaterloo.ca/watdiv/ has been designed at the University of Waterloo. It implements stress testing tools that focus on addressing the observation that the state-of-the-art SPARQL benchmarks do not fully cover the variety of queries and workloads [Aluç et al. (2014)]. The benchmark focuses on two types of query aspects – structural and data-driven – and performs a detailed analysis on existing SPARQL benchmarks (LUBM, BSBM, DBPSB, and SP²Bench) using these two properties of queries. The structural features involve triple pattern count, join vertex degree, and join vertex count. The data-driven features involve result cardinality and several types of selectivity. The analysis of the four benchmarks reveals that their diversity is insufficient for evaluation of the weaknesses/strengths of the distinct design alternatives implemented by the different RDF systems.

In particular, WatDiv, provides (1) a data generator which generates scalable datasets according to the WatDiv schema, (2) a query template generator which produces a set of query templates according to the WatDiv schema, and (3) a query generator that uses the generated templates and instantiates them with real RDF values from the dataset, and (4) a feature extractor which extracts the structural features of the generated data and workload.

RBench [Qiao and Özsoyoğlu (2015)] is an application-specific benchmark which receives any RDF dataset as an input and produces a set of datasets, that have similar characteristics of the input dataset, using size scaling factor $s$ and (node) degree scaling factor $d$. These factors ensure that the original RDF graph $G$ and the synthetic graph $G^{\prime}$ are similar and the average node degree and the number of edges of $G^{\prime}$ are changed by $s$ and $d$ respectively. A query generation process has been implemented to produce 5 different types of queries (edge-based queries, node-based queries, path queries, star queries, subgraph queries) for any generated data. The benchmark project FEASIBLE [Saleem et al. (2015)] is also an application-specific benchmark; however, contrary to RBench, it is designed to produce benchmarks from the set of sample input queries of a user-defined size.

In practice, one way for handling big RDF graphs is to process them using the streaming mode where the data stream could consist of the edges of the graph. In this mode, the RDF processing algorithms can process the input stream in the order it arrives while using only a limited amount of memory [McGregor (2014)]. The streaming mode has mainly attracted the attention of the RDF and Semantic Web community.

Phuoc et al. [Le-Phuoc et al. (2012)] presented an evaluation framework for linked stream data processing engines. The framework uses a dataset generated with the Stream Social network data Generator (S2Gen), which simulates streams of user interactions (or events) in social networks (e.g., posts) in addition to the user metadata such as users’ profile information, social network relationships, posts, photos and GPS information. The data generator of this framework provides the users the flexibility to control the characteristics of the generated stream by tuning a range of parameters, which includes the frequency at which interactions are generated, limits such as the maximum number of messages per user and week, and the correlation probabilities between the different objects (e.g., users) in the social network.

Tommasini et al. [Tommasini et al. (2017)] introduced another framework for benchmarking RDF Stream Processing systems, RSPLab. The Streamer component of this framework is designed to publish RDF streams from the various existing RDF benchmarks (e.g., BSBM, LUBM). In particular, the Streamer component uses TripleWave¹⁷¹⁷17http://streamreasoning.github.io/TripleWave/, an open-source framework which enables to share RDF streams on the Web [Mauri et al. (2016)]. TripleWave acts as a means for plugging-in and combining streams from multiple Web data sources using either pull or push mode.

The Linked Data Benchmark Council¹⁸¹⁸18http://ldbcouncil.org/industry/organization/origins (LDBC) [Angles et al. (2014)] had the goal of developing open source, yet industrial grade benchmarks for RDF and graph databases. In the Semantic Web domain, it released the Semantic Publishing Benchmark (SPB) [LDBC (2015)] that has been inspired by the Media/Publishing industry (namely BBC¹⁹¹⁹19http://www.bbc.com/). The application scenario of this benchmark simulates a media or a publishing organization that handles large amount of streaming content (e.g., news, articles). The data generator mimics three types of relations in the generated synthetic data: correlations of entities, data clustering, and random tagging of entities. Two workloads are provided: (1) basic, involving an interactive query-mix querying the relations between entities in reference data, and (2) advanced, focusing on interactive and analytical query-mixes. The LDBC has designed two other benchmarks: the Social Network Benchmark (SNB) [Erling et al. (2015)] for the social network domain (see Section 3.4) and Graphalytics [Iosup et al. (2016)] for the analytics domain.

LinkGen is a synthetic linked data generator that has been designed to generate RDF datasets for a given vocabulary [Joshi et al. (2016)]. The generator is designed to receive a vocabulary as an input and supports two statistical distributions for generating entities: Zipf’s power-law distribution and Gaussian distribution. LinkGen can augment the generated data with inconsistent and noisy data such as updating a given datatype property with two conflicting values or adding triples with syntactic errors. The generator also provides a feature to inter-link the generated objects with real-world ones from user-provided real-world datasets. The datasets can be generated in any of of two modes: on-disk and streaming.

Graphs are intuitive and standard representation for the RDF model that form the basis for the Semantic Web community which has been very active on building several benchmarks, associated with graph generators that had various design principles.

A comparison of 4 RDF benchmarks (namely TPC-H [Solutions (2016)] data expressed in RDF, LUBM, BSBM, and SP²Bench) and 6 real-wold data sets (such as, e.g., DBpedia, the Barton Libraries Dataset [Abadi et al. (2007)] or WordNet [Miller (1995)]) has been reported by [Duan et al. (2011)]. The authors focus mainly on the structuredness (coherence) of each benchmark dataset claiming that a primitive metric (e.g., the number of triples or the average in/outdegree) quantifies only some target characteristics of each dataset. With respect to a type $T$ the degree of structuredness of a dataset $D$ is based on the regularity of instance data in $D$ in conforming to type $T$. The type system is extracted from the data set by finding the RDF triples that have property²⁰²⁰20http://www.w3.org/1999/02/22-rdf-syntax-ns\#type and extract type $T$ from their object. Properties of $T$ are determined as the union of all properties of type $T$. The structuredness is then expressed as a weighted sum of share of set properties of each type, whereas higher weights are assigned to types with more instances. The authors show that the structuredness of the chosen benchmarks is fixed, whereas real-world RDF datasets are belonging to the non-tested area of the spectrum. As a consequence, they introduce a new benchmark that receives as input any dataset associated with a required level of structuredness and size (smaller than the size of the original data), and exploits the input documents as a seed to produce a subset of the original data with the target structuredness and size. In addition, they show that structuredness and size mutually influence each other.

With the recent increasing momentum of streaming data, the Semantic Web community started to consider the issues and challenges of RDF streaming data. However, there are still a lot of open challenges that need to tackled in this direction such as covering different real-world application scenarios.

XGDBench [Dayarathna and Suzumura (2014)] is an extensible benchmarking platform for graph databases used in cloud-based systems. Its intent is to automate benchmarking of graph databases in the cloud by focusing on the domain social networking services. It extends the Yahoo! Cloud Multiplicative Attribute (MAG) Graph Serving Benchmark (YCSB) [Cooper et al. (2010)] and provides a set of standard workloads representing various performance issues. In particular, the workload of XGDBench involves basic operations such as read / insert / update / delete an attribute, loading of the list of neighbours and BFS traversal. Using the generators, 7 workloads are created, such as update heavy, read mostly, short range scan, traverse heavy etc. The data model of XGDBench is a simplified version of the Multiplicative Attribute Graph (MAG) [Kim and Leskovec (2010)] model, a synthetic graph model which models the interactions between node attributes and graph structure. The generated graphs are thus in MAG format, with power-law degree distribution closely simulating real-world social networks. The simplified MAG algorithm accepts the required number of nodes and for each node the number of attributes, a threshold for random initialization of attributes, a threshold for edge affinity which determines the existence of an edge between two nodes, and an affinity matrix. Large graphs can be generated on multi-core systems by XGDBench multi-threaded version.

gMark [Bagan et al. (2016)] is a schema-driven and domain-agnostic generator of both graph instances and graph query workloads. It can generate instances under the form of N-triples and queries in various concrete query languages, including OpenCypher²¹²¹21https://neo4j.com/developer/cypher-query-language/, recursive SQL, SPARQL and LogicQL. In gMark, it is possible to specify a graph configuration involving the admitted edge predicates and node labels occurring in the graph instance along with additional parameters such as degree distribution, occurrence constraints, etc. The Query workload configuration describes parameters of the query workload to be generated, by including the number of queries, arity, shape and selectivity of the queries. The problem of deciding whether there exists a graph that satisfies a defined graph specification $G$ is NP-complete. The same applies to the problem of deciding whether there exists a query workload compliant with a given query workload configuration $Q$. In view of this, gMark adopts a best effort approach in which the parameters specified in the configuration files are attained in a relaxed fashion in order to achieve linear running time whenever possible.

GraphAware GraphGen²²²²22http://graphgen.graphaware.com/ is a graph generation engine based on Neo4j’s²³²³23https://neo4j.com/ query language OpenCypher [Ltd. (2015)]. It creates nodes and relationships based on a schema definition expressed in Cypher, and it can also generate property values on both nodes and edges. As such, GraphGen is a precursor of property graphs generators. The resulting graph can be exported to several formats (namely GraphJson²⁴²⁴24https://github.com/GraphAlchemist/GraphJSON/wiki/GraphJSON and CypherQueries) or loaded directly to a DBMS. However, it is very likely that it is not maintained anymore due to the lack of available recent commits.

The graph DBMS generators discussed in this section have in common the fact that they can generate semantically rich labeled graphs with properties (ranging from properties values in GraphGen to MAG structures in XGDBench). They are also capable of generating graph instances and query workloads in concrete syntaxes (among which OpenCypher in GraphGen and gMark) and one of them (XGDBench) can also handle update operations on both graph structure and content. However, more comprehensive graph DBMS generators that also produce data manipulation operations (such as updates for graph databases) are urgently needed. Additionally, none of these generators is enabled to work on corresponding query languages for property graphs, such as the newly emerging standard GQL [Chafi et al. (2018)] and G-Core [Angles et al. (2018)]. Hence, a full-fledged graph DBMS generator for property graphs and property graph query workloads [Bonifati et al. (2018b)] is still missing and there exists an interesting opportunity to build such a generator in the near future.

Another apparent inconvenience is represented by the fact that explicit correlations among graph elements cannot be encoded for instance in gMark or GraphGen, whereas they could be fruitful in order to reproduce the behavior of real-world graphs in which attribute values are correlated one with another. On the other hand, social network and Linked Data generators that support correlations (as highlighted in Section 3.4 and Section 3.2) typically exhibit a fixed schema and are not not necessarily multi-domain as are some of the graph DBMS generators discussed in this section (namely GraphGen and gMark).

[Barrett et al. (2009)] focused on the construction of realistic social networks. For this purpose the authors combine both private and public data sets with large-scale agent-based techniques. The process works as follows: In the first step it generates synthetic data by combining public and commercial databases. In the second step, it determines a set of activity templates. A 24-hour activity sequence including geolocations is assigned to each synthetic individual. To demonstrate the approach, the authors create a synthetic US population consisting of people and households together with respective geolocations. For this purpose the authors combine simulation and data fusion techniques utilizing various real-world data sources such as U.S. Census data, responses to a time-use survey or an activity survey. The result is captured by a dynamic network of social contacts. Similar methods for agent-based strategies have been reported in [Bernstein and O’Brien (2013)].

[Yao et al. (2011)] distinguished between two types of social network graphs – the linkage graph, where nodes correspond to people and edges correspond to their friendships, and the activity graph, where nodes also represent people but edges correspond to their interactions. On the basis of the analysis of Flickr²⁵²⁵25https://www.flickr.com/ social links and Epinions²⁶²⁶26http://www.epinions.com/ network of user interactions, the authors discover that they both exhibit high clustering coefficient (community structure), power-law degree distribution and small diameter. Considering the dynamic properties they both have relatively stable clustering coefficient over time and follow the densification law. On the other hand, diameter shrinking is not observed in Epinions activity graph and there is a difference in degree correlation (i.e., frequency of mutual connections of similar nodes) – activity graphs have neutral, whereas linkage graphs have positive degree correlation. With regards to the findings, the proposed generator focuses on linkage graphs with positive degree correlation. For this purpose it extends the forest fire spreading process algorithm [Leskovec et al. (2005b)] with link symmetry. It has two parameters: the symmetry probability $P_{s}$ and the burning probability $P_{b}$. $P_{b}$ ensures a forward burning process based on BFS in which fire burns strongly with $P_{b}$ approaching 1. $P_{s}$ ensures backward linking from old nodes to new nodes and “adds fuel to the fire as it brings more links”.

The LinkBench benchmark [Armstrong et al. (2013)] has been designed for the purpose of analysis of efficiency of a database storing Facebook’s production data. The benchmark considers true Big Data and related problems with sharding, replication etc. The social graph at Facebook comprises objects (nodes with IDs, version, timestamp and data) and associations (directed edges, pairs of node IDs, with visibility, timestamp and data). The size of the target graph is the number of nodes. Graph edges and nodes are generated concurrently during bulk loading. The space of node IDs is divided into chunks which enable parallel processing. The edges of the graph are generated in accordance with the results of analysing real-world Facebook data (such as outdegree distribution). A workload corresponding to 10 graph operations (such as insert object, count the number of associations etc.) and their respective characteristics over the real-world data is generated for the synthetic data.

The Scalable Structure-correlated Social Graph Generator (S3G2) [Pham et al. (2013)] is a general framework which produces a directed labeled graph whose vertices represent objects having property values. The respective classes determine the structure of the properties. S3G2 does not aim at generating near real-world data, but at generating synthetic graphs with a correlated structure. Hence, the existing data values influence the probability of choosing a particular property value from a pre-defined dictionary or connecting two nodes. For example, the degree distribution can be correlated with the properties of a node and thus, e.g., people who have many friend relationships typically post more comments and pictures. The data generation process starts with generating a number of nodes with property values generated according to specified property value correlations and then adding respective edges according to specified correlation dimensions. It has multiple phases, each focusing on one correlation dimension. Data is generated in a Map phase corresponding to a pass along one correlation dimension. Then the data are sorted along the correlation dimension in the following Reduce phase. A heuristic observation that “the probability that two nodes are connected is typically skewed with respect to some similarity between the nodes” enables to focus only on sliding window of most probable candidates. The core idea of the framework is demonstrated using an example of a social network (consisting of persons and social activities). The dictionaries for property values are inspired by DBpedia and provided with 20 property value correlations. The edges are generated according to 3 correlation dimensions.

The developers of the Social Network Intelligence BenchMark (SIB)²⁷²⁷27https://www.w3.org/wiki/Social_Network_Intelligence_BenchMark based the design of their benchmark on the claim that the state-of-the-art benchmarks are limited in reflecting the characteristics of the real RDF databases and are mostly focusing on the relational style aspects. Hence, they proposed a benchmark for query evaluation using real graphs [Boncz et al. (2013)]. The proposed benchmark mimics using an RDF store for a social network. The distribution of the generated data for each type follows the distribution of the associated type inferred from real-world social networks. Additionally, association rules are exploited for representing the real-world data correlation in the generated synthetic data. The generated data is linked with the RDF datasets from DBpedia. The benchmark specification contains 3 query mixes – interactive, update, and analysis – expressed in SPARQL 1.1 Working Draft.

[Ali et al. (2014)] introduces two synthetic generators to reproduce two characteristics typically observed in social networks: node features and multiple link types. Both generators extend the generator proposed by [Wang et al. (2011)]. which starts with a small number of nodes and new nodes are added until the network reaches the required number. It has two basic parameters: homophily and link density. A high homophily value reflects that links have higher chances to be established among the nodes belonging to the same community, whereas the community membership is represented by the same labels.

The first proposed generator is Attribute Synthetic Generator (ASG), used for reproducing the node feature distribution of standard networks and rewiring the network to preferentially connect nodes that exhibit a high feature similarity. The network is initialized with a group of three nodes. New nodes and links are added to the network based on link density, homophily, and feature similarity. As new nodes are created, their labels are assigned based on the prior label distribution. After the network has reached the same number of nodes as the original social media dataset, each node initially receives a random attribute assignment. Then a stochastic optimization process is used to move the initial assignments closer to the target distribution extracted from social media dataset using the Particle Swarm Optimization algorithm. The tuned attributes are then used to add additional links to the network based on the feature similarity parameter – a source node is selected randomly and connected to the most similar node. The second proposed generator, so-called Multi-Link Generator (MLG), further uses link co-occurrence statistics from the original dataset to create a multiplex network. MLG uses the same network growth process as ASG. Based on the link density parameter, either a new node is generated with a label based on the label distribution of the target dataset or a new link is created between two existing nodes.

Despite having a common Facebook-like dataset, thanks to three distinct workloads the Social Network Benchmark (SNB) [Erling et al. (2015)] provided by LDBC represents three distinct benchmarks. The network nodes correspond to people and the edges represent their friendship and messages they post in discussion trees on their forums. The three query workloads involve: (1) SNB-Interactive, i.e., complex read-only queries accessing a high portion of data, (2) SNB-BI, i.e., queries accessing a high percentage of entities and grouping them in various dimensions, and (3) SNB-Algorithms, involving graph analysis algorithms, such as community detection, PageRank, BFS, and clustering. The graph generator, called Datagen, is a fork of S3G2  [Pham et al. (2013)] and realizes power laws, uses skewed value distributions, and ensures reasonable correlations between graph structures and property values. Additionally, it extends S3G2 with ”spiky” patterns in the distribution of social network activity along the timeline, also provides the ability of generating update streams to the social network. Datagen is also based on Hadoop in order to provide scalability, but compared to S3G2, it contains numerous performance improvements and the ability to be deterministic regardless of the number of computer nodes used for the generation of the graphs and for a given set of configuration parameters.

[Nettleton (2016)] argued that the majority of existing works focuses on topology generation which approximates the features of a real-world social network (e.g., community structures, skew degree distribution, a small average path length, or a small graph diameter); however, this is usually done without any data. Hence, they introduced a general stochastic modeling approach that enables the users to fill a graph topology with data. The approach has three steps: (1) topology generation (using R-MAT) plus community identification using the Louvain method [Blondel et al. (2008)] or usage of a real-world topology from SNAP²⁸²⁸28https://snap.stanford.edu/data/, (2) data definition that describes definitions of attribute values (distribution profiles) using a parameterizable set of affinities and data propagation rules, and (3) data population.

Compared to more general graph generators, social network generators focus mainly on reproducing intra- and inter-node feature correlations. Among existing generators, LDBC SNB and S3G2 look like the most advanced ones in terms of the complexity of the generated graph and the amount of features and correlations they can generate, while providing a large degree of scalability. Their generation process is based on input dictionaries and have configuration files that allow tweaking many parameters of the generated graphs, but their schema is mainly static and cannot be easily configured to meet the needs of other use cases besides the benchmarks they have been designed for. In this regard, the approaches like those proposed in [Nettleton (2016)] and [Ali et al. (2014)] offer a more flexible and understandable configuration process to tweak the types, values, and correlations between different features.

Regarding the correlation between the underlying graph structure and the node features, approaches such as LDBC SNB, S3G2 or  [Nettleton (2016)] take into account this aspect and the generated graphs have realistic structural properties while similar nodes have a larger probability of being connected. However, their approach seems to be more based on intuition and common sense than to be backed up by any study of how the relation between structure and attributes showcase in real social networks. In this regard, this remains as a clear open challenge for social network generators.

Finally, scalability is another aspect to be considered in social network graph generators. LDBC SNB and S3G2 are engineered with this in mind, thus they provide a way to scale to billions of nodes and edges. This is not the case for the other generators, which can make them impractical if our goal is to generate real sized social network graphs.

The first attempts to compare community detection algorithms using synthetic graphs proposed the use of random graphs composed by several Erdös-Rényi subgraphs, connected more internally than externally [Danon et al. (2005)]. Each of these subgraphs has the same size and the same internal/external density of edges. However, such graphs miss the realism observed in real-world graphs, where communities are of different sizes and densities, thus several proposals exist to overcome such an issue.

Lancichinetti, Fortunato and Radicchi (hence LFR) [Lancichinetti et al. (2008)] propose a class of benchmark graphs for community detection where communities are of diverse sizes and densities. The generated communities follow a power-law distribution whose parameters can be configured. The degree of the nodes is also sampled from a power-law distribution. Additionally, the generator introduces the concept of the “mixing factor”, which consists of the percentage of edges in the graph connecting nodes that belong to distinct communities. Such parameter allows the degree of modularity of the generated graph to be tuned, thus testing the robustness of the algorithms under different conditions. The generation process is implemented as an optimization process starting with an empty graph and progressively filling it with nodes and edges guided by the specified constraints.

Lancichinetti, Fortunato and Radicchi [Lancichinetti and Fortunato (2009)] extended LFR to support the notion of directed graphs and overlapping communities. Overlapping communities extend the notion of communities by allowing the sharing of vertices, thus a vertex can belong to more than one community. This extended generator allows controlling the same parameters of LFR, as well as the amount of overlap of the generated communities.

Another popular family of generators widely used in the community detection field are the stochastic block models [Holland et al. (1983)]. In such models, the community structure of the graph is typically defined as an array of $n$ community or cluster sizes and a density square matrix of size $n\times n$ containing the density of intra-cluster edges (in the diagonal of the matrix) and the density of inter-cluster edges. Then, a stochastic procedure is run to sample graphs from such array and matrix, using the sizes to compute the possible edges and the densities as probabilities of such edges to exist. The popularity of these methods stem from its simplicity and scalability, which makes them suitable for generating large graphs fast and in distributed environments, provided that the density matrix is sparse (as it happens in most of real-world graphs). Moreover, given that the generation process of such models is mathematically tractable, they are typically used to analyze the limitations of algorithms for community detection such as those based on modularity optimization [Fortunato and Barthelemy (2007)] or based on triads [Prat-Pérez et al. (2016)]. Extensions of such models exist, such as the Mixed Membership Stochastic Block Model [Airoldi et al. (2008)], for overlapping communities.

Besides synthetic graph generators, Yang and Leskovec [Yang and Leskovec (2015)] proposed the use of real-world graphs with explicit group annotations (e.g., forums in a social network, categories of products, etc.) to infer what they call meta-communities, and use them to evaluate overlapping community detection algorithms. However, a recent study from Hric, Darst and Fortunato [Hric et al. (2014)] reveal a loose correspondence between communities (the authors refer to them as structural communities) and meta-communities. This result reveals that algorithms working for structural communities do not work well for finding meta-communities and vice versa, suggesting significantly different underlying characteristics between the two types of communities, which are yet to be identified.

In this regard and to the best of our knowledge, there are no available generators that can generate graphs with meta-communities for community detection algorithm benchmarking. The closest one is the LDBC SNB data generator which has been provided by the generation of groups of users in the social network. Even though the generation process does not specifically enforce the generation of groups (meta-communities) for benchmarking community detection algorithms, the study [Prat-Pérez and Dominguez-Sal (2014)] reveals that these groups are more similar to the real meta-communities than those structural communities generated by the LFR benchmark.

The differences observed between structural and meta-communities reveal the need of more accurate community definitions that are more tight and more specific to the domain or the use case. Current community detection algorithms and graph generators for community detection are stuck to the traditional (and vague) definition of community, assuming that there exists a single algorithm that would fit all the use cases. Thus, future work requires the study of domain-specific community characteristics that can be used to generate graphs with a community structure that accurately resembles that of specific use cases, and thus revealing which are the best algorithms for each particular scenario.