Targeted spreader identification via lexicographic core decomposition Authors: Arianna D’Ulizia, Alessia D’Andrea, Riccardo Denni Published: 2026 ABSTRACT Centrality measures quantify node importance, but they typically evaluate it globally across an entire network. However, nodes often belong to distinct categories, and a user analyzing influence may prioritize certain categories over others. It is therefore natural to evaluate node importance according to a specific preference ranking of these categories. To address this, we extend standard core decomposition and the well-known peeling algorithm to a lexicographic setting, introducing lexicographic core decomposition and lexipeeling, which we show is a special case of weighted node core decomposition. We evaluate lexipeeling against 79 baselines on 7 real-world networks. Lexipeeling ranks the true top spreader higher than any other baseline on 5 of 7 datasets, with MRR ranging from 0.478 on iPhone-Samsung to 1.0 on PolBlogs, PolBooks, and LastFM-Asia. However, like standard coreness, it assigns the same rank to many nodes, so weak spreaders may appear among the highest ranked ones. To address this, we propose composite methods that break lexipeeling’s ties using a secondary measure. Among these, lexipeeling-degree most reliably places truly influential nodes among its highest ranked ones across all datasets. Our code is publicly available: https://github.com/rdenni/Lexicoreness Introduction A fundamental problem in complex systems and network analysis is determining which nodes are the most important in a network or, more generally, assigning each node a score that quantifies its importance. The functions that assign these scores are called centrality measures1. The study of centrality measures dates back at least to the 1950s2, and over time, many centrality measures have been defined in the literature3,4. There is no single universal definition of importance; depending on the context, some definitions are more appropriate than others. A widely used definition relies on spreading power. In this context, a node is considered highly important if it can successfully spread information, innovations, or a virus to many other nodes. Identifying the most influential individuals in a social network is a foundational problem with many applications, from viral marketing5,6 and public health interventions7–9 to containing the spread of misinformation10,11. However, nodes in networks are rarely uniform. They possess specific features and can be grouped into distinct categories. For example, people in a social network have different ages, opinions, behaviors, or geographic locations. In practice, a user analyzing a network often values certain categories more than others. Therefore, it is natural to consider an importance score that depends on a priority ranking of these groups supplied by the user (throughout this paper, we will use the terms “categories” and “groups” interchangeably). For example, to prevent hospital collapse during an epidemic, public health officials with a limited supply of vaccines must decide exactly who to immunize. To distribute these vaccines effectively, they must identify and immunize the specific spreaders who primarily reach frontline healthcare workers first, vulnerable patients second, and the general public last. Similarly, consider the spread of information regarding a highly polarizing topic. Instead of asking who the most influential nodes are globally, a researcher might want to analyze influence relative to specific demographics. Suppose we want to understand who drives the conversation among female users by setting a clear order of interest: first targeting young supporters aged 18 to 25, followed by supporters aged 26 to 35, and finally those over 35. Reversing this order to prioritize older demographics first, or shifting the focus entirely to users opposing the topic, would likely identify a completely different set of key spreaders. By evaluating node importance according to these specific rankings, we obtain a much more granular and actionable understanding of how information cascades through a complex network. Global importance scores entirely obscure these granular dynamics. Classical centrality measures usually ignore categories and evaluate importance globally across the entire network. While recent fairness-aware centrality measures do consider node categories12, their main goal is to satisfy fairness constraints, such as ensuring equitable representation across all groups. In this work, we have a fundamentally different focus: we aim to find the most influential nodes according to a preference ranking of groups provided by a user. To the best of our knowledge, there are no studies that explicitly examine centrality measures with this specific focus. This leads to our research question: How can we identify the best spreaders in a network when we prioritize certain groups over others? In this work, we quantify a node’s importance by its spreading power and rank nodes lexicographically: given a network where each node belongs to one category and a priority ranking of categories supplied by the user, we compare nodes by their spreading capability in the top category first, breaking ties using the second category, and so on down the hierarchy. To determine this spreading capability, we follow a common approach in the literature and rely on the Reed-Frost model, a discrete-time Susceptible-Infectious-Recovered (SIR) epidemic process13–15. In this process, all nodes start susceptible (S) except for an initial set of infected nodes (I). In discrete rounds, each infected node attempts to infect each susceptible neighbor with probability p. After trying, infected nodes become recovered (R) and no longer spread the contagion. The expected number of recovered nodes quantifies the influence of the initial infected set. To evaluate individual spreading capability, the initial set of infected nodes consists solely of the node under evaluation. However, even providing an approximation of the expected number of recovered nodes is computationally expensive for medium-sized and large graphs. In a seminal work, Kitsak et al.16 experimentally showed that a centrality measure, coreness, is a very effective measure to predict nodes that are individually powerful spreaders under such epidemic model. A k-core is a subset of nodes such that every node has at least k neighbors in the k-core. The coreness of a node u ∈ V is the highest k such that u belongs to the k-core 17. The core decomposition problem consists in finding the coreness for every node. Intuitively, a node with high coreness has many neighbours with many neighbours, and so on 18. The coreness of every node can be computed in linear time using the peeling algorithm: the node with smallest degree is iteratively removed from the network, and a node’s coreness is the maximum degree observed at the exact moment of its extraction. To address our focus, we extend coreness to a lexicographic setting. We formally define the lexicographic core decomposition problem, generalizing the definition of a core to vectors and a lexicographic order determined by a preference ranking of components. We also introduce lexipeeling: at each iteration, the algorithm extracts the node with the smallest lexicographic degree, and a node’s lexicographic coreness is the maximum lexicographic degree observed at the moment of its extraction. We prove that lexipeeling correctly computes the lexicographic coreness for all nodes. Lexicographic coreness is substantially different from standard coreness, as shown in Fig. 1. In this example network, the set of nodes with maximum standard coreness is disjoint from the set of nodes with maximum lexicographic coreness. This disjointness remains even if we only consider the nodes with maximum coreness among the ones belonging to the top priority group. Therefore, simply computing standard coreness and then filtering by category is not sufficient to identify the targeted top spreaders.Fig. 1Divergence between standard and lexicographic core decomposition. The network consists of a triangle connected to a complete bipartite structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{4,4}$$\end{document}. The input ranking prioritizes green nodes over white nodes. While standard decomposition assigns the highest coreness (k=4) to the bipartite component, Lexipeeling correctly isolates the green triangle as the most critical structure, assigning it the maximum lexicoreness of [2, 0]. Divergence between standard and lexicographic core decomposition. The network consists of a triangle connected to a complete bipartite structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{4,4}$$\end{document}. The input ranking prioritizes green nodes over white nodes. While standard decomposition assigns the highest coreness (k=4) to the bipartite component, Lexipeeling correctly isolates the green triangle as the most critical structure, assigning it the maximum lexicoreness of [2, 0]. Finally, we show that the lexicographic core decomposition problem reduces to a special case of weighted node core decomposition. Our contribution lies in the problem formulation and its application to spreader identification: a perspective on centrality measures where node importance is evaluated under a priority ranking of categories supplied by the user. We extensively compared lexipeeling to 79 non-trivial baselines, ranging from classical centrality measures to very recent methods, on 7 real-world networks across multiple rankings. Our experiments show that lexipeeling is highly effective at identifying the most influential nodes, emerging as the best method for finding the true top spreader on 5 of 7 datasets, with MRR’s absolute values ranging from 0.478 on iPhone-Samsung to 1.0 on PolBlogs, PolBooks, and LastFM-Asia. Similar to standard coreness, lexicographic coreness frequently assigns the same rank to multiple nodes. However, our experiments show that the top ranked nodes consistently contain actual top spreaders. Furthermore, while lexipeeling excels at finding the very best spreaders, it is less effective at correctly sorting the entire network from top to bottom. When evaluating the global ranking of all nodes, distance and gravity-based centralities perform better. However, because lexipeeling assigns many nodes to the same rank, these tied sets can also contain nodes with low actual influence. To address this, we propose composite methods that combine lexipeeling with a secondary centrality measure to break ties. We show that one such composite, lexipeeling-degree, is the most reliable method for selecting sets of influential nodes, maintaining consistent quality across all datasets. We also address a natural limitation of strict lexicographic sorting: a node with even minimal influence in a higher-priority group always dominates a node with much larger influence in groups with lower priority. To soften this rigidity, we introduce a relaxed version of lexipeeling controlled by a parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta \in (0, 1)$$\end{document}. Our experiments show that, on the seven real-world networks we evaluate, standard lexipeeling and its β-variants identify top spreaders that influence similar fractions of each ranked group. To summarise, our main contributions are:We introduce a new perspective on centrality measures: evaluating node importance according to a preference ranking of node categories supplied by the user. Unlike fairness-aware approaches, which aim for equitable representation, our framework explicitly prioritizes certain groups over others, reflecting real-world scenarios where not all categories are equally relevant.We instantiate this perspective with lexicographic core decomposition, a special case of weighted node core decomposition. We give the lexicographic version of the peeling algorithm explicitly and prove it correct.We construct two structural counterexamples in which a node with smaller coreness reaches strictly more nodes in expectation under SIR than a node with larger coreness. The failure applies to standard coreness and to the lexicographic generalization we introduce.We extensively evaluate lexipeeling on the spreader identification problem, comparing against 79 baselines on 7 real-world networks with a rigorous SIR-based ground truth. Lexipeeling ranks the true top spreader highest on 5 of 7 datasets.We propose composite methods that mitigate lexipeeling’s tie problem. Among these, lexipeeling-degree is the method that, across all datasets, most reliably places truly influential nodes among its highest ranked ones.The remainder of the article is organized as follows. In Section 2 we discuss how previous work relates to our own, considering centrality measures, fair centrality measures, and fair influence maximization. Section 3 formally defines lexicographic core decomposition, the lexipeeling algorithm, the reduction to weighted node core decomposition, and two counterexamples where lexicographic coreness and coreness outside the lexicographic setting fails. In Section 4 we describe the setup of our experiments: the datasets, strategies to generate rankings, baselines, and evaluation metrics. Section 5 shows the experimental results and discusses them. Finally, Section 6 concludes the article with an outlook on future work. We introduce a new perspective on centrality measures: evaluating node importance according to a preference ranking of node categories supplied by the user. Unlike fairness-aware approaches, which aim for equitable representation, our framework explicitly prioritizes certain groups over others, reflecting real-world scenarios where not all categories are equally relevant. We introduce a new perspective on centrality measures: evaluating node importance according to a preference ranking of node categories supplied by the user. Unlike fairness-aware approaches, which aim for equitable representation, our framework explicitly prioritizes certain groups over others, reflecting real-world scenarios where not all categories are equally relevant. We instantiate this perspective with lexicographic core decomposition, a special case of weighted node core decomposition. We give the lexicographic version of the peeling algorithm explicitly and prove it correct. We instantiate this perspective with lexicographic core decomposition, a special case of weighted node core decomposition. We give the lexicographic version of the peeling algorithm explicitly and prove it correct. We construct two structural counterexamples in which a node with smaller coreness reaches strictly more nodes in expectation under SIR than a node with larger coreness. The failure applies to standard coreness and to the lexicographic generalization we introduce. We construct two structural counterexamples in which a node with smaller coreness reaches strictly more nodes in expectation under SIR than a node with larger coreness. The failure applies to standard coreness and to the lexicographic generalization we introduce. We extensively evaluate lexipeeling on the spreader identification problem, comparing against 79 baselines on 7 real-world networks with a rigorous SIR-based ground truth. Lexipeeling ranks the true top spreader highest on 5 of 7 datasets. We extensively evaluate lexipeeling on the spreader identification problem, comparing against 79 baselines on 7 real-world networks with a rigorous SIR-based ground truth. Lexipeeling ranks the true top spreader highest on 5 of 7 datasets. We propose composite methods that mitigate lexipeeling’s tie problem. Among these, lexipeeling-degree is the method that, across all datasets, most reliably places truly influential nodes among its highest ranked ones. We propose composite methods that mitigate lexipeeling’s tie problem. Among these, lexipeeling-degree is the method that, across all datasets, most reliably places truly influential nodes among its highest ranked ones. Related work We review three lines of research relevant to our work: centrality measures for spreader identification, fairness in centrality measures, and fairness-aware influence maximization. Centrality and single spreader identification Broadly, centrality measures can be categorized by the topological features they exploit4: there are measures based on the neighborhood (e.g., degree, coreness16, h-index19,20), on paths (e.g., betweenness21, closeness22) and spectral properties of some matrix associated with the graph (e.g., PageRank23, eigenvector24,25 and Katz centrality26). Other measures are based on the clustering coefficient27,28 or entropy29,30. Furthermore, there are centrality measures that integrate multiple network attributes, like the ones based on gravity31–33 that combine coreness and distances or h-index and distances34, as well as measures that integrate local and global characteristics like degree and distances35. Among these, coreness has emerged as a strong predictor of spreading potential. Kitsak et al. 16 showed that nodes in the innermost core outperform high degree and high betweenness nodes under the SIR model. Using real-world cascades, Pei et al. 18,36 corroborated these findings. Coreness is also computationally efficient, with linear-time algorithms. A known limitation of coreness is that it could assign the same values to a large number of nodes, reducing the discriminative power 37,38. Several refinements have been proposed to address this: mixed degree decomposition 39, entropy based coreness 40, distance to core refinements 41,42, structural hole aware coreness 43, just to name a few. In this work, we utilize baseline coreness to establish our novel ranking-aware framework; while we acknowledge the issue of ties, we defer the integration of these refined tie-breaking mechanisms to future extensions. Although coreness is able to successfully identify individual nodes that are powerful spreaders, it is unable to identify a group of powerful spreaders; this is due to the overlapping influence regions of the nodes 16. Since we are considering the case of the single most influential spreader, this is not a concern. Fairness in centrality measures There are many open questions regarding the application of fairness to network centralities12. To the best of our knowledge, the only two centrality measures on which fairness has been studied are degree12 and PageRank44–48. Standard PageRank49–51 measures a node’s importance using a random-walk process, where a surfer navigates to neighboring nodes but has a certain probability of “jumping” to other nodes in the network. Therefore, PageRank is defined by three components: the jump vector, the probability transition matrix of the random walk, and the underlying graph. Because real-world networks are heavily homophilic, standard PageRank gives unfairly high scores to the majority while systematically ignoring minority groups52,53. To address this bias, researchers have proposed several fairness-aware interventions. One family of algorithms, such as FSPR54, involves modifying the jump vector while keeping the transition matrix fixed. A closely related approach, LFPR54, goes further by ensuring fairness in both the transition matrix and the jump vectors. Another major approach is edge reweighting, introduced by Wang et al.47, with methods like FairGD and AdaptGD; these methods dynamically optimize the graph’s edge weights to achieve fair group rankings. Furthermore, a very recent work provided a unified, “plug-and-play” optimization framework to enforce various group-fairness constraints48. Fair influence maximization A topic closely related to our work is fair influence maximization. In the influence maximization (IM) problem, given a network and a budget k, the goal is to find a set of k users, the seed set, that maximizes the expected number of influenced individuals under a given diffusion model, such as the Independent Cascade or Linear Threshold models55. Because aiming solely to maximize total outreach inherently favors larger communities12,56, a growing line of research investigates fairness-aware IM. Various fairness constraints have been considered; for example, Farnad et al.57 studied equality (the number of influencers per group is proportional to group size), equity (the expected outreach per group is proportional to group size), diversity (ensuring each group receives outreach at least equal to its internal one), and maxmin (maximizing outreach in the most disadvantaged group). Our work fundamentally departs from these approaches. Rather than enforcing fairness through constraints, we leverage a group priority ranking as an input. Furthermore, we do not seek to find an optimal set of top k spreaders; instead, we aim to quantify the intrinsic spreading potential of every individual node in the network. Within fairness-aware IM research, the closest formulation to ours is Influence Maximization with Priority (IMP)58,59. In IMP, given a graph G = (V, E), a priority set P ⊆ V, a threshold T ∈ [0, |P|], and a budget k, the goal is to find a seed set of k nodes that maximizes the total expected outreach such that the expected outreach within P is at least T. Our problem differs in two key aspects. First, our objective is not to satisfy a constraint while maximizing total outreach, but rather to directly maximize influence following the lexicographic ordering itself. Second, it is not guaranteed for a single individual spreader to satisfy the priority constraint of IMP, highlighting the fundamental structural difference between IMP and our problem. Lexicographic core decomposition and lexipeeling In this section we formally define the lexicographic core decomposition problem and introduce the lexipeeling algorithm. They are the extensions of core decomposition and the peeling algorithm to the multidimensional case. We also discuss when (lexicographic) coreness is a reliable proxy for SIR spreading and exhibit two structural counterexamples. All formal proofs are provided in the Supplementary Information. Notation Throughout the paper, unless explicitly stated otherwise, we consider an undirected graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = \left( \bigcup _{i=1}^l V_i,\, E\right)$$\end{document}, where the groups \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_1,\dots ,V_l$$\end{document} are pairwise disjoint, i.e. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V_i\cap V_j=\emptyset$$\end{document} for i≠ j. We indicate with n:= |V|, with m:= |E|, and with l the number of groups. Given a node u ∈ V, we denote by N(u) its neighborhood, i.e. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N(u) = \{v \in V \mid (u,v) \in E\}$$\end{document}, and by δ (u) = |N(u)| its degree. For a subset of nodes S ⊆ V and a node u ∈ V, the degree of u induced by S is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta _{[S]}(u) := |\{s \in S \mid (u,s) \in E\}|$$\end{document}. For a group index i∈ [l] and vertex u∈ V we write \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta _i(u):=|\{v\in V_i\mid (u,v)\in E\}|$$\end{document} and, restricting to a subset S⊆ V, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta _{i,[S]}(u):=|\{v\in V_i\cap S\mid (u,v)\in E\}|$$\end{document}. The degree vector of u is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }^\intercal (u) := [\delta _1(u), \dots , \delta _l(u)]$$\end{document}, and the degree vector induced by a subset S is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{[S]}^\intercal (u) := [\delta _{1, [S]}(u), \dots , \delta _{l, [S]}(u)]$$\end{document}. Given a ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r} = (i_1, \dots , i_s)$$\end{document} with s ≤ l, we define the degree vector of u restricted to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document} as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{\textbf{r}}^\intercal (u) := [\delta _{i_1}(u), \dots , \delta _{i_s}(u)]$$\end{document}. The degree vector of u restricted to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document} and induced by a subset S ⊆ V is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{\textbf{r}, [S]}^\intercal (u) := [\delta _{i_1, [S]}(u), \dots , \delta _{i_s, [S]}(u)]$$\end{document}. Preliminaries: coreness and peeling To contextualize our lexicographic generalization, we briefly recall standard core decomposition. Given a graph G, a k-core is the largest subgraph where every node has induced degree at least k. The cores form a nested sequence, in the sense that i) they are unique, and ii) for every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k_1 < k_2$$\end{document} the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k_1$$\end{document}-core is included in the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k_2$$\end{document}-core. So it makes sense to consider the coreness, or core value, of a node v ∈ V, that is, the maximum k such that v belongs to the k-core. The maximum coreness is called the degeneracy of a graph. In the core decomposition problem we have to find the coreness of every node. This problem can be solved to the optimum by the peeling algorithm, which iteratively peels out the node with the smallest degree and assigns its coreness at the moment of removal. In this section, we generalize these results to a multidimensional, group-aware setting. Lexicographic core decomposition problem and lexipeeling In this paper we consider the lexicographic order, formally defined as follows. Definition 1 (Lexicographic order) Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s \in \mathbb {N}_{\ge 1}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{a},\textbf{b}\in \mathbb {R}^s$$\end{document}. We write \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{a}\succeq \textbf{b}$$\end{document} (“\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{a}$$\end{document} is lexicographically at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{b}$$\end{document}”) iff either \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{a}=\textbf{b}$$\end{document} or the first index j with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_j\ne b_j$$\end{document} satisfies \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_j>b_j$$\end{document}. It can be shown that it is a total order. We now extend the k-core concept to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\textbf{r}}$$\end{document}-core. Definition 2 (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\textbf{r}}$$\end{document}-Core) Let G be a graph, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k} \in \mathbb {R}^s$$\end{document}, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r} = (i_1, \ldots , i_s)$$\end{document} be a ranking. The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\textbf{r}}$$\end{document} core is the maximal subset C ⊆ V such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\forall \, c \in C$$\end{document}, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{\textbf{r}, [C]}(c) \succeq _{\textbf{r}} \textbf{k}$$\end{document}. In the Supplementary Information, we show that the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\textbf{r}}$$\end{document}-cores form a nested sequence, that is i) every \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\textbf{r}}$$\end{document}-core is unique and ii) if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {k'}_{\textbf{r}} \succeq \mathbf {k^{''}}_{\textbf{r}}$$\end{document} then the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {k^{'}}_{\textbf{r}}$$\end{document}-core is included in the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf {k^{''}}_{\textbf{r}}$$\end{document}-core. Therefore it makes sense to define the lexicographic coreness or lexicoreness of a node, which is the generalization of the coreness in the lexicographic setting. Definition 3 (Lexicoreness) Given a graph G, a ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r} = (i_1, \dots , i_s)$$\end{document}, and a node v ∈ V, the lexicoreness of v is the lexicographically largest vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}\in \mathbb {R}^s$$\end{document} such that v belongs to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\textbf{r}}$$\end{document}-core. We call the lexicographically maximum lexicoreness as the lexicographic degeneracy of the graph. We can finally define the problem that we study, the lexicographic core decomposition problem. Problem 1 (Lexicographic Core Decomposition Problem) Given a graph G, a ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document}, for every v ∈ V determine its lexicoreness vector. We solve the lexicoreness decomposition problem to the optimum with an extension of the peeling algorithm to the lexicographic setting, that we call lexipeeling. The lexipeeling simply consists of iteratively removing the node with the smallest lexicographic degree, as described in Algorithm 1. The proof of correctness is in the Supplementary Information. Divergence between standard and lexicographic core decomposition Crucially, as illustrated in Fig. 1, the nodes belonging to the maximum lexicographic core do not necessarily align with those in the maximum standard k-core, highlighting the need for this multidimensional approach. The figure depicts a graph composed of a triangle connected via a single bridge edge to a complete bipartite graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{4,4}$$\end{document}. The nodes in the triangle have a coreness of 2, while the nodes in the bipartite graph have a coreness of 4. However, Lexipeeling reveals a completely different structural hierarchy. First, it extracts the green nodes in the bipartite component, assigning them a lexicoreness of [0, 4]. Without the green nodes, the bipartite structure collapses; the algorithm then extracts the remaining white nodes in the bipartite component, leaving the white bridge node for last. It assigns a lexicoreness of [0, 4] to the first three extracted white nodes, and [1, 0] to the white bridge node. Finally, Lexipeeling extracts the green nodes of the triangle and assigns them a lexicoreness of [2, 0], which represents the lexicographic degeneracy of the network. Standard core decomposition entirely fails to identify the critical importance of the triangle, and this failure persists even if we restrict our evaluation strictly to the highest-coreness nodes within the primary priority group. The azure babà problem and the β-lexicographic variants The strict lexicographic order has a structural rigidity: a single connection in a higher-priority group dominates any number of connections in lower-priority groups. We call this the azure babà problem, after the dictionary analogue where “azure” precedes “babà” simply because it starts with “a”, even though “babà” is composed of top-tier letters, i.e., “a” and “b”, while “azure” has low-tier letters like “z” and “u”. To allow controlled influence across groups, we introduce the β-lexicographic variants. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta \in (0, 1)$$\end{document} be a user-defined relaxation parameter. For a node v ∈ V and a ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document} of length s, the j-th component of the β-degree vector restricted to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document} is defined as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{j, \beta , \textbf{r}}(v) = \boldsymbol{\delta }_{j, \textbf{r}}(v) + \beta \cdot \boldsymbol{\delta }_{i_{j+1}, \textbf{r}}(v)$$\end{document} for j < s, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{j, \beta , \textbf{r}}(v) = \boldsymbol{\delta }_{j, \textbf{r}}(v)$$\end{document} if j=s. Consequently, the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\beta , \textbf{r}}$$\end{document}-core is the maximal subset C ⊆ V such that for all c ∈ C, it holds \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\boldsymbol{\delta }_{\beta , \textbf{r}, [C]}(c) \succeq \textbf{k}_{\beta , \textbf{r}}$$\end{document}. The β-lexicoreness of a node v is the lexicographically maximum vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\beta , \textbf{r}}$$\end{document} such that v belongs to the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{k}_{\beta , \textbf{r}}$$\end{document}-core. In the β-lexicographic core decomposition problem, given a graph G, an input ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document}, and a parameter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta \in (0, 1)$$\end{document}, the objective is to determine the β-lexicoreness of all nodes. Intuitively, the β parameter has the following meaning: influencing one node in group j is considered equivalent to influencing 1/β nodes in the immediately subsequent lower-priority group j+1. Note that when β = 0, this formulation reduces to the lexicographic core decomposition. Reduction to core decomposition with weights on nodes It is possible to reduce exactly the lexicographic core decomposition problem, with or without the β variant, to the node weighted core decomposition problem. Moreover, the standard peeling algorithm for the weighted core decomposition yields an identical node extraction sequence to that of lexipeeling. To achieve this reduction, we assign specific scalar weights to the nodes of each group such that the resulting numerical hierarchy strictly preserves the priority order dictated by the input ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r}$$\end{document}. A formal proof of this equivalence is provided in the Supplementary Information. Algorithm 1Lexipeeling Lexipeeling Failure modes of (lexicographic) coreness In this paragraph we examine when (lexicographic) coreness is a reliable proxy for SIR spreading and when it fails. The suitability of any centrality measure as a proxy for SIR spreading cannot be assessed independently of the infection probability p; we therefore organize the discussion by p, then exhibit two structural counterexamples. Small p. For sufficiently small p, the infection rarely propagates beyond the immediate neighbourhood of the seed v, so the major contribution comes from one hop infections. The expected spread of v is therefore well approximated by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[\textrm{spread}(v)] \approx p \cdot \deg (v)$$\end{document}. Since p is the same for all nodes, degree is a natural proxy in this regime; empirical evidence confirms this 60. Large p. For sufficiently large p, the epidemic reaches a large fraction of the network regardless of the seed: epidemics are “easy”. On some classes of graphs, with constant probability, the epidemic infects a constant fraction of nodes in O(łog n) time starting from any single seed 61. In this regime degree remains a good empirical predictor 60. Critical p. Following standard practice, we focus on the critical regime, where p is slightly above the epidemic threshold and outbreaks reach a non trivial but non saturating fraction of the network. This is the regime where the question of an effective structural proxy is most interesting and where coreness has been empirically established as the best predictor of SIR spread 16,18,60,62. Intuitive justification. To the best of our knowledge, there is no rigorous theoretical proof that coreness is an optimal SIR proxy in the critical regime, the established support is empirical. An intuitive justification, due to Pei et al. 18, is that nodes with high coreness have well connected neighbours who have well connected neighbors and so on, whereas hubs surrounded by low degree peers are pruned early in the k-core computation. Consider two seeds in a contact network with the same degree k: a person A whose k contacts have no other contacts (degree k, coreness 1), and a person B whose k contacts each have k contacts who themselves have k contacts, recursively (degree k, coreness k). An outbreak starting at A is structurally confined, while an outbreak starting at B propagates through the recursive structure. Although A and B have the same degree, coreness distinguishes them. The peeling algorithm removes at every iteration the node that is worst connected to the graph and the same intuition extends to lexipeeling: at every iteration lexipeeling removes the node with the weakest connections to the graph with respect to the input ranking, so a node with high lexicographic coreness is well connected to neighbours who are well connected to neighbours who are well connected and so on, measured with respect to the input ranking. We stress that this is an intuitive justification, not a theoretical guarantee. Coreness exhibits known biases. We make two of them concrete with the following counterexamples. Both share the same template: a node u with low coreness but some structural advantage has higher expected spread than a node v with higher coreness in a small dense cluster. In Counterexample 1 the advantage of u is multi hop access to a dense substructure; in Counterexample 2 the advantage is the degree.Fig. 2Counterexample 1 (dumbbell). Two cliques, of size l+1 and k, joined by a bridging path. Node v sits in the (l+1)-clique and is at the endpoint of the path; node u sits on the path at distance z from v and h from the k-clique. Coreness assigns l to v and 2 to u. Green nodes belong to the top priority group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} in the lexicographic extension. Counterexample 1 (dumbbell). Two cliques, of size l+1 and k, joined by a bridging path. Node v sits in the (l+1)-clique and is at the endpoint of the path; node u sits on the path at distance z from v and h from the k-clique. Coreness assigns l to v and 2 to u. Green nodes belong to the top priority group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} in the lexicographic extension. Counterexample 1: dumbbell graph The construction is shown in Fig. 2. The graph consists of two cliques, one of size l+1 and one of size k, connected by a bridging path. Assume l > 2. Let v be a node in the (l+1)-clique connected to one endpoint of the bridging path; so \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(v) = l$$\end{document}. Let u be a node on the bridging path, at graph distance z from v and h from the k-clique. Since u has degree 2 along the path, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(u) = 2$$\end{document}. Since l > 2, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(v) > \textrm{coreness}(u)$$\end{document}. We show that, despite this, u has a higher spreading ability than v. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_v$$\end{document} be the random variable denoting the number of infected nodes when the epidemic starts at v, we want to show an upper bound to its expected value. Decompose \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_v$$\end{document} into four contributions: (a) v itself; (b) infected nodes in the (l+1)-clique excluding v; (c) infected nodes on the bridge path between v and the k-clique; (d) infected k-clique nodes. In expectation: (a) = 1; (b) ≤ l; (c) ≤ p / (1 - p), the expected value of the geometric random variable counting consecutive successful transmissions along the bridge path from v (derivation in the Supplementary Information); (d) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\le k \cdot P(\text {epidemic reaches the } k\text {-clique}) \le k \cdot p^{z + h}$$\end{document}, since the only path from v to the k-clique has length z + h. Choosing z = O(łog k) makes this contribution at most a small constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon \le 1$$\end{document}. Summing:\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[X_v] \;\le \; 1 + l + \frac{p}{1 - p} + \varepsilon \;=\; l + \frac{1}{1 - p} + \varepsilon .$$\end{document}Under the mild assumption l > 1 / (1 - p), both 1 / (1 - p) and \varepsilon are at most l, so1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} E[X_v] \le 3l. \end{aligned}$$\end{document}Now bound \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[X_u]$$\end{document} from below, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X_u$$\end{document} indicates the number of infected nodes when u is the seed. From u the infection reaches the first node of the k-clique with probability \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p^h$$\end{document} (the bridging path is the unique simple path of length h from u). Once this first clique node is infected, each of its k - 1 clique neighbours is directly infected with probability at least p, so the expected number of additional infections inside the clique is at least (k - 1) · p. Therefore2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} E[X_u] \;\ge \; p^h \cdot (k - 1) \cdot p \;=\; p^{h + 1} (k - 1). \end{aligned}$$\end{document}For k sufficiently large relative to l, (2) exceeds (1):\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[X_u] \;\ge \; 3l \;\ge \; E[X_v] \quad \text {while} \quad \textrm{coreness}(u) = 2 < l = \textrm{coreness}(v).$$\end{document}For h = 1, u is a bridge node: a single edge away from a dense cluster. For h > 1, the construction realizes the multi hop diffusion case. Lexicographic extension. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{r} = (r_1, \dots , r_s)$$\end{document} be the input group ranking. Place both cliques in the top group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} (highlighted in Fig. 2); all nodes of the bridging path belong to lower-priority groups. Under this coloring, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {lex\text {-}coreness}(v) \succ \mathrm {lex\text {-}coreness}(u)$$\end{document}: all of v’s clique neighbours are in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document}, while u has no neighbours in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document}. The same bounds (1) and (2) transfer per group to the number of infected \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} nodes: starting from v, only the l other clique members are in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document}, so \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[\#\, r_1\text {-infected} \mid v] \le 1 + l + \varepsilon \le 3l$$\end{document}; starting from u, the entire k-clique is in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document}, so (2) transfers verbatim. For k sufficiently large, u dominates v in expected per group spread on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document}, despite the opposite ordering by lexicographic coreness. This realizes the cross group propagation paths failure mode.Fig. 3Counterexample 2 (star variant). Same left side as Fig. 2; on the right, u is the centre of a star with d leaves. Coreness assigns l to v and 1 to u, yet for d large enough \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[X_u] > E[X_v]$$\end{document}. Green nodes belong to the top priority group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} in the lexicographic extension. Counterexample 2 (star variant). Same left side as Fig. 2; on the right, u is the centre of a star with d leaves. Coreness assigns l to v and 1 to u, yet for d large enough \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[X_u] > E[X_v]$$\end{document}. Green nodes belong to the top priority group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} in the lexicographic extension. Counterexample 2: star variant The construction is shown in Fig. 3. We modify Counterexample 1 by replacing the k-clique with a star: u is the centre of a star with d leaves (each of degree 1, connected only to u), and u is connected to one endpoint of the bridging path. In this graph, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(v) = l$$\end{document} (unchanged). For u: the d leaves are peeled at the 2-core level; u then has degree 1 and is also peeled, so \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(u) = 1$$\end{document}. Since l > 2, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(v) > \textrm{coreness}(u)$$\end{document}. The v-side bound from Counterexample 1 transfers verbatim, with \varepsilon now bounding the leakage to u and its d leaves under z = O(łog d):3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} E[X_v] \le 3l. \end{aligned}$$\end{document}From u, each of the d leaves is infected independently with probability p, contributing d · p in expectation; including u itself,4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} E[X_u] \ge 1 + d \cdot p. \end{aligned}$$\end{document}For d > 3l / p, (4) exceeds (3) while \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{coreness}(u) = 1 < l = \textrm{coreness}(v)$$\end{document}. This realizes a failure mode distinct from Counterexample 1: the spreading ability of u here is a pure degree effect, even though those neighbours have no further reach. Coreness does not capture this advantage. Lexicographic extension. Place v’s clique and the star (the node u and all leaves) in the top group \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document}, and the bridging path in lower-priority groups. The bounds (3) and (4) transfer to the number of infected \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} nodes: the bound on v stays at most 3l (in fact tighter, since path infections do not count toward the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} total), and the bound on u transfers verbatim. For d > 3l / p, u dominates v in per group spread on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r_1$$\end{document} despite the opposite ordering by lexicographic coreness. Experimental setup We describe the datasets, ranking strategies, baselines, evaluation metrics, and ground-truth construction used in our experiments. Datasets We evaluate our method on seven real-world networks, treating all as undirected graphs. Graph statistics are summarized in Table 1. PolBooks (https://websites.umich.edu/~mejn/netdata/) captures Amazon co-purchases of political books, the groups are liberal, neutral, and conservative. We used the LCC of Email-EU-Core 63,64, a network where edges denote internal email communications between employees at a European research institution, the groups are the departments of the employees. PolBlogs 65 is a network where edges are hyperlinks between blogs, groups are liberal and conservative; we used its largest connected component (LCC). For MIND 66, we use the filtered version by Wang et al. 47, in this network edges connect co-read news articles from Microsoft News; we used the 14 news categories as groups. LastFM-Asia 67 captures mutual follower relationships between users in Asian countries on the LastFM music network (groups: geographic locations). Finally, Brexit and iPhone-Samsung 68 originate from Twitter follower networks with distinct retweet probabilities for different opinions. To establish the groups for these two, for every node, we computed a polarity score representing the difference between the average probabilities of retweeting opinion A versus opinion B across incoming edges. Nodes are then assigned to one of five opinion groups (neutral, slightly or strongly favoring A, or slightly or strongly favoring B) by binning these scores using \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu \pm 0.5\sigma$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu \pm 1.5\sigma$$\end{document} thresholds.Table 1Graph statistics.Dataset|V||E|Avg. deg.Max deg.Max core.|G|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\mathcal {R}|$$\end{document}Assort.PolBlogs1,22216,71427.3635136220.811PolBooks1054418.402563100.723Email-EU-Core98616,06432.583453442320.302MIND2,26911,3019.961,584514470.162Brexit22,74543,0713.79549565320.018iPhone-Samsung36,74248,1082.62261455320.235LastFM-Asia7,62427,8067.292162018300.856 Table 1Graph statistics.Dataset|V||E|Avg. deg.Max deg.Max core.|G|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\mathcal {R}|$$\end{document}Assort.PolBlogs1,22216,71427.3635136220.811PolBooks1054418.402563100.723Email-EU-Core98616,06432.583453442320.302MIND2,26911,3019.961,584514470.162Brexit22,74543,0713.79549565320.018iPhone-Samsung36,74248,1082.62261455320.235LastFM-Asia7,62427,8067.292162018300.856 Graph statistics. Ranking strategies For every dataset, we generated rankings with lengths ranging from 2 to 4 groups according to the following strategies: 3 random rankings per length; sequences of the top, bottom, or alternating groups based on size, average coreness, or average degree; and combinations of mixed metrics (size × coreness, size × degree, and coreness × degree). Because identical rankings could occasionally be produced by different strategies, we removed duplicates. Consequently, the final number of unique rankings evaluated varies across datasets, in Table 1 is indicated the number of rankings used for each graph. Baselines We evaluated our method against an exhaustive suite of 79 non-trivial baselines derived from 26 base algorithms, divided into two main families. Ranking-independent baselines (18): These algorithms ignore the input ranking. They are categorized by: (i) neighborhood (degree69, coreness, h-index variants \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_1$$\end{document} through \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_5$$\end{document} 19); (ii) paths (betweenness 21, closeness 22); (iii) gravity (gravity centrality 31, local gravity 32, extended gravity 31, gravity h-index 34); (iv) spectral properties (PageRank 23); (v) node removal (dangling centrality 70,71); and (vi) hybrid or other types (entropy degree distance combination 30, clustering coefficient 72, local global centrality 35). Ranking-dependent baselines (8): These algorithms leverage the input ranking. They include lexicographic degree (sorting nodes lexicographically by their degree vectors according to the input ranking), two standard PageRank variants (using uniform or exponential decay jump distributions over nodes whose group is in the input ranking), and five fair PageRank algorithms (FairGD 47, AdaptGD 47, FSPR 46, LFPR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_U$$\end{document} 46, LFPR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_N$$\end{document} 46). We evaluated FSPR, LFPR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_U$$\end{document}, and LFPR\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$_N$$\end{document} strictly on rankings of length 247. To account for self-influence, we incremented the degree vector component of a node’s own group by 1 for both lexicographic degree and lexipeeling. For all PageRank baselines, the damping factor was set at 0.85. We configured FairGD and AdaptGD with a learning rate lr = 1.0 and a 50-iteration limit. For all gravity-based baselines, the neighbourhood radius was set to 3 hops, following 31,32. For fair PageRank methods, we used the following target distribution: a node whose group is at position i ≥ 1 in the input ranking receives weight \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w = 0.5^{i-1}$$\end{document}, while a node whose group is not in the input ranking receives weight \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w = 0.5^{s+1}$$\end{document}, where s is the length of the ranking. We then normalized these weights to sum to 1. For PageRank with exponential decay jump vector, we applied this identical \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0.5^{i-1}$$\end{document} scaling, but assigning a probability of 0 to nodes whose group is not in the input ranking. Variants and combinations: For all 26 algorithms, we considered three variants: (i) unrestricted, leaving the ranking returned by the centrality measure unchanged; (ii) restricted, moving the nodes whose group is in the input ranking to the top positions while preserving the relative internal sorting; and (iii) top-restricted, moving only the nodes whose group is first in the input ranking to the top positions, again preserving the relative internal sorting. This yielded 26 × 3 = 78 different baselines. A random node selection baseline completed our 79 methods. We excluded any algorithm exceeding a 1-hour execution time for a specific ranking from all evaluations on that dataset. Evaluation metrics To test the quality of lexipeeling against baselines, we used the following metrics:Average Reciprocal Hit Rate (ARHR@ k) measures how highly the method ranks the true top spreaders. Given a method and a value k, are considered all the nodes whose ground truth rank is at most k. ARHR@k is equal to the average of the reciprocals of the ranks assigned to these nodes by the method, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {ARHR@}k = (1/|T_k|) \sum _{v \in T_k} 1/\textrm{rank}_{\textrm{method}}(v)$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_k = \{v \in V \mid \textrm{rank}_{\mathrm {ground-truth}}(v) \le k\}$$\end{document}. Note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|T_k|$$\end{document} may exceed k due to ties. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {ARHR@}1$$\end{document} it is also called Mean Reciprocal Rank (MRR). MRR measures the rank a method gives to the true top spreader. The tied rank-1 set size, reported separately, captures how many other nodes share that rank.Coverage@ k is the fraction of the ground truth’s top-k spreaders that the method places in its top-k tier. When the ground truth top-k has size k, this is equivalent to recall over a target of size k. We handle ties at the k-th rank optimistically by including all tied nodes in the candidate sets, we ensure that the numerator is capped at k. More formally: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {Coverage@}k = \min (|M_k \cap G_k|,\; k) / k$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_k = \{v \in V \mid \textrm{rank}_{\textrm{method}}(v) \le k\}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_k = \{v \in V \mid \textrm{rank}_{\mathrm {ground-truth}}(v) \le k\}$$\end{document}. For ARHR@k and Coverage@k, we used both absolute \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 3, 5, 10\}$$\end{document} and relative values \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1\%, 3\%, 5\%, 10\%\}$$\end{document} of the number of nodes.Rank Correlation is reported using two variants of Kendall’s τ: the standard one and the weighted one, which prioritizes agreement at the top of the ranking.Cumulative Score@(k , t) measures the percentage of nodes that a method ranks within the top k positions that fall within the top t positions of the ground truth ranking. Formally, for a given ranking r, infection probability p, and method m: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {Cumulative}(k, t) = \frac{|\{v : \text {rank}_m(v) \le k \;\wedge \; \text {rank}_{\text {GT}}(v) \le t\}|}{|\{v : \text {rank}_m(v) \le k\}|}$$\end{document} where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {rank}_m(v)$$\end{document} is the rank assigned by method m and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {rank}_{\text {GT}}(v)$$\end{document} is the ground-truth rank (based on SIR spreading influence) specific to the pair (r, p). The reported score is the average across all rankings and infection probabilities. We consider \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 5, 10\}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \in \{1, 5, 10\}$$\end{document}, where both thresholds are absolute (not percentages). Average Reciprocal Hit Rate (ARHR@ k) measures how highly the method ranks the true top spreaders. Given a method and a value k, are considered all the nodes whose ground truth rank is at most k. ARHR@k is equal to the average of the reciprocals of the ranks assigned to these nodes by the method, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {ARHR@}k = (1/|T_k|) \sum _{v \in T_k} 1/\textrm{rank}_{\textrm{method}}(v)$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_k = \{v \in V \mid \textrm{rank}_{\mathrm {ground-truth}}(v) \le k\}$$\end{document}. Note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|T_k|$$\end{document} may exceed k due to ties. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {ARHR@}1$$\end{document} it is also called Mean Reciprocal Rank (MRR). MRR measures the rank a method gives to the true top spreader. The tied rank-1 set size, reported separately, captures how many other nodes share that rank. Average Reciprocal Hit Rate (ARHR@ k) measures how highly the method ranks the true top spreaders. Given a method and a value k, are considered all the nodes whose ground truth rank is at most k. ARHR@k is equal to the average of the reciprocals of the ranks assigned to these nodes by the method, i.e., \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {ARHR@}k = (1/|T_k|) \sum _{v \in T_k} 1/\textrm{rank}_{\textrm{method}}(v)$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T_k = \{v \in V \mid \textrm{rank}_{\mathrm {ground-truth}}(v) \le k\}$$\end{document}. Note that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|T_k|$$\end{document} may exceed k due to ties. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {ARHR@}1$$\end{document} it is also called Mean Reciprocal Rank (MRR). MRR measures the rank a method gives to the true top spreader. The tied rank-1 set size, reported separately, captures how many other nodes share that rank. Coverage@ k is the fraction of the ground truth’s top-k spreaders that the method places in its top-k tier. When the ground truth top-k has size k, this is equivalent to recall over a target of size k. We handle ties at the k-th rank optimistically by including all tied nodes in the candidate sets, we ensure that the numerator is capped at k. More formally: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {Coverage@}k = \min (|M_k \cap G_k|,\; k) / k$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_k = \{v \in V \mid \textrm{rank}_{\textrm{method}}(v) \le k\}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_k = \{v \in V \mid \textrm{rank}_{\mathrm {ground-truth}}(v) \le k\}$$\end{document}. For ARHR@k and Coverage@k, we used both absolute \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 3, 5, 10\}$$\end{document} and relative values \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1\%, 3\%, 5\%, 10\%\}$$\end{document} of the number of nodes. Coverage@ k is the fraction of the ground truth’s top-k spreaders that the method places in its top-k tier. When the ground truth top-k has size k, this is equivalent to recall over a target of size k. We handle ties at the k-th rank optimistically by including all tied nodes in the candidate sets, we ensure that the numerator is capped at k. More formally: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm {Coverage@}k = \min (|M_k \cap G_k|,\; k) / k$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M_k = \{v \in V \mid \textrm{rank}_{\textrm{method}}(v) \le k\}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G_k = \{v \in V \mid \textrm{rank}_{\mathrm {ground-truth}}(v) \le k\}$$\end{document}. For ARHR@k and Coverage@k, we used both absolute \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 3, 5, 10\}$$\end{document} and relative values \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1\%, 3\%, 5\%, 10\%\}$$\end{document} of the number of nodes. Rank Correlation is reported using two variants of Kendall’s τ: the standard one and the weighted one, which prioritizes agreement at the top of the ranking. Rank Correlation is reported using two variants of Kendall’s τ: the standard one and the weighted one, which prioritizes agreement at the top of the ranking. Cumulative Score@(k , t) measures the percentage of nodes that a method ranks within the top k positions that fall within the top t positions of the ground truth ranking. Formally, for a given ranking r, infection probability p, and method m: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {Cumulative}(k, t) = \frac{|\{v : \text {rank}_m(v) \le k \;\wedge \; \text {rank}_{\text {GT}}(v) \le t\}|}{|\{v : \text {rank}_m(v) \le k\}|}$$\end{document} where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {rank}_m(v)$$\end{document} is the rank assigned by method m and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {rank}_{\text {GT}}(v)$$\end{document} is the ground-truth rank (based on SIR spreading influence) specific to the pair (r, p). The reported score is the average across all rankings and infection probabilities. We consider \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 5, 10\}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \in \{1, 5, 10\}$$\end{document}, where both thresholds are absolute (not percentages). Cumulative Score@(k , t) measures the percentage of nodes that a method ranks within the top k positions that fall within the top t positions of the ground truth ranking. Formally, for a given ranking r, infection probability p, and method m: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {Cumulative}(k, t) = \frac{|\{v : \text {rank}_m(v) \le k \;\wedge \; \text {rank}_{\text {GT}}(v) \le t\}|}{|\{v : \text {rank}_m(v) \le k\}|}$$\end{document} where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {rank}_m(v)$$\end{document} is the rank assigned by method m and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {rank}_{\text {GT}}(v)$$\end{document} is the ground-truth rank (based on SIR spreading influence) specific to the pair (r, p). The reported score is the average across all rankings and infection probabilities. We consider \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 5, 10\}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \in \{1, 5, 10\}$$\end{document}, where both thresholds are absolute (not percentages). Ground truth We used the well-known Susceptible-Infected-Recovered (SIR) model to establish our ground truth. Our goal was to select 10 transmission probabilities per graph that yield non-trivial epidemics, avoiding scenarios where the spread consistently dies out immediately or infects the vast majority of the network. To find these probabilities, first we computed the mean-field epidemic threshold \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau = \langle k \rangle / (\langle k^2 \rangle - \langle k \rangle )$$\end{document} for each graph 73, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle k \rangle$$\end{document} is the average degree and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle k^2 \rangle$$\end{document} is the average squared degree. Because the true percolation threshold can deviate from mean-field estimates, as shown in 61, we generated 40 uniformly spaced probabilities within \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[0.5\tau , 4\tau ]$$\end{document}. Using 100 initial SIR simulations per node, we performed a binary search across this space to identify the minimum and maximum probabilities that produced a fraction of significant spreaders between 1% and 20% of the total network size n. A significant spreader is defined as any node whose average spread exceeded \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max (0.01n, 1.5\langle k \rangle )$$\end{document}. For the MIND dataset, we shifted this search window to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$[4\tau , 12\tau ]$$\end{document}, due to a lack of significant spreaders. Having established this valid range, we uniformly sampled 10 transmission probabilities from it. We then executed 500 SIR simulations per node for Brexit and iPhone-Samsung, and 1000 simulations for all other networks. For every network, we then checked that the distribution of average spreads indicates a non-trivial epidemic. For example, Fig. 4 shows the distributions for Email-EU-Core (LCC).Fig. 4Average spread distribution on Email-EU-Core (LCC) across the ten probabilities, the red dotted line indicates the average degree. Average spread distribution on Email-EU-Core (LCC) across the ten probabilities, the red dotted line indicates the average degree. After the SIR simulations, every node v ∈ V has a spread vector, where the j-th component \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu _j(v)$$\end{document} is the average number of infected nodes in group j when v is the seed. Because these average spreads are continuous variables, exact ties are unlikely even when values are practically identical (e.g., distinguishing between 15.0001 and 15.0002). Without ties, our proposed lexicographic ranking would default to a trivial comparison dominated entirely by the first vector component or, if the first component is never reached, by the first vector component that is not zero. To mitigate statistical noise and enable meaningful lexicographic sorting, we discretize the continuous spreads. We use the following heuristic. We have two requirements to satisfy: the discretization must produce a well-defined lexicographic ranking, and it must reflect the precision of the spread estimates. We address them in turn. Binning. To get a well-defined lexicographic order, the discretization must induce a total order on each component. We obtain this by binning with uniform bin width w: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(x) = \lfloor x / w \rfloor$$\end{document}. The integer order on the image of f is reflexive, antisymmetric, transitive, and total, so the lexicographic order on the resulting finite product of total orders is itself a total order (full proof in Supplementary Information). What remains is to fix w so that it reflects the precision of the spread estimates. Bin width. The natural noise scale of a sample mean is its Standard Error, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{SEM}(v) = \sigma (v) / \sqrt{n_{\textrm{sim}}}$$\end{document}, with σ the population standard deviation across simulations and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n_{\textrm{sim}}$$\end{document} the number of simulations. Using SEM as the building block ensures that two estimates land in the same bin only when their difference is comparable to the simulation noise. We use one bin width per group: let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon _j$$\end{document} denote the bin width for component j. Since SEM varies across nodes within a group, we summarize the per-node SEMs into a single \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon _j$$\end{document} via a percentile t: we set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon _j$$\end{document} equal to the t-th percentile of the strictly positive SEM values in group j. The discretized j-th component of v’s spread vector then becomes \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lfloor \mu _j(v) / \epsilon _j \rfloor$$\end{document}. Choice of t. We evaluated \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \in \{0, 1, 10, 50\}$$\end{document}, where t=0 denotes no discretization. We observed that t=50 is too aggressive (it produces a large number of ties in the ground truth) while t=1 has little effect (most values remain unique); t=10 sits between these two extremes. Table 2 reports the number of unique discretized ground truth ranks per percentile on all seven datasets. Unless otherwise specified, all results in this section use the ground truth discretized at t = 10. We evaluated t=10 for iPhone-Samsung, Brexit, and LastFM-Asia, and the full grid \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t \in \{0, 1, 10, 50\}$$\end{document} for the remaining networks. Across the four networks where the sweep was feasible (PolBlogs, PolBooks, Email-EU-Core, MIND), lexipeeling’s rank among the other methods is unchanged in the large majority of (metric, dataset) pairs, and in the few pairs where it changes the shift is at most 5 ranks. Per-metric per-percentile tables are in the Supplementary Information.Table 2Unique ground truth ranks after SEM discretization (mean±std across rankings). Higher SEM percentile → coarser bins → more ties.DatasetSEM 0%SEM 1%SEM 10%SEM 50%PolBlogs1221 ± 0 / 1222 (99.9%)1209 ± 0 / 1222 (98.9%)821 ± 0 / 1222 (67.2%)408 ± 0 / 1222 (33.4%)PolBooks105 ± 0 / 105 (100.0%)103 ± 2 / 105 (98.5%)102 ± 3 / 105 (97.5%)98 ± 5 / 105 (93.5%)Email-EU-Core896 ± 177 / 986 (90.8%)842 ± 186 / 986 (85.4%)681 ± 187 / 986 (69.1%)391 ± 161 / 986 (39.6%)MIND2213 ± 104 / 2269 (97.6%)938 ± 597 / 2269 (41.3%)553 ± 378 / 2269 (24.4%)379 ± 250 / 2269 (16.7%)Brexit14253 ± 5548 / 22745 (62.7%)12729 ± 5804 / 22745 (56.0%)3783 ± 2383 / 22745 (16.6%)807 ± 209 / 22745 (3.5%)iPhone-Samsung27096 ± 6385 / 36742 (73.7%)24737 ± 7179 / 36742 (67.3%)20797 ± 6973 / 36742 (56.6%)3077 ± 1454 / 36742 (8.4%)LastFM-Asia4826 ± 2093 / 7624 (63.3%)4826 ± 2093 / 7624 (63.3%)4246 ± 1938 / 7624 (55.7%)1787 ± 997 / 7624 (23.4%) Table 2Unique ground truth ranks after SEM discretization (mean±std across rankings). Higher SEM percentile → coarser bins → more ties.DatasetSEM 0%SEM 1%SEM 10%SEM 50%PolBlogs1221 ± 0 / 1222 (99.9%)1209 ± 0 / 1222 (98.9%)821 ± 0 / 1222 (67.2%)408 ± 0 / 1222 (33.4%)PolBooks105 ± 0 / 105 (100.0%)103 ± 2 / 105 (98.5%)102 ± 3 / 105 (97.5%)98 ± 5 / 105 (93.5%)Email-EU-Core896 ± 177 / 986 (90.8%)842 ± 186 / 986 (85.4%)681 ± 187 / 986 (69.1%)391 ± 161 / 986 (39.6%)MIND2213 ± 104 / 2269 (97.6%)938 ± 597 / 2269 (41.3%)553 ± 378 / 2269 (24.4%)379 ± 250 / 2269 (16.7%)Brexit14253 ± 5548 / 22745 (62.7%)12729 ± 5804 / 22745 (56.0%)3783 ± 2383 / 22745 (16.6%)807 ± 209 / 22745 (3.5%)iPhone-Samsung27096 ± 6385 / 36742 (73.7%)24737 ± 7179 / 36742 (67.3%)20797 ± 6973 / 36742 (56.6%)3077 ± 1454 / 36742 (8.4%)LastFM-Asia4826 ± 2093 / 7624 (63.3%)4826 ± 2093 / 7624 (63.3%)4246 ± 1938 / 7624 (55.7%)1787 ± 997 / 7624 (23.4%) Unique ground truth ranks after SEM discretization (mean±std across rankings). Higher SEM percentile → coarser bins → more ties. Evaluating β-variants. To evaluate the β-relaxed variants of lexipeeling, we adapted the ranking-dependent baselines and the ground truth accordingly. For the PageRank baselines, we used 0.5 + β instead of 0.5 as base to calculate on the target distribution and jump probability vector. For the lexicographic degree baseline, we substituted the standard degree vector with the β-degree vector. Finally, we modified the ground truth in a similar way to the β-degree vector. Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{gt}(v)$$\end{document} denote the ground-truth spread vector for node v ∈ V (evaluated post-discretization, when it is applied) and suppose, w.l.o.g., that the input ranking is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1, \ldots , i, i+1, \ldots , \ldots , s)$$\end{document}. We modified \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{gt}(v)$$\end{document} as follows, if i < s then the i-th component becomes \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{gt}_i(v) + \beta \textbf{gt}_{i+1}(v)$$\end{document}, otherwise it remains the same. Implementation details Timeout policy. The 1-hour budget is measured per (method, ranking) pair. When a method exceeds the budget on any ranking, it is dropped for all rankings on that dataset and any partial results are discarded; the same applies, by propagation, to every composite method whose base or refiner is dropped. Rank convention. Tied nodes share the same integer rank, and the next rank is one larger. The size of the rank-1 set is reported separately. SIR seeds. For each node, the simulator is seeded deterministically with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$42 + 1000 \times \mathrm {node\_id}$$\end{document}. Experimental results We evaluate lexipeeling and its variants on four aspects: whether they assign high scores to the true top spreaders (MRR, ARHR, Coverage), quality of top-ranked nodes (Cumulative Score), global ranking agreement (Kendall’s τ and weighted Kendall’s τ), and sensitivity to β and SEM discretization. Identifying the top spreader We first ask: how effectively does lexipeeling assign the highest possible rank to the true top spreader? We measure this with MRR, which equals 1 when the method places the best spreader at rank 1, and decreases as the best spreader is ranked lower. Table 3 shows that lexipeeling achieves the highest MRR on 5 of 7 datasets: it is the sole best method on PolBooks (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {MRR}=1.0$$\end{document}), Email-EU-Core (0.973), iPhone-Samsung (0.478), and LastFM-Asia (1.0), and is tied for best on PolBlogs (1.0, shared with four other methods). iPhone-Samsung is the only of these five datasets where lexipeeling’s MRR is below 0.84; on this dataset, the second-best method achieves 0.263, which lexipeeling exceeds by roughly 1.8×. On Brexit, lexipeeling is the second best method (0.879) behind coreness (1.0), which achieves its perfect score by assigning all 153 core nodes to rank 1. The one dataset where lexipeeling clearly underperforms is MIND (25-th position, MRR = 0.8252), which we discuss below. The case of MIND. MIND is structurally unusual: all 2,269 nodes share the same coreness value (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k_{\max }=5$$\end{document}), so coreness returns the whole graph at rank 1 and reaches a trivial MRR of 1.0. The degree distribution is also extreme: 83% of nodes have degree exactly 5, while a single hub in the movies category has degree 1,584 and is connected to the majority of nodes in every one of the 14 categories. The hub is the SIR top spreader in 452 of 470 cases under the 10 probability ground truth. Lexipeeling reaches MRR 0.8252 (25th among non-variant baselines) and assigns the hub average rank 1.18, placing it at rank 1 for most categories used as the first group in the ranking. The failures concentrate on two categories: news and weather. When one of them is the first group, lexipeeling demotes the hub from rank 1, even though the hub has the most edges in that group and is still the SIR top spreader. When the news is the first group, lexipeeling places 7 nodes at rank 1 and the hub is never among them; when weather is the first group there are 8 nodes with rank 1 and again the hub is excluded. The mechanism is structural. The hub connects to 448 news nodes, but these 448 nodes form a sparse subgraph (density 0.0097): the hub touches many news nodes, but those news nodes barely touch each other. The hub looks like a star. The most frequent member of lexipeeling’s rank-1 set in news-first instances connects to only 291 news nodes, which form a denser subgraph (density 0.0171, about 1.8 times denser). Peeling preserves dense subgraphs longer than sparse ones, so it gives a higher score to a node whose first-group neighbours are interconnected, even when the star center has more edges in the same group. The weather case follows the same pattern, even more starkly: the hub’s 14 weather neighbours have no edges between them at all (density 0), a pure star, while the most frequent member of lexipeeling’s rank-1 set in weather-first instances has the same weather degree (14) but its weather neighbours are interconnected (density 0.0330).Table 3MRR across datasets (avg. #rank-1 nodes in parentheses).Datasetlexipeelingt.r.-h5-indext.r.-h3-indext.r.-h4-indext.r.-corenesst.r.-lex.-degreelex.-degreer.-lex.-degreecorenessh5-indexh4-indexh3-indexr.-corenessPolBlogs1.0000 (74.0)1.0000 (10.0)1.0000 (4.5)1.0000 (7.5)1.0000 (70.0)0.7000 (1.0)0.7000 (1.0)0.7000 (1.0)0.6000 (55.0)0.6000 (17.0)0.6000 (14.0)0.6000 (8.0)0.5049 (55.0)PolBooks1.0000 (16.8)0.9000 (12.2)0.9000 (7.8)0.9000 (13.0)0.9000 (15.8)0.9600 (1.0)0.9600 (1.0)0.9600 (1.0)0.9000 (40.0)0.6667 (8.0)0.6667 (10.0)0.8667 (20.0)0.8096 (32.0)Email-EU-Core0.9729 (29.8)0.6952 (4.0)0.4318 (2.3)0.4311 (2.3)0.6952 (6.9)0.3555 (1.1)0.2762 (1.8)0.3555 (1.1)0.7607 (79.0)0.7320 (31.0)0.3791 (7.0)0.2546 (1.0)0.6422 (11.0)MIND0.8252 (11.7)0.1780 (48.1)0.1780 (43.9)0.1780 (48.3)0.1780 (202.5)0.1780 (1.0)0.8388 (1.0)0.2745 (1.0)1.0000 (2269.0)0.9809 (5.0)0.9809 (8.0)0.9809 (5.0)0.2841 (413.8)Brexit0.8794 (80.5)0.5120 (7.2)0.4942 (1.6)0.4912 (1.8)0.6076 (31.0)0.4501 (1.0)0.2579 (1.2)0.2347 (1.1)1.0000 (153.0)0.6091 (33.0)0.3779 (5.0)0.3149 (5.0)0.7522 (88.8)iPhone-Samsung0.4777 (51.5)0.1621 (18.4)0.1701 (18.1)0.1434 (18.1)0.1672 (18.6)0.1997 (1.1)0.2634 (1.1)0.2530 (1.1)0.1212 (47.0)0.1284 (47.0)0.1276 (47.0)0.1194 (47.0)0.0496 (30.9)LastFM-Asia1.0000 (31.3)0.8042 (9.8)0.5854 (2.4)0.7875 (9.2)0.8161 (15.0)0.9203 (2.0)0.8492 (1.0)0.9203 (2.0)0.1027 (47.0)0.0978 (9.0)0.0903 (8.0)0.0825 (10.0)0.3678 (24.3)Methods: lexipeeling plus the union of top-3 non-variant baselines by MRR per dataset (with tie expansion) Table 3MRR across datasets (avg. #rank-1 nodes in parentheses).Datasetlexipeelingt.r.-h5-indext.r.-h3-indext.r.-h4-indext.r.-corenesst.r.-lex.-degreelex.-degreer.-lex.-degreecorenessh5-indexh4-indexh3-indexr.-corenessPolBlogs1.0000 (74.0)1.0000 (10.0)1.0000 (4.5)1.0000 (7.5)1.0000 (70.0)0.7000 (1.0)0.7000 (1.0)0.7000 (1.0)0.6000 (55.0)0.6000 (17.0)0.6000 (14.0)0.6000 (8.0)0.5049 (55.0)PolBooks1.0000 (16.8)0.9000 (12.2)0.9000 (7.8)0.9000 (13.0)0.9000 (15.8)0.9600 (1.0)0.9600 (1.0)0.9600 (1.0)0.9000 (40.0)0.6667 (8.0)0.6667 (10.0)0.8667 (20.0)0.8096 (32.0)Email-EU-Core0.9729 (29.8)0.6952 (4.0)0.4318 (2.3)0.4311 (2.3)0.6952 (6.9)0.3555 (1.1)0.2762 (1.8)0.3555 (1.1)0.7607 (79.0)0.7320 (31.0)0.3791 (7.0)0.2546 (1.0)0.6422 (11.0)MIND0.8252 (11.7)0.1780 (48.1)0.1780 (43.9)0.1780 (48.3)0.1780 (202.5)0.1780 (1.0)0.8388 (1.0)0.2745 (1.0)1.0000 (2269.0)0.9809 (5.0)0.9809 (8.0)0.9809 (5.0)0.2841 (413.8)Brexit0.8794 (80.5)0.5120 (7.2)0.4942 (1.6)0.4912 (1.8)0.6076 (31.0)0.4501 (1.0)0.2579 (1.2)0.2347 (1.1)1.0000 (153.0)0.6091 (33.0)0.3779 (5.0)0.3149 (5.0)0.7522 (88.8)iPhone-Samsung0.4777 (51.5)0.1621 (18.4)0.1701 (18.1)0.1434 (18.1)0.1672 (18.6)0.1997 (1.1)0.2634 (1.1)0.2530 (1.1)0.1212 (47.0)0.1284 (47.0)0.1276 (47.0)0.1194 (47.0)0.0496 (30.9)LastFM-Asia1.0000 (31.3)0.8042 (9.8)0.5854 (2.4)0.7875 (9.2)0.8161 (15.0)0.9203 (2.0)0.8492 (1.0)0.9203 (2.0)0.1027 (47.0)0.0978 (9.0)0.0903 (8.0)0.0825 (10.0)0.3678 (24.3)Methods: lexipeeling plus the union of top-3 non-variant baselines by MRR per dataset (with tie expansion) MRR across datasets (avg. #rank-1 nodes in parentheses). Methods: lexipeeling plus the union of top-3 non-variant baselines by MRR per dataset (with tie expansion) Beyond the top spreader: ARHR@ k This advantage extends beyond the single top spreader when evaluating ARHR@k, which generalizes MRR by measuring how highly a method ranks all top-k spreaders, not just the single best one. For absolute values of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{3, 5\}$$\end{document}, lexipeeling is the sole best performing method on 5 of 7 datasets (PolBlogs, PolBooks, Email-EU-Core, iPhone-Samsung, LastFM-Asia) and second best method on Brexit. At k = 10, lexipeeling remains 1st on 4 datasets and it is 3rd on Email-EU-Core and Brexit. For percentage-based k (top 3%–10% of nodes), lexipeeling remains first or second at ARHR@3% on most datasets, but coreness overtakes it at larger percentages. Full ARHR results are in the Supplementary Information.Fig. 5MRR robustness on Email-EU-Core (LCC) across infection probabilities, ranking strategies, ranking lengths, and lexicographic degeneracies. For clarity, only lexipeeling (red) and the top 3 competing baselines are shown. Lexipeeling consistently achieves the highest MRR across all experimental conditions. MRR robustness on Email-EU-Core (LCC) across infection probabilities, ranking strategies, ranking lengths, and lexicographic degeneracies. For clarity, only lexipeeling (red) and the top 3 competing baselines are shown. Lexipeeling consistently achieves the highest MRR across all experimental conditions. Robustness Figure 5 shows that lexipeeling’s advantage on Email-EU-Core is robust across infection probabilities, ranking strategies, ranking lengths, and lexicographic degeneracies. On PolBlogs, PolBooks, and LastFM-Asia, lexipeeling achieves a perfect MRR of 1.0 under every ranking strategy, probability, ranking length, and lexicographic degeneracy. On iPhone-Samsung, it ranks 1st across all ranking lengths and 8 of 10 infection probabilities, with lower performance limited to a few specific strategies. On Brexit, lexipeeling is the second-best method when MRR is averaged across all instances and reaches first place on 5 of 10 infection probabilities. The robustness plots for every networks is in the Supplementary Information. Ranking strategies The main ingredient of lexipeeling is the input ranking, it is interesting to analyze how the choice of ranking strategy affects the lexipeeling performance with respect to that of coreness. Table 4 summarizes the comparison. Excluding MIND, where coreness is uninformative (it returns the entire graph at rank 1), lexipeeling wins on 29 strategy evaluations, ties on 22, and loses on 10. The wins are concentrated on LastFM-Asia, iPhone-Samsung, and Email-EU-Core, while Brexit is the only dataset where lexipeeling consistently loses. The magnitude of the gains substantially exceeds the losses: the maximum gain reaches 0.97 (Email-EU-Core) while the worst loss is 0.47 (Brexit). Some strategy families favor lexipeeling more than others, but no single strategy provides a universal advantage. Full per-strategy results are in the Supplementary Information.Table 4Lexipeeling vs. coreness on MRR by ranking strategy: per-dataset wins, losses, ties, and extreme score differencesDatasetWTLMax gainMax lossPolBlogs1100.80–PolBooks2600.50–Email-EU-Core5710.970.29MIND01013–0.50Brexit085–0.47iPhone-Samsung9040.920.04LastFM-Asia12000.95–Total293223 Table 4Lexipeeling vs. coreness on MRR by ranking strategy: per-dataset wins, losses, ties, and extreme score differencesDatasetWTLMax gainMax lossPolBlogs1100.80–PolBooks2600.50–Email-EU-Core5710.970.29MIND01013–0.50Brexit085–0.47iPhone-Samsung9040.920.04LastFM-Asia12000.95–Total293223 Lexipeeling vs. coreness on MRR by ranking strategy: per-dataset wins, losses, ties, and extreme score differences How many top spreaders are captured? To complement our analysis, we also evaluate Coverage@k, which quantifies the fraction of the true top-k spreaders successfully captured within the method’s top-k nodes. An important caveat: because both the method and the ground truth can produce ties, we break ties optimistically, that is, we assume the best possible assignment of tied nodes to the top-k slots. When evaluating large percentage-based thresholds (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 3\%$$\end{document}), Coverage@k is largely saturated, with various methods achieving a perfect score of 1.0 on all datasets. At k = 1%, the metric begins to discriminate: no method achieves >0.9 across all datasets. Lexipeeling secures 1st place on three datasets; on the remaining ones, it ranks as low as 8th but with negligible performance gaps (scores ≥ 0.985 on all except PolBlogs at 0.88). For absolute k values, the picture changes: no method scores above 0.8 on all datasets, allowing finer discrimination. Lexipeeling demonstrates a distinct advantage at the lowest thresholds (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 3\}$$\end{document}). For example, at k=3, lexipeeling secures first place on 5 out of 7 datasets. It outperforms the second-best methods on Email-EU-Core (0.955 vs. coreness at 0.781) and more than doubles the score of the top-restricted lexicographic degree on iPhone-Samsung (0.480 vs. 0.210), while achieving a perfect 1.0 on PolBooks, 0.833 on PolBlogs (tied with two other methods), and 0.977 on LastFM-Asia. As the threshold expands to k=5 and k=10, lexipeeling remains the sole best method on Email-EU-Core, iPhone-Samsung, and LastFM-Asia. On PolBooks, it drops to 8th place at k=5 while still maintaining a high score of 0.980, before fully recovering for first place (with ties) at k=10. On the remaining networks (PolBlogs, Brexit, and MIND), standard coreness and the h-indices eventually overtake it in rank at these wider thresholds. A striking example is LastFM-Asia, where standard coreness and all h-index variants completely fail to identify any true top spreaders at \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 3, 5\}$$\end{document} (scoring exactly 0.0), whereas lexipeeling reaches near-perfect Coverage (1.0, 0.977, and 0.975, respectively). The quality of top ranked nodes We now address the natural continuation of our analysis: if a method declares a node as highly ranked, can we trust that it is truly influential? We use the Cumulative Score@(k, t) to answer this question. This metric evaluates how reliably a method identifies truly influential nodes: among the nodes ranked in the top k by a method, what fraction actually falls within the top t of the ground-truth ranking? We systematically evaluate this across all combinations of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k, t \in \{1, 5, 10\}$$\end{document}. Lexipeeling vs coreness and h-indices Lexipeeling decisively outperforms standard coreness, winning in 61 out of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3 \times 3 \times 7 = 63$$\end{document} combinations of k, t, and datasets. The performance of the h-indices degrades as the index order increases, indeed, increasing the order of the h-indices converges towards coreness. Lexipeeling outperforms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_5$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_4$$\end{document} and slightly outperforms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_3$$\end{document}. However, it slightly underperforms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_2$$\end{document}, underperforms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_1$$\end{document}, and consistently loses to both standard degree and lexicographic degree. Despite outperforming coreness and higher-order h-indices, lexipeeling’s scores remain low. For example, focusing on k=1 and t=10, PolBooks is the only dataset where more than half (55.9%) of lexipeeling’s rank-1 nodes have a ground-truth rank of ≤ 10. For the remaining datasets, this fraction ranges from 9.8% (Brexit) to 41.5% (LastFM-Asia). Furthermore, these inclusion percentages drop even lower as we expand the selection to k=5 and k=10, indicating that lexipeeling also assigns high scores to nodes that are not highly effective spreaders. Full details of the cumulative scores are in the Supplementary Information. Composite methods Motivated by this limitation, we explore several variants of lexipeeling. We investigate composite methods to resolve ties: given a “base” method and a “refiner” method, the composite method uses the “refiner” to break the ties of the “base” method. (Of course, if two nodes share the same score in both methods, their final composite rank remains a tie.) We combine lexipeeling with degree, coreness, and lexicographic degree in both roles, creating six composites: lexipeeling-degree, lexipeeling-coreness, and lexipeeling-lexicographic-degree (lexipeeling as base), and degree-lexipeeling, coreness-lexipeeling, and lexicographic-degree-lexipeeling (lexipeeling as refiner). Figure 6 shows tie-size distribution on Email-EU-Core of coreness, lexipeeling, degree, lexicographic-degree, and lexipeeling-degree: lexipeeling-degree substantially reduces tie sizes.Fig. 6Ties size distribution on Email-EU-Core (LCC). Each curve shows the number of nodes sharing each rank (log scale) vs. rank position (% of nodes). Ties size distribution on Email-EU-Core (LCC). Each curve shows the number of nodes sharing each rank (log scale) vs. rank position (% of nodes). Beyond the composite family, we also consider a variant that handles incomplete rankings. When the user-supplied ranking does not cover all the groups of the network, standard lexipeeling ignores the nodes whose group is not in the ranking. The lexipeeling-extended variant addresses this by gathering all such nodes into a single artificial group and appending this artificial group to the end of the ranking. For example, if the network has groups \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{A, B, C, D, E\}$$\end{document} and the user supplies the ranking (A, B), lexipeeling-extended runs standard lexipeeling on the ranking \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(A, B, \{C, D, E\})$$\end{document}. We evaluate the performance of these composite methods across all combinations of k and t. Overall, adding a refiner improves the cumulative score compared to using a single base method. This improvement is highly reliable: across the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3 \times 3 \times 7 \times 6 = 378$$\end{document} (composite, dataset, k, t) combinations evaluated, the composite score dropped below the base score in 13 instances, with the largest drop being 1.6%. The largest improvements occur when lexipeeling serves as the base method. Here, the composite variants show consistent performance gains when using degree or lexicographic degree as the refiner. For example, at k=1 and t=1, standard lexipeeling achieves a 1.4% score on the PolBlogs dataset. Refining it with degree (lexipeeling-degree) jumps this score to 90.0%. Similarly, on LastFM-Asia, the score grows from 6.6% to 80.3% with lexipeeling-degree, and to 82.0% with lexipeeling-lexicographic-degree. These improvements remain consistent across k=5 and k=10 for all values of t. While lexipeeling-coreness also strictly improves upon standard lexipeeling, its gains are smaller than those produced by the other two refiners. Finally, lexipeeling-extended presents a tiny overall improvement compared to standard lexipeeling. The full results are available in the Supplementary Information. Best overall method Overall, lexipeeling-degree emerges as the most robust method, achieving the best average rank (13.06) across all datasets and (k, t) combinations, maintaining first place for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \{1, 5\}$$\end{document} and dropping to second at k = 10, edged out by PageRank with exponential jump. Looking at the average rank, it is followed by top-restricted local gravity (avg. rank 14.21), top-restricted entropy degree distance combination (15.37), and top-restricted local-global centrality (15.89). In fact, seven of the top ten methods by average rank belong to the top-restricted centrality family; the only exceptions are lexipeeling-degree (1st), PageRank with exponential jump (5th), and degree-lexicographic-lexipeeling (10th). The two variants serve different goals. If we want to identify the single top spreader (or a very small set), lexipeeling is the right choice: it achieves higher MRR and places the true top spreader at rank 1 more often. If we want a top-k list of good quality for k > 1 (e.g., a seed set for a campaign), lexipeeling-degree is the right choice: it keeps a larger fraction of the true top spreaders in the top-k, at the cost of sometimes missing rank 1. Robustness across datasets No single method dominates across all datasets: the winners of each dataset exhibit sharp weaknesses elsewhere (see Supplementary Information for full results). Lexipeeling-degree is never the absolute best on any individual dataset, placing between 4th and 23rd, but it achieves the most consistent performance across all of them. To quantify this, we compute for each method the maximum gap between the dataset winner and the method’s own score. Lexipeeling-degree achieves the smallest gap (18.90 points, on MIND), ahead of PageRank with exponential jump (22.06, on PolBlogs) and lexipeeling-lexicographic-degree (26.16, on Email-EU-Core). Figure 7 visualizes this ranking for the top 5 methods.Fig. 7Robustness across datasets: worst-case cumulative score gap for the top 5 methods. For each method, we compute its average cumulative score per dataset (across all (k, t) combinations) and report the maximum difference between the dataset winner’s score and the method’s own score. Lower bars indicate more consistent performance. Lexipeeling-degree (orange) achieves the smallest worst-case gap (18.90 points, on MIND). Robustness across datasets: worst-case cumulative score gap for the top 5 methods. For each method, we compute its average cumulative score per dataset (across all (k, t) combinations) and report the maximum difference between the dataset winner’s score and the method’s own score. Lower bars indicate more consistent performance. Lexipeeling-degree (orange) achieves the smallest worst-case gap (18.90 points, on MIND). MRR trade-off. A natural question is how these lexipeeling variants behave in assigning high scores to the top spreaders. Overall, lexipeeling-extended exhibits an MRR profile nearly identical to standard lexipeeling, with only negligible performance degradation. Generally, composite methods have lower MRR scores than their base methods. However, the magnitude of this degradation depends on the chosen base method. Using degree or lexicographic degree as the base incurs very little disruption when adding lexipeeling as the refiner method. Conversely, applying lexipeeling to a coreness base causes a substantially more pronounced performance drop. When lexipeeling itself serves as the base, combining it with coreness preserves the MRR best, followed by degree, while adding lexicographic degree triggers the largest penalty. Finally, MRR scores of lexipeeling-degree fluctuate depending on the network topology. For example, it ranks 43rd on Brexit (0.28 vs. the top score of 1.0 achieved by coreness), but climbs to 6th on Email-EU-Core (0.72 vs. 0.97 for the top method, lexipeeling). We also analyzed the Pareto frontiers of MRR against cumulative score at \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k{=}1, t{=}1)$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(k{=}5, t{=}5)$$\end{document}. Lexipeeling, lexipeeling-extended, or both anchor the frontier across Brexit, Email-EU-Core, iPhone-Samsung, and LastFM-Asia. Full details are in the Supplementary Information. Global ranking quality While lexipeeling excels at identifying top spreaders, its full-ranking quality is limited. We measure this with weighted Kendall’s τ (which emphasises agreement at the top of the ranking) and standard Kendall’s τ (uniform weight across all pairs). On weighted Kendall’s τ, lexipeeling ranks in the bottom half on 3 of 7 datasets (PolBlogs, Email-EU-Core, LastFM-Asia), with values ranging from 0.39 (LastFM-Asia) to 0.82 (PolBlogs). On standard Kendall’s τ, lexipeeling performs better relatively, ranking in the top half on 6 of 7 datasets, with values from 0.17 (iPhone-Samsung) to 0.77 (PolBooks). Extended-gravity emerges as the dominant method for standard Kendall’s τ, ranking first on 6 out of 7 datasets. The sole exception is PolBooks, where it places 13th (0.36 vs. 0.78 for the top method, lexicographic-degree). Standard gravity centrality closely follows, ranking 2nd on 5 of those 6 datasets (third on MIND, where dangling centrality is second) and 12th on PolBooks with 0.37. When evaluating with weighted Kendall’s τ, however, there is no single dominant method. Extended-gravity remains highly competitive, ranking first on Brexit and iPhone-Samsung, second on Email-EU-Core, and third on PolBlogs, but suffers a significant drop on PolBooks (66th place, 0.50 vs. 0.82 for the top method, top-restricted dangling centrality). Standard gravity centrality experiences an even more pronounced performance degradation. Full details are provided in the Supplementary Information. Lexipeeling variants. On all the instances where lexipeeling-extended is defined (i.e., when the ranking does not cover all groups), lexipeeling-extended improves upon lexipeeling across both standard and weighted Kendall’s τ, with PolBooks as the sole exception (where standard Kendall’s τ drops from 0.77 to 0.75, and weighted Kendall’s τ drops from 0.77 to 0.76). Despite these improvements, the absolute scores of lexipeeling-extended remain relatively low compared to the dominant baselines: it reaches the top 10 for standard Kendall’s τ on only one dataset (3rd on PolBooks; 11th on MIND). The composite methods, instead, yield contrasting results across the two metrics: they consistently decrease the standard Kendall’s τ of their base methods (with the outlier exception of coreness on MIND, where the base method fails entirely) while yielding slight improvements, or maintaining strict parity, in their weighted Kendall’s τ. Excluding MIND, where no variants achieve optimality, lexipeeling or at least one of its variants consistently anchors the Pareto frontier for either standard or weighted Kendall’s τ against MRR. For standard Kendall’s τ, the frontier includes lexipeeling (4 datasets) and lexipeeling-extended (3 datasets), with no composite of lexipeeling appearing on the frontier. On Brexit, no lexipeeling variant reaches the frontier. For weighted Kendall’s τ, composites play a much larger role: lexipeeling-coreness appears on 3 datasets, while lexipeeling and lexipeeling-extended appear on 3 and 4 networks respectively. Full details are in the Supplementary Information. Sensitivity analysis The azure babà problem The β-relaxation was designed to handle the azure babà case from Section 3: a node with a tiny first-group advantage but no influence elsewhere can overtake a node with comparable first-group influence and much more on the lower groups. To check whether this occurs in practice, for each ranking and β, we find the best spreader among the rank-1 nodes of three methods: lexipeeling, its β-variant, and the best method excluding lexipeeling and its variants. We measure what fraction of each group in the ranking the best spreader infects. For β-lexipeeling, the best spreader is selected according to the β-weighted ground truth described in Section 4. Across all datasets, rankings, and infection probabilities, the best spreaders selected by standard lexipeeling and its β-variants show similar influence on lower-priority groups, with the largest differences at β = 0.99, as expected. Full plots are in the Supplementary Information Sensitivity to β. For β > 0, the beta-adapted lexipeeling generally worsens or maintains its rank on all metrics compared to standard lexipeeling. A few exceptions exist: for example, for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta \ge 0.1$$\end{document}, the Kendall rank improves on PolBlogs and LastFM-Asia, and weighted Kendall improves on PolBlogs, though without reaching top positions. On MRR, the beta-adapted variant loses its top-3 position only at the extreme case of β = 0.99 on PolBooks and Email-EU-Core, β = 0.5 on Email-EU-Core, and β = 0.01 on Brexit (where it ranks 4th). ARHR shows similar stability: excluding the extreme case of β = 0.99 and MIND, the rank never drops by more than three positions, with isolated exceptions on PolBlogs at β = 0.5 (ARHR@3, ARHR@5), on Email-EU-Core at β = 0.5 (ARHR@1, where it ranks 7th), and on Brexit at β = 0.01 (ARHR@3, @5, @10, @1%, where it ranks between 6th and 7th). Coverage@k follows the same pattern as ARHR but with more pronounced drops, especially for PolBlogs. The beta-adapted lexipeeling-degree, instead, shows substantially lower cumulative scores compared to standard lexipeeling-degree, with only a few isolated exceptions at low β. Full details are in the Supplementary Information. Sensitivity to SEM discretization For the four datasets with multiple SEM levels (PolBlogs, PolBooks, Email-EU-Core, MIND), we verify that the results reported at \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {SEM}=10\%$$\end{document} are representative. Lexipeeling’s rank among non-variant methods is largely stable across SEM values: MRR, Kendall τ, Cumulative scores, and most Coverage ranks are unchanged on all four datasets. The only notable variation occurs on PolBlogs, where weighted Kendall τ rank shifts by ± 5 (from 43rd to 48th) and Coverage@5 by ± 3 (from 2nd to 5th), though the underlying score differences remain negligible. Full SEM results are in the Supplementary Information. Conclusions and future work Classical centrality measures evaluate node importance globally, ignoring that users often care about specific categories more than others. In this work, we proposed lexicographic core decomposition and lexipeeling to address this gap, ranking nodes according to a group hierarchy. The problem reduces to a special case of weighted node core decomposition. Our experiments on 7 real-world networks against 79 baselines show that lexipeeling assigns the highest rank to the true top spreader on 5 of 7 datasets. However, like standard coreness, it assigns the same rank to many nodes, so weak spreaders may appear among the highest ranked ones. We show that lexipeeling-degree, which uses degree to break lexipeeling’s ties, is the method that, across all datasets and among all 79 baselines, most reliably places truly influential nodes among its highest ranked ones. Several questions remain open. Lexipeeling excels at assigning high scores to the true top spreaders, while lexipeeling-degree excels at ensuring that its highest ranked nodes are truly influential; designing a method that achieves both simultaneously is a natural next step. More broadly, in this work we asked which nodes are the best spreaders when certain categories are prioritized; the same question for other definitions of node importance remains unexplored. Moreover, in our formulation, priorities among categories reduce to weights on nodes. Whether there exist natural priority models not expressible as node weights is an open question. A systematic comparison with recent learning-based methods for influence ranking and influence maximization (e.g., 74–77) is a natural next step. Incorporating machine learning-based techniques to further enhance the predictive power of group-priority-aware spreader identification (e.g., 78,79) is another. Extending lexicographic core decomposition to dynamic and temporal networks (e.g., 80–82) — with time-varying group memberships, evolving lexicographic cores, and incremental peeling for streaming graphs — is a further direction. Supplementary Information Supplementary Information. Supplementary Information.