Title | ||
---|---|---|
Attack Resistance Of Power-Law Random Graphs In The Finite-Mean, Infinite-Variance Region |
Abstract | ||
---|---|---|
We consider a conditionally Poisson random-graph model in which the mean degrees, "capacities," follow a power-tail distribution with finite mean and infinite variance. Such a graph of size N has a giant component that is supersmall in the sense that the typical distance between vertices is of order log logN. The shortest paths travel through a core consisting of nodes with high mean degrees. In this paper we derive upper bounds for the distance between two random vertices when an upper part of the core is removed, including the case that the whole core is removed. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1080/15427951.2008.10129162 | INTERNET MATHEMATICS |
Keywords | Field | DocType |
power law,shortest path,random graph,upper bound,giant component | Graph center,Random regular graph,Discrete mathematics,Combinatorics,Path (graph theory),Random graph,Graph power,Distance,Giant component,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
5 | 3 | 1542-7951 |
Citations | PageRank | References |
1 | 0.38 | 0 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ilkka Norros | 1 | 613 | 86.52 |
H. Reittu | 2 | 46 | 7.16 |