Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Average Distance in a General Class of Scale-Free Networks with Underlying Geometry

Bringmann, K., Keusch, R., & Lengler, J. (2016). Average Distance in a General Class of Scale-Free Networks with Underlying Geometry. Retrieved from http://arxiv.org/abs/1602.05712.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
1602.05712.pdf (Preprint), 333KB
Name:
1602.05712.pdf
Beschreibung:
File downloaded from arXiv at 2017-02-01 15:52
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bringmann, Karl1, Autor                 
Keusch, Ralph2, Autor
Lengler, Johannes1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Discrete Mathematics, cs.DM,cs.SI
 Zusammenfassung: In Chung-Lu random graphs, a classic model for real-world networks, each vertex is equipped with a weight drawn from a power-law distribution (for which we fix an exponent $2 < \beta < 3$), and two vertices form an edge independently with probability proportional to the product of their weights. Modern, more realistic variants of this model also equip each vertex with a random position in a specific underlying geometry, which is typically Euclidean, such as the unit square, circle, or torus. The edge probability of two vertices then depends, say, inversely polynomial on their distance. We show that specific choices, such as the underlying geometry being Euclidean or the dependence on the distance being inversely polynomial, do not significantly influence the average distance, by studying a generic augmented version of Chung-Lu random graphs. Specifically, we analyze a model where the edge probability of two vertices can depend arbitrarily on their positions, as long as the marginal probability of forming an edge (for two vertices with fixed weights, one fixed position, and one random position) is as in Chung-Lu random graphs, i.e., proportional to the product of their weights. The resulting class contains Chung-Lu random graphs, hyperbolic random graphs, and geometric inhomogeneous random graphs as special cases. Our main result is that this general model has the same average distance as Chung-Lu random graphs, up to a factor $1+o(1)$. The proof also yields that our model has a giant component and polylogarithmic diameter with high probability.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2016-02-182016
 Publikationsstatus: Online veröffentlicht
 Seiten: 25 pages. arXiv admin note: text overlap with arXiv:1511.00576
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1602.05712
URI: http://arxiv.org/abs/1602.05712
BibTex Citekey: Bringarx16
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: