Computer Science – Social and Information Networks
Scientific paper
2011-10-03
Proceedings of IEEE International Conference on Data Mining (ICDM), pp. 1200-1205 (2011)
Computer Science
Social and Information Networks
A short version of this paper will be published for ICDM'11, December 2011
Scientific paper
Large graphs are difficult to represent, visualize, and understand. In this paper, we introduce "gate graph" - a new approach to perform graph simplification. A gate graph provides a simplified topological view of the original graph. Specifically, we construct a gate graph from a large graph so that for any "non-local" vertex pair (distance higher than some threshold) in the original graph, their shortest-path distance can be recovered by consecutive "local" walks through the gate vertices in the gate graph. We perform a theoretical investigation on the gate-vertex set discovery problem. We characterize its computational complexity and reveal the upper bound of minimum gate-vertex set using VC-dimension theory. We propose an efficient mining algorithm to discover a gate-vertex set with guaranteed logarithmic bound. We further present a fast technique for pruning redundant edges in a gate graph. The detailed experimental results using both real and synthetic graphs demonstrate the effectiveness and efficiency of our approach.
Huang Yan
Jin Ruoming
Ruan Ning
No associations
LandOfFree
Distance Preserving Graph Simplification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distance Preserving Graph Simplification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distance Preserving Graph Simplification will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-267213