A two-stage basic algorithm that quickly initializes a possible world and then refines it iteratively, and it is proved that the problem seeks the possible world that best preserves the expected numbers of common neighbors between node pair, and it is proved that is NP-hard.
Abstract
A representative possible world (RPW) is a deterministic graph derived from an uncertain graph $\mathcal{G}$ where a designated structural feature closely approximates its expected value in $\mathcal{G}$. Serving as a proxy for $\mathcal{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 $\mathcal{G}$. Existing studies on RPWs primarily focus on individual node features, e.g., degree or triangle degree. 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 \underline{C}ommon-neighbor-count-based \underline{R}epresentative \underline{P}ossible \underline{W}orld (CRPW) problem, extending RPWs from preserving node-level statistics to preserving pairwise structural relationships. The problem seeks the possible world that best preserves the expected numbers of common neighbors between node pair, and we prove that 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 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. 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.
The planted subgraph detection problem asks whether a random graph contains a hidden structured subgraph. In the classical formulation, the entire adjacency matrix is observed and one distinguishes between an Erd\H{o}s--R\'enyi random graph and one obtained by planting a copy of a prescribed graph inside an Erd\H{o}s--R\'enyi random graph. The statistical and computational limits of this problem under full observation are now well understood, even for arbitrary planted subgraphs. In this paper, we investigate an information-limited version of the problem in which the planted structure is an arbitrary sequence of graphs $\Gamma=(\Gamma_n)_{n\geq1}$, where $\Gamma_n$ is embedded in an ambient graph on $n$ vertices, but the observer does not have access to the full adjacency matrix. Instead, information is acquired through a limited number of non-adaptive edge queries. We study the minimum query complexity required for reliable detection. We derive general information-theoretic lower bounds and complementary algorithmic upper bounds on the query complexity as functions of the query budget and structural properties of the planted graph. The proposed algorithms exploit three distinct structural mechanisms: dense local motifs, high-degree vertices, and global edge density. We establish matching bounds, up to polylogarithmic factors, for several broad families of planted graphs, including clique-like, bounded-cover, and hub-dominated graph classes. Our framework substantially generalizes existing query-complexity results for planted clique and planted dense subgraph models, providing a unified treatment of arbitrary planted subgraphs under restricted graph access.
This work shows that one can maintain an O(\alpha)-approximate MDS with update time for dynamic graphs whose {\em arboricity} is bounded by $\alpha$ throughout the update sequence, which replaces the dependence on $\Delta$ in prior update bounds with $\alpha$, while also improving the approximation guarantee for bounded-arboricity graphs.
A. Bukov, Shay Solomon· Embedded Systems and Applica...· 0 citations
This work proposes an algorithm that approximates the number of spanning trees in $\widetilde O(m+n^{7/4}\eps^{-3/2})$ time on a graph with $n$ vertices and $m$ edges and is based on the novel concept of $\ell_1$-regularized resistance.
A randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions is given, which follows from a simple stability principle for partially dynamic graphs.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
It is proved that any dataset admits a $\gamma$-almost navigable graph with just $O\left(\frac{n}{1-\gamma}\right)$ edges, linear in the dataset size, and a randomized algorithm for constructing such a graph in near-linear time is presented.
Pratyush Avi, Christopher Musco· arXiv.org· 0 citations
We study exact single-source shortest paths when the output is only the materialized labeled distance vector ($\mathrm{DIST}$), rather than a distance order. In the full deterministic comparison-addition model, the minimum worst-case number of additions on every fixed directed topology is exactly the maximum number $\rho_{\mathrm{fwd}}$ of forward nonsource endpoint classes over rooted vertex orders; the lower bound permits adaptive control, literals, and arbitrary mixed sums. This arithmetic law aligns with the comparison optimum on DAGs, where the full resource region is an exact rectangle. Cycles destroy that alignment: a two-spoke shared-hub graph has coordinatewise optima $(4,2)$ but requires five comparisons at the two-addition budget. Its $k$-spoke extension forces $k\log_2 k+O(k)$ comparisons at the addition optimum and has an entropy-tight deterministic tradeoff $C_{k+r}^*(H_k)=\Theta(k+\Lambda_{k,r})$, where $\Lambda_{k,r}=\log_2(k!/[r!(r+1)^{k-r}])$, with leading constant one when $\Lambda_{k,r}/k\to\infty$. Because the two coordinatewise minima need not belong to one program, these conflicts lead to the same-program benchmark $\operatorname{OPT}_{\mathrm{DIST}}=\inf_A\sup_w(C_A(w)+P_A(w))$. An exact transcript-cone game yields one uniform interpreter whose charged addition-comparison cost equals $\operatorname{OPT}_{\mathrm{DIST}}$ on every topology; its optimal actions are synthesizable in polynomial space but may require exponential time. Finally, an active-core reduction and the current deterministic directed-SSSP bound give an efficient uniform $O\!\bigl(\operatorname{OPT}_{\mathrm{DIST}}\sqrt{\log(2+\operatorname{OPT}_{\mathrm{DIST}})\log\log(4+\operatorname{OPT}_{\mathrm{DIST}})}\bigr)$ charged-operation bound. Thus optimal numerical policies exist uniformly, while efficient constant-competitive navigation remains open.
Bin Cai· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
