This chapter is from the book
This chapter is from the book
This chapter is from the book
1.2 Types of Complex Networks
Complex networks can be classified into the following major types: random networks, small-world networks, and scale-free networks.
Random networks can be considered as models of physical systems where the connectivity between subsystems is probabilistically determined. In other words, a random network consists of a probabilistic model of a graph where the edges are determined with certain probability value p.
Physical systems of similar kind can interact among themselves with certain probability; therefore, models of such interactions can result in a random graph. For example, consider a social network that involves people and the relationship between people in a society. Many times, social interactions can happen through random events, and when we model the social relationship, the social relationship can be a random function characterized by a probability value p or a probability distribution function. Interaction between many physical parameters can be considered in a similar way. In communication networks such as ad hoc wireless networks [12], formed by highly mobile nodes communicating over wireless channels, network topology can change frequently. Further, the wireless channels limit the range of communication possible for a given ad hoc network node. Therefore, network topology of such an ad hoc wireless network for an instant can also be considered a random network.
Another example of a complex network is the road networks that show arbitrary topologies, as can be found in the road networks in a variety of urban settlements around the world. Figure 1.3 shows the network representation of the roads and intersections in several cities located in the United States, Europe, and India. The US locations are New York City, Manhattan Borough, Los Angeles, and Detroit. Each of the 13 types of roads is represented as a different colored line and presented accordingly for better visual perception of complex network representation of the road networks. It can be noticed that the road networks of New York and Manhattan are closer to a regular network topology. In comparison to the road networks of the United States, road networks of European cities have significant differences in the visual representation, as can be found from the city maps of London, Paris, Milan, and Berlin in Figure 1.3. The larger number of footways, tracks, steps, and paths gives a different look to the European cities. Compared to the networks of US and European cities, those of the Indian cities such as Bangalore, Chennai, Kolkata, and New Delhi have a very different visual appearance. Despite the differences in the visual appearances of these networks, the graph theoretical characteristics do not show significant difference, as can be observed in [13]. All these road networks can be seen as network topologies that can be instances of random network topologies.
)
Figure 1.3 Examples of road networks. Road types are numbered as superscripts1−13. © [2016] IEEE. Reprinted, with permission, from Sarath Babu and B. S. Manoj, “On the topology of indian and western road networks,” in Proc. 2016 Eighth International Conference on COMmunication Systems and NETworkS (COMSNETS 2016) Intelligent Transportation Systems Workshop, pp. 1–6, January 2016.
Graphs created by mathematical models can also be considered as random networks. For example, in order to study the behavior of a network through mathematical analysis, a graph can be created using mathematical models for network edges between node pairs. Study of such mathematical modeling can be useful in revealing properties of complex systems with similar network formation.
Small-world networks are either formed by natural formation processes or created artificially by network designing processes aimed specifically at achieving small-world characteristics. The most important element of small-world properties is that the average path length (APL) is lower than that of a regular network. In addition to a lower APL, small-world networks exhibit a low average clustering coefficient (ACC). Many large-scale natural networks are found to have very small APL, O(log N), where N is the number of nodes in the network, despite having large network size N. Further, regular networks can be transformed to bring down the APL by adding long-ranged links. Small-world networks have many applications in real-world networks. In Chapter 4, more details on small-world networks are provided, and in Chapters 6 and 7, small-world transformations of wireless mesh networks (WMNs) and wireless sensor neworks (WSNs) are discussed.
Studies of real-world networks, by the complex network research community, led to a very important observation that many real-world networks demonstrate a scale-free property. The scale-free property is defined by the degree distribution of the network nodes following a linear line on a log-log scale. That is, in a scale-free network, the probability of finding a node with a certain degree decreases rapidly with higher degrees. In other words, a fraction of nodes with degree D, represented as P(D) ∼ D−γ where 1 ≤ γ ≤ 3, is the scaling exponent. Scale-free networks have many interesting characteristics, one of which is the ultra small-world property, which results in the network having APL of O(log log N) where N is the number of nodes in the network. Identifying a real-world network as following a scale-free distribution helps in quickly characterizing the properties of the network. Chapter 5 provides details of scale-free networks.
