Research ArticleNETWORK SCIENCE

A physical model for efficient ranking in networks

See allHide authors and affiliations

Science Advances  20 Jul 2018:
Vol. 4, no. 7, eaar8260
DOI: 10.1126/sciadv.aar8260
  • 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 setType% Trials higher σa versus BTL% Trials higher σL versus BTL
    SpringRank+RegularizationSpringRank+Regularization
    Computer science (3)Faculty hiring100.097.2100.099.6
    Alakāpuram (2)Social support99.2*99.6100.0100.0
    Synthetic β = 5Synthetic98.463.276.446.4
    History (3)Faculty hiring97.6*96.898.898.8
    NCAA Women (1998–2017) (39)Basketball94.4*87.069.151.0
    Tenpaṭṭi (2)Social support88.893.6100.0100.0
    Synthetic β = 1Synthetic83.265.298.498.4
    NCAA Men (1985–2017) (39)Basketball76.0*62.368.552.4
    Parakeet G1 (5)Animal dominance71.2*56.841.237.2
    Business (3)Faculty hiring66.8*59.239.236.8
    Parakeet G2 (5)Animal dominance62.051.647.647.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)

    • 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)

      Download PDF

      Files in this Data Supplement:

    Navigate This Article