Graphs appear in several settings, like social networks, recommendation systems, and numerous more. A deep, recurring question is "How do real graphs look like?" That is, how can we separate real graphs from synthetic or real graphs with masked portions? The main contribution of this paper is ShatterPlots, a simple and powerful algorithm to tease out patterns of real graphs that help us spot fake/masked graphs. The idea is to shatter a graph, by deleting edges, force it to reach a critical ("Shattering") point, and study the properties at that point. One of our most discriminative patterns is the "NodeShatteringRatio": that can almost perfectly separate the real from the synthetic graphs of our extensive collection. Additional contributions of this paper are (a) the careful, scalable design of the algorithm that needs only O(E) time, (b) extensive experiments on a large collection of graphs (19 in total), with up to hundred of thousand of nodes and million edges; and (c) a wealth of observations and patterns, which show how to distinguish synthetic or masked graphs from real ones.

28 pages

*ICMC - USP São Carlos, Brazil
**Yahoo! Research

This page maintained by [email protected]