Reviews of EE6605 Lesson 2

Last week, Professor Chen briefly introduced graph theories, three types of networks, and some fundamental concepts of the complex studies. This week, he focused on Paul Erdős and Alfréd Rényi's random graph theory.

Assume that there are N isolated nodes. Let's randomly link two of them to generate a random graph network. We use p to represent the probability of randomly linking two nodes. Here, the number of all links can be easily calculated, which is K (number of links) = p*N (N-1)/2. Professor Chen also demonstrated how to calculate L(the average path length) and C(the cluster coefficient) step by step.

http://www.nature.com/nphys/journal/v6/n7/full/nphys1665.html

What impressed me most was the comparison between various real networks, such as social networks, information networks, protein networks, and so on. Networks which have relatively small L and small C are more likely the random graph networks. Meanwhile, small L and large C are features of small world networks. Those that follow the power-law distribution are scale-free networks.

However, in our daily life, networks composed of isolated nodes are rare. What if the nodes are not isolated and the edges are not randomly linked?