We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Graph repairing under neighborhood constraints.
- Authors
Song, Shaoxu; Liu, Boge; Cheng, Hong; Yu, Jeffrey; Chen, Lei
- Abstract
A broad class of data, ranging from similarity networks, workflow networks to protein networks, can be modeled as graphs with data values as vertex labels. Both vertex labels and neighbors could be dirty for various reasons such as typos or erroneous reporting of results in scientific experiments. Neighborhood constraints, specifying label pairs that are allowed to appear on adjacent vertices in the graph, are employed to detect and repair erroneous vertex labels and neighbors. In this paper, we study the problem of repairing vertex labels and neighbors to make graphs satisfy neighborhood constraints. Unfortunately, the problem is generally hard, which motivates us to devise approximation methods for repairing and identify interesting special cases (star and clique constraints) that can be efficiently solved. First, we propose several label repairing approximation algorithms including greedy heuristics, contraction method and an approach combining both. The performances of algorithms are also analyzed for the special case. Moreover, we devise a cubic-time constant-factor graph repairing algorithm with both label and neighbor repairs (given degree-bounded instance graphs). Our extensive experimental evaluation on real data demonstrates the effectiveness of eliminating frauds in several types of application networks.
- Subjects
GRAPHIC methods; WORKFLOW; ALGORITHMS
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2017, Vol 26, Issue 5, p611
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-017-0466-5