GRAFT: An Efficient Graphlet Counting Method for Large Graph Analysis

doi:10.1109/TKDE.2013.2297929

Return

GRAFT: An Efficient Graphlet Counting Method for Large Graph Analysis

2014-10-01

PRE

Mahmudur Rahman *

Mohammad Al Hasan

DOI：10.1109/TKDE.2013.2297929

Original

Original request for help

Save

Abstract

En 中文

Majority of the existing works on network analysis study properties that are related to the global topology of a network. Examples of such properties include diameter, power-law exponent, and spectra of graph Laplacian. Such works enhance our understanding of real-life networks, or enable us to generate synthetic graphs with real-life graph properties. However, many of the existing problems on networks require the study of local topological structures of a network, which did not get the deserved attention in the existing works. In this work, we use graphlet frequency distribution (GFD) as an analysis tool for understanding the variance of local topological structure in a network; we also show that it can help in comparing, and characterizing real-life networks. The main bottleneck to obtain GFD is the excessive computation cost for obtaining the frequency of each of the graphlets in a large network. To overcome this, we propose a simple, yet powerful algorithm, called GRAFT, that obtains the approximate graphlet frequency for all graphlets that have up-to five vertices. Comparing to an exact counting algorithm, our algorithm achieves a speedup factor between 10 and 100 for a negligible counting error, which is, on average, less than 5 percent.

Keywords:

Graph mining

graphlet counting

GFD

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.