Searching for Key Cycles in a Complex Network

Searching for key nodes and edges in a network is a long-standing problem. Recently cycle structure in a network has received more attention. Is it possible to propose a ranking algorithm for cycle importance? We address the problem of identifying the key cycles of a network. First, we provide a more concrete definition of importance—in terms of Fiedler value (the second smallest Laplacian eigenvalue). Key cycles are those that contribute most substantially to the dynamical behavior of the network. Second, by comparing the sensitivity of Fiedler value to different cycles, a neat index for ranking cycles is provided. Numerical examples are given to show the effectiveness of this method.

Figure 1

The generation of a connected graph. Starting from node 1, hanging nodes 2, 3, 4, 5, and 6 in turn to get a spanning tree. Then adding other edges to get the connected graph.

Figure 2

Adding weight $\epsilon$ to cycle (1,2,3), namely adding weight $\epsilon$ to each edge of this cycle.

Figure 3

A sample network with 6 cycles. Cycles are identified as $c_1,c_2,\dots ,c_6$ which are depicted by distinct colors.

Figure 4

The variation trend of $\delta {\lambda }_{c_i}^{\epsilon }$ versus the variation of $\epsilon \in [0,4]$ in the sample network.

Figure 5

The norm of error $e_j(t)=||{\xi }_j(t)-s(t)|{|}_2$, $1\le j\le 8$ versus time $t$ by, respectively, controlling cycles $c_1$, $c_3$, and $c_6$ in the network in Fig. 3, where ${\xi }_j(t)$ and $s(t)$ are the node state and the synchronization state respectively. The average error is obtained after 50 simulations by using initial state value range of $[-25,25]$.

Figure 6

The ranking result and the corresponding locations of triangles in the C. elegans metabolic network.

Figure 7

The variation trend of $\delta {\lambda }_{c_i}^{\epsilon }$ versus the variation of $\epsilon \in [0,3]$ in the C. elegans metabolic network. The $c_1,\dots ,c_{11},c_{3284}$ are shown. The ranking results with $\delta {\lambda }_{c_i}^{\epsilon }$ and $I_{c_i}$ are consistent when $\epsilon <0.025$.