Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Jurij Leskovec , Deepayan Chakrabarti , Jon Kleinberg , Christos Faloutsos

ABSTRACT

How can we generate realistic graphs? In addition, how can we do so with a mathematically tractable model that makes it feasible to analyze their properties rigorously? Real graphs obey a long list of surprising properties: Heavy tails for the in- and out-degree distribution; heavy tails for the eigenvalues and eigenvectors; small diameters; and the recently discovered “Densification Power Law” (DPL). All published graph generators either fail to match several of the above properties, are very complicated to analyze mathematically, or both. Here we propose a graph generator that is mathematically tractable and matches this collection of properties. The main idea is to use a non-standard matrix operation, the Kronecker product, to generate graphs that we refer to as “Kronecker graphs”.We show that Kronecker graphs naturally obey all the above properties; in fact, we can rigorously prove that they do so. We also provide empirical evidence showing that they can mimic very well several real graphs. More... »

PAGES

133-145

Book

TITLE

Knowledge Discovery in Databases: PKDD 2005

ISBN

978-3-540-29244-9
978-3-540-31665-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11564126_17

DOI

http://dx.doi.org/10.1007/11564126_17

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "School of Computer Science, Carnegie Mellon University", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "School of Computer Science, Carnegie Mellon University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Leskovec", 
        "givenName": "Jurij", 
        "id": "sg:person.01110503424.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01110503424.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computer Science, Carnegie Mellon University", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "School of Computer Science, Carnegie Mellon University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chakrabarti", 
        "givenName": "Deepayan", 
        "id": "sg:person.011311406373.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011311406373.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Cornell University", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Department of Computer Science, Cornell University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kleinberg", 
        "givenName": "Jon", 
        "id": "sg:person.011522233557.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Computer Science, Carnegie Mellon University", 
          "id": "http://www.grid.ac/institutes/grid.147455.6", 
          "name": [
            "School of Computer Science, Carnegie Mellon University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Faloutsos", 
        "givenName": "Christos", 
        "id": "sg:person.010155142175.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010155142175.75"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "How can we generate realistic graphs? In addition, how can we do so with a mathematically tractable model that makes it feasible to analyze their properties rigorously? Real graphs obey a long list of surprising properties: Heavy tails for the in- and out-degree distribution; heavy tails for the eigenvalues and eigenvectors; small diameters; and the recently discovered \u201cDensification Power Law\u201d (DPL). All published graph generators either fail to match several of the above properties, are very complicated to analyze mathematically, or both. Here we propose a graph generator that is mathematically tractable and matches this collection of properties. The main idea is to use a non-standard matrix operation, the Kronecker product, to generate graphs that we refer to as \u201cKronecker graphs\u201d.We show that Kronecker graphs naturally obey all the above properties; in fact, we can rigorously prove that they do so. We also provide empirical evidence showing that they can mimic very well several real graphs.", 
    "editor": [
      {
        "familyName": "Jorge", 
        "givenName": "Al\u00edpio M\u00e1rio", 
        "type": "Person"
      }, 
      {
        "familyName": "Torgo", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Brazdil", 
        "givenName": "Pavel", 
        "type": "Person"
      }, 
      {
        "familyName": "Camacho", 
        "givenName": "Rui", 
        "type": "Person"
      }, 
      {
        "familyName": "Gama", 
        "givenName": "Jo\u00e3o", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11564126_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29244-9", 
        "978-3-540-31665-7"
      ], 
      "name": "Knowledge Discovery in Databases: PKDD 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "densification power law", 
      "heavy tails", 
      "Kronecker graphs", 
      "out-degree distributions", 
      "Kronecker product", 
      "Kronecker multiplication", 
      "real graphs", 
      "graph generator", 
      "above properties", 
      "collection of properties", 
      "matrix operations", 
      "realistic graphs", 
      "tractable model", 
      "main idea", 
      "graph", 
      "surprising properties", 
      "graph generation", 
      "power law", 
      "eigenvalues", 
      "eigenvectors", 
      "generator", 
      "law", 
      "properties", 
      "multiplication", 
      "model", 
      "idea", 
      "tail", 
      "distribution", 
      "operation", 
      "fact", 
      "evolution", 
      "long list", 
      "generation", 
      "collection", 
      "empirical evidence", 
      "addition", 
      "list", 
      "products", 
      "In", 
      "small diameter", 
      "diameter", 
      "evidence", 
      "non-standard matrix operation", 
      "Mathematically Tractable Graph Generation", 
      "Tractable Graph Generation"
    ], 
    "name": "Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication", 
    "pagination": "133-145", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016924784"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11564126_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11564126_17", 
      "https://app.dimensions.ai/details/publication/pub.1016924784"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_52.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11564126_17"
  }
]
 

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/11564126_17'

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/11564126_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11564126_17'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11564126_17'


 

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

