Core Decomposition on Uncertain Graphs Revisited

Core decomposition on uncertain graphs is a fundamental problem in graph analysis. Given an uncertain graph <inline-formula><tex-math notation="LaTeX">$\mathcal {G}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">G</mml:mi></mml:math><inline-graphic xlink:href="li-ieq1-3088504.gif"/></alternatives></inline-formula>, the core decomposition problem is to determine all <inline-formula><tex-math notation="LaTeX">$(k,\eta)\text{-cores}$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>η</mml:mi><mml:mo>)</mml:mo><mml:mtext>-cores</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq2-3088504.gif"/></alternatives></inline-formula> in <inline-formula><tex-math notation="LaTeX">$\mathcal {G}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">G</mml:mi></mml:math><inline-graphic xlink:href="li-ieq3-3088504.gif"/></alternatives></inline-formula>, where a <inline-formula><tex-math notation="LaTeX">$(k,\eta)\text{-core}$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>η</mml:mi><mml:mo>)</mml:mo><mml:mtext>-core</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq4-3088504.gif"/></alternatives></inline-formula> is a maximal subgraph of <inline-formula><tex-math notation="LaTeX">$\mathcal {G}$</tex-math><alternatives><mml:math><mml:mi mathvariant="script">G</mml:mi></mml:math><inline-graphic xlink:href="li-ieq5-3088504.gif"/></alternatives></inline-formula> such that each node has an <inline-formula><tex-math notation="LaTeX">$\eta \text{-}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mtext>-</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq6-3088504.gif"/></alternatives></inline-formula><inline-formula><tex-math notation="LaTeX">${\mathsf {degree}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">degree</mml:mi></mml:math><inline-graphic xlink:href="li-ieq7-3088504.gif"/></alternatives></inline-formula> no less than <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="li-ieq8-3088504.gif"/></alternatives></inline-formula> within the subgraph. The <inline-formula><tex-math notation="LaTeX">$\eta \text{-}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mtext>-</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq9-3088504.gif"/></alternatives></inline-formula><inline-formula><tex-math notation="LaTeX">${\mathsf {degree}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">degree</mml:mi></mml:math><inline-graphic xlink:href="li-ieq10-3088504.gif"/></alternatives></inline-formula> of a node <inline-formula><tex-math notation="LaTeX">$v$</tex-math><alternatives><mml:math><mml:mi>v</mml:mi></mml:math><inline-graphic xlink:href="li-ieq11-3088504.gif"/></alternatives></inline-formula> is defined as the maximum integer <inline-formula><tex-math notation="LaTeX">$r$</tex-math><alternatives><mml:math><mml:mi>r</mml:mi></mml:math><inline-graphic xlink:href="li-ieq12-3088504.gif"/></alternatives></inline-formula> such that the probability that <inline-formula><tex-math notation="LaTeX">$v$</tex-math><alternatives><mml:math><mml:mi>v</mml:mi></mml:math><inline-graphic xlink:href="li-ieq13-3088504.gif"/></alternatives></inline-formula> has a degree no less than <inline-formula><tex-math notation="LaTeX">$r$</tex-math><alternatives><mml:math><mml:mi>r</mml:mi></mml:math><inline-graphic xlink:href="li-ieq14-3088504.gif"/></alternatives></inline-formula> is larger than or equal to the threshold <inline-formula><tex-math notation="LaTeX">$\eta \in [0,1]$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo>]</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq15-3088504.gif"/></alternatives></inline-formula>. The state-of-the-art algorithm for solving this problem is based on a peeling technique which iteratively removes the nodes with the smallest <inline-formula><tex-math notation="LaTeX">$\eta \text{-}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mtext>-</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq16-3088504.gif"/></alternatives></inline-formula><inline-formula><tex-math notation="LaTeX">${\mathsf {degrees}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">degrees</mml:mi></mml:math><inline-graphic xlink:href="li-ieq17-3088504.gif"/></alternatives></inline-formula> and also dynamically updates their neighbors’ <inline-formula><tex-math notation="LaTeX">$\eta \text{-}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mtext>-</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq18-3088504.gif"/></alternatives></inline-formula><inline-formula><tex-math notation="LaTeX">${\mathsf {degrees}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">degrees</mml:mi></mml:math><inline-graphic xlink:href="li-ieq19-3088504.gif"/></alternatives></inline-formula>. Unfortunately, we find that such a peeling algorithm with the dynamical <inline-formula><tex-math notation="LaTeX">$\eta \text{-}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mtext>-</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq20-3088504.gif"/></alternatives></inline-formula><inline-formula><tex-math notation="LaTeX">${\mathsf {degree}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">degree</mml:mi></mml:math><inline-graphic xlink:href="li-ieq21-3088504.gif"/></alternatives></inline-formula> updating technique is incorrect due to the inaccuracy of the recursive floating-point number division operations involved in the dynamical updating procedure. To correctly compute the <inline-formula><tex-math notation="LaTeX">$(k,\eta)\text{-cores}$</tex-math><alternatives><mml:math><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>,</mml:mo><mml:mi>η</mml:mi><mml:mo>)</mml:mo><mml:mtext>-cores</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq22-3088504.gif"/></alternatives></inline-formula>, we first propose a bottom-up algorithm based on an on-demand <inline-formula><tex-math notation="LaTeX">$\eta \text{-}$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>η</mml:mi><mml:mtext>-</mml:mtext></mml:mrow></mml:math><inline-graphic xlink:href="li-ieq23-3088504.gif"/></alternatives></inline-formula><inline-formula><tex-math notation="LaTeX">${\mathsf {degree}}$</tex-math><alternatives><mml:math><mml:mi mathvariant="sans-serif">degree</mml:mi></mml:math><inline-graphic xlink:href="li-ieq24-3088504.gif"/></alternatives></inline-formula> computational strategy. To further improve the efficiency, we also develop a more efficient top-down algorithm with several nontrivial optimization techniques. Both of our algorithms do not involve any floating-point number division operations, thus the correctness can be guaranteed. In addition, we also develop the parallel variants of all the proposed algorithms. Finally, we conduct extensive experiments to evaluate the proposed algorithms using five large real-life datasets. The results show that our algorithms are at least three orders of magnitude faster than the existing exact algorithms on large uncertain graphs. The results also demonstrate the high scalability and parallel performance of the proposed algorithms.