Supervised sampling for networked data

Publisher:
Elsevier
Publication Type:
Journal Article
Citation:
Signal Processing, 2016, 124 pp. 93 - 102
Issue Date:
2016-01-01
Full metadata record
Files in This Item:
Filename Description Size
Supervised.pdfPublished Version703.79 kB
Adobe PDF
© 2015 Elsevier B.V. Traditional graph sampling methods reduce the size of a large network via uniform sampling of nodes from the original network. The sampled network can be used to estimate the topological properties of the original network. However, in some application domains (e.g., disease surveillance), the goal of sampling is also to help identify a specified category of nodes (e.g., affected individuals) in a large network. This work therefore aims to, given a large information network, sample a subgraph under a specific goal of acquiring as many nodes with a particular category as possible. We refer to this problem as supervised sampling, where we sample a large network for a specific category of nodes. To this end, we model a network as a Markov chain and derive supervised random walks to learn stationary distributions of the sampled network. The learned stationary distribution can help identify the best node to be sampled in the next iteration. The iterative sampling process ensures that with new sampled nodes being acquired, supervised sampling can be strengthened in turn. Experiments on synthetic as well as real-world networks show that our supervised sampling algorithm outperforms existing methods in obtaining target nodes in the sampled networks.
Please use this identifier to cite or link to this item: