GUISE: a uniform sampler for constructing frequency histogram of graphlets |
| |
Authors: | Mahmudur Rahman Mansurul Alam Bhuiyan Mahmuda Rahman Mohammad Al Hasan |
| |
Affiliation: | 1. Department of Computer Science, Indiana University–Purdue University, Indianapolis, IN, USA 2. Department of Computer Science, Syracuse University, Syracuse, NY, USA
|
| |
Abstract: | Graphlet frequency distribution (GFD) has recently become popular for characterizing large networks. However, the computation of GFD for a network requires the exact count of embedded graphlets in that network, which is a computationally expensive task. As a result, it is practically infeasible to compute the GFD for even a moderately large network. In this paper, we propose Guise, which uses a Markov Chain Monte Carlo sampling method for constructing the approximate GFD of a large network. Our experiments on networks with millions of nodes show that Guise obtains the GFD with very low rate of error within few minutes, whereas the exhaustive counting-based approach takes several days. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|