Effective Index Construction Algorithm for Optimal $(k,\eta)$-cores Computation

Guanming Jiang; Peng Xu; Philip S.Yu; Shengli Sun; Yi Li

REVIEW 3 major objections 5 minor 23 references

Effective Index Construction Algorithm for Optimal $(k,\eta)$-cores Computation

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A new algorithm builds the UCF-Index for $(k,\eta)$-cores on uncertain graphs without the floating-point division errors that make the current index construction incorrect, and it runs one to two orders of magnitude faster than a correct…

desk verdict Plausibly fixes a real numerical bug in UCF-Index construction with a solid DP baseline and large speedups, but it still needs a correctness proof and an output-equivalence check; the stress-test's concrete counterexample does not survive close reading. read the letter →

arxiv 2504.20795 v1 pith:FYILY7VF submitted 2025-04-29 cs.DS

Shengli Sun , Peng Xu , Guanming Jiang , Philip S.Yu , Yi Li This is my paper · ORCID

classification cs.DS MSC 68R1005C8568W40

keywords uncertaingraphs(keta)-coreUCF-Indexk-probabilitycoredecompositionfloating-pointerrorlazyrefreshingprogressiverefinement

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the state-of-the-art index for answering $(k,\eta)$-core queries on uncertain graphs, the UCF-Index, is usually built incorrectly because its construction relies on recursive floating-point division to update $k$-probabilities during vertex peeling, and these errors worsen sharply as $k$ grows. To fix this, the paper proposes OptiUCF, which recomputes $k$-probabilities exactly by dynamic programming, but only for the vertices that truly need it, using tight bounds to skip or delay refreshes and a layer-by-layer search to find the minimum-probability vertex cheaply. If correct, this makes the UCF-Index both exact and practical: queries for any $k$ and $\eta$ can be answered in optimal time, and construction is reported to be one to two orders of magnitude faster than a correct DP-based baseline on real-world graphs.

What carries the argument

The mechanism is the combination of two bounds and an on-demand refresh loop. The $\beta$-function based bound gives a constant-time interval $[\mathrm{LB}(u),\mathrm{UB}(u)]$ for each vertex's $k$-probability from its minimum and maximum incident edge probabilities, and the top-$K$ lower bound tightens $\mathrm{LB}(u)$ using the product of the $k$ highest-probability edges of $u$ (Lemma 1). An additional lower bound comes from Corollary 1: for any vertex $u$, $k$-prob$(u,G) \ge \eta$-$\mathrm{thres}_{k+1}(u)$, which supports the layer partition. Algorithm 2, refKPROB, uses these bounds to decide which indefinite vertices must have their exact $k$-probability recomputed by DP, while Algorithm 3, OptiUCF, manages the working set $V_w$ and adds layers progressively until the true minimum-probability vertex is found.

What would settle it

Run OptiUCF and an exact baseline that recomputes every affected $k$-probability by dynamic programming after every vertex deletion on all uncertain graphs with up to about a dozen vertices and edge probabilities drawn from $\{0.1, 0.5, 0.9\}$; any graph where the two algorithms produce different $\eta$-thresholds for any vertex, or delete vertices in a different order, shows that the bound-based pruning does not preserve the exact decomposition.

Watch

Extended reading notes

Core claim

The paper's central claim is that a correct UCF-Index for uncertain graphs can be constructed efficiently by replacing the error-prone recursive floating-point update of $k$-probabilities with exact dynamic-programming recomputation performed on demand. The proposed OptiUCF algorithm maintains upper and lower bounds on each vertex's $k$-probability and uses a lazy refreshing strategy: when a vertex is deleted, a neighbor is refreshed only if its upper bound exceeds the current threshold, and a neighbor whose lower bound is at least the current minimum $k$-probability is left un-refreshed. A further progressive refinement partitions vertices into layers using their $\eta$-thresholds from the previous $k$, so the search for the minimum-probability vertex starts in the outermost layer and expands only when needed. The paper claims this yields a correct index for every $k$ and $\eta$, with construction time one to two orders of magnitude faster than a baseline that recomputes every affected $k$-probability exactly.

