Statistical and Machine Learning Approaches for Network Analysis

2.3 Classical Network

How are real-world networks constructed? Although it is difficult to answer this question, we have used ideal models to discuss network structure.

These models are not in complete agreement with real-world networks (see Section 2.4 and subsequent sections for details). However, these models are the basis of complex networks, and they contribute toward understanding network science in the future. Next, we briefly discuss some classical network models.

2.3.1 Random Network

In 1960, the Erdös–Rényi model (the so-called “random network model”) was proposed by two mathematicians, Erdös and Rényi, with the assumption that networks are randomly constructed because their identities are averaged when the system has many elements [5]. This model is considered in several fields such as sociology, ecology, and mathematical biology because of its simplicity.

In addition, the random network model serves as a foundation for network analysis. Although random networks conflict with real-world networks (see Section 2.4 and subsequent sections for details), we can evaluate the significance of statistical properties observed in real-world networks on the basis of the discrepancy between random networks and real-world ones.

Model networks are generated as follows: supposing N nodes, the edges are drawn between the nodes with probability p. In the case of simple networks, the expected number of edges E is expressed as

(2.2)

because the total number of possible edges (combinations) ...