Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs

arXiv:2607.23085 · cs.DB · Submitted 2026-07-25 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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. p. 3

Where the paper says it

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 𝑇 .

23085#pg5> This NP-hardness is established via a reduction from the Monotone 1-in-3 3SAT problem <ref:2607. p. 4
Where the paper says it

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.

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. p. 3
Where the paper says it

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.

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. p. 0

Where the paper says it

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.

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. p. 0
Where the paper says it

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.

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. p. 0

Where the paper says it

arXiv:2607. 23085v1 [cs.

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. p. 7
Where the paper says it

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.

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. p. 8
Where the paper says it

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.

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. p. 9

Where the paper says it

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 𝜏𝑐 .

18 <ref:2607. p. 0
Where the paper says it

arXiv:2607. 23085v1 [cs.

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. p. 8
Where the paper says it

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.

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. p. 1

Where the paper says it

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].

12 of P+RSR, confirming that the integer-based refinement preserves representativeness while improving efficiency <ref:2607. p. 7
Where the paper says it

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

23085#pg2> Furthermore, the methods show good results across different structural features, including common neighbor-derived features like trussness and clustering coefficient <ref:2607. p. 1
Where the paper says it

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].

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. p. 1
Where the paper says it

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].

23085#pg2>

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

Where the paper says it

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.

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. p. 7
Where the paper says it

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

23085#pg10>

References

[1] Milton Abramowitz and Irene A Stegun. 1948. Handbook of mathematical functions with formulas, graphs, and mathematical tables. p. 0

Where the paper says it

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.

Vol. 55.<ref:2607.23085#pg12>

[2] Khawla Asmi and Abdallah Abarda. 2022. An efficient local algorithm for overlapping community detection in social networks. p. 1

Where the paper says it

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].

<ref:2607.23085#pg12>

[3] Saurabh Asthana, Oliver D King, Francis D Gibbons, and Frederick P Roth. 2004. Predicting protein complex membership using probabilistic network reliability. p. 0

Where the paper says it

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].

<ref:2607.23085#pg12>

[4] Michael O Ball. 1986. Computational complexity of network reliability analysis: An overview. p. 3

Where the paper says it

𝐺 = arg min 𝐺⊑ G 𝑑𝑖𝑠G (𝐺) (6) 2. 2 Analysis of Problem Complexity We establish that the CRPW Problem is NP-hard.

<ref:2607.23085#pg12>

[5] Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core decomposition of uncertain graphs. p. 7

Where the paper says it

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.

p. 7
Where the paper says it

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.

<ref:2607.23085#pg12>

[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

Where the paper says it

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.

<ref:2607.23085#pg12>

[8] Xuelu Chen, Muhao Chen, Weijia Shi, Yizhou Sun, and Carlo Zaniolo. 2019. Embedding uncertain knowledge graphs. p. 0

Where the paper says it

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].

<ref:2607.23085#pg12>

[9] Code. 2026. Code.<ref:2607.23085#pg12>

[10] Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. p. 0

Where the paper says it

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].

<ref:2607.23085#pg12>

[11] Qiangqiang Dai, Rong-Hua Li, Guoren Wang, Rui Mao, Zhiwei Zhang, and Ye Yuan. 2021. Core decomposition on uncertain graphs revisited. p. 7

Where the paper says it

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.

<ref:2607.23085#pg12>

[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

Where the paper says it

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].

<ref:2607.23085#pg12>

[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

Where the paper says it

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

<ref:2607.23085#pg12>

[15] Kurt Hornik. 2024. Two Monotonicity Results for Beta Distribution Functions. p. 1

Where the paper says it

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].

<ref:2607.23085#pg12>

[16] Ruoming Jin, Lin Liu, and Charu C Aggarwal. 2011. Discovering highly reliable subgraphs in uncertain graphs. p. 8

Where the paper says it

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.

<ref:2607.23085#pg12>

[17] Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. 2011. Distance-constraint reachability computation in uncertain graphs. p. 1

Where the paper says it

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].

<ref:2607.23085#pg12>

[18] Amin Kaveh, Matteo Magnani, and Christian Rohner. 2021. Defining and measuring probabilistic ego networks. p. 0

Where the paper says it

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].

<ref:2607.23085#pg12>

[19] Xiangyu Ke, Arijit Khan, and Leroy Lim Hong Quan. 2019. An in-depth comparison of st reliability algorithms over uncertain graphs. p. 0

Where the paper says it

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.

<ref:2607.23085#pg12>

[20] Faiza Riaz Khawaja, Zuping Zhang, and Aman Ullah. 2025. Common-neighbor-based overlapping community detection in complex networks. p. 1

Where the paper says it

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].

<ref:2607.23085#pg12>

[21] Jon Kleinberg and Eva Tardos. 2006. Algorithm design. p. 2

Where the paper says it

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

<ref:2607.23085#pg12>

[23] Peter M Kogge. 2016. Jaccard coefficients as a potential graph benchmark. p. 1

Where the paper says it

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].

<ref:2607.23085#pg12>

[24] Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. p. 2

Where the paper says it

exhaustive enumeration computationally infeasible for large uncertain graphs. We further prove that the CRPW problem is NP-hard (§2.

<ref:2607.23085#pg12>

[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

Where the paper says it

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.

<ref:2607.23085#pg12>

[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

Where the paper says it

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.

<ref:2607.23085#pg12>

[28] You Peng, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Lu Qin. 2018. Efficient probabilistic k-core computation on uncertain graphs. p. 0

Where the paper says it

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].

<ref:2607.23085#pg12>

[29] Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. K-Nearest Neighbors in Uncertain Graphs. p. 0

Where the paper says it

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.

<ref:2607.23085#pg12>

[30] Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. K-nearest neighbors in uncertain graphs. p. 0

Where the paper says it

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.

<ref:2607.23085#pg12>

[31] Jay Pujara, Hui Miao, Lise Getoor, and William Cohen. 2013. Knowledge graph identification. p. 5

Where the paper says it

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.

<ref:2607.23085#pg12>

[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

Where the paper says it

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.

<ref:2607.23085#pg12>

[33] Arkaprava Saha, Ruben Brokkelkamp, Yllka Velaj, Arijit Khan, and Francesco Bonchi. 2021. Shortest paths and centrality in uncertain networks. p. 1

Where the paper says it

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].

<ref:2607.23085#pg12>

[34] Thomas J Schaefer. 1978. The complexity of satisfiability problems. p. 3

Where the paper says it

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.

<ref:2607.23085#pg12>

[35] Shaoying Song, Zhaonian Zou, and Kang Liu. 2016. Triangle-based representative possible worlds of uncertain graphs. p. 0

Where the paper says it

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.

<ref:2607.23085#pg12>

[36] Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ‘smallworld’networks. p. 0

Where the paper says it

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].

<ref:2607.23085#pg12>

[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

Where the paper says it

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].

<ref:2607.23085#pg12>

[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

Where the paper says it

exhaustive enumeration computationally infeasible for large uncertain graphs. We further prove that the CRPW problem is NP-hard (§2.

<ref:2607.23085#pg12>

[39] Lin Yao, Luning Wang, Lv Pan, and Kai Yao. 2016. Link prediction based on common-neighbors for dynamic social network. p. 0

Where the paper says it

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.

<ref:2607.23085#pg12>

[40] Zhaonian Zou and Rong Zhu. 2017. Truss decomposition of uncertain graphs. p. 0

Where the paper says it

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.

<ref:2607.

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

  1. 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.

  2. 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.

  3. 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