Load-bearing premise

The algorithm assumes that its bound-based pruning never changes which vertex actually has the smallest $k$-probability at each peeling step; specifically, a vertex can be safely skipped or delayed whenever its stored upper or lower bound says so, without a proof that this preserves the exact peeling order.

Editorial extensions

If this is right

Applications that rely on $(k,\eta)$-cores, such as community search, fraud detection, and influence maximization, can now use a UCF-Index that is correct for all parameter combinations instead of one that degrades as $k$ grows.
The correct construction remains practical at scale: on the tested graphs the full algorithm was one to two orders of magnitude faster than a DP-based exact baseline and scaled smoothly to graphs with millions of vertices.
The error ratio of the previous construction approaches 100% on real graphs for large $k$, so avoiding floating-point division is a qualitative correctness requirement, not a minor numerical tweak.
Because the index supports online queries in time linear in the result size, the speedup in construction translates directly to more reliable and responsive interactive exploration of uncertain graphs.
The progressive refinement technique makes the index construction faster on larger graphs, as the gap between the optimized algorithm and the baseline widens with graph size.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same bound-then-refresh-on-demand pattern could repair other uncertain-graph peeling indices that suffer from floating-point division drift, notably $(k,\gamma)$-truss index construction, where the failure mechanism is analogous.
The pruning rules place a bet on the tightness of the bounds; a natural stress test is to instrument the algorithm and count how often a delayed vertex later turns out to have been the true minimum, which would tell whether the heuristic is robust on adversarial as well as real-world inputs.
The $\eta$-threshold-based lower bound from Corollary 1 could make construction self-validating: if a vertex's stored threshold from layer $k+1$ ever exceeds its recomputed $k$-probability within the same layer, that would signal a violated bound before the index is used.
An alternative repair path, not explored in this paper, is to replace floating-point arithmetic with exact rational arithmetic or compensated summation in the update rule itself; if that were cheap enough, the need for bound-based pruning might disappear entirely.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear [Colleague],

I've read the arXiv paper by Sun et al. on constructing the UCF-Index for (k,η)-cores without floating-point division errors. The problem is real: Yang et al.'s original construction uses recursive division and can be badly wrong on large graphs. Replacing that with a DP-based baseline is the obvious correct move, and the paper's optimization of that baseline is the actual contribution.

What's good: the baseline BC is straightforward and correct. The lazy refreshing strategy is a reasonable combination of known bounds (Bonchi's beta-function bound and a top-K product bound) with on-demand DP recalculation. The progressive refinement using η-thresholds from the previous k is a neat way to reduce initialization cost. The experiments are extensive, four real graphs and four SNAP graphs, and the speedups over BC are consistently one to two orders of magnitude. That's a practical improvement.

The soft spot, as the reader's report notes, is the absence of a correctness proof for the pruning. Theorem 2 only analyzes running time. If the lazy strategy ever peeled a vertex out of order, the resulting η-thresholds would be inflated and the whole index would be wrong. The paper does not supply a proof, and it never verifies that OP/OP* produce the exact same thresholds as BC on any dataset. That's a real gap in evidence.

However, I want to push back on the stress-test note's concrete counterexample. It claims that lower bounds can go stale after a neighbor's edge is deleted, allowing an inflated LB to delay a refresh. That would be a genuine bug, but it doesn't hold up. In Algorithm 3, line 19 removes pcrt, and then lines 20–24 process every neighbor of pcrt, recomputing bounds for each one. Any vertex whose incident edges changed is exactly a neighbor of the deleted vertex, so its stored LB is refreshed. A vertex in D that is not adjacent to the deleted vertex has an unchanged incident edge set, so its old LB remains valid. So the pruning looks sound on a careful reading. What's missing, then, is not a demonstrated error but a rigorous statement and proof that these invariants hold.