149 TRIPLES      23 PREDICATES      71 URIs      64 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11564126_17 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N4e4612625e924bb4ae188788a5af145f
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description How can we generate realistic graphs? In addition, how can we do so with a mathematically tractable model that makes it feasible to analyze their properties rigorously? Real graphs obey a long list of surprising properties: Heavy tails for the in- and out-degree distribution; heavy tails for the eigenvalues and eigenvectors; small diameters; and the recently discovered “Densification Power Law” (DPL). All published graph generators either fail to match several of the above properties, are very complicated to analyze mathematically, or both. Here we propose a graph generator that is mathematically tractable and matches this collection of properties. The main idea is to use a non-standard matrix operation, the Kronecker product, to generate graphs that we refer to as “Kronecker graphs”.We show that Kronecker graphs naturally obey all the above properties; in fact, we can rigorously prove that they do so. We also provide empirical evidence showing that they can mimic very well several real graphs.
7 schema:editor N62e906fed2894947aa51e62b1f0cd7d4
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfd86808db053478c9e36c28ae5690b13
12 schema:keywords In
13 Kronecker graphs
14 Kronecker multiplication
15 Kronecker product
16 Mathematically Tractable Graph Generation
17 Tractable Graph Generation
18 above properties
19 addition
20 collection
21 collection of properties
22 densification power law
23 diameter
24 distribution
25 eigenvalues
26 eigenvectors
27 empirical evidence
28 evidence
29 evolution
30 fact
31 generation
32 generator
33 graph
34 graph generation
35 graph generator
36 heavy tails
37 idea
38 law
39 list
40 long list
41 main idea
42 matrix operations
43 model
44 multiplication
45 non-standard matrix operation
46 operation
47 out-degree distributions
48 power law
49 products
50 properties
51 real graphs
52 realistic graphs
53 small diameter
54 surprising properties
55 tail
56 tractable model
57 schema:name Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
58 schema:pagination 133-145
59 schema:productId N45b528f4d9464614829afb2356c24a03
60 Nfda4bcf7ddb54f72ad68da0d28a6ba72
61 schema:publisher Nab91862035b247b6bfdfecfb023693c6
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016924784
63 https://doi.org/10.1007/11564126_17
64 schema:sdDatePublished 2022-01-01T19:26
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher N27573adb70bd40ad88142b01d56e8bf4
67 schema:url https://doi.org/10.1007/11564126_17
68 sgo:license sg:explorer/license/
69 sgo:sdDataset chapters
70 rdf:type schema:Chapter
71 N2011db5b213048369b2545de7708e1f9 rdf:first sg:person.011522233557.04
72 rdf:rest Nc498bfe029bc4e17a749ddb2c7b63e36
73 N20df6f469e9a4a50b8e765c455eff47d schema:familyName Torgo
74 schema:givenName Luís
75 rdf:type schema:Person
76 N27573adb70bd40ad88142b01d56e8bf4 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N2de4d1d418d640e1b552ff8c46d39426 rdf:first N4d4ac7139c774749b1ce0b9f4ff2fe7e
79 rdf:rest Nb7749e1d304545588ba493a661fed124
80 N45b528f4d9464614829afb2356c24a03 schema:name doi
81 schema:value 10.1007/11564126_17
82 rdf:type schema:PropertyValue
83 N4d4ac7139c774749b1ce0b9f4ff2fe7e schema:familyName Brazdil
84 schema:givenName Pavel
85 rdf:type schema:Person
86 N4e4612625e924bb4ae188788a5af145f rdf:first sg:person.01110503424.15
87 rdf:rest N701c0e696bbd4ff0a7bfcc6df81aa41b
88 N62e906fed2894947aa51e62b1f0cd7d4 rdf:first Ne6a2071a3d394dd8b34957397c9f1fc9
89 rdf:rest Nd5f62c7a5b4b4f62800ab692b11d229d
90 N701c0e696bbd4ff0a7bfcc6df81aa41b rdf:first sg:person.011311406373.48
91 rdf:rest N2011db5b213048369b2545de7708e1f9
92 Na9b3557d04fa43738ffea09d8751e1c9 schema:familyName Camacho
93 schema:givenName Rui
94 rdf:type schema:Person
95 Nab91862035b247b6bfdfecfb023693c6 schema:name Springer Nature
96 rdf:type schema:Organisation
97 Nb7749e1d304545588ba493a661fed124 rdf:first Na9b3557d04fa43738ffea09d8751e1c9
98 rdf:rest Nc5e86f22d1144637b8709d7f1ac824ea
99 Nc498bfe029bc4e17a749ddb2c7b63e36 rdf:first sg:person.010155142175.75
100 rdf:rest rdf:nil
101 Nc5e86f22d1144637b8709d7f1ac824ea rdf:first Nf7e5e4a959744309b4a021de475c2042
102 rdf:rest rdf:nil
103 Nd5f62c7a5b4b4f62800ab692b11d229d rdf:first N20df6f469e9a4a50b8e765c455eff47d
104 rdf:rest N2de4d1d418d640e1b552ff8c46d39426
105 Ne6a2071a3d394dd8b34957397c9f1fc9 schema:familyName Jorge
106 schema:givenName Alípio Mário
107 rdf:type schema:Person
108 Nf7e5e4a959744309b4a021de475c2042 schema:familyName Gama
109 schema:givenName João
110 rdf:type schema:Person
111 Nfd86808db053478c9e36c28ae5690b13 schema:isbn 978-3-540-29244-9
112 978-3-540-31665-7
113 schema:name Knowledge Discovery in Databases: PKDD 2005
114 rdf:type schema:Book
115 Nfda4bcf7ddb54f72ad68da0d28a6ba72 schema:name dimensions_id
116 schema:value pub.1016924784
117 rdf:type schema:PropertyValue
118 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
119 schema:name Mathematical Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
122 schema:name Pure Mathematics
123 rdf:type schema:DefinedTerm
124 sg:person.010155142175.75 schema:affiliation grid-institutes:grid.147455.6
125 schema:familyName Faloutsos
126 schema:givenName Christos
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010155142175.75
128 rdf:type schema:Person
129 sg:person.01110503424.15 schema:affiliation grid-institutes:grid.147455.6
130 schema:familyName Leskovec
131 schema:givenName Jurij
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01110503424.15
133 rdf:type schema:Person
134 sg:person.011311406373.48 schema:affiliation grid-institutes:grid.147455.6
135 schema:familyName Chakrabarti
136 schema:givenName Deepayan
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011311406373.48
138 rdf:type schema:Person
139 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
140 schema:familyName Kleinberg
141 schema:givenName Jon
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
143 rdf:type schema:Person
144 grid-institutes:grid.147455.6 schema:alternateName School of Computer Science, Carnegie Mellon University
145 schema:name School of Computer Science, Carnegie Mellon University
146 rdf:type schema:Organization
147 grid-institutes:grid.5386.8 schema:alternateName Department of Computer Science, Cornell University
148 schema:name Department of Computer Science, Cornell University
149 rdf:type schema:Organization
 




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


...