  Exploring small connected and induced subgraph patterns (CIS patterns, or
graphlets) has recently attracted considerable attention. Despite recent
efforts on computing the number of instances a specific graphlet appears in a
large graph (i.e., the total number of CISes isomorphic to the graphlet),
little attention has been paid to characterizing a node's graphlet degree,
i.e., the number of CISes isomorphic to the graphlet that include the node,
which is an important metric for analyzing complex networks such as social and
biological networks. Similar to global graphlet counting, it is challenging to
compute node graphlet degrees for a large graph due to the combinatorial nature
of the problem. Unfortunately, previous methods of computing global graphlet
counts are not suited to solve this problem. In this paper we propose sampling
methods to estimate node graphlet degrees for undirected and directed graphs,
and analyze the error of our estimates. To the best of our knowledge, we are
the first to study this problem and give a fast scalable solution. We conduct
experiments on a variety of real-word datasets that demonstrate that our
methods accurately and efficiently estimate node graphlet degrees for graphs
with millions of edges.
