Robustness of spatial preferential attachment networks

Emmanuel Jacob, Peter Morters

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study robustness under random attack for a class of networks, in which new nodes are given a spatial position and connect to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering one can independently tune the power law exponent τ > 2 of the degree distribution and a parameter δ > 1 determining the decay rate of the probability of long edges. We argue that the network is robust if (Formula Presented.), but fails to be robust if (Formula Presented.). Hence robustness depends not only on the power-law exponent but also on the clustering features of the network.

Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publicationProceedings of 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015
EditorsD. F. Gleich, J. Komjathy, N. Litvak
Place of PublicationSwitzerland
PublisherSpringer
Pages3-14
Number of pages12
ISBN (Print)9783319267838
DOIs
Publication statusPublished - 9 Dec 2015
Event12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015 - Eindhoven, Netherlands
Duration: 10 Dec 201511 Dec 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9479

Conference

Conference12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015
CountryNetherlands
CityEindhoven
Period10/12/1511/12/15

Fingerprint

Preferential Attachment
Robustness
Power Law
Exponent
Clustering
Scale-free Networks
Degree Distribution
Decay Rate
Attack
Vertex of a graph
Model

Keywords

  • Barabasi-Albert model
  • Clustering
  • Geometric random graph
  • Giant component
  • Power law
  • Preferential attachment
  • Resilience
  • Robustness
  • Scale-free network

Cite this

Jacob, E., & Morters, P. (2015). Robustness of spatial preferential attachment networks. In D. F. Gleich, J. Komjathy, & N. Litvak (Eds.), Algorithms and Models for the Web Graph: Proceedings of 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015 (pp. 3-14). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9479). Switzerland: Springer. https://doi.org/10.1007/978-3-319-26784-5_1

Robustness of spatial preferential attachment networks. / Jacob, Emmanuel; Morters, Peter.

Algorithms and Models for the Web Graph: Proceedings of 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015. ed. / D. F. Gleich; J. Komjathy; N. Litvak. Switzerland : Springer, 2015. p. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9479).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Jacob, E & Morters, P 2015, Robustness of spatial preferential attachment networks. in DF Gleich, J Komjathy & N Litvak (eds), Algorithms and Models for the Web Graph: Proceedings of 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9479, Springer, Switzerland, pp. 3-14, 12th International Workshop on Algorithms and Models for the Web Graph, WAW 2015, Eindhoven, Netherlands, 10/12/15. https://doi.org/10.1007/978-3-319-26784-5_1
Jacob E, Morters P. Robustness of spatial preferential attachment networks. In Gleich DF, Komjathy J, Litvak N, editors, Algorithms and Models for the Web Graph: Proceedings of 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015. Switzerland: Springer. 2015. p. 3-14. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-26784-5_1
Jacob, Emmanuel ; Morters, Peter. / Robustness of spatial preferential attachment networks. Algorithms and Models for the Web Graph: Proceedings of 12th International Workshop, WAW 2015, Eindhoven, The Netherlands, December 10-11, 2015. editor / D. F. Gleich ; J. Komjathy ; N. Litvak. Switzerland : Springer, 2015. pp. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{45141d56bd754654961008250befb9fe,
title = "Robustness of spatial preferential attachment networks",
abstract = "We study robustness under random attack for a class of networks, in which new nodes are given a spatial position and connect to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering one can independently tune the power law exponent τ > 2 of the degree distribution and a parameter δ > 1 determining the decay rate of the probability of long edges. We argue that the network is robust if (Formula Presented.), but fails to be robust if (Formula Presented.). Hence robustness depends not only on the power-law exponent but also on the clustering features of the network.",
keywords = "Barabasi-Albert model, Clustering, Geometric random graph, Giant component, Power law, Preferential attachment, Resilience, Robustness, Scale-free network",
author = "Emmanuel Jacob and Peter Morters",
year = "2015",
month = "12",
day = "9",
doi = "10.1007/978-3-319-26784-5_1",
language = "English",
isbn = "9783319267838",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "3--14",
editor = "Gleich, {D. F.} and J. Komjathy and N. Litvak",
booktitle = "Algorithms and Models for the Web Graph",

}

TY - GEN

T1 - Robustness of spatial preferential attachment networks

AU - Jacob, Emmanuel

AU - Morters, Peter

PY - 2015/12/9

Y1 - 2015/12/9

N2 - We study robustness under random attack for a class of networks, in which new nodes are given a spatial position and connect to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering one can independently tune the power law exponent τ > 2 of the degree distribution and a parameter δ > 1 determining the decay rate of the probability of long edges. We argue that the network is robust if (Formula Presented.), but fails to be robust if (Formula Presented.). Hence robustness depends not only on the power-law exponent but also on the clustering features of the network.

AB - We study robustness under random attack for a class of networks, in which new nodes are given a spatial position and connect to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering one can independently tune the power law exponent τ > 2 of the degree distribution and a parameter δ > 1 determining the decay rate of the probability of long edges. We argue that the network is robust if (Formula Presented.), but fails to be robust if (Formula Presented.). Hence robustness depends not only on the power-law exponent but also on the clustering features of the network.

KW - Barabasi-Albert model

KW - Clustering

KW - Geometric random graph

KW - Giant component

KW - Power law

KW - Preferential attachment

KW - Resilience

KW - Robustness

KW - Scale-free network

UR - http://www.scopus.com/inward/record.url?scp=84951870631&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-26784-5_1

DO - 10.1007/978-3-319-26784-5_1

M3 - Conference contribution

SN - 9783319267838

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 14

BT - Algorithms and Models for the Web Graph

A2 - Gleich, D. F.

A2 - Komjathy, J.

A2 - Litvak, N.

PB - Springer

CY - Switzerland

ER -