.png){kind=icon}
.png){kind=icon}
Return
A Vertex Partitioning Algorithm for Large-Scale Uncertain Graphs
.png){kind=icon}
PRE
AI
DOI：10.1002/cpe.70580.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
With the exponential growth of graph-structured data, single-machine efficient analysis has become increasingly impractical, making high-performance distributed graph computing systems indispensable. The efficacy of these systems hinges critically on high-quality graph partitioning. The edges of many graphs stemmed from real applications are uncertain, but many existing graph partitioning algorithms are only for deterministic graphs without considering uncertainty. This paper presents a novel partitioning algorithm, PAUG (Partitioning Algorithm for Uncertain Graphs), tailored for uncertain graphs. First, it formalizes the partitioning problem as an optimization task to minimize the cut-edge ratio while balancing load. Second, it introduces probabilistic similarity to quantify vertex relationships under uncertainty. Finally, it details the PAUG algorithm which consists of initial partition phase and score-function-guided refinement strategy. Experimental results shows that PAUG achieves an average 23.2% reduction in cut-edge ratio and a 26.2% improvement in load balance over state-of-the-art algorithms.
Keywords:
distributed graph computing
graph partitioning
probabilistic similarity
uncertain graph
Journal
C
IF:
1.5
Papers:
473
Citations:
0