Home
This Title All WIREs
WIREs RSS Feed
How to cite this WIREs title:
WIREs Data Mining Knowl Discov
Impact Factor: 1.939

Change detection in dynamic attributed networks

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

A network provides powerful means of representing complex relationships between entities by abstracting entities as vertices, and relationships as edges connecting vertices in a graph. Beyond the presence or absence of relationships, a network may contain additional information that can be attributed to the entities and their relationships. Attaching these additional attribute data to the corresponding vertices and edges yields an attributed graph. Moreover, in the majority of real‐world applications, such as online social networks, financial networks and transactional networks, relationships between entities evolve over time. Change detection in dynamic attributed networks is an important problem in many areas, such as fraud detection, cyber intrusion detection, and health care monitoring. It is a challenging problem because it involves a time sequence of attributed graphs, each of which is usually very large and can contain many attributes attached to the vertices and edges, resulting in a complex, high‐dimensional mathematical object. In this survey we provide an overview of some of the existing change detection methods that utilize attribute information. We categorize these methods based on the levels of structure in the graph that are exploited to detect changes. These levels are vertices, edges, subgraphs, communities, and the overall graph. We focus attention on the strengths and weaknesses of these methods, including their performance and scalability. Furthermore, we discuss some publicly available dynamic network datasets and give a brief overview of models to generate dynamic attributed networks. Finally, we discuss the limitations of existing approaches identifying key areas for future research.

This article is categorized under:

  • Fundamental Concepts of Data and Knowledge > Data Concepts
  • Algorithmic Development > Spatial and Temporal Data Mining
  • Technologies > Machine Learning
  • Application Areas > Business and Industry
Illustration of an attributed graph. The vertices and edges are tagged with attribute information corresponding to the entities and their relationships in the network
[ Normal View | Magnified View ]
Burst of traffic concentrated in a certain time interval on a single port showing human activity (Reprinted with permission from Koutra et al. (). Copyright 2012 Conference Publishing Services (CPS))
[ Normal View | Magnified View ]
Bot‐attack like behavior evident from evenly spaced spikes of activity (Reprinted with permission from Koutra et al. (). Copyright 2012 IEEE Computer Society)
[ Normal View | Magnified View ]
Illustration of Koujaku et al.'s change detection framework with double sliding windows (Reprinted with permission from Koujaku et al. (). Copyright 2015 Association for Computing Machinery (ACM) New York, NY, USA)
[ Normal View | Magnified View ]
Possible changes occurring in community structure (Reprinted with permission from Chen et al. (). Copyright 2012 Springer)
[ Normal View | Magnified View ]
The traversal behavior of an intruder in a computer network (Reprinted with permission from Neil, Hash, et al. (). Copyright 2013 © the American Statistical Association, www.amstat.org, reprinted by permission of Taylor & Francis Ltd)
[ Normal View | Magnified View ]
The star shaped subgraph centered at vertex i in Priebe et al. (). The star contains the set of all vertices in the graph that lie within a shortest path length of at most 1 from vertex i (Reprinted with permission from Neil, Hash, et al. (). Copyright 2013 © the American Statistical Association, www.amstat.org, reprinted by permission of Taylor & Francis Ltd)
[ Normal View | Magnified View ]
Representing multiple edge attributes as a 3D tensor. The first two coordinates denote vertices and the third dimension denotes edge attributes
[ Normal View | Magnified View ]
Illustrative example of change detection. Each graph represents the behavior of the entities and their relationships at the corresponding time instant. A sequence of graphs inside the window containing the recent past time instants characterizes profile behavior of entities and their relationships. A change detection method compares the current behavior of the overall graph, vertices, edges, or subgraphs with their profile behavior. A change can be detected when the current behavior shows high dissimilarity to the profile behavior
[ Normal View | Magnified View ]

Browse by Topic

Algorithmic Development > Spatial and Temporal Data Mining
Application Areas > Business and Industry
Fundamental Concepts of Data and Knowledge > Data Concepts
Technologies > Machine Learning

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts