Systems and methods for estimating typed graphlets in large data

A computer system comprising:

• at least one memory having processor-readable instructions stored therein;
• and
• at least one processor configured to access the at least one memory and execute the processor-readable instructions to perform operations including:
• receiving a dataset identifying:
• a set of entities corresponding to nodes in a graph;
• edges connecting the nodes in the graph;
• and
• a plurality of types corresponding to the nodes and of the edges, respectively, in the graph;
• sampling a portion of the graph;
• determining a number of typed graphlets in the sampled portion of the graph;
• identifying a typed graphlet pattern having a combinatorial relationship of the determined number of typed graphlets;
• determining an occurrence frequency of the typed graphlet pattern in the sampled portion of the graph based on the identifying;
• and
• determining an estimation of a total number of typed graphlets in the graph having the typed graphlet pattern based on the determined occurrence frequency of the typed graphlet pattern in the sampled portion of the graph.

A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for estimating a total number of typed graphlets in a graph, the method comprising:

• receiving a dataset identifying:
• a set of entities corresponding to nodes in the graph;
• edges connecting the nodes in the graph;
• and
• a plurality of types corresponding to the nodes and the edges, respectively, in the graph, each type of the plurality of types corresponding to a characteristic of a corresponding entity of the set of entities;
• sampling a portion of the graph;
• determining a number of typed graphlets in the sampled portion of the graph;
• identifying a typed graphlet pattern having a combinatorial relationship of the determined number of the typed graphlets;
• determining an occurrence frequency of the typed graphlet pattern in the sampled portion of the graph based on the identifying;
• determining an estimation of the total number of typed graphlets in the graph based on the determined occurrence frequency of the typed graphlet pattern.