Who this is for: researchers working on uncertain graph analysis, specifically core decomposition and index construction. A referee should ask for a correctness proof or at least an output-equivalence experiment. I'd take the paper, but with requiring that addition.

Best, [You]

Referee Report

3 major / 5 minor

Summary. The paper addresses the construction of the UCF-Index for (k,η)-cores on uncertain graphs. It observes that the existing index construction algorithm, which updates k-probabilities by recursive floating-point division, can produce incorrect thresholds. The paper proposes OptiUCF, which replaces division updates with exact DP refreshes, and accelerates this baseline with two techniques: (i) a lazy refreshing strategy using upper and lower bounds on k-probability, and (ii) a progressive refinement strategy that partitions vertices according to their η-thresholds from the previous k iteration. The authors claim that OptiUCF constructs a correct UCF-Index and runs one to two orders of magnitude faster than a DP-based baseline. Experiments on eight real-world graphs report running times, the error ratio of the old EC algorithm, and scalability results.

Significance. If the correctness claim were established, this would be a useful contribution: it would provide a way to build the UCF-Index without the floating-point division errors identified in prior work, and the proposed bound-based pruning is a natural and potentially effective optimization. The baseline algorithm (Algorithm 1) is sound in principle, and the upper/lower bound inequalities used for pruning are parameter-free and taken from known results. The empirical study is on substantial graphs and includes a demonstration that the previous EC algorithm has very high error rates. However, the central correctness claim is not supported by a proof, and the progressive refinement strategy appears to rely on a lower bound that is not valid for the dynamically shrinking graph. Because correctness is the paper's headline contribution, this issue is load-bearing.

major comments (3)

[Section 4.2 and Algorithm 3 (lines 14–16, 25–27)] The progressive refinement strategy uses η-thres_{k+1}(u) as a lower bound on the k-probability of u in the current subgraph G′. Corollary 1 only states k-prob(u,G) ≥ η-thres_{k+1}(u) for the original graph G. During the peeling phase for k, G′ is obtained by deleting vertices, and the k-probability of a vertex can only decrease when incident edges are removed. Thus η-thres_{k+1}(u) can exceed the true k-probability of u in G′. Concretely, if k=2 and u has three high-probability edges to vertices a,b,c whose own k-probabilities are small, then after a and b are peeled u may have degree below k and k-probability 0, while η-thres_3(u) is still high. The condition in Algorithm 3 line 14 (η_{i+1} < k-prob(pcrt,G′)) can then fail to add u's layer before a moderate-probability vertex c is peeled; c receives an inflated threshold and u is processed only after curThres has risen, yielding an incorrect index. The paper needs either a proof that η-thres_{k+1}(u) remains a valid lower bound on k-prob(u,G′) throughout the peeling, or a modification of the progressive refinement rule.
[Section 4.1 and Algorithms 2–3] There is no correctness theorem for the pruning rules of OptiUCF. The paper asserts in Section 4.1 that Steps 2 and 4 avoid unnecessary refreshes, and Algorithm 2 (refKPROB) is described as returning the vertex with minimum k-probability, but no lemma or theorem states that these comparisons—using freshly computed or lazily maintained bounds—preserve the exact peeling order of the baseline. In particular, the manuscript does not specify how lower bounds stored in the heap D are updated when an incident edge is deleted, nor does it prove that the condition LB(u) ≥ k-prob(pnxt,G′) in Step 4 is sufficient to delay refreshing. Since the central claim is that OptiUCF constructs a correct UCF-Index, this missing invariant is a load-bearing gap that must be filled with a formal proof.
[Section 5.2] The accuracy experiments quantify the error of the old EC algorithm but never compare the η-thresholds produced by OP or OP* with those produced by the correct baseline BC. Given that no correctness proof is supplied, an empirical output-equivalence check is essential to support the claim that OP and OP* build a correct index. The authors should report, for each dataset and at least for a range of k, the fraction of vertices whose η-thres_k matches BC, or compare the resulting η-trees directly.

