Faculty Digital Archive

Archive@NYU >
Stern School of Business >
IOMS: Information Systems Working Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2451/14127

Title: Building an Effective Representation for Dynamic Networks
Authors: Hill, Shawndra
Agarwal, Deepak
Bell, Robert
Volinsky, Chris
Keywords: approximate subgraphs
dynamic graphs
exponential averaging
fraud detection
transactional data streams
Issue Date: 19-Feb-2005
Publisher: Stern School of Business, New York University
Series/Report no.: CeDER-05-11
Abstract: A dynamic network is a special type of network which is comprised of connected transactors which have repeated evolving interaction. Data on large dynamic networks such as telecommunications networks and the Internet are pervasive. However, representing dynamic networks in a manner that is conducive to efficient large-scale analysis is a challenge. In this paper, we represent dynamic graphs using a data structure introduced by Cortes et. a]. [Q]. We advocate their representation because it accounts for the evolution of relationships between transactors through time, mitigates noise at the local transactor level, and allows for the removal of stale relationships. Our work improves on their heuristic arguments by formalizing the representation with three tunable parameters. In doing this, we develop a generic framework for evaluating and tuning any dynamic graph. We show that the storage saving approximations involved in the representation do not affect predictive performance, and typically improve it. We motivate our approach using a fraud detection example from the telecommunications industry, and demonstrate that we can outperform published results on the fraud detection task. In addition, we present preliminary analysis on web logs and email networks.
URI: http://hdl.handle.net/2451/14127
Appears in Collections:CeDER Working Papers
IOMS: Information Systems Working Papers

Files in This Item:

File Description SizeFormat
CeDER-05-11.pdf6.09 MBAdobe PDFView/Open

Items in Faculty Digital Archive are protected by copyright, with all rights reserved, unless otherwise indicated.


The contents of the FDA may be subject to copyright, be offered under a Creative Commons license, or be in the public domain.
Please check items for rights statements. For information about NYU’s copyright policy, see http://www.nyu.edu/footer/copyright-and-fair-use.html 
Valid XHTML 1.0 | CSS