Exploring statistics of locally connected subgraph patterns (also known as
network motifs) has helped researchers better understand the structure and
function of biological and online social networks (OSNs). Nowadays the massive
size of some critical networks -- often stored in already overloaded relational
databases -- effectively limits the rate at which nodes and edges can be
explored, making it a challenge to accurately discover subgraph statistics. In
this work, we propose sampling methods to accurately estimate subgraph
statistics from as few queried nodes as possible. We present sampling
algorithms that efficiently and accurately estimate subgraph properties of
massive networks. Our algorithms require no pre-computation or complete network
topology information. At the same time, we provide theoretical guarantees of
convergence. We perform experiments using widely known data sets, and show that
for the same accuracy, our algorithms require an order of magnitude less
queries (samples) than the current state-of-the-art algorithms.

本文提出了一种基于抽样的算法，有效地从大规模网络中准确估算子图统计量，并展示实验结果表明其能更加快速地完成与现行技术相同准确度的查询量（样本量）