Statistical and Machine Learning Approaches for Network Analysis

2.5 Small-World Network

Interestingly, in networks, the distance between a given node pair is known to be surprisingly small although the network size is very large. This property is referred to as the “small-world property” and was originally known as the “six degrees of separation” in sociology [18]. For example, the small-world property has been experimentally confirmed in the social network formed by the communication via internet tools such as instant-messaging systems [19].

2.5.1 Average Shortest Path Length

The distance between a node pair can be measured using the average shortest path length of a network, which is defined as

(2.14)

where d(i, j) indicates the shortest path length between nodes i and j. In addition, d(i, i) = 0 and d(i, j) =∞, if there is no shortest path between nodes i and j. Thus, the average shortest path length is only calculated in connected networks, in which there are shortest paths between all node pairs.

The ER random network model helps in explaining a small average shortest path length [7] when the probability p is not too small. When considering the breadth-first search from a node on the random network constructed with N nodes and probability p, the total number of nodes within a distance l is approximately expressed as

(2.15)

where k = p(