Week 6: network formation

Question 1

In what way can real-world networks be replicated by random networks?

Answer 1

The short path length in real networks can be replicated by random networks but the high clustering cannot

Question 2

What is the Edos-Renyi random graph model?

Answer 2

A graph of n nodes and each edge appears i.i.d. With probability p

Question 3

What is the main property of the ER model?

Answer 3

Low clustering, low diameter

Question 4

What are the 3 key properties of the ER model?

Answer 4

1. The degree by nodes follows a binomial distribution with average degree p(N-1)
2. Small average path length, even when networks grow large. Average path length ~ log(N)
3. Less local clustering than real networks. The expected mean local clustering coefficient is c_rand = p

Question 5

What is the typical path length between two people in the US?

Answer 5

6

Question 6

What is a regular/clustered network?

Answer 6

A lattice where each node is connected to the k nodes closest to it

Question 7

What is the small-world random graph model?

Answer 7

Start with a low-dimensional regular lattice. For each edge with a rewire probability p_r move the end of the edge to a non-neighbouring node

Question 8

What is the main property of the small-world model?

Answer 8

High clustering, low diameter

Question 9

What is a property of the clustering coefficient in the small-world model?

Answer 9

The clustering coefficient is independent of the network size

Question 10

How do you get the small-world model to have high clustering, low diameter?

Answer 10

As you increase p_r, the average shortest path decreases quicker than the global clustering coefficient. Therefore there is a range of pr that gives high clustering low diameter. p_r approx between 0.001 and 0.05

Question 11

What is the reason for small average path length in the small-world model?

Answer 11

Every random shortcut is likely to connect widely separated parts of the graph

Question 12

What is the degree distribution for small-world network?

Answer 12

Similar to a random graph

Question 13

What is the time required for a maximally infectious disease to infect the entire population in a small-world network?

Answer 13

Follows the same path as the average path length

Question 14

What is the university of the network topology?

Answer 14

many real networks converge to similar architectures (degree distribution), independent of the scale of the system

Question 15

What is the distribution of a random network?

Answer 15

Poison distribution

Question 16

What is the distribution of a large real-world network? And the formula?

Answer 16

Power law distribution (scale-free), many nodes with small degrees and few nodes with high degrees. p(k)= proportion of nodes with k neighbours. p(k) = k^-gamma

Question 17

What is the distribution of the world-wide web

Answer 17

Power law distribution

Question 18

What are growth and preferential attachment in the real-world?

Answer 18

Growth: real-world networks from by the continuous addition of new nodes
Preferential attachment: new nodes are more likely to link to nodes of higher degrees

Question 19

How is the barabasi-albert model formed?

Answer 19

Growth: at each time step we add a new node with m links

Preferential attachment: the probability that a link of the new node connects to node i depends on the degree of node i

Question 20

What is another name for the barabasi-albert model?

Answer 20

Scale-free model

Question 21

What is the first mover advantage?

Answer 21

The earlier node i is added, the higher will be its degree

Question 22

What are the properties for the standard BA model, compared with real-world networks?

Answer 22

1. Average path length ~ log(N)/log(log(N)). Systematically underestimates average path length
2. The global clustering coefficient rapidly decreases with network size (smaller than real-world)

Question 23

How does a BA network handle targeted attacks?

Answer 23

Extremely vulnerable to attacks, a few nodes play a vital role in maintaining the networks connectivity

Question 24

How does a BA network handle random failures?

Answer 24

High error tolerance, communication ability of the nodes are unaffected even by high failure rates.

Question 25

What happens as nodes are removed from a BA model randomly?

Answer 25

As fraction of nodes removed increases, network diameter barely increases. The large component remains connected until high f

Question 26

What happens as nodes are removed from a BA model by targeted attack?

Answer 26

As fraction of nodes removed increases, network diameter increases a lot, the network becomes disconnected quickly

Question 27

What is the controversy of the BA model?

Answer 27

A study showed that strongly scale-free structure is empirically rare. For most networks log-normal distributions fit the data too

Question 28

What are 5 variants of the BA model?

Answer 28

1. Non-linear preferential attachment. When alpha <1, the degree distribution is sublinear closer to random network. When alpha>1 the degree distribution is superlinear, fewer big hubs and many small hubs, winner takes all market.
2. Internal links: two nodes that are already in the network can choose to connect to each other
3. High degree cutoffs: a cut-off in the degree distribution of a finite size due to structural limitations
4. Age correction: first mover advantage is not always true e.g. citation networks
5. Local-world evolving model: considers preferential attachment but only for existing nodes in the same area