Chain motifs: The tails and handles of complex networks

A great part of the interest in complex networks has been motivated by the presence of structured, frequently nonuniform, connectivity. Because diverse connectivity patterns tend to result in distinct network dynamics, and also because they provide the means to identify and classify several types of complex network, it becomes important to obtain meaningful measurements of the local network topology. In addition to traditional features such as the node degree, clustering coefficient, and shortest path, motifs have been introduced in the literature in order to provide complementary descriptions of the network connectivity. The current work proposes a different type of motif, namely, chains of nodes, that is, sequences of connected nodes with degree 2. These chains have been subdivided into cords, tails, rings, and handles, depending on the type of their extremities (e.g., open or connected). A theoretical analysis of the density of such motifs in random and scale-free networks is described, and an algorithm for identifying these motifs in general networks is presented. The potential of considering chains for network characterization has been illustrated with respect to five categories of real-world networks including 16 cases. Several interesting findings were obtained, including the fact that several chains were observed in real-world networks, especially the world wide web, books, and the power grid. The possibility of chains resulting from incompletely sampled networks is also investigated.

Figure 1

Chains can be classified into different types, depending on the connections among their external vertices. Here are shown six types of chains (dark gray vertices): (a) a cord, (b) a tail, (c) a two-tail, (d) a ring, (e) a handle, and (f) an $n$—handle.

Figure 2

The chain can be (a) undirected, (b) directed, or (c) mixed. Mixed chains have arcs in any direction. Note that (c) and (d) are equivalent.

Figure 3

The main steps to identify handles of size greater than 2 in networks are the following. (i) Choose a vertex of degree 2 and add it to a list (dark gray vertex); (ii) go to its neighbors and also add them if they have degree 2; (iii) go to the next neighbors, excluding the vertices already added to the list, and also add them if they have degree 2; (iv) stop adding vertices to the list after finding two vertices of degree greater than 2. In this case, the size of the obtained handle is 6. The same procedure can also be applied to find cords and tails, but at least one extremity should have degree equal to 1.

Figure 4

Number of cords (a), tails (b), and handles (c) of different sizes in the model with Poisson degree distribution. The points are the averaged measured values (each of the error bars corresponds to one standard deviation); the lines are the values computed analytically. Note that the abrupt increase of the width of the error bars is a consequence of the logarithmic scale.

Figure 5

Number of cords (a), tails (b), and handles (c) of different sizes in the model with scale-free degree distribution. The points are the averaged measured values (each of the error bars corresponds to one standard deviation); the lines are the values computed analytically.

Figure 6

$Z$ scores of the number of cords (first column), tails (second column), and handles (third column) for each size. The number of generated random networks was 1000 for all considered networks, except for the WWW, for which it was 100 (because of the substantially larger size of this network).

Figure 7

Distributions shown in (a), (b), and (c) correspond to the most significant data (each distribution has at least three points). Points correspond to the real data, and the solid lines correspond to the theoretical predictions.

Figure 8

(a) and (b) present the number of tails and handles of different sizes in the Erdős-Rényi model, respectively. (c) and (d), on the other hand, present the number of tails and handles for the Barabási and Albert scale-free model, respectively. Each point in the mesh grid is the average obtained by considering 1000 realizations of each random walk.