A Graph-theoretic Approach to Enterprise Network Dynamics

by Bunke, Horst; Dickinson, Peter J.; Kraetzl, Miro; Wallis, Walter D.

• ISBN13: 9780817644857
• ISBN10: 0817644857
• Format: Hardcover
• Copyright: 2006-11-30
• Publisher: Birkhauser

Summary

Networks have become nearly ubiquitous and increasingly complex, and their support of modern enterprise environments has become fundamental. Accordingly, robust network management techniques are essential to ensure optimal performance of these networks. This monograph treats the application of numerous graph-theoretic algorithms to a comprehensive analysis of dynamic enterprise networks. Network dynamics analysis yields valuable information about network performance, efficiency, fault prediction, cost optimization, indicators and warnings.The exposition is organized into four relatively independent parts: an introduction and overview of typical enterprise networks and the graph theoretical prerequisites for all algorithms introduced later; an in-depth treatise of usage of various graph distances for event detection; a detailed exploration of properties of underlying graphs with modeling applications; and a theoretical and applied treatment of network behavior inferencing and forecasting using sequences of graphs.Based on many years of applied research on generic network dynamics, this work covers a number of elegant applications (including many new and experimental results) of traditional graph theory algorithms and techniques to computationally tractable network dynamics analysis to motivate network analysts, practitioners and researchers alike. The material is also suitable for graduate courses addressing state-of-the-art applications of graph theory in analysis of dynamic communication networks, dynamic databasing, and knowledge management.

Table of Contents

