图 书 馆
图形采样和保持：大图形分析的框架Graph Sample and Hold: A Framework for Big-Graph Analytics |
|
| 课程网址: | http://videolectures.net/kdd2014_ahmed_big_graph_analytics/ |
| 主讲教师: | Nesreen K.Ahmed |
| 开课单位: | 普渡大学 |
| 开课时间: | 2014-10-07 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Sampling is a standard approach in big-graph analytics; the goal is to efficiently estimate the graph properties by consulting a sample of the whole population. A perfect sample is assumed to mirror every property of the whole population. Unfortunately, such a perfect sample is hard to collect in complex populations such as graphs (e.g. web graphs, social networks etc), where an underlying network connects the units of the population. Therefore, a good sample will be representative in the sense that graph properties of interest can be estimated with a known degree of accuracy. While previous work focused particularly on sampling schemes used to estimate certain graph properties (e.g. triangle count), much less is known for the case when we need to estimate various graph properties with the same sampling scheme. In this paper, we propose a generic stream sampling framework for big-graph analytics, called Graph Sample and Hold (gSH). To begin, the proposed framework samples from massive graphs sequentially in a single pass, one edge at a time, while maintaining a small state. We then show how to produce unbiased estimators for various graph properties from the sample. Given that the graph analysis algorithms will run on a sample instead of the whole population, the runtime complexity of these algorithm is kept under control. Moreover, given that the estimators of graph properties are unbiased, the approximation error is kept under control. Finally, we show the performance of the proposed framework (gSH) on various types of graphs, such as social graphs, among others. |
| 关 键 词: | 大图分析; 无偏估计; 分析算法 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-03-04：chenjy |
| 最后编审: | 2023-05-11：chenjy |
| 阅读次数: | 39 |