Abstract—Being able to keep the graph scale small while capturing the properties of the original social graph, graph sampling provides an efficient, yet inexpensive solution for social network analysis. The challenge is how to create a small, but representative sample out of the massive social graph with millions or even billions of nodes. Several sampling algorithms have been proposed in previous studies, but there lacks fair evaluation and comparison among them. In this paper, we analyze the state-ofart graph sampling algorithms and evaluate their performance on some widely recognized graph properties on directed graphs using large-scale social network datasets. We evaluate not only the commonly used node degree distribution, but also clustering coefficient, which quantifies how well connected are the neighbors of a node in a graph. Through the comparison we have found that none of the algorithms is able to obtain satisfied sampling results in both of these properties, and the performance of each algorithm differs much in different kinds of datasets. I.
Description
Understanding Graph Sampling Algorithms for Social Network Analysis
%0 Generic
%1 Wang_understandinggraph
%A Wang, Tianyi
%A Chen, Yang
%A Zhang, Zengbin
%A Xu, Tianyin
%A Jin, Long
%A Hui, Pan
%A Deng, Beixing
%A Li, Xing
%D 2009
%K graph
%T Understanding Graph Sampling Algorithms for Social Network Analysis
%U http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.204.7138
%X Abstract—Being able to keep the graph scale small while capturing the properties of the original social graph, graph sampling provides an efficient, yet inexpensive solution for social network analysis. The challenge is how to create a small, but representative sample out of the massive social graph with millions or even billions of nodes. Several sampling algorithms have been proposed in previous studies, but there lacks fair evaluation and comparison among them. In this paper, we analyze the state-ofart graph sampling algorithms and evaluate their performance on some widely recognized graph properties on directed graphs using large-scale social network datasets. We evaluate not only the commonly used node degree distribution, but also clustering coefficient, which quantifies how well connected are the neighbors of a node in a graph. Through the comparison we have found that none of the algorithms is able to obtain satisfied sampling results in both of these properties, and the performance of each algorithm differs much in different kinds of datasets. I.
@misc{Wang_understandinggraph,
abstract = {Abstract—Being able to keep the graph scale small while capturing the properties of the original social graph, graph sampling provides an efficient, yet inexpensive solution for social network analysis. The challenge is how to create a small, but representative sample out of the massive social graph with millions or even billions of nodes. Several sampling algorithms have been proposed in previous studies, but there lacks fair evaluation and comparison among them. In this paper, we analyze the state-ofart graph sampling algorithms and evaluate their performance on some widely recognized graph properties on directed graphs using large-scale social network datasets. We evaluate not only the commonly used node degree distribution, but also clustering coefficient, which quantifies how well connected are the neighbors of a node in a graph. Through the comparison we have found that none of the algorithms is able to obtain satisfied sampling results in both of these properties, and the performance of each algorithm differs much in different kinds of datasets. I.},
added-at = {2015-04-16T16:56:53.000+0200},
author = {Wang, Tianyi and Chen, Yang and Zhang, Zengbin and Xu, Tianyin and Jin, Long and Hui, Pan and Deng, Beixing and Li, Xing},
biburl = {https://www.bibsonomy.org/bibtex/23f1c13ded51cb601a06e99b42a68e4c0/shabbychef},
description = {Understanding Graph Sampling Algorithms for Social Network Analysis},
interhash = {ac5dbcea06a6af78da78c9b6e749a060},
intrahash = {3f1c13ded51cb601a06e99b42a68e4c0},
keywords = {graph},
timestamp = {2015-04-16T16:56:53.000+0200},
title = {Understanding Graph Sampling Algorithms for Social Network Analysis},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.204.7138},
year = 2009
}