Eight Properties of Social Network (1~4)

這幾天 survey 關於 social network 相關研究後，從 M. E. J. Newman 以及 Christos Faloutsos 的論文中歸納了以下八項 social network 或者說是 complex system 的特性（我用英文寫，感覺比較有學問 XD）：

Recently, during my survey for social network and complex system from papers of M. E. J. Newman, I think it could be briefly summed up to eight properties, as follows:

1. Network diameter
The diameter of a network is the length (edges) of the longest path between any two nodes. Generally, the diameter is small, like 6 of small-world phenomenon, and it is independent of network size. The small-world effect imply the dynamics of processes taking place on networks. e.g. fast spread of information for the network, like rumor. This effect also underlies some well-known parlor games, particularly the calculation of Erdős number and Bacon Number.

2. Network Transitivity or Clustering
The concept was derived from the behavior of random graph. The most comprehensible instance is that the friend of your friend is likely to be your friend. In terms of graph topology, transitivity means the presence of a heightened number of triangles in the network - sets of three nodes each of which is connected to each of the others. It can be measured through the definition of clustering coefficient C (with an example):


3. Degree distribution
The degree of a node in a network is the number of links connected to that node. We can define a probability pk to be the fraction of nodes in the network that have degree k. Meanwhile, the pk could be considered as an uniform probability for choosing nodes with degree k at random. Plot pk (vertical axis) with degree k (horizontal axis) for some networks can form a histogram of degree distribution of nodes, as follows.

It is observed that the degrees of nodes are highly right-skewed. In other words, the distribution has a long right tail, or heavy-tailed distribution, it might be the well-known long tail effect. Alternatively, this distribution can be plotted in a logarithmic method, as follows. Marvellously, it is nearly conformed with Power law, which is the primary property of scale-free network. In contrast to the Poisson distribution of random graph (Erdős-Rényi model).


4. Network resilience
The resilience of network means the removal of its nodes, which is related to the concept of degree distributions. The function and structure of a network usually rely on its connectivity. Once some nodes are removed, the length of paths could be increase, even the network becomes disconnected. However, there are a different ways to remove the nodes. One way to remove the nodes in a network is to random removal. This approach wouldn't affect the distances between nodes almost since most nodes in a network have low degree and therefore lie on few paths between others. The other way to remove nodes from networks is targeted at high-degree nodes. Needless to say, it will have tremendous effects on the structure of a network. And the distance would increase acutely with the fraction of nodes removed. The following picture can explan it! (Note blue for random removal and red for high-degree removal.)