G. Cormode, F. Korn, S. Muthukrishnan, and Y. Wu. On signatures for communication graphs. In International Conference on Data Engineering (ICDE), 2008.

Communications between individuals can be represented by (weighted, multi-) graphs. Many applications operate on communication graphs associated with telephone calls, emails, Instant Messages (IM), blogs, web forums, e-business relationships and so on. These applications include identifying repetitive fraudsters, message board aliases, multihoming of IP addresses, etc. Tracking such electronic identities on communication network can be achieved if we have a reliable “signature” for nodes and activities. While many examples of adhoc signatures can be proposed for particular tasks, what is needed is a systematic study of the principles behind the usage of signatures in any task.

We develop a formal framework for the use of signatures on communication graphs and identify three fundamental properties that are natural to signature schemes: persistence, uniqueness and robustness. We justify these properties by showing how they impact a set of applications. We then explore several signature schemes - previously defined or new - in our framework and evaluate them on real data in terms of these properties. This provides insights into suitable signature schemes for desired applications. Finally, as case studies, we focus on the concrete application of enterprise network traffic.

bib | .pdf ] Back

This file was generated by bibtex2html 1.92.