Preferential Attachment Model

There is a fundamental dichtomy between “generative” models and “non-generative” models. Generative models, tell you how the graph is generated; it is a rather simple recipe for sampling the graph; it is also a “story” about how the world might generate a graph. “Non-generative” models do not provide this intuition; perhaps instead, they give a probability distribution.

The preferential attachment model is a simple story of how to sample a graph. This story generates a graph with a power law degree distribution. In essence, it is the story of “the rich getting richer”.

1. Start out with an initial graph. For example, \(G_2\) is a simple dyad.
   
2. Iteratively add nodes to the graph. Each node has \(m\) edges that they connect to the previous nodes with probability proportional to the previous nodes current degree.

Probabilists like the regime \(m=1\). Do you notice anything funny about this regime?

library(igraph)
plot(barabasi.game(30, m=1))

plot(barabasi.game(30, m=2))

transitivity(barabasi.game(1000, m=2))

## [1] 0.01112765

mean(transitivity(barabasi.game(1000, m=2), type = "local"))

## [1] 0.1105688

mean(transitivity(barabasi.game(1000, m=2), type = "local"))

## [1] 0.111008

transitivity(barabasi.game(1000, m=5))

## [1] 0.03148695

mean(transitivity(barabasi.game(1000, m=5), type = "local"))

## [1] 0.3082898

mean(transitivity(barabasi.game(1000, m=5), type = "local"))

## [1] 0.2492136

transitivity(barabasi.game(1000, m=10))

## [1] 0.05731902

mean(transitivity(barabasi.game(1000, m=10), type = "local"))

## [1] 0.4813237

mean(transitivity(barabasi.game(1000, m=10), type = "local"))

## [1] 0.5028854

Between sparse ER graphs and preferential attachment graphs, which should have larger pairwise distances?

diameter(erdos.renyi.game(n = 1000,p.or.m = 10/1000))

## [1] 6

diameter(barabasi.game(1000, m=10),directed = F)

## [1] 3

diameter(erdos.renyi.game(n = 10000,p.or.m = 10/10000))

## [1] 7

diameter(barabasi.game(10000, m=10),directed = F)

## [1] 4

Which is more likely to be disconnected?

is.connected(erdos.renyi.game(n = 10000,p.or.m = 2/10000))

## [1] FALSE

is.connected(barabasi.game(10000, m=2),mode = "weak")

## [1] TRUE