Tracking Moving Clutches in Streaming Graphs.
Sudarshan S. Chawathe.
Technical Report CS-TR-4376 (UMIACS-TR-2002-56). Computer Science
Department, University of Maryland, College Park, Maryland 20742. May
2002.
[ paper |
citation ]
We address the problem of tracking groups of interacting entities as they move in a graph with vertices representing hosts or locations and edges representing interactions between hosts. The graph of interactions is modeled as a stream of edges (with the arrival of an edge signifying an interaction between the hosts it connects). This problem arises in applications such as tracking groups of fraudulent callers in a telephone network and tracking identities of malicious agents (programs or people) on a data network. We present a formalization of this problem and a streaming solution that uses bounded storage and provides real-time response. Our solution is based on maintaining, at each instant, an approximation of the streaming graph seen so far. We present empirical results to quantify the effectiveness of our solution.