The AUC-ROC is a widespread measure to assess the performance of a binary classification model across various discrimination thresholds. Yet, it is not apt for unbalanced class problems and is misleading for early retrieval. For instance, link prediction in complex networks is an unbalanced early retrieval problem, whose goal is to offer a ranking of the nonobserved network links, prioritizing a small cohort of positive links (for which we are sure the labels are reliable) on top of a list largely populated by unlabeled links (for which the labels are uncertain). Differently from binary classification, here the evaluation focuses on how the predictor prioritizes the positive class, because the negative class does not exist and is replaced by an unlabeled class. For decades, scholars have been investigating the necessity to correct and to generalize the AUC-ROC to work for both unbalanced classification and early retrieval evaluation, this is requested in many applied domains of computational science. Here we propose the area under the magnified ROC (AUC-mROC), a new measure that adjusts the standard AUC-ROC to work for unbalanced early retrieval problems such as link prediction. Finally, we introduce the area under the generalized ROC (AUC-gROC), which unifies both AUC-mROC and AUC-ROC to provide a universal and reliable evaluation measure that can work for both classification and early retrieval problems, regardless of class proportion.This discovery represents a critical achievement, culminating in success after decades of contentious research. Its solution promises to significantly impact various domains within applied computational science.
Hyperbolic geometry explains many structural features of real-world networks, yet existing hyperbolic generative network models with community organization such as the nonuniform popularity-similarity optimization (nPSO) are restricted to unipartite graphs. Here we introduce a bipartite extension of the nPSO model called nBPSO, motivated by the prevalence of community organization in real-world bipartite networks and the emerging evidence of hyperbolic hierarchical connectivity in trained sparse neural networks. nBPSO provides explicit control over link density, degree distribution, average clustering, and community organization. We engineer the model to generate consecutive and concatenated bipartite layers, enabling initialization of dynamic sparse training multilayer perceptron neural networks with tunable hyperbolic organization for each layer. We find that task-agnostic (unaligned with the task) hyperbolic random network initialization degrades the performance of sparse neural networks compared with uniform random initialization. This degradation arises because the hyperbolic random initialization imposes an arbitrary hierarchical prior into the sparse topology. Dynamic sparse training may then need to optimize the weights and reorganize this arbitrary task-agnostic hierarchy into a task-driven one. By contrast, a uniform random initialization imposes at start less structural bias and may therefore be easier to reconfigure during training toward the hierarchical topology suited to the task. This work motivates the need for data-informed hyperbolic initialization methods which generate sparse topologies with a hierarchical prior closer to the task, facilitating the further learning of a task-oriented hierarchical organization during dynamic sparse training. In addition, nBPSO represents the first hyperbolic bipartite network generative model that allows the mesoscale community structure to be explicitly controlled through model parameters, making it a useful tool for broader complex systems applications where community organization is central to accurate and interpretable modeling.
Connectivity laws conserved across systems, independently of edge weights, are compelling in network science. Many network metrics aggregate information counting all shortest-paths between node pairs, which is costly. Here we formalize the all-pairs shortest-path number (APSPN) problem and establish a shared computational foundation for these kinds of problems, including betweenness centrality (BC) and geometrical congruence (GC). We introduce the CC-APSPN kernel, which exploits network science principles to accelerate their shared computations on unweighted graphs via knowledge memoization, reducing runtime by up to 90% over the Brandes-APSPN baseline across diverse network topologies. Parallel CC-APSPN carries this acceleration onto multicore CPUs through batched source processing with a dedicated scheduling strategy, reducing exact BC and GC runtimes from hours to a few minutes on a 100,000-node network. Besides, we propose CC-bbBFS, a single-pair primitive for efficient sampling-based approximation of BC and GC. Together, these advances translate network-science-informed algorithm design into practical large-scale analysis.
Network science frequently seeks general laws of connectivity that persist across scales and disciplines, regardless of specific edge weights. A primitive in this setting is the computation of unweighted all-pairs shortest paths (APSP), which underlies measures of distance, centrality [1], and navigability [2]. However, the canonical Zuse-Moore breadth-first search (ZM-BFS) [3,4] algorithm is prohibitively slow for large and dense networks. Here, leveraging network science principles [2], we introduce CC-BFS: a dynamic programming algorithm for APSP. By prioritizing influential hubs, memoizing intermediate results and exploiting network hierarchy, CC-BFS drastically reduces computational effort, with up to 2500× speedup over ZM-BFS on scale-free networks. Furthermore, CC-BFS substantially outperforms the state-of-the-art direction-optimizing BFS (DO-BFS) [5] across diverse artificial and real-world benchmarks, while utilizing around 80% less memory. In practice, solving the APSP problem on dense and scale-free topologies can approach a time complexity of 0 (n2.5) and in networks with 100,000 nodes passes from over 2 days for ZM-BFS to around 2 minutes for CC-BFS, which represents a milestone potentially impacting many domains of science. CC-BFS scales across shared-memory threads and generalizes to related problems like computing network diameter and radius. By integrating network science into algorithm design, CC-BFS overcomes long-standing scalability challenges, opening new avenues for network-based computational analysis.