Characterizing cycle structure in complex networks

• The cycle number matrix counts shortest cycles shared by node pairs, and cycle ratio uses this matrix to measure a node’s participation in other nodes’ shortest cycles.Source: Results · p. 4
• The index considers only each node’s shortest cycles because longer cycles are usually less relevant to network functions and counting all cycles is infeasible amid exponential growth in cycle counts.Source: Results · p. 4
• The average Kendall’s τ among degree, H-index, and coreness is 0.89, while cycle ratio and betweenness have low correlations with other indices and add distinct ranking information.Source: Figure 2 · p. 6, Results · pp. 6–7
• The dispersed selections by cycle ratio and betweenness are advantageous when choosing a set of vital nodes, because clustering can cause influential areas to overlap.Source: Results · p. 7
• In Yeast, cycle ratio’s Kendall’s τ is 0.56 with betweenness and 0.09 with articulation ranking, suggesting it may reveal insights not directly obtained from other centralities.Source: Results · p. 7
• In the Yeast network, degree, H-index, and coreness select clustered, densely connected nodes, whereas cycle ratio and betweenness select dispersed nodes with sparser connections.Source: Results · p. 7, Figure 3 · p. 8
• Betweenness usually collapsed networks fastest, with its advantage emerging later; it had the best robustness R, while cycle ratio was close and articulation ranking was worst.Source: Figure 4 · p. 9, Results · p. 9, Table 2 · p. 11
• Under pinning efficiency, betweenness and articulation ranking outperformed cycle ratio, which outperformed degree, H-index, and coreness.Pinning efficiency characterizes index performance in pinning control; faster decay indicates better performance.Source: Results · p. 10, Table 3 · p. 11
• On synthetic ER and BA networks, cycle ratio performed in the middle of the six indices, possibly because both network types lack short cycles.Source: Results · pp. 12–13
• Across 24 real-network/time-step comparisons, cycle ratio ranked No. 1 14 times, No. 2 eight times, and No. 3 twice, outperforming other indices overall.The comparisons covered six networks and four time steps.Source: Results · p. 12, Figure 6 · p. 13

Discussion

• Cycle ratio and betweenness outperform the other indices in identifying vital nodes for connectivity, pinning control, and epidemic spreading.The reported applications include maintaining connectivity, facilitating network synchronization, and influencing epidemic spreading.Source: Discussion · p. 14
• For node percolation, the top-ranked nodes should be protected to maintain connectivity or considered primary targets in an intentional attack.The discussion relates such scenarios to power grids, air transportation, financial networks, and the Internet.Source: Discussion · p. 14
• Including longer cycles does not necessarily improve cycle ratio, because greater overlap among nodes’ associated cycles can reduce discriminability and accuracy.The discussion attributes this to longer cycles depressing differences in local cycle structure.Source: Discussion · p. 14
• Cycle ratio cannot be applied to trees or tree-like networks, and assigns zero to cycle-free nodes even when their influences differ.The discussion suggests combining cycle ratio with another index, such as degree, to rank nodes with zero cycle ratio.Source: Discussion · pp. 14–15
• The cycle-structure method can extend to hypernetworks by treating hyperedges as cycles and measuring node participation in other nodes’ hyperedges.The proposed construction uses the incidence matrix multiplied by its transpose.Source: Discussion · p. 15
• Degree-preserved null, Watts–Strogatz, and Barabási–Albert models do not reproduce real networks’ cycle-based statistics, motivating further study of how cycles form.The discussion also identifies cycle-based indices for link prediction and study of longer and higher-order cycles as future directions.Source: Discussion · p. 15

Resource Availability

• Further information and requests for resources and reagents should be directed to the lead contact.Source: Resource Availability · p. 16
• Data used in the work are provided as Supporting Data and can also be accessed at the stated link.The passage supplies the resource URL.Source: Resource Availability · p. 16

Methods

• Degree counts immediate neighbors, H-index uses neighbors with degrees at least h, and coreness is obtained through k-core decomposition.Coreness is also referred to as the k-shell index.Source: Methods · p. 16
• Betweenness is the fraction of shortest paths between node pairs passing through a node, while articulation ranking counts components added upon its deletion.Source: Methods · p. 16
• Kendall’s Tau compares two indices by counting concordant and discordant node pairs, with adjustments for tied values.The method states that Tau near zero indicates independent indices and that values exceeding zero indicate correlation strength.Source: Methods · pp. 16–17

I. The number of cycles with different lengths

• Fig. S1 plots the number of cycles with different lengths on log-linear axes.The supplied text does not state the plotted cycle-count values or a specific trend.Source: Figure S1 · p. 21, §I · p. 21
• Correlations among degree, H-index, and coreness are very high, while cycle ratio’s correlations with the other indices are much lower.Fig. S2 presents correlation matrices for six indices across six real networks.Source: §II · p. 22, Figure S2 · p. 22
• The correlation matrices encode pairwise Kendall’s Tau values for real networks, with each value represented by color.The indices are degree, H-index, coreness, cycle ratio, betweenness, and articulation ranking.Source: §II · p. 22

III. Distributions of indices

• Cycle ratio has good distinguishability in the distributions of six indices across six real networks.Source: §III · p. 23
• Histograms compare the six indices for C. elegans, Email, and Jazz.Source: Figure S3 · p. 23, Figure S4 · p. 23, Figure S5 · p. 24
• Histograms also compare the six indices for NS, USAir, and Yeast.Source: Figure S6 · p. 24, Figure S7 · p. 25, Figure S8 · p. 25

IV. Detailed results for epidemic spreading

• Spreading comparisons cover the first 10 time steps at infection probabilities 0.5β_c, β_c, and 2β_c, averaged over 1,000 independent runs.Source: §IV · pp. 26, 29
• Separate matrices show rankings of the six indices at corresponding time steps, with darker or warmer colors indicating better performance.Source: Figure S10 · p. 27, Figure S12 · p. 29
• The figures report cumulative infected-node counts with the top-0.05N or top-0.1N nodes as initially infected seeds.Source: §IV · p. 26, Figure S9 · p. 26

V. Results for synthetic networks

• The study uses Erdős–Rényi and Barabási–Albert networks, whose basic topological features are tabulated.Source: §V · p. 30, Table S1 · p. 30
• Node percolation is evaluated by largest-component size against the fraction of removed nodes, with robustness reported for both synthetic networks.Source: Figure S13 · p. 30, §V · p. 30, Table S2 · p. 30
• Pinning control is evaluated by synchronizability against the pinned-node fraction, with pinning efficiency reported for both network types.Source: Figure S14 · p. 31, §V · p. 31, Table S3 · p. 31
• For epidemic spreading, the top-0.1N nodes selected by each index are infected initially at β=β_c, and matrices compare the six indices over time.Source: Figure S15 · p. 31, §V · p. 31

VI. Performance of longer cycles

• The three cycle-ratio variants use each node’s shortest cycles, cycles up to its second-shortest-cycle length, or cycles up to its third-shortest-cycle length.Source: §VI · p. 32
• Because calculating longer cycles is highly time-consuming, the variants are tested on only two smaller networks.Source: §VI · p. 32
• The comparisons cover node percolation and pinning control, reporting robustness and pinning efficiency for the three cycle-ratio variants.Source: §VI · p. 32, Figure S16 · p. 32, Table S4 · p. 32

VII. Distributions of sizes of shortest cycles

• Degree-preserved null networks are generated by repeatedly rewiring pairs of links while retaining the original network’s degree sequence.The rewiring replaces two links with two different links when the proposed new links do not already exist.Source: §VII · p. 34
• Real networks’ shortest-cycle size distributions differ significantly from degree-preserved null networks, and most cycles in real networks’ set S have size 3.The comparison covers the size distributions of shortest cycles in set S.Source: Figure S18 · p. 34, §VII · p. 34
• Shortest-cycle distributions in Watts–Strogatz and Barabási–Albert networks are significantly different from those in real networks.The comparisons use model networks with various parameters.Source: §VII · pp. 34–35, Figure S19 · p. 35, Figure S20 · p. 35