A graph-theoretic approach to enterprise network dynamics. (Q2432941)

Graph-theoretic and combinatorial models of networks are pervasive in both small and large organizations. This monograph focusses on the dynamic nature of networks. It provides guidance in answering questions concerning the detection and identification of faults, monitoring of network performance, and enforcement of security policies. Each of these relies on a representation of the dynamic nature of the network as a time series of graphs, or graph sequence. The detection of change from one graph to the next in the sequence is fundamental; tools to quantify this change using a number of combinatorial and algebraic ideas are explored in detail. In each case, algorithms are given, and empirical results are presented to validate the theoretical analyses. Often these validations employ large, real-world data. The presentation treats numerous approaches from the mathematical underpinnings and challenges, through algorithms and complexity, to application in dynamic network analysis. Most mathematicians will appreciate the applications of sometimes elegant mathematics to real applications, and at the same time find numerous open problems in mathematics suggested by the needs of dynamic network modelling. The monograph is presented in four parts, each divided into chapters. The first part is an introduction. Chapter 1 introduces the fundamentals of networks used in large enterprises; it motivates the graph-theoretic models and provides a solid understanding of how they represent the networks of interest. It motivates the need for the detection of anomalous behaviour, and outlines methods to observe such anomalies. Chapter 2 provides an introduction to the concepts of graph theory to be used. Already in this chapter, the basic results from graph theory are motivated using the problems on dynamic networks. The second part is the majority of the monograph, concerning event detection in dynamic networks. The basic premise is that event detection can be accomplished by determining distances among graphs in a time-dependent graph sequence; which distance to use, how to compute it, and what it tells us about important events, are all central issues. Chapter 3 concerns graph matching (not to be confused with matching in a graph), in which similarities between consecutive graphs in the sequence are determined when network nodes are uniquely labelled (for example, by IP addresses). Chapter 4 treats distance measures more generally, examining measures based on graph isomorphism, subgraph isomorphism, and graph edit distance. The latter explores the number of changes (edits) needed to produce one graph from the preceding graph in the sequence. In addition to using the connection structure of the underlying network, distances based on traffic patterns and distances based on local connectivity, are also explored. The analysis extends from detecting when a change occurs to identifying where in the network the changes are significant. Chapter 5 treats the important question of characterizing a `normal' or `average' state of a graph over a graph sequence. Median graphs are introduced for this purpose, and their use in detecting deviation from expected behaviour is discussed. While Chapters 3 and 4 concern primarily consecutive graphs in a sequence, and Chapter 5 concerns deviation from an overall median, Chapters 6 and 7 examine clustering the graphs in the sequence based on distance. They introduce clustering techniques and describe their application in finding patterns of network behaviour in order to detect significant change. Chapter 8 develops extensions to a pair of graph sequences, and advocates this analysis for the characterization of network behaviour using patterns of past behaviour whose meaning is understood. The third part concerns properties of the underlying graphs arising in enterprise networks. Chapter 9 treats small-world networks, and examines measures based on path lengths and on clustering coefficients. Chapter 10 introduces tools for assessing importance of nodes in a network, using novel techniques from tournament ranking. The fourth part extends the work from Chapters 3--8 to inference and forecasting. Chapter 11 addresses the important problem of inferring missing data and introduces machine learning techniques. Chapter 12 extends the distance-based techniques to graph models that are hierarchical in nature, and demonstrates that employing hierarchical structure can result in improvements in computation time. The monograph should prove interesting not only to network managers, but also to mathematicians in a variety of fields. Particularly relevant for the work here are graph similarity and graph distances. While the monograph does not delve deeply into the mathematics, it provides a good starting point for the underlying mathematics.