2.2 Representation of Networks

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.

Table 2.1 Examples of Nodes and Edges in Networks Based on Ref. [4]

There are several types of networks (graphs); the major types are shown in Figure 2.1.

Figure 2.1 Examples of small networks: a simple network (a), a directed network (b), and a weighted network (c) in which the numbers along the edges correspond to the weights. The integers in circles correspond to the labels for nodes.

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.

(2.1)

In simple networks (Fig. 2.1a), the edges have similar weights and A_ij = A_ji and A_ii = 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.