Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs".
Jane: Here's the gist of the paper. A representative possible world (RPW) is a deterministic graph derived from an uncertain graph where a designated structural feature closely approximates its expected value in G <ref:2607.23085#pg2> Serving as a proxy for G, the RPW allows conventional deterministic algorithms to be directly executed on it for mining tasks targeting this feature, thereby avoiding computationally expensive enumeration or sampling on G <ref:2607.23085#pg2> Problem Formulation and Complexity The Common-Neighbor-Count-Based Representative Possible World (CRPW) problem seeks the possible world that best preserves the expected number of common neighbors between node pair, and it is proven to be NP-hard <ref:2607.23085#pg3> The decision version of this problem, determining whether there exists a possible world G such that the total discrepancy d G (G) ≤ T, is also NP-hard <ref:2607.23085#pg5> This NP-hardness is established via a reduction from the Monotone 1-in-3 3SAT problem <ref:2607.23085#pg6> The reduction involves constructing an uncertain graph G∗ with a threshold T such that the SAT instance is satisfiable if and only if (G∗,T) is a Yes-instance of the CRPW Decision Problem <ref:2607.23085#pg7> Algorithm Design and Optimization The authors developed a two-stage basic algorithm to construct a CRPW, which first rapidly initializes a possible world and then refines it iteratively <ref:2607.23085#pg8> The refinement stage is accelerated by replacing costly floating-point evaluation with an efficient integer counting strategy, as the refinement only requires determining whether a change is beneficial rather than computing its exact magnitude <ref:2607.23085#pg9> To address adaptive termination, a Beta-based adaptive termination method is designed to automatically stop the refinement once the desired quality of the possible world is reached <ref:2607.23085#pg10> Efficiency Gains through Integer Counting The core efficiency improvement in the refinement process comes from replacing costly floating-point arithmetic with cheap integer counting, which reduces running time by 38.6% on average compared to P+RSR <ref:2607.23085#pg5> This is achieved by rounding each edge discrepancy to the nearest integer, allowing the decision whether to change an edge state to be determined by cheap integer counting instead of costly floating-point arithmetic <ref:2607.23085#pg10> The complexity of the basic algorithm is analyzed as O(E + k/¯d), where k is the number of iterations and ¯d is the average degree of nodes in G <ref:2607.23085#pg10> Adaptive Termination Mechanism The Beta-based adaptive termination method controls refinement quality by measuring the state-changeable edge proportion (SEP) through edge sampling and modeling uncertainty with a Beta distribution <ref:2607.23085#pg10> The algorithm terminates when the confidence that SEP < τq reaches a user-specified threshold τc, quantified by Eq.
Tom: 18 <ref:2607.23085#pg10> This mechanism allows users to specify the desired quality directly, enabling adaptive termination without requiring a manually specified iteration count k <ref:2607.23085#pg10> Experimental Validation Extensive experiments on four real-world uncertain graphs demonstrate the effectiveness of the algorithms on diverse mining tasks, achieving the best performance among all compared methods especially on common-neighbor-related tasks <ref:2607.23085#pg2> The results show that P+IR and P+BIR stay within 0.12 of P+RSR, confirming that the integer-based refinement preserves representativeness while improving efficiency <ref:2607.23085#pg2> Furthermore, the methods show good results across different structural features, including common neighbor-derived features like trussness and clustering coefficient <ref:2607.23085#pg2> The overall performance confirms that preserving the number of common neighbors helps keep the features derived from it close to Expected <ref:2607.23085#pg2> The study successfully proposes the CRPW, proves its NP-hardness, and develops an efficient two-stage algorithm combining quick initialization with iterative refinement accelerated by integer counting and adaptive termination <ref:2607.23085#pg10> The methods are effective on real-world uncertain graphs, achieving superior performance on common-neighbor-related tasks compared to baselines <ref:2607.23085#pg2> The combination of efficiency gains from integer counting and adaptive quality control from the Beta distribution makes P+BIR a powerful tool for finding high-quality representative possible worlds <ref:2607.23085#pg10> References
1: Milton Abramowitz and Irene A Stegun.
Tom: Handbook of mathematical functions with formulas, graphs, and mathematical tables.
Paper summary: Jane: We've talked about the Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs, and what it means for finding these representative worlds in uncertain graphs. The authors tackled the NP hard nature of the problem by proposing a two stage basic algorithm <ref:2607.23085#pg3>.
Tom: They combined rapid initialization with iterative refinement, using integer counting to speed up the evaluation step, and adaptive termination based on a Beta distribution to control quality ten <ref:2607.23085#pg2>. It’s an approach that balances speed and accuracy rather than chasing a perfect solution exactly <ref:2607.23085#pg1>.
Lu: The main point is that they developed a method to construct a deterministic graph, the representative possible world, that closely approximates the expected value of structural features in the uncertain graph one <ref:2607.23085#pg1>. They proved that this specific problem is NP hard, which means finding an exact solution in polynomial time is impossible three <ref:2607.23085#pg1>.
Meng: So for those of us shipping models to production, what does this mean practically? It means we can use these representative worlds as a deterministic proxy graph for mining tasks targeting common neighbor counts twelve.
Jane: Exactly. They showed that this approach works on real world uncertain graphs, achieving results within zero point twelve of the P plus RSR baseline, which is a solid measure of performance <ref:2607.23085#pg2>.
Tom: So it’s not about finding the perfect possible world, it’s about finding a very good representative one quickly enough to be useful for mining tasks five <ref:2607.23085#pg2>. It's an engineering solution to an NP hard problem.
Lu: The future work would likely focus on scaling this refinement process further or maybe exploring how the Beta distribution modeling could be adapted for even more complex uncertainty structures ten <ref:2607.23085#pg2>.
Jane: It’s a practical tool for when you need to analyze uncertain networks where pairwise features matter, and the goal is to get an answer that's close enough without getting bogged down in the complexity of finding the absolute best one <ref:2607.23085#pg1>.
Conclusion: Tom: So we’re wrapping up on this one and looking at what these authors actually achieved with their Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs paper one.
Jane: It sounds like they took a really messy, uncertain graph and tried to figure out the single best deterministic version of it to use for mining tasks two.
Tom: Right. They proved that this problem is NP hard, which means finding that absolute perfect representative world is computationally impossible for large graphs three.
Lu: But their contribution is the algorithm they designed, a two stage method starting with a quick guess and then refining it iteratively to get close to what we want eight.
Meng: From an engineering standpoint, the big win here is how they speed up that refinement by using integer counting instead of slow floating point math ten.
Jane: So instead of doing heavy calculations every single time you check a graph change, you just round things to integers and count them fast ten.
Tom: Exactly. They showed this integer counting technique cuts the running time by about thirty-eight percent compared to other methods like P plus RSR five.
Lu: And they made it adaptive, using a Beta distribution to automatically stop refining once you hit the quality level you need, rather than just running for a set number of steps ten.
Jane: What does this actually mean for someone who is just building an AI model? It means you can use these fast, high-quality approximations to guide your mining tasks without getting bogged down in the worst complexity twenty-seven.
Tom: It means we get a very good answer quickly, which is what we need when dealing with huge networks where time matters ten.
Lu: The paper confirms that preserving those common neighbor counts actually helps keep other important features of the graph, like clustering coefficients, close to their expected values two.
Jane: So it’s a practical tool for getting usable results from complex uncertainty when you don't have infinite time or computing power one.
Tom: It sets a new benchmark for how we can tackle these kinds of representation problems in uncertain settings.
Hangzhou Dianzi University · Sichuan Normal University · Southeast University Department of Computer Science and Engineering, Zhejiang University Department of Computer Science
cs.DB
Submitted: 2026-07-25
Updated: 2026-11-12
Comments: Full version; 16 pages, 15 figures
Code: https://github.com/KGLab-HDU/CRPW
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Importance score: 92/100
The gist: A representative possible world (RPW) is a deterministic graph derived from an uncertain graph where a designated structural feature closely approximates its expected value in G <ref:2607.23085#pg2>…
Key concepts
- Representative Possible World (RPW)
- An RPW is a deterministic graph derived from an uncertain one that closely matches its expected structure. It serves as a fast, usable proxy for the original uncertain graph, allowing standard algorithms to run directly on it without complex sampling or enumeration.
- CRPW Problem
- This problem asks to find a possible world (a specific realization of the uncertain graph) that minimizes the discrepancy in common neighbor counts between pairs of nodes. Finding this optimal world is proven to be NP-hard, meaning no fast general solution exists.
- Integer Counting Efficiency
- The algorithm replaces computationally expensive floating-point calculations with simple integer counting. By rounding edge discrepancies to integers, the decision to change an edge state becomes a cheap integer comparison instead of a costly calculation, leading to significant speed improvements.
- Beta-based Adaptive Termination
- This mechanism controls the refinement process by measuring how much the structure changes during iteration using sampling and modeling uncertainty with a Beta distribution. It automatically stops the search when the confidence that structural changes are beneficial reaches a user-defined level, eliminating the need for manual iteration counts.
Terminology
Summary
A representative possible world (RPW) is a deterministic graph derived from an uncertain graph where a designated structural feature closely approximates its expected value in G <ref:2607. p. 0 cn,xiayingjie,xiangyu. cn
ABSTRACT
A representative possible world (RPW) is a deterministic graph
derived from an uncertain graph G where a designated structural
feature closely approximates its expected value in G. cn
ABSTRACT
A representative possible world (RPW) is a deterministic graph
derived from an uncertain graph G where a designated structural
feature closely approximates its expected value in G. Serving as a
proxy for G, the RPW allows conventional deterministic algorithms
to be directly executed on it for mining tasks targeting this feature,
thereby avoiding computationally expensive enumeration or sampling on G.Where the paper says it
Where the paper says it
Problem Formulation and Complexity
The Common-Neighbor-Count-Based Representative Possible World (CRPW) problem seeks the possible world that best preserves the expected number of common neighbors between node pair, and it is proven to be NP-hard <ref:2607.23085#pg3> The decision version of this problem, determining whether there exists a possible world G such that the total discrepancy d G (G) ≤ T, is also NP-hard <ref:2607. p. 3 Given an uncertain
graph G
∗ = (V∗
, E
∗
, P
∗
) and a threshold 𝑇 , the CRPW Decision
Problem determines whether there exists a possible world 𝐺
∗ ⊑ G∗
such that the total discrepancy 𝑑𝑖𝑠G∗ (𝐺
∗
) ≤ 𝑇 . Generally, the decision version of a problem is no harder than
its optimization version [21]: any polynomial-time algorithm for
the CRPW Problem also solves the CRPW Decision Problem, by
computing the total discrepancy of the returned possible world and
comparing it against 𝑇 . Since the construction takes
polynomial time and Monotone 1-in-3 3SAT is NP-complete, the
CRPW Decision Problem is NP-hard. As established earlier, the
NP-hardness of the CRPW Decision Problem implies that of the
CRPW Problem. The Monotone 1-in-3 3SAT instance is satisfiable if there exists a truth assignment such that every clause has
exactly one true variable. Our reduction maps a Monotone 1-in-3
3SAT instance to an uncertain graph G
∗ with a threshold 𝑇 , such
that the Monotone 1-in-3 3SAT instance is satisfiable if and only if
(G∗
,𝑇 ) is a Yes-instance of the CRPW Decision Problem.Where the paper says it
Where the paper says it
Where the paper says it
Algorithm Design and Optimization
The authors developed a two-stage basic algorithm to construct a CRPW, which first rapidly initializes a possible world and then refines it iteratively <ref:2607.23085#pg8> The refinement stage is accelerated by replacing costly floating-point evaluation with an efficient integer counting strategy, as the refinement only requires determining whether a change is beneficial rather than computing its exact magnitude <ref:2607. p. 0 To address it, we develop
a two-stage basic algorithm that quickly initializes a possible world
and then refines it iteratively. We next accelerate the refinement
by replacing its costly floating-point evaluation with an efficient
integer counting strategy, as the refinement only requires determining whether a change is beneficial, rather than computing its
exact magnitude. We next accelerate the refinement
by replacing its costly floating-point evaluation with an efficient
integer counting strategy, as the refinement only requires determining whether a change is beneficial, rather than computing its
exact magnitude. Moreover, we design a Beta-based adaptive termination method to automatically stop the refinement once the
desired quality of the possible world is reached, preventing over- or
under-execution.Where the paper says it
Where the paper says it
Efficiency Gains through Integer Counting
The core efficiency improvement in the refinement process comes from replacing costly floating-point arithmetic with cheap integer counting, which reduces running time by 38.6% on average compared to P+RSR <ref:2607. p. 0 arXiv:2607. 23085v1 [cs. To reduce
this cost, we observe that determining whether to change the state
of 𝑒𝑢𝑣 requires only the sign of 𝛿𝐺𝑖
(𝑒𝑢𝑣 ), not its exact value. We
therefore propose integer-based refinement that rounds each edge
discrepancy to the nearest integer, so that whether 𝛿𝐺𝑖
(𝑒𝑢𝑣 ) < 0 is
determined by cheap integer counting instead of costly floatingpoint arithmetic. We analyze the time complexity of the
integer-based refinement (Algorithm 3). Let ¯𝑑 denote the average
degree of nodes in G, and the neighbor set of each node is stored as
a hash set.Where the paper says it
Where the paper says it
Where the paper says it
Adaptive Termination Mechanism
The Beta-based adaptive termination method controls refinement quality by measuring the state-changeable edge proportion (SEP) through edge sampling and modeling uncertainty with a Beta distribution <ref:2607.23085#pg10> The algorithm terminates when the confidence that SEP < τq reaches a user-specified threshold τc, quantified by Eq. p. 9 Since the Beta distribution is well suited
to modeling an unknown proportion, we adopt it to model the
SEP estimation, through which the confidence that the SEP < 𝜏𝑞
can be quantified. The user further specifies a confidence threshold
𝜏𝑐 ∈ (0, 1), the minimum confidence they require, and the refinement terminates once the confidence that SEP < 𝜏𝑞 reaches 𝜏𝑐 . arXiv:2607. 23085v1 [cs. Since
the 𝑘 required for a given quality varies with graph structure, when
a user has a desired quality in mind, there is no reliable way to
know how large 𝑘 must be to reach it on the graph at hand, which
makes 𝑘 difficult to set appropriately. This motivates an adaptive
alternative: rather than forcing users to guess an iteration count, we
let them specify the desired quality directly, so that the refinement
terminates on its own once that quality is attained.Where the paper says it
Where the paper says it
Where the paper says it
Experimental Validation
Extensive experiments on four real-world uncertain graphs demonstrate the effectiveness of the algorithms on diverse mining tasks, achieving the best performance among all compared methods especially on common-neighbor-related tasks <ref:2607.23085#pg2> The results show that P+IR and P+BIR stay within 0. p. 1 Under the possible world model, an uncertain graph amounts to
a probability distribution over its possible worlds. Because graph
topology varies across possible worlds, structural features and mining task results also vary [18, 28, 33]. We
therefore propose integer-based refinement that rounds each edge
discrepancy to the nearest integer, so that whether 𝛿𝐺𝑖
(𝑒𝑢𝑣 ) < 0 is
determined by cheap integer counting instead of costly floatingpoint arithmetic. Experiments show that this approach incurs limited quality loss while providing substantial efficiency gains (§6). Under the possible world model, an uncertain graph amounts to
a probability distribution over its possible worlds. Because graph
topology varies across possible worlds, structural features and mining task results also vary [18, 28, 33]. 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
The study successfully proposes the CRPW, proves its NP-hardness, and develops an efficient two-stage algorithm combining quick initialization with iterative refinement accelerated by integer counting and adaptive termination <ref:2607.23085#pg10> The methods are effective on real-world uncertain graphs, achieving superior performance on common-neighbor-related tasks compared to baselines <ref:2607. p. 0 Extensive experiments on real-world uncertain
graphs demonstrate the effectiveness of our algorithms on diverse
mining tasks. Especially on common-neighbor-related tasks, we
achieve the best performance among all compared methods. We
therefore propose integer-based refinement that rounds each edge
discrepancy to the nearest integer, so that whether 𝛿𝐺𝑖
(𝑒𝑢𝑣 ) < 0 is
determined by cheap integer counting instead of costly floatingpoint arithmetic. Experiments show that this approach incurs limited quality loss while providing substantial efficiency gains (§6).Where the paper says it
Where the paper says it
References
[1] Milton Abramowitz and Irene A Stegun. 1948. Handbook of mathematical functions with formulas, graphs, and mathematical tables. p. 0 23085v1 [cs. DB] 25 Jul 2026
Common-Neighbor-Count-Based Representative Possible World
Finding on Uncertain Graphs
Chengjie Gu1
, Xiaoliang Xu1
, Yuxiang Wang1
, Kai Yao2
Mengzhao Wang1
, Tianxing Wu3
, Yingjie Xia1
, Xiangyu Ke4
1Hangzhou Dianzi University, China; 2 Sichuan normal university, China;
3 Southeast University, China; 4 Zhejiang University, China
chengjiegu,xxl,lsswyx,wmzssy@hdu.Where the paper says it
[2] Khawla Asmi and Abdallah Abarda. 2022. An efficient local algorithm for overlapping community detection in social networks. p. 1 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
[3] Saurabh Asthana, Oliver D King, Francis D Gibbons, and Frederick P Roth. 2004. Predicting protein complex membership using probabilistic network reliability. p. 0 In protein-protein interaction networks, an interaction between two proteins is established through noisy biological experiments and therefore holds only with a confidence derived from
experimental evidence [3, 13]. In social networks, the influence or
trust between two users is estimated from their interaction history,
yielding a probabilistic connection [5, 22].Where the paper says it
[4] Michael O Ball. 1986. Computational complexity of network reliability analysis: An overview. p. 3 𝐺 = arg min
𝐺⊑ G
𝑑𝑖𝑠G (𝐺) (6)
2. 2 Analysis of Problem Complexity
We establish that the CRPW Problem is NP-hard.Where the paper says it
[5] Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core decomposition of uncertain graphs. p. 7 Combining the two stages, the
overall time complexity of the basic algorithm is 𝑂
|E | + 𝑘
¯𝑑
. 4 INTEGER DISCREPANCIES FOR FAST
REFINEMENT
The core of Algorithm 2 is a per-iteration decision: whether changing the state of the selected edge 𝑒𝑢𝑣 reduces the total discrepancy,
i. Combining the two stages, the
overall time complexity of the basic algorithm is 𝑂
|E | + 𝑘
¯𝑑
. 4 INTEGER DISCREPANCIES FOR FAST
REFINEMENT
The core of Algorithm 2 is a per-iteration decision: whether changing the state of the selected edge 𝑒𝑢𝑣 reduces the total discrepancy,
i.Where the paper says it
Where the paper says it
[6] Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core decomposition of uncertain graphs.<ref:2607.23085#pg12>
[7] Russel E Caflisch. 1998. Monte carlo and quasi-monte carlo methods. p. 0 Extensive experiments on real-world uncertain
graphs demonstrate the effectiveness of our algorithms on diverse
mining tasks. Especially on common-neighbor-related tasks, we
achieve the best performance among all compared methods.Where the paper says it
[8] Xuelu Chen, Muhao Chen, Weijia Shi, Yizhou Sun, and Carlo Zaniolo. 2019. Embedding uncertain knowledge graphs. p. 0 In knowledge graphs,
relations are extracted by automated tools that often with errors, so
each extracted edge carries a confidence score [8, 31]. To faithfully
capture such uncertainty, uncertain graphs [27] are employed, in
which each edge is annotated with an existence probability varies
in [0, 1].Where the paper says it
[9] Code. 2026. Code.<ref:2607.23085#pg12>
[10] Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. p. 0 In protein-protein interaction networks, an interaction between two proteins is established through noisy biological experiments and therefore holds only with a confidence derived from
experimental evidence [3, 13]. In social networks, the influence or
trust between two users is estimated from their interaction history,
yielding a probabilistic connection [5, 22].Where the paper says it
[11] Qiangqiang Dai, Rong-Hua Li, Guoren Wang, Rui Mao, Zhiwei Zhang, and Ye Yuan. 2021. Core decomposition on uncertain graphs revisited. p. 7 Combining the two stages, the
overall time complexity of the basic algorithm is 𝑂
|E | + 𝑘
¯𝑑
. 4 INTEGER DISCREPANCIES FOR FAST
REFINEMENT
The core of Algorithm 2 is a per-iteration decision: whether changing the state of the selected edge 𝑒𝑢𝑣 reduces the total discrepancy,
i.Where the paper says it
[12] Simone Daminelli, Josephine Maria Thomas, Claudio Durán, and Carlo Vittorio Cannistraci. 2015. Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks. p. 1 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
[13] Lauri Eronen and Hannu Toivonen. 2012. Biomine: Predicting Links Between Biological Entities Using Network Models of Heterogeneous Databases.<ref:2607.23085#pg12>
[14] Bernard D Flury. 1990. Acceptance–rejection sampling made easy. p. 5 Algorithm 1 outlines the process of probability-based
initialization. For each edge 𝑒 ∈ E, we use the acceptance-rejection
method [14] to simulate its independent sampling process (as justified in Theorem 2), where 𝑒 is accepted with 𝑝(𝑒) and rejected with
1 − 𝑝(𝑒) (lines 3-7).Where the paper says it
[15] Kurt Hornik. 2024. Two Monotonicity Results for Beta Distribution Functions. p. 1 Under the possible world model, an uncertain graph amounts to
a probability distribution over its possible worlds. Because graph
topology varies across possible worlds, structural features and mining task results also vary [18, 28, 33].Where the paper says it
[16] Ruoming Jin, Lin Liu, and Charu C Aggarwal. 2011. Discovering highly reliable subgraphs in uncertain graphs. p. 8 However, users actually care about the quality
of the resulting possible world rather than the iteration count. Since
the 𝑘 required for a given quality varies with graph structure, when
a user has a desired quality in mind, there is no reliable way to
know how large 𝑘 must be to reach it on the graph at hand, which
makes 𝑘 difficult to set appropriately.Where the paper says it
[17] Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. 2011. Distance-constraint reachability computation in uncertain graphs. p. 1 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
[18] Amin Kaveh, Matteo Magnani, and Christian Rohner. 2021. Defining and measuring probabilistic ego networks. p. 0 In protein-protein interaction networks, an interaction between two proteins is established through noisy biological experiments and therefore holds only with a confidence derived from
experimental evidence [3, 13]. In social networks, the influence or
trust between two users is estimated from their interaction history,
yielding a probabilistic connection [5, 22].Where the paper says it
[19] Xiangyu Ke, Arijit Khan, and Leroy Lim Hong Quan. 2019. An in-depth comparison of st reliability algorithms over uncertain graphs. p. 0 Moreover, we design a Beta-based adaptive termination method to automatically stop the refinement once the
desired quality of the possible world is reached, preventing over- or
under-execution. Extensive experiments on real-world uncertain
graphs demonstrate the effectiveness of our algorithms on diverse
mining tasks.Where the paper says it
[20] Faiza Riaz Khawaja, Zuping Zhang, and Aman Ullah. 2025. Common-neighbor-based overlapping community detection in complex networks. p. 1 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
[21] Jon Kleinberg and Eva Tardos. 2006. Algorithm design. p. 2 • We present a two-stage basic algorithm that initializes a
possible world and iteratively refine it (§3), along with an
optimized algorithm that replaces costly floating-point evaluations with efficient integer counting (§4). • We design a Beta-based adaptive termination method that
assesses refinement quality through edge sampling and
terminates automatically once the user-desired quality is
attained with sufficient confidence (§5).Where the paper says it
[23] Peter M Kogge. 2016. Jaccard coefficients as a potential graph benchmark. p. 1 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
[24] Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. p. 2 exhaustive enumeration computationally infeasible for large uncertain graphs. We further prove that the CRPW problem is NP-hard
(§2.Where the paper says it
[25] Michael Ley. 2002. The DBLP computer science bibliography: Evolution, research issues, perspectives.<ref:2607.23085#pg12>
[26] Linyuan Lü, Ci-Hang Jin, and Tao Zhou. 2009. Similarity index based on local paths for link prediction of complex networks. p. 0 However, many mining tasks, such as link prediction, critically rely on the number of
common neighbors between two nodes, which is a pairwise feature. To bridge this gap, we study the Common-neighbor-count-based
Representative Possible World (CRPW) problem, extending RPWs
from preserving node-level statistics to preserving pairwise structural relationships.Where the paper says it
[27] Panos Parchas, Francesco Gullo, Dimitris Papadias, and Franceseco Bonchi. 2014. The pursuit of a good possible world: extracting representative instances of uncertain graphs. p. 2 However, determining an appropriate iteration budget
is inherently challenging. The exact number of iterations required
to achieve a good representative possible world is generally unknown and varies significantly across different uncertain graphs.Where the paper says it
[28] You Peng, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Lu Qin. 2018. Efficient probabilistic k-core computation on uncertain graphs. p. 0 In social networks, the influence or
trust between two users is estimated from their interaction history,
yielding a probabilistic connection [5, 22]. In knowledge graphs,
relations are extracted by automated tools that often with errors, so
each extracted edge carries a confidence score [8, 31].Where the paper says it
[29] Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. K-Nearest Neighbors in Uncertain Graphs. p. 0 9
1 v
2 v
3 v
4 v
5 v
0 v
1 v
2 v
0 v
1 v 5 v
0 v 1 v
3 v
0 v
(a) Possible World (b) (c) (d)
Gi
0 2 3 1 0 0 5 1 5 1 ( ) { , , } ,
i v v v v v v v v v v
Selected edge:
S e e e e = e
0 1 v v i e G
Figure 1: (a) An uncertain graph, (b-c) two of its possible
worlds preserving the triangle degree and the number of
common neighbors respectively, and (d) their total discrepancies from the expected values of three structural features. 1 INTRODUCTION
Graphs are widely used across scientific and industrial domains,
where nodes represent objects and edges reflect the connections
among them.Where the paper says it
[30] Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. K-nearest neighbors in uncertain graphs. p. 0 9
1 v
2 v
3 v
4 v
5 v
0 v
1 v
2 v
0 v
1 v 5 v
0 v 1 v
3 v
0 v
(a) Possible World (b) (c) (d)
Gi
0 2 3 1 0 0 5 1 5 1 ( ) { , , } ,
i v v v v v v v v v v
Selected edge:
S e e e e = e
0 1 v v i e G
Figure 1: (a) An uncertain graph, (b-c) two of its possible
worlds preserving the triangle degree and the number of
common neighbors respectively, and (d) their total discrepancies from the expected values of three structural features. 1 INTRODUCTION
Graphs are widely used across scientific and industrial domains,
where nodes represent objects and edges reflect the connections
among them.Where the paper says it
[31] Jay Pujara, Hui Miao, Lise Getoor, and William Cohen. 2013. Knowledge graph identification. p. 5 Next, we begin by establishing how the state change of 𝑒𝑢𝑣 affects the number of common neighbors between the endpoints of
adjacent edges (Lemma 1), which underlies the identification of
edge influence set. Given an uncertain graph G = (V, E, P), a possible
world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, an edge 𝑒𝑢𝑣 ∈ E, and a node 𝑤 ∈
𝐶G (𝑢, 𝑣), where 𝐶G (𝑢, 𝑣) denotes the set of common neighbors of 𝑢
and 𝑣 within the topological structure of G, ignoring edge probabilities.Where the paper says it
[32] Lianpeng Qiao, Rong-Hua Li, Zhiwei Zhang, Ye Yuan, Guoren Wang, and Hongchao Qin. 2021. Maximal quasi-cliques mining in uncertain graphs. p. 0 Moreover, we design a Beta-based adaptive termination method to automatically stop the refinement once the
desired quality of the possible world is reached, preventing over- or
under-execution. Extensive experiments on real-world uncertain
graphs demonstrate the effectiveness of our algorithms on diverse
mining tasks.Where the paper says it
[33] Arkaprava Saha, Ruben Brokkelkamp, Yllka Velaj, Arijit Khan, and Francesco Bonchi. 2021. Shortest paths and centrality in uncertain networks. p. 1 The representative possible world
was first studied in [27], which constructs one that preserves the
degree of each node. This degree-preserving representative possible world has proven effective for mining tasks that relevant
to node degrees, such as computing shortest-path distance and
betweenness centrality [27].Where the paper says it
[34] Thomas J Schaefer. 1978. The complexity of satisfiability problems. p. 3 2 Analysis of Problem Complexity
We establish that the CRPW Problem is NP-hard. Since NP-hardness
is defined over decision problems, we investigate the decision version of the CRPW Problem, which is formulated below.Where the paper says it
[35] Shaoying Song, Zhaonian Zou, and Kang Liu. 2016. Triangle-based representative possible worlds of uncertain graphs. p. 0 9
1 v
2 v
3 v
4 v
5 v
0 v
1 v
2 v
0 v
1 v 5 v
0 v 1 v
3 v
0 v
(a) Possible World (b) (c) (d)
Gi
0 2 3 1 0 0 5 1 5 1 ( ) { , , } ,
i v v v v v v v v v v
Selected edge:
S e e e e = e
0 1 v v i e G
Figure 1: (a) An uncertain graph, (b-c) two of its possible
worlds preserving the triangle degree and the number of
common neighbors respectively, and (d) their total discrepancies from the expected values of three structural features. 1 INTRODUCTION
Graphs are widely used across scientific and industrial domains,
where nodes represent objects and edges reflect the connections
among them.Where the paper says it
[36] Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ‘smallworld’networks. p. 0 In many real-world scenarios, such connections cannot be observed with certainty, but are instead estimated or predicted, and are thus inherently associated with an existence probability. In protein-protein interaction networks, an interaction between two proteins is established through noisy biological experiments and therefore holds only with a confidence derived from
experimental evidence [3, 13].Where the paper says it
[37] Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski. 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. p. 1 81 in the uncertain graph, while
𝑣5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible
world shows potential for many common neighbor-relevant mining
tasks, including: link prediction where candidate node pairs are
ranked by their numbers of common neighbors [12, 26, 39]; Jaccard
coefficient computation of two nodes that is directly derived from
their common neighbors [23]; overlapping community detection,
which groups nodes sharing more common neighbors into the same
community [2, 20, 37].Where the paper says it
[38] Bohua Yang, Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Rong-Hua Li. 2019. Index-based optimal algorithm for computing k-cores in large uncertain graphs. p. 2 exhaustive enumeration computationally infeasible for large uncertain graphs. We further prove that the CRPW problem is NP-hard
(§2.Where the paper says it
[39] Lin Yao, Luning Wang, Lv Pan, and Kai Yao. 2016. Link prediction based on common-neighbors for dynamic social network. p. 0 However, many mining tasks, such as link prediction, critically rely on the number of
common neighbors between two nodes, which is a pairwise feature. To bridge this gap, we study the Common-neighbor-count-based
Representative Possible World (CRPW) problem, extending RPWs
from preserving node-level statistics to preserving pairwise structural relationships.Where the paper says it
[40] Zhaonian Zou and Rong Zhu. 2017. Truss decomposition of uncertain graphs. p. 0 23085v1 [cs. DB] 25 Jul 2026
Common-Neighbor-Count-Based Representative Possible World
Finding on Uncertain Graphs
Chengjie Gu1
, Xiaoliang Xu1
, Yuxiang Wang1
, Kai Yao2
Mengzhao Wang1
, Tianxing Wu3
, Yingjie Xia1
, Xiangyu Ke4
1Hangzhou Dianzi University, China; 2 Sichuan normal university, China;
3 Southeast University, China; 4 Zhejiang University, China
chengjiegu,xxl,lsswyx,wmzssy@hdu.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Adaptive termination of refinement based on quality control allows for stopping
once the SEP falls below tauq
with a specified confidence threshold tauc, ensuring that "the confidence that SEP < tauq reaches tc" is met before stopping. -
Integer-based refinement replaces costly floating-point arithmetic in each iteration with cheap integer counting by determining whether to change an edge state based on the sign of the total discrepancy variation, which is determined by counting the sizes of three subsets of edges in the influence set.
-
The system can efficiently construct a representative possible world by using a two-stage algorithm: a probability-based initialization and iterative refinement, where refinement accelerates by replacing
costly floating-point evaluation with an efficient integer counting strategy.
Abstract
Given an uncertain graph G with probabilistic edges, a representative possible world (RPW) is a deterministic graph that closely preserves the expected value of a designated basic structural feature in G. As a proxy for G, the RPW allows us to directly obtain approximate expectations of the higher-order features related to this preserved basic feature, thereby avoiding expensive enumeration or sampling on G. Existing RPWs preserve per-node features such as degree and triangle degree but overlook common-neighbor counts between node pairs. As a result, they may poorly approximate the expected values of higher-order features that depend on these counts, e.g., Jaccard coefficient. Therefore, we study the ommon-neighbor-count-based epresentative ossible orld (CRPW) problem, extending RPWs from node features to node-pair features. Our problem seeks the possible world that best preserves the expected numbers of common neighbors between node pairs, and we prove that it is NP-hard. To address it, we develop a two-stage basic algorithm that quickly initializes a possible world and then refines it iteratively. We next accelerate the refinement with a counting-based estimation, as the refinement only requires determining whether an edge state change to the possible world is beneficial, rather than computing its exact magnitude. Furthermore, we design a Beta distribution-based adaptive termination method to automatically stop the refinement once the desired quality of the possible world is reached, preventing over- or under-execution. Extensive experiments on five real-world uncertain graphs demonstrate the effectiveness of our algorithms in preserving structural features.
Sources
Related papers
- Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
- EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
- Open Biomedical Knowledge Graphs at Scale: Construction, Federation, and AI Agent Access with Samyama Graph Database
- Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration
- GenTUS: Table Union Search via Constrained Generation of Semantic Table Identifiers
- SAGA: Synthetic Agentic Graph Architecture for Temporal Benchmark Generation