Choosing a subgraph that can concisely represent a large real-world graph is useful in many scenarios. The usual strategy employed is to sample nodes so that the induced subgraph matches the original graph’s degree distribution, clustering coecient, etc., but no attempt is made to preserve ne-grained relationships between nodes, which are vital for applications like clustering, classication, and ranking. In this work, we model such relationships via the notion of Personalized PageRank Value (PPV). We show that induced subgraphs output by current sampling methods do not preserve PPVs, and propose algorithms for creating PPV-preserving subgraphs on any given subset of graph nodes. Experiments on three large real-world graphs show that the subgraphs created by our method improve upon induced subgraphs in terms of preserving PPVs, clustering accuracy, and maintaining basic graph properties.
['Andrea Vattani', 'Deepayan Chakrabarti', 'Maxim Gurevich']
Preserving Personalized Pagerank in Subgraphs