This repo is where I am going to be pushing some general implementations of models from the advanced algorithms two module to. Also decided I am going to be slapping some general notes in this README file.
- An implementation for the generation of the ER Random, complex network model.
- Some notes about structural properties of:
- ER-Random Networks.
- Hopefully I won't forget to add more here when I actually commit other code.. (I am only human!)
- Average Path Length (size)
- Global Clustering Coefficient (density)
- Degree Distribution (connectivity)
- Topological Characteristics:
- Centrality (Degree, Closeness, Betweenness)
- Mixing Patterns
- Classification & properties of different network models:
- ER-Random
- Small World:
- Watts-Strogatz
- Newman-Watts
- Scale Free:
- Barabási and Albert (BA) Model
- BA Variant: Rewiring
- BA Variant: Competition
Check out the ER-Random folder in the Repo.
- AVG Node Degree: < k > = 2M / N = p(N - 1) ~= pN.
- AVG Path Length: L ~ ln(N) / ln(< k >).
- L increases logarithmically with the size of the network (Small World Property)
- ln(N) grows much slower than N (see plot How ln(N) varies as N increases.png in repo) -> a very large sized usually has a relatively small L. Additional reasoning: The numerator for L is growing very slowly and the denominator for L is decreasing, therefore L is increasing as N is increasing. Therefore as more nodes are added to the network, the average path length is decreasing.
- Clustering Co-Efficient: C = p ~= / N << 1.
- Node Degree Distribution follows a Poisson distribution. (Need to think about this one a little more..)
- ER Random graphs are not small world networks, even though they exhibit a small L. This is because they generally do not have a large clustering co-efficient, it is fairly small and C ~ p, which makes sense if you take a look at the figureOne in the repo.
- ER Random graphs have a small clustering coefficient (this is a distinguishing characteristic).
Its also important to note that these types of graphs have an emergent feature, in this case, you generally see the appearance of cycles or a giant component at some threshold value of p.
Check out the Small-World-Network folder in the Repo.
Small world networks are more like real world networks, two distinguishing characteristics of small world networks are as follows:
- Short AVG path length.
- High clustering coefficient.
And there exist two primary models that we need to know about (for the exam anyway):
- Watts-Strogatz Model
- Newman-Watts variant of the Watts-Strogatz Model.
- Initialise a regular nearest-neighbour coupled network of N nodes arranged in a ring, in which each node i is symmetrically connected to its nearest neighbours i ± 1, i ± 2, ..., i ± K/2 with K an even integer (being the number of adjacent nodes to i). The number of links is NK/2.
- Randomisation: Randomly rewire each link of the network with probability p: a. For every node i (i = 1,...,N), each link connected to a clockwise (or counter-clockwise) neighbour of i is rewired to a randomly chosen node (from anywhere in the network) with a probability of p. b. The link will be preserved with a probability 1 - p.
Implementation!
- Eva Navarro Lopez (2015), Advanced Algorithms 2 Lecture Slides, University of Manchester.
- Alain Barrat, Marc Barthelemy, Alessando Vespignani (2008), Dynamical Processes on Complex Networks, Cambridge University Press.