In one embodiment, a device obtains telemetry data regarding a plurality of traffic flows in a network. The device forms a directed graph based on the telemetry data, wherein nodes of the graph represent devices in the network. The device simulates traffic for one or more of the devices by performing random walks starting at a particular node on the directed graph to generate a set of trails, each trail representing a sequence of one or more flows. The device clusters the set of trails to form one or more clusters. The device generates an application fingerprint for an application based on one of the one or more clusters. The device uses the application fingerprint to identify traffic in the network as associated with the application.