Adobe Inc.
System for identifying typed graphlets

Abstract:

A system is disclosed for identifying and counting typed graphlets in a heterogeneous network. A methodology implementing techniques for the disclosed system according to an embodiment includes identifying typed k-node graphlets occurring between any two selected nodes of a heterogeneous network, wherein the nodes are connected by one or more edges. The identification is based on combinatorial relationships between (k-1)-node typed graphlets occurring between the two selected nodes of the heterogeneous network. Identification of 3-node typed graphlets is based on computation of typed triangles, typed 3-node stars, and typed 3-paths associated with each edge connecting the selected nodes. The method further includes maintaining a count of the identified k-node typed graphlets and storing those graphlets with non-zero counts. The identified graphlets are employed for applications including visitor stitching, user profiling, outlier detection, and link prediction.