Detecting degree symmetries in networks

The surrounding of a vertex in a network can be more or less symmetric. We derive measures of a specific kind of symmetry of a vertex which we call degree symmetry—the property that many paths going out from a vertex have overlapping degree sequences. These measures are evaluated on artificial and real networks. Specifically we consider vertices in the human metabolic network. We also measure the average degree-symmetry coefficient for different classes of real-world network. We find that most studied examples are weakly positively degree symmetric. The exceptions are an airport network (having a negative degree-symmetry coefficient) and one-mode projections of social affiliation networks that are rather strongly degree symmetric.

Figure 1

(Color online) Illustrations of degree symmetry. Consider paths of length-2 (i.e., $l=2$). All paths out from the central (black) vertex have the degree sequence (3,2) meaning the central vertex has high degree symmetry.

Figure 2

(Color online) Illustrations of concepts in the derivation of the degree symmetry coefficient. (a) illustrates the branching number. Consider paths of length-3 out from $i$. The branching number of the path $(i,j)$ is five (there are five paths from $i$ of length-3 that goes through $j$). The branching number at $j^{\prime }$ is two. (b) shows the set $\Delta (P,i)$, where $P$ is the path $(i,j,j^{\prime })$.

Figure 3

(Color online) Degree symmetries of small example networks. (a) is consistent with the example Fig. 1a. (b) is an example of a graph with only positive degree symmetries. (c) shows a graph with only negative degree symmetries. The cutoff length $l=2$ is used.

Figure 4

(Color online) The average approximative symmetry coefficient for $l=3$ and random graphs with $M=2N$. The line is a fit to a power-law decay form ($0.124+0.435N^{-1.02}$, to be exact).

Figure 5

(Color online) The 2-neighborhood of spermine—a vertex with high degree symmetry—(a), and C04850—a vertex with low degree symmetry—(b), in the human metabolic network. The symbols indicate the equivalence classes defined by exponentially growing intervals. Filled circles have degree 2, unfilled circles have degree 4 or 5, a vertex symbolized by an $n$-gon have degree in the interval $[2^n,2^{n+1})$. In case the chemical names are overly long the KEGG codes are given (“C” and five digits): C07282 represents eIF5A-precursor-deoxyhypusine, C04850 represents $1,3\text{−}\beta \text{−}D$-galactosyl-($\alpha \text{−}1,4\text{−}L$-fucosyl)-$N$-acetyl-$D$-glucosaminyl-$R$, C04556 represents 4-amino-2-methyl-5-phosphomethylpyrimidine, C04467 represents $\alpha \text{−}L$-fucosyl-$1,2\text{−}\beta \text{−}D$-galactosyl-$R$ and C01311 represents $1,4\text{−}\beta \text{−}D$-galactosyl-($\alpha \text{−}1,3\text{−}L$-fucosyl)-$N$-acetyl-$D$-glucosaminyl-$R$.