Name
Abstract | ||
|---|---|---|
Consider a preferential attachment model for network evolution that allows both node and edge arrival events: at time t, with probability $$p_t$$ a new node arrives and a new edge is added between the new node and an existing node, and with probability $$1-p_t$$ a new edge is added between two existing nodes. In both cases existing nodes are chosen at random according to preferential attachment, i.e., with probability proportional to their degree. For $$\\delta \\in 0,1$$, the $$\\delta $$-founders of the network at time t is the minimal set of the first nodes to enter the network i.e., founders guaranteeing that the sum of degrees of nodes in the set is at least a $$\\delta $$ fraction of the number of edges in the graph at time t. We show that for the common model where $$p_t$$ is constant, i.e., when $$p_t=p$$ for every t and the network is sparse with linear number of edges, the size of the $$\\delta $$-founders set is concentrated around $$\\delta ^{2/p} n_t$$, and thus is linear in $$n_t$$, the number of nodes at time t. In contrast, we show that for $$p_t=\\min \\{1,\\frac{2a}{\\ln t}\\}$$ and when the network is dense with super-linear number of edges, the size of the $$\\delta $$-founders set is sub-linear in $$n_t$$ and concentrated around $$\\tilde{\\Theta }n_t^{\\eta }$$, where $$\\eta =\\delta ^{1/a}$$. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-47666-6_39 | ICALP |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Degree distribution,Mathematics,Preferential attachment | Conference | 9135 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.51 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chen Avin | 1 | 608 | 48.60 |
| Zvi Lotker | 2 | 1000 | 79.68 |
| Yinon Nahum | 3 | 5 | 0.85 |
| David Peleg | 4 | 6662 | 824.19 |