minor comments (5)

[Section 4.3, Theorem 2] The statement of Theorem 2 contains unbalanced parentheses and an unexplained term k^2_max|E|; the proof sketch does not account for all terms, and the sentence 'In the worst-case scenario, we need to updated the k-probabilities of all vertices in D during each peeling' is not a complete derivation. Please restate the complexity bound and justify each term.
[Section 2.2, Definition 3] Definition 3 says the k-probability 'is the probability that Pr(deg(u,G)≥k)'; this should read 'is Pr(deg(u,G)≥k)' to avoid redundancy.
[Section 1, Example 1 and Figure 1] The illustrative floating-point example in Figure 1 is helpful but the choice of ε=10^-3 is not connected to any actual machine precision; please clarify how the error bound from [8] is instantiated in this example.
[Section 5.1] The running-time plots in Figure 5 would benefit from explicit axis labels and a note on whether the y-axis is logarithmic, since the claimed one-to-two-orders-of-magnitude improvement is otherwise hard to verify from the figure.
[General] There are several minor typographical issues: 'Problem Defnition 1' in Section 2.2, the inconsistent notation 'η-tree2' in Figure 2(b), and the phrase 'the probability that Pr(deg(u,G)≥k)' in Definition 3. A careful proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the index-construction bounds and recalculation strategy are derived from independent probability inequalities and a DP baseline, not from the claimed output.

full rationale

The paper's central claim is that OptiUCF constructs a correct UCF-Index efficiently. The correctness-relevant ingredients are not defined in terms of the target η-thresholds. The Beta-function bounds in Eq. (7) are cited from Bonchi et al. [4], an external source. The Top-K lower bound in Lemma 1 is proved directly from possible-world semantics and the definition of k-probability, independent of the final index. Corollary 1, which gives the η-threshold based lower bound, is proved from Theorem 1 via monotonicity of cores, again independent of any fitted value. The k-probability refreshes use exact dynamic programming from Eq. (4), and the baseline Algorithm 1 explicitly avoids floating-point division, so the comparison baseline is a correct DP construction rather than a quantity derived from the optimized algorithm's own choices. The reported speedups are measured against this baseline and against ablation variants, so they are empirical claims rather than conclusions forced by construction. The only notable weakness is that the lazy refreshing pruning rules in Section 4.1 and Algorithm 3 are not accompanied by a correctness theorem showing that stale lower bounds remain valid after edge deletions; however, that is a potential correctness gap, not circular reasoning. There is no self-citation chain carrying the argument, no fitted parameter renamed as a prediction, and no equation in the derivation reduces to its own input. The paper is therefore self-contained with respect to external benchmarks and exhibits no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The algorithm has no fitted constants; edge probabilities are inputs. It relies on the standard independence assumption, on beta-function bounds from prior work, on the unproven freshness and validity of stored bounds during the lazy refresh, and on the equivalence between peeling and the eta-threshold definition.

assumptions (4)

domain assumption Edge existence probabilities are independent.
Stated in Section 2: 'we assume that the existing probability of each edge is independent.' This is the basis for the DP equations (3)-(5).
standard math The regularized beta-function inequalities of Bonchi et al. bound the k-probability of a vertex.
Equations (7) in Section 4.1 use these known inequalities without proof; they are adopted from the cited work.
domain assumption Stored bounds for a vertex are recomputed at the moment the vertex loses a neighbor, so they are valid when used.
The correctness of the lazy strategy relies on bounds being current each time they are compared. Algorithm 3 processes all neighbors of each deleted vertex, but this invariant is not stated or proved.
domain assumption The peeling order of the baseline algorithm yields the same eta-thresholds as the UCF-Index definition of Yang et al.
The paper adopts the peeling approach and does not prove equivalence to Definition 2, citing [22] for the index structure.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Effective Index Construction Algorithm for Optimal $(k,\eta)$-cores Computation." pith.science (2026). https://pith.science/paper/FYILY7VF

@misc{pith2026250420795,
  author       = {Pith},
  title        = {Pith review of: Effective Index Construction Algorithm for Optimal $(k,\eta)$-cores Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FYILY7VF}},
  note         = {Machine review of arXiv:2504.20795}
}

abstract

Computing $(k,\eta)$-cores from uncertain graphs is a fundamental problem in uncertain graph analysis. UCF-Index is the state-of-the-art resolution to support $(k,\eta)$-core queries, allowing the $(k,\eta)$-core for any combination of $k$ and $\eta$ to be computed in an optimal time. However, this index constructed by current algorithm is usually incorrect. During decomposition, the key is to obtain the $k$-probabilities of its neighbors when the vertex with minimum $k$-probability is deleted. Current method uses recursive floating-point division to update it, which can lead to serious errors. We propose a correct and efficient index construction algorithm to address this issue. Firstly, we propose tight bounds on the $k$-probabilities of the vertices that need to be updated, and the accurate $k$-probabilities are recalculated in an on-demand manner. Secondly, vertices partitioning and progressive refinement strategy is devised to search the vertex with the minimum $k$-probability, thereby reducing initialization overhead for each $k$ and avoiding unnecessary recalculations. Finally, extensive experiments demonstrate the efficiency and scalability of our approach.

Figures

Figures reproduced from arXiv: 2504.20795 by the authors.

**Figure 1.** The (k, η)-core of G for k = 2 and η = 0.107 vertex for each k. However, the UCF-Index constructed by current algorithm is usually incorrect. The k-probability of vertex u on G is the probability that u has a degree no less than k. During (k, η)-core decomposition, the key is to obtain the k-probability of its neighbors when a vertex is deleted. Yang et al. iteratively removed the vertex with minimum k-probabilit… view at source ↗

**Figure 2.** The (k, η)-core and η-tree2 of G 2.2 UCF-Index To support the online search for (k, η)-cores on large-scale uncertain graphs, Yang et al. proposed a forest-based index UCF-Index, which is composed of k η-trees. Before introducing the UCF-Index, we first provide the definition of the η-threshold. Definition 2 (η-threshold). Given an uncertain graph G and an integer k, the η-threshold of a vertex u, denoted by ηthre… view at source ↗

**Figure 3.** Lazy refreshing strategy • Step 5. We compute the k-probabilities for all vertices in X and select the vertex with minimum k-probability in X ∪ {pnxt} as pcrt. To further reduce unnecessary computation in Step 5, we directly compute the k-probability of the vertex u that satisfies LB(u) < k-prob(pnxt, G) in Step 4, and dynamically update pnxt to the vertex with the smaller k-probability between u and pnxt. As a re… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: The vertices partitioning framework partition of vertices in G is that P(k, i) = {u ∈ V |ηthresk+1(u) = ηi}. The vertices partitioning framework is shown in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: Time cost for UCF-Index construction [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 8.** Figure 8: Scalability of UCF-Index construction division calculation errors during the η-degree update process [8]. Yang et al. introduced a forest-based index structure called UCF-Index, which can support query of (k, η)-cores in an optimal time for any input parameters k and …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[1]

Managing uncertainty in social networks

Eytan Adar and Christopher Re. Managing uncertainty in social networks. IEEE Data Eng. Bull., 30(2):15–22, 2007

work page 2007
[2]

Managing and mining graph data, volume 40

Charu C Aggarwal, Haixun Wang, et al. Managing and mining graph data, volume 40. Springer, 2010

work page 2010
[3]

An o (m) al- gorithm for cores decomposition of networks

Vladimir Batagelj and Matjaz Zaversnik. An o (m) al- gorithm for cores decomposition of networks. arXiv preprint cs/0310049, 2003

arXiv 2003
[4]

Core decom- position of uncertain graphs

Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana V olkovich. Core decom- position of uncertain graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1316–1325, 2014

work page 2014
[5]

Cores matter? an analysis of graph decomposition ef- fects on influence maximization problems

Antonio Cali`o, Andrea Tagarelli, and Francesco Bonchi. Cores matter? an analysis of graph decomposition ef- fects on influence maximization problems. In Proceed- ings of the 12th ACM Conference on Web Science, pages 184–193, 2020

work page 2020
[6]

Efficient top-k vulnerable nodes detection in un- certain graphs

Dawei Cheng, Chen Chen, Xiaoyang Wang, and Sheng Xiang. Efficient top-k vulnerable nodes detection in un- certain graphs. IEEE Transactions on Knowledge and Data Engineering, 35(2):1460–1472, 2021

work page 2021
[7]

Fast maximal clique enu- meration on uncertain graphs: A pivot-based approach

Qiangqiang Dai, Rong-Hua Li, Meihao Liao, Hongzhi Chen, and Guoren Wang. Fast maximal clique enu- meration on uncertain graphs: A pivot-based approach. In Proceedings of the 2022 international conference on management of data, pages 2034–2047, 2022

work page 2022
[8]

Core decomposition on un- certain graphs revisited

Qiangqiang Dai, Rong-Hua Li, Guoren Wang, Rui Mao, Zhiwei Zhang, and Ye Yuan. Core decomposition on un- certain graphs revisited. IEEE Transactions on Knowl- edge and Data Engineering, 35(1):196–210, 2021

work page 2021

Show all 23 references

[9]

Efficient computation of probabilistic core decomposition at web-scale

Fatemeh Esfahani, Venkatesh Srinivasan, Alex Thomo, and Kui Wu. Efficient computation of probabilistic core decomposition at web-scale. In 22nd International Conference on Extending Database Technology, EDBT 2019, pages 325–336. OpenProceedings. org, 2019

2019
[10]

Distance-constraint reachability computation in uncer- tain graphs

Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. Distance-constraint reachability computation in uncer- tain graphs. Proceedings of the VLDB Endowment , 4(9):551–562, 2011

2011
[11]

SNAP Datasets: Stanford large network dataset collection

Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap. stanford.edu/data, June 2014

2014
[12]

Improved algorithms for maximal clique search in uncertain networks

Rong-Hua Li, Qiangqiang Dai, Guoren Wang, Zhong Ming, Lu Qin, and Jeffrey Xu Yu. Improved algorithms for maximal clique search in uncertain networks. In 2019 IEEE 35th International Conference on Data En- gineering (ICDE), pages 1178–1189. IEEE, 2019

2019
[13]

Efficient and accurate query evaluation on uncertain graphs via recursive stratified sampling

Rong-Hua Li, Jeffrey Xu Yu, Rui Mao, and Tan Jin. Efficient and accurate query evaluation on uncertain graphs via recursive stratified sampling. In 2014 IEEE 30th International Conference on Data Engineering , pages 892–903. IEEE, 2014

2014
[14]

Efficient influential community search in large uncertain graphs

Wensheng Luo, Xu Zhou, Kenli Li, Yunjun Gao, and Keqin Li. Efficient influential community search in large uncertain graphs. IEEE Transactions on Knowl- edge and Data Engineering, 35(4):3779–3793, 2021

2021
[15]

Tables of the incomplete beta function, 1968

HE Mckean. Tables of the incomplete beta function, 1968

1968
[16]

Reliable community search on uncertain graphs

Xiaoye Miao, Yue Liu, Lu Chen, Yunjun Gao, and Jianwei Yin. Reliable community search on uncertain graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 1166–1179. IEEE, 2022

2022
[17]

K-nearest neighbors in un- certain graphs

Michalis Potamias, Francesco Bonchi, Aristides Gio- nis, and George Kollios. K-nearest neighbors in un- certain graphs. Proceedings of the VLDB Endowment , 3(1-2):997–1008, 2010

2010
[18]

Maximal quasi- cliques mining in uncertain graphs

Lianpeng Qiao, Rong-Hua Li, Zhiwei Zhang, Ye Yuan, Guoren Wang, and Hongchao Qin. Maximal quasi- cliques mining in uncertain graphs. IEEE Transactions on Big Data, 9(1):37–50, 2021

2021
[19]

Efficient probabilistic truss indexing on un- certain graphs

Zitan Sun, Xin Huang, Jianliang Xu, and Francesco Bonchi. Efficient probabilistic truss indexing on un- certain graphs. In Proceedings of the Web Conference 2021, pages 354–366, 2021

2021
[20]

Containment of rumor spread by selecting immune nodes in social net- works

Hong Wu, Zhijian Zhang, Yabo Fang, Shaotang Zhang, Zuo Jiang, Jian Huang, and Ping Li. Containment of rumor spread by selecting immune nodes in social net- works. Math. Biosci. Eng, 18:2614–2631, 2021

2021
[21]

Truss community search in uncertain graphs

Bo Xing, Yuting Tan, Junfeng Zhou, and Ming Du. Truss community search in uncertain graphs. Knowl- edge and Information Systems , 66(12):7739–7773, 2024

2024
[22]

Index-based optimal algo- rithm for computing k-cores in large uncertain graphs

Bohua Yang, Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Rong-Hua Li. Index-based optimal algo- rithm for computing k-cores in large uncertain graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 64–75. IEEE, 2019

2019
[23]

Finding antagonistic communities in signed uncertain graphs

Qiqi Zhang, Lingyang Chu, Zijin Zhao, and Jian Pei. Finding antagonistic communities in signed uncertain graphs. IEEE Transactions on Knowledge and Data En- gineering, 2024

2024

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Managing uncertainty in social networks

Eytan Adar and Christopher Re. Managing uncertainty in social networks. IEEE Data Eng. Bull., 30(2):15–22, 2007

work page 2007

[2] [2]

Managing and mining graph data, volume 40

Charu C Aggarwal, Haixun Wang, et al. Managing and mining graph data, volume 40. Springer, 2010

work page 2010

[3] [3]

An o (m) al- gorithm for cores decomposition of networks

Vladimir Batagelj and Matjaz Zaversnik. An o (m) al- gorithm for cores decomposition of networks. arXiv preprint cs/0310049, 2003

arXiv 2003

[4] [4]

Core decom- position of uncertain graphs

Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana V olkovich. Core decom- position of uncertain graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1316–1325, 2014

work page 2014

[5] [5]

Cores matter? an analysis of graph decomposition ef- fects on influence maximization problems

Antonio Cali`o, Andrea Tagarelli, and Francesco Bonchi. Cores matter? an analysis of graph decomposition ef- fects on influence maximization problems. In Proceed- ings of the 12th ACM Conference on Web Science, pages 184–193, 2020

work page 2020

[6] [6]

Efficient top-k vulnerable nodes detection in un- certain graphs

Dawei Cheng, Chen Chen, Xiaoyang Wang, and Sheng Xiang. Efficient top-k vulnerable nodes detection in un- certain graphs. IEEE Transactions on Knowledge and Data Engineering, 35(2):1460–1472, 2021

work page 2021

[7] [7]

Fast maximal clique enu- meration on uncertain graphs: A pivot-based approach

Qiangqiang Dai, Rong-Hua Li, Meihao Liao, Hongzhi Chen, and Guoren Wang. Fast maximal clique enu- meration on uncertain graphs: A pivot-based approach. In Proceedings of the 2022 international conference on management of data, pages 2034–2047, 2022

work page 2022

[8] [8]

Core decomposition on un- certain graphs revisited

Qiangqiang Dai, Rong-Hua Li, Guoren Wang, Rui Mao, Zhiwei Zhang, and Ye Yuan. Core decomposition on un- certain graphs revisited. IEEE Transactions on Knowl- edge and Data Engineering, 35(1):196–210, 2021

work page 2021