Networks are represented as sets of nodes and edges drawn between the nodes; thus, networks are essentially similar to “graphs” in mathematics. Examples of networks representing real-world systems are listed in Table 2.1.
Network | Nodes | Edges |
Internet | Computer or router | Cable or wireless data connection |
World Wide Web | Web page | Hyperlink |
Citation relationship | Article, patent, or legal case | Citation |
Power grid | Generating station or substation | Transmission line |
Friendship network | Person | Friendship |
Metabolism | Metabolite | Metabolic reaction |
Food web | Species | Predation |
There are several types of networks (graphs); the major types are shown in Figure 2.1.
In the simplest case, networks are represented as shown in Figure 2.1a. The relationship (or interaction) between two given nodes is represented in a network by drawing edges between the nodes. In this case, multiedges, which refer to multiple edges between the same pair of nodes, and self-edges, in which the source is identical to the target, are neglected for simplicity. However, the above-mentioned edges are important in certain networks. For instance, multiedges are necessary if there are different types of interactions between the same pair. Further, self-edges are considered as self-regulations.
In the above case, we assume that the relationships are symmetric. However, the direction of a relationship is often observed in real-world systems. In food webs, for example, lions prey on gazelles but gazelles never eat lions. These asymmetric interactions are represented as directed networks (see Fig. 2.1b).
In addition to direction, the weight (or strength) of edges is also important in real-world systems although it is not considered in the above networks. In the World Wide Web, for example, the weight of hyperlinks for famous sites (e.g., Google and Yahoo!) may be different from those of personal sites that are visited by only a few people. Such systems are represented as weighted graphs (see Fig. 2.1c).
As with the networks mentioned above, several types of networks are generally expressed using the adjacency matrix, where multiedges are considered as weighted edges (e.g., three edges drawn between a node pair are regarded as an edge with weight 3). The weights of unweighted edges are considered as 1.
In simple networks (Fig. 2.1a), the edges have similar weights and Aij = Aji and Aii = 0 are satisfied. The representation of these networks can be well utilized due to their simplicity.
In this chapter, we consider the same simple network (i.e., Fig. 2.1a), unless specified otherwise.
3.15.186.79