| | |
| | |
Stat |
Members: 3645 Articles: 2'501'711 Articles rated: 2609
20 April 2024 |
|
| | | |
|
Article overview
| |
|
Asymptotic Analysis of Equivalences and Core-Structures in Kronecker-Style Graph Models | Alex J. Chin
; Timothy D. Goodrich
; Michael P. O'Brien
; Felix Reidl
; Blair D. Sullivan
; Andrew van der Poel
; | Date: |
16 Sep 2016 | Abstract: | Growing interest in modeling large, complex networks has spurred significant
research into generative graph models. Kronecker-style models (SKG and R-MAT)
are often used due to their scalability and ability to mimic key properties of
real-world networks. Although a few papers theoretically establish these
models’ behavior for specific parameters, many claims used to justify their use
are supported only empirically. In this work, we prove several results using
asymptotic analysis which illustrate that empirical studies may not fully
capture the true behavior of the models.
Paramount to the widespread adoption of Kronecker-style models was the
introduction of a linear-time edge-sampling variant (R-MAT), which existing
literature typically treats as interchangeable with SKG. We prove that although
several R-MAT formulations are asymptotically equivalent, their behavior
diverges from that of SKG. Further, we show these results are observable even
at relatively small graph sizes. Second, we consider a case where asymptotic
analysis reveals unexpected behavior within a given model. | Source: | arXiv, 1609.5081 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |