A Graph-Theoretic Approach to Enterprise Network Dynamics Book

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