Week 6: network formation Flashcards
In what way can real-world networks be replicated by random networks?
The short path length in real networks can be replicated by random networks but the high clustering cannot
What is the Edos-Renyi random graph model?
A graph of n nodes and each edge appears i.i.d. With probability p
What is the main property of the ER model?
Low clustering, low diameter
What are the 3 key properties of the ER model?
- The degree by nodes follows a binomial distribution with average degree p(N-1)
- Small average path length, even when networks grow large. Average path length ~ log(N)
- Less local clustering than real networks. The expected mean local clustering coefficient is c_rand = p
What is the typical path length between two people in the US?
6
What is a regular/clustered network?
A lattice where each node is connected to the k nodes closest to it
What is the small-world random graph model?
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
What is the main property of the small-world model?
High clustering, low diameter
What is a property of the clustering coefficient in the small-world model?
The clustering coefficient is independent of the network size
How do you get the small-world model to have high clustering, low diameter?
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
What is the reason for small average path length in the small-world model?
Every random shortcut is likely to connect widely separated parts of the graph
What is the degree distribution for small-world network?
Similar to a random graph
What is the time required for a maximally infectious disease to infect the entire population in a small-world network?
Follows the same path as the average path length
What is the university of the network topology?
many real networks converge to similar architectures (degree distribution), independent of the scale of the system
What is the distribution of a random network?
Poison distribution
What is the distribution of a large real-world network? And the formula?
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
What is the distribution of the world-wide web
Power law distribution
What are growth and preferential attachment in the real-world?
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
How is the barabasi-albert model formed?
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
What is another name for the barabasi-albert model?
Scale-free model
What is the first mover advantage?
The earlier node i is added, the higher will be its degree
What are the properties for the standard BA model, compared with real-world networks?
- Average path length ~ log(N)/log(log(N)). Systematically underestimates average path length
- The global clustering coefficient rapidly decreases with network size (smaller than real-world)
How does a BA network handle targeted attacks?
Extremely vulnerable to attacks, a few nodes play a vital role in maintaining the networks connectivity
How does a BA network handle random failures?
High error tolerance, communication ability of the nodes are unaffected even by high failure rates.
What happens as nodes are removed from a BA model randomly?
As fraction of nodes removed increases, network diameter barely increases. The large component remains connected until high f
What happens as nodes are removed from a BA model by targeted attack?
As fraction of nodes removed increases, network diameter increases a lot, the network becomes disconnected quickly
What is the controversy of the BA model?
A study showed that strongly scale-free structure is empirically rare. For most networks log-normal distributions fit the data too
What are 5 variants of the BA model?
- 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.
- Internal links: two nodes that are already in the network can choose to connect to each other
- High degree cutoffs: a cut-off in the degree distribution of a finite size due to structural limitations
- Age correction: first mover advantage is not always true e.g. citation networks
- Local-world evolving model: considers preferential attachment but only for existing nodes in the same area