Preface	p. vii
Introduction
Intranets and Network Management	p. 3
Introduction	p. 3
Enterprise Intranets	p. 4
Network Management	p. 7
Network Management System	p. 9
Network Management in TCP/IP Networks	p. 11
Simple Network Management Protocol (SNMP)	p. 12
Remote Network Monitoring (RMON) Protocol	p. 14
Network Monitoring	p. 16
Active and Passive Monitoring	p. 17
Common Monitoring Solutions for Intranets	p. 18
Alternative Methods for Network Monitoring	p. 19
Sampling Interval and Polling Rate	p. 20
Minimizing Collection Infrastructure and Reducing Data Volume	p. 21
Synthesis of Improved Network Measures	p. 21
Network Anomaly Detection and Network Anomalies	p. 22
Anomaly Detection Methods	p. 23
Network-Wide Approach to Anomaly Detection	p. 25
Examples of Network Anomalies	p. 26
Summary	p. 28
Graph-Theoretic Concepts	p. 31
Introduction	p. 31
Basic Ideas	p. 32
Connectivity, Walks, and Paths	p. 34
Trees	p. 37
Factors, or Spanning Subgraphs	p. 38
Directed Graphs	p. 38
Event Detection Using Graph Distance
Matching Graphs with Unique Node Labels	p. 43
Introduction	p. 43
Basic Concepts and Notation	p. 44
Graphs with Unique Node Labels	p. 45
Experimental Results	p. 51
Synthetic Network Data	p. 52
Real Network Data	p. 53
Verification of O(n[superscript 2]) Theoretical Computational Complexity for Isomorphism, Subgraph Isomorphism, MCS, and GEO	p. 53
Comparison of Computational Times for Real and Synthetic Data Sets	p. 57
Verification of Theoretical Computational Times for Median Graph	p. 59
Conclusions	p. 59
Graph Similarity Measures for Abnormal Change Detection	p. 63
Introduction	p. 63
Representing the Communications Network as a Graph	p. 64
Graph Topology-Based Distance Measures	p. 65
Using Maximum Common Subgraph	p. 65
Using Graph Edit Distance	p. 67
Traffic-Based Distance Measures	p. 70
Differences in Edge-Weight Values	p. 70
Analysis of Graph Spectra	p. 72
Measures Using Graph Structure	p. 73
Graphs Denoting 2-hop Distance	p. 75
Identifying Regions of Change	p. 75
Symmetric Difference	p. 76
Vertex Neighborhoods	p. 77
Conclusions	p. 78
Median Graphs for Abnormal Change Detection	p. 79
Introduction	p. 79
Median Graph for the Generalized Graph Distance Measure d[subscript 2]	p. 80
Median Graphs and Abnonnal Change Detection in Data Networks	p. 82
Median vs. Single Graph, Adjacent in Time (msa)	p. 83
Median vs. Median Graph, Adjacent in Time (mma)	p. 84
Median vs. Single Graph, Distant in Time (msd)	p. 84
Median vs. Median Graph, Distant in Time (mmd)	p. 84
Experimental Results	p. 84
Edit Distance and Single Graph vs. Single Graph Adjacent in Time (ssa)	p. 85
Edit Distance and Median Graph vs. Single Graph Adjacent in Time (msa)	p. 86
Edit Distance and Median Graph vs. Median Graph Adjacent in Time (mma)	p. 87
Edit Distance and Median Graph vs. Single Graph Distant in Time (msd)	p. 89
Edit Distance and Median Graph vs. Median Graph Distant in Time (mmd)	p. 89
Conclusions	p. 90
Graph Clustering for Abnormal Change Detection	p. 93
Introduction	p. 93
Clustering Algorithms	p. 94
Hierarchical Clustering	p. 94
Nonhierarchical Clustering	p. 97
Cluster Validation	p. 100
Fuzzy Clustering	p. 104
Clustering in the Graph Domain	p. 105
Clustering Time Series of Graphs	p. 112
Conclusion	p. 114
Graph Distance Measures based on Intragraph Clustering and Cluster Distance	p. 115
Introduction	p. 115
Basic Teiminology and Intragraph Clustering	p. 116
Distance of Clusterings	p. 118
Rand Index	p. 118
Mutuai Information	p. 119
Bipartite Graph Matching	p. 122
Novel Graph Distance Measures	p. 123
Applications to Computer Network Monitoring	p. 128
Conclusion	p. 130
Matching Sequences of Graphs	p. 131
Introduction	p. 131
Matching Sequences of Symbols	p. 131
Preliminaries	p. 131
Edit Distance of Sequences of Symbols	p. 132
Graph Sequence Matching	p. 137
Applications in Network Behavior Analysis	p. 139
Anomalous Event Detection Using a Library of Past Time Series	p. 139
Prediction of Anomalous Events	p. 141
Recovery of Incomplete Network Knowledge	p. 141
Conclusions	p. 142
Propertaes of the Underlying Graphs
Distances, Clustering, and Small Worlds	p. 147
Graph Functions	p. 147
Distance	p. 147
Longest Distances	p. 147
Average Distances	p. 148
Characteristic Path Length	p. 148
Clustering Coefficient	p. 149
Directed Graphs	p. 149
Diameters	p. 149
A Pseudometric	p. 150
Sensitivity Analysis	p. 151
An Example Network	p. 153
Time Series Using f	p. 154
Time Series Using D	p. 155
Characteristic Path Lengths, Clustering Coefficients, and Small Worlds	p. 156
Two Classes of Graphs	p. 156
Small-World Graphs	p. 158
Enterprise Graphs and Small Worlds	p. 159
Sampling Traffic	p. 159
Results on Enterprise Graphs	p. 160
Discovering Anomalous Behavior	p. 162
Tournament Scoring	p. 165
Introduction	p. 165
Tournaments	p. 165
Definitions	p. 165
Tournament Matrices	p. 166
Ranking Tournaments	p. 166
The Ranking Problem	p. 166
Kendall-Wei Ranking	p. 167
The Perron-Frobenius Theorem	p. 168
Application to Networks	p. 168
Matrix of a Network	p. 168
Modality Distance	p. 169
Defining the Measure	p. 169
Applying the Distance Measure	p. 170
Variations in the Weight Function	p. 172
Conclusion	p. 172
Prediction and Advanced Distance Measures
Recovery of Missing Information in Graph Sequences	p. 177
Introduction	p. 177
Recovery of Missing Information in Computer Networks Using Context in Time	p. 177
Basic Concepts and Notation	p. 178
Recovery of Missing Information Using a Voting Procedure	p. 180
Recovery of Missing Information Using Reference Patterns	p. 182
Recovery of Missing Information Using Linear Prediction	p. 187
Recovery of Missing Information Using a Machine Learning Approach	p. 189
Decision Tree Classifiers	p. 189
Missing Information Recovery by Means of Decision Tree Classifiers: A Basic Scheme	p. 194
Possible Extensions of the Basic Scheme	p. 196
Conclusions	p. 197
Matching Hierarchical Graphs	p. 199
Introduction	p. 199
Hierarchical Graph Abstraction	p. 200
Distance Measures for Hierarchical Graph Abstraction	p. 201
Application to Computer Network Monitoring	p. 206
Experimental Results	p. 207
Conclusions	p. 210
References	p. 211
Index	p. 221
Table of Contents provided by Ingram. All Rights Reserved.