Fig. 1 Performance on synthetic data. (A) A synthetic network of N = 100 nodes, with ranks drawn from a standard Gaussian and edges drawn via the generative model Eq. 7 for two different values of β and average degree 5. Blue edges point down the hierarchy and red edges point up, indicated by arrows. (B) Accuracy of the inferred ordering defined as the Spearman correlation averaged over 100 independently generated networks. Error bars indicate 1 SD. (C and D) Identical to (A) and (B) but with ranks drawn from a mixture of three Gaussians so that the nodes cluster into three tiers (Materials and Methods). See fig. S1 for performance curves for Pearson correlation r.
Fig. 2 Ranking the history faculty hiring network. (A) Linear hierarchy diagram with nodes embedded at their inferred SpringRank scores. Blue edges point down the hierarchy and red edges point up. (B) Histogram of the empirical distribution of ranks, with a vertical axis of ranks matched to (A). (C) Histogram of ground-state energies from 10,000 randomizations of the network according to the null model where edge directions are random. The dashed red line shows the ground-state energy of the empirical network depicted in (A) and (B). The fact that the ground-state energy is so far below the tail of the null model is overwhelming evidence that the hierarchical structure is statistically significant, with P < 10−4.
Fig. 3 Edge prediction accuracy over BTL. Distribution of differences in performance of edge prediction of SpringRank compared to BTL on real and synthetic networks defined as (A) edge prediction accuracy σa Eq. 12 and (B) the conditional log likelihood σL Eq. 13. Error bars indicate quartiles and markers show medians, corresponding to 50 independent trials of fivefold cross-validation, for a total of 250 test sets for each network. The two synthetic networks are generated with N = 100, average degree 5, and Gaussian-distributed ranks as in Fig. 1A, with inverse temperatures β = 1 and β = 5. For each experiment shown, the fractions of trials in which each method performed equal to or better than BTL are shown in Table 1. These differences correspond to prediction of an additional 1 to 12 more correct edge directions, on average.
Fig. 4 Probabilistic edge prediction accuracy σa of SpringRank versus BTL. For 50 independent trials of fivefold cross-validation (250 total folds per network), the values of σa for SpringRank (SR) and BTL are shown on the vertical and the horizontal axes, respectively. Points above the diagonal, shown in black, are trials where SpringRank is more accurate than BTL. The fractions for which each method is superior are shown in plot legends, matching Table 1.
Fig. 5 Bitwise prediction accuracy σb of Spring Rank versus SyncRank. For 50 independent trials of fivefold cross-validation (250 total folds per NCAA season), the fractions of correctly predicted game outcomes σb for SpringRank and SyncRank are shown on the vertical and the horizontal axes, respectively. Points above the equal performance line, shown in black, are trials where SpringRank is more accurate than SyncRank. The fractions for which each method is superior are shown in plot legends.
- Table 1 Edge prediction with BTL as a benchmark.
Edge prediction with BTL as a benchmark.. During 50 independent trials of fivefold cross-validation (250 total folds per network), columns show the percentages of instances in which SpringRank Eq. 3 and regularized SpringRank Eq. 5 with α = 2 produced probabilistic predictions with equal or higher accuracy than BTL. Distributions of accuracy improvements are shown in Fig. 3. Center columns show accuracy σa, and right columns show σL (Materials and Methods). Italics indicate where BTL outperformed SpringRank for more than 50% of tests. NCAA Basketball data sets were analyzed 1 year at a time.
Data set Type % Trials higher σa versus BTL % Trials higher σL versus BTL SpringRank +Regularization SpringRank +Regularization Computer science (3) Faculty hiring 100.0 97.2 100.0 99.6 Alakāpuram (2) Social support 99.2* 99.6 100.0 100.0 Synthetic β = 5 Synthetic 98.4 63.2 76.4 46.4 History (3) Faculty hiring 97.6* 96.8 98.8 98.8 NCAA Women (1998–2017) (39) Basketball 94.4* 87.0 69.1 51.0 Tenpaṭṭi (2) Social support 88.8 93.6 100.0 100.0 Synthetic β = 1 Synthetic 83.2 65.2 98.4 98.4 NCAA Men (1985–2017) (39) Basketball 76.0* 62.3 68.5 52.4 Parakeet G1 (5) Animal dominance 71.2* 56.8 41.2 37.2 Business (3) Faculty hiring 66.8* 59.2 39.2 36.8 Parakeet G2 (5) Animal dominance 62.0 51.6 47.6 47.2 *Tests that are shown in detail in Fig. 4.
Supplementary Materials
Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/4/7/eaar8260/DC1
Section S1. Deriving the linear system minimizing the Hamiltonian
Section S2. Poisson generative model
Section S3. Rewriting the energy
Section S4. Ranks distributed as a multivariate Gaussian distribution
Section S5. Bayesian SpringRank
Section S6. Fixing c to control for sparsity
Section S7. Comparing optimal β for predicting edge directions
Section S8. Bitwise accuracy σb
Section S9. Performance metrics
Section S10. Parameters used for regularizing ranking methods
Section S11. Supplementary tables
Section S12. Supplementary figures
Table S1. Pearson correlation coefficients between various rankings of faculty hiring networks.
Table S2. Statistics for SpringRank applied to real-world networks.
Fig. S1. Performance (Pearson correlation) on synthetic data.
Fig. S2. Statistical significance testing using the null model distribution of energies.
Fig. S3. Edge prediction accuracy over BTL for NCAA basketball data sets.
Fig. S4. Bitwise edge direction prediction.
Fig. S5. Edge prediction accuracy with twofold cross-validation.
Fig. S6. Summary of SpringRank applied to computer science faculty hiring network.
Fig. S7. Summary of SpringRank applied to history faculty hiring network.
Fig. S8. Summary of SpringRank applied to business faculty hiring network.
Fig. S9. Summary of SpringRank applied to Asian elephants network.
Fig. S10. Summary of SpringRank applied to parakeet G1 network.
Fig. S11. Summary of SpringRank applied to parakeet G2 network.
Fig. S12. Summary of SpringRank applied to Tenpaṭṭi social support network.
Fig. S13. Summary of SpringRank applied to Alakāpuram social support network.
Reference (46)
Additional Files
Supplementary Materials
This PDF file includes:
- Section S1. Deriving the linear system minimizing the Hamiltonian
- Section S2. Poisson generative model
- Section S3. Rewriting the energy
- Section S4. Ranks distributed as a multivariate Gaussian distribution
- Section S5. Bayesian SpringRank
- Section S6. Fixing c to control for sparsity
- Section S7. Comparing optimal β for predicting edge directions
- Section S8. Bitwise accuracy σb
- Section S9. Performance metrics
- Section S10. Parameters used for regularizing ranking methods
- Section S11. Supplementary tables
- Section S12. Supplementary figures
- Table S1. Pearson correlation coefficients between various rankings of faculty hiring networks.
- Table S2. Statistics for SpringRank applied to real-world networks.
- Fig. S1. Performance (Pearson correlation) on synthetic data.
- Fig. S2. Statistical significance testing using the null model distribution of energies.
- Fig. S3. Edge prediction accuracy over BTL for NCAA basketball data sets.
- Fig. S4. Bitwise edge direction prediction.
- Fig. S5. Edge prediction accuracy with twofold cross-validation.
- Fig. S6. Summary of SpringRank applied to computer science faculty hiring network.
- Fig. S7. Summary of SpringRank applied to history faculty hiring network.
- Fig. S8. Summary of SpringRank applied to business faculty hiring network.
- Fig. S9. Summary of SpringRank applied to Asian elephants network.
- Fig. S10. Summary of SpringRank applied to parakeet G1 network.
- Fig. S11. Summary of SpringRank applied to parakeet G2 network.
- Fig. S12. Summary of SpringRank applied to Tenpaṭṭi social support network.
- Fig. S13. Summary of SpringRank applied to Alakāpuram social support network.
- Reference (46)
Files in this Data Supplement:
