S3G2: A Scalable Structure-Correlated Social Graph Generator View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Minh-Duc Pham , Peter Boncz , Orri Erling

ABSTRACT

Benchmarking graph-oriented database workloads and graph-oriented database systems is increasingly becoming relevant in analytical Big Data tasks, such as social network analysis. In graph data, structure is not mainly found inside the nodes, but especially in the way nodes happen to be connected, i.e. structural correlations. Because such structural correlations determine join fan-outs experienced by graph analysis algorithms and graph query executors, they are an essential, yet typically neglected, ingredient of synthetic graph generators. To address this, we present S3G2: a Scalable Structure-correlated Social Graph Generator. This graph generator creates a synthetic social graph, containing non-uniform value distributions and structural correlations, which is intended as test data for scalable graph analysis algorithms and graph database systems. We generalize the problem by decomposing correlated graph generation in multiple passes that each focus on one so-called correlation dimension; each of which can be mapped to a MapReduce task. We show that S3G2 can generate social graphs that (i) share well-known graph connectivity characteristics typically found in real social graphs (ii) contain certain plausible structural correlations that influence the performance of graph analysis algorithms and queries, and (iii) can be quickly generated at huge sizes on common cluster hardware. More... »

PAGES

156-172

Book

TITLE

Selected Topics in Performance Evaluation and Benchmarking

ISBN

978-3-642-36726-7
978-3-642-36727-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-36727-4_11

DOI

http://dx.doi.org/10.1007/978-3-642-36727-4_11

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1044694691


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "CWI, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pham", 
        "givenName": "Minh-Duc", 
        "id": "sg:person.015106130107.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015106130107.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CWI, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Boncz", 
        "givenName": "Peter", 
        "id": "sg:person.015341641231.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341641231.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "OpenLink Software, U.K.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "OpenLink Software, U.K."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Erling", 
        "givenName": "Orri", 
        "id": "sg:person.011715705740.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011715705740.17"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "Benchmarking graph-oriented database workloads and graph-oriented database systems is increasingly becoming relevant in analytical Big Data tasks, such as social network analysis. In graph data, structure is not mainly found inside the nodes, but especially in the way nodes happen to be connected, i.e. structural correlations. Because such structural correlations determine join fan-outs experienced by graph analysis algorithms and graph query executors, they are an essential, yet typically neglected, ingredient of synthetic graph generators. To address this, we present S3G2: a Scalable Structure-correlated Social Graph Generator. This graph generator creates a synthetic social graph, containing non-uniform value distributions and structural correlations, which is intended as test data for scalable graph analysis algorithms and graph database systems. We generalize the problem by decomposing correlated graph generation in multiple passes that each focus on one so-called correlation dimension; each of which can be mapped to a MapReduce task. We show that S3G2 can generate social graphs that (i) share well-known graph connectivity characteristics typically found in real social graphs (ii) contain certain plausible structural correlations that influence the performance of graph analysis algorithms and queries, and (iii) can be quickly generated at huge sizes on common cluster hardware.", 
    "editor": [
      {
        "familyName": "Nambiar", 
        "givenName": "Raghunath", 
        "type": "Person"
      }, 
      {
        "familyName": "Poess", 
        "givenName": "Meikel", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-36727-4_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-36726-7", 
        "978-3-642-36727-4"
      ], 
      "name": "Selected Topics in Performance Evaluation and Benchmarking", 
      "type": "Book"
    }, 
    "keywords": [
      "graph analysis algorithms", 
      "graph generator", 
      "social graph", 
      "database systems", 
      "analysis algorithm", 
      "big data tasks", 
      "synthetic social graphs", 
      "graph database system", 
      "real social graphs", 
      "synthetic graph generators", 
      "query executor", 
      "graph data", 
      "social network analysis", 
      "MapReduce tasks", 
      "cluster hardware", 
      "data tasks", 
      "database workloads", 
      "graph generation", 
      "huge size", 
      "way nodes", 
      "connectivity characteristics", 
      "algorithm", 
      "graph", 
      "network analysis", 
      "nodes", 
      "test data", 
      "task", 
      "queries", 
      "hardware", 
      "join", 
      "workload", 
      "system", 
      "executor", 
      "generator", 
      "performance", 
      "data", 
      "correlation dimension", 
      "value distribution", 
      "structural correlations", 
      "generation", 
      "focus", 
      "dimensions", 
      "characteristics", 
      "size", 
      "analysis", 
      "structure", 
      "correlation", 
      "distribution", 
      "ingredients", 
      "problem", 
      "graph-oriented database workloads", 
      "graph-oriented database systems", 
      "analytical Big Data tasks", 
      "such structural correlations", 
      "graph query executors", 
      "Scalable Structure-correlated Social Graph Generator", 
      "Structure-correlated Social Graph Generator", 
      "Social Graph Generator", 
      "non-uniform value distributions", 
      "scalable graph analysis algorithms", 
      "correlated graph generation", 
      "S3G2", 
      "graph connectivity characteristics", 
      "certain plausible structural correlations", 
      "plausible structural correlations", 
      "common cluster hardware"
    ], 
    "name": "S3G2: A Scalable Structure-Correlated Social Graph Generator", 
    "pagination": "156-172", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044694691"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-36727-4_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-36727-4_11", 
      "https://app.dimensions.ai/details/publication/pub.1044694691"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_208.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-36727-4_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36727-4_11'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36727-4_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36727-4_11'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36727-4_11'


 

This table displays all metadata directly associated to this object as RDF triples.

148 TRIPLES      23 PREDICATES      92 URIs      85 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-36727-4_11 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N34c8dbc391024f50920d952783a7078d
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description Benchmarking graph-oriented database workloads and graph-oriented database systems is increasingly becoming relevant in analytical Big Data tasks, such as social network analysis. In graph data, structure is not mainly found inside the nodes, but especially in the way nodes happen to be connected, i.e. structural correlations. Because such structural correlations determine join fan-outs experienced by graph analysis algorithms and graph query executors, they are an essential, yet typically neglected, ingredient of synthetic graph generators. To address this, we present S3G2: a Scalable Structure-correlated Social Graph Generator. This graph generator creates a synthetic social graph, containing non-uniform value distributions and structural correlations, which is intended as test data for scalable graph analysis algorithms and graph database systems. We generalize the problem by decomposing correlated graph generation in multiple passes that each focus on one so-called correlation dimension; each of which can be mapped to a MapReduce task. We show that S3G2 can generate social graphs that (i) share well-known graph connectivity characteristics typically found in real social graphs (ii) contain certain plausible structural correlations that influence the performance of graph analysis algorithms and queries, and (iii) can be quickly generated at huge sizes on common cluster hardware.
7 schema:editor Na05ba0137297412c860a7b6620552a45
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ne5ebf4169fe54a5e8ea79ddbb7eb56c3
12 schema:keywords MapReduce tasks
13 S3G2
14 Scalable Structure-correlated Social Graph Generator
15 Social Graph Generator
16 Structure-correlated Social Graph Generator
17 algorithm
18 analysis
19 analysis algorithm
20 analytical Big Data tasks
21 big data tasks
22 certain plausible structural correlations
23 characteristics
24 cluster hardware
25 common cluster hardware
26 connectivity characteristics
27 correlated graph generation
28 correlation
29 correlation dimension
30 data
31 data tasks
32 database systems
33 database workloads
34 dimensions
35 distribution
36 executor
37 focus
38 generation
39 generator
40 graph
41 graph analysis algorithms
42 graph connectivity characteristics
43 graph data
44 graph database system
45 graph generation
46 graph generator
47 graph query executors
48 graph-oriented database systems
49 graph-oriented database workloads
50 hardware
51 huge size
52 ingredients
53 join
54 network analysis
55 nodes
56 non-uniform value distributions
57 performance
58 plausible structural correlations
59 problem
60 queries
61 query executor
62 real social graphs
63 scalable graph analysis algorithms
64 size
65 social graph
66 social network analysis
67 structural correlations
68 structure
69 such structural correlations
70 synthetic graph generators
71 synthetic social graphs
72 system
73 task
74 test data
75 value distribution
76 way nodes
77 workload
78 schema:name S3G2: A Scalable Structure-Correlated Social Graph Generator
79 schema:pagination 156-172
80 schema:productId N5687afd27c404c41accc01d136dd9d54
81 Ndde3a87b7aa24e959cab5b124c79d445
82 schema:publisher N63f7932f95644c5f9cfaa84f929c0b20
83 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044694691
84 https://doi.org/10.1007/978-3-642-36727-4_11
85 schema:sdDatePublished 2021-12-01T20:00
86 schema:sdLicense https://scigraph.springernature.com/explorer/license/
87 schema:sdPublisher N686669a67d9d4e1a9a5fdfc3b9a82eb1
88 schema:url https://doi.org/10.1007/978-3-642-36727-4_11
89 sgo:license sg:explorer/license/
90 sgo:sdDataset chapters
91 rdf:type schema:Chapter
92 N34c8dbc391024f50920d952783a7078d rdf:first sg:person.015106130107.21
93 rdf:rest Nd20e41ec1d9a47b2b66f1d7493f14cde
94 N5687afd27c404c41accc01d136dd9d54 schema:name doi
95 schema:value 10.1007/978-3-642-36727-4_11
96 rdf:type schema:PropertyValue
97 N61b42ed78a054a24bceae1f9e3b04678 schema:familyName Nambiar
98 schema:givenName Raghunath
99 rdf:type schema:Person
100 N63f7932f95644c5f9cfaa84f929c0b20 schema:name Springer Nature
101 rdf:type schema:Organisation
102 N686669a67d9d4e1a9a5fdfc3b9a82eb1 schema:name Springer Nature - SN SciGraph project
103 rdf:type schema:Organization
104 N6fe9a2918a234788855bcdbeea26398e rdf:first Na402b44d23d6481eb99e4f1a2728bbe7
105 rdf:rest rdf:nil
106 Na05ba0137297412c860a7b6620552a45 rdf:first N61b42ed78a054a24bceae1f9e3b04678
107 rdf:rest N6fe9a2918a234788855bcdbeea26398e
108 Na402b44d23d6481eb99e4f1a2728bbe7 schema:familyName Poess
109 schema:givenName Meikel
110 rdf:type schema:Person
111 Nd20e41ec1d9a47b2b66f1d7493f14cde rdf:first sg:person.015341641231.33
112 rdf:rest Ne0839ce3975c4707af0188fed0f77bdf
113 Ndde3a87b7aa24e959cab5b124c79d445 schema:name dimensions_id
114 schema:value pub.1044694691
115 rdf:type schema:PropertyValue
116 Ne0839ce3975c4707af0188fed0f77bdf rdf:first sg:person.011715705740.17
117 rdf:rest rdf:nil
118 Ne5ebf4169fe54a5e8ea79ddbb7eb56c3 schema:isbn 978-3-642-36726-7
119 978-3-642-36727-4
120 schema:name Selected Topics in Performance Evaluation and Benchmarking
121 rdf:type schema:Book
122 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
123 schema:name Information and Computing Sciences
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
126 schema:name Information Systems
127 rdf:type schema:DefinedTerm
128 sg:person.011715705740.17 schema:affiliation grid-institutes:None
129 schema:familyName Erling
130 schema:givenName Orri
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011715705740.17
132 rdf:type schema:Person
133 sg:person.015106130107.21 schema:affiliation grid-institutes:grid.6054.7
134 schema:familyName Pham
135 schema:givenName Minh-Duc
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015106130107.21
137 rdf:type schema:Person
138 sg:person.015341641231.33 schema:affiliation grid-institutes:grid.6054.7
139 schema:familyName Boncz
140 schema:givenName Peter
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015341641231.33
142 rdf:type schema:Person
143 grid-institutes:None schema:alternateName OpenLink Software, U.K.
144 schema:name OpenLink Software, U.K.
145 rdf:type schema:Organization
146 grid-institutes:grid.6054.7 schema:alternateName CWI, The Netherlands
147 schema:name CWI, The Netherlands
148 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...