Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs
Chengjie Gu, Xiaoliang Xu, Yuxiang Wang, Kai Yao, Mengzhao Wang, Tianxing Wu, Yingjie Xia, Xiangyu Ke
原文摘要
Given an uncertain graph $\mathcal{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 $\mathcal{G}$. As a proxy for $\mathcal{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 $\mathcal{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 \underline{C}ommon-neighbor-count-based \underline{R}epresentative \underline{P}ossible \underline{W}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.
cs.DB