A graph-theoretic approach to enterprise network dynamics

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010119039	TK5105.7 G72 2007	Open Access Book	Book	Searching... Unknown
Searching... PSZ KL	30000010150620	TK5105.7 G72 2007	Open Access Book	Book	Searching... Unknown

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.

Based on many years of applied research of 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.

Preface	p. vii
Part I Introduction
1 Intranets and Network Management	p. 3
1.1 Introduction	p. 3
1.2 Enterprise Intranets	p. 4
1.3 Network Management	p. 7
1.4 Network Management System	p. 9
1.5 Network Management in TCP/IP Networks	p. 11
1.5.1 Simple Network Management Protocol (SNMP)	p. 12
1.5.2 Remote Network Monitoring (RMON) Protocol	p. 14
1.6 Network Monitoring	p. 16
1.6.1 Active and Passive Monitoring	p. 17
1.6.2 Common Monitoring Solutions for Intranets	p. 18
1.6.3 Alternative Methods for Network Monitoring	p. 19
1.6.4 Sampling Interval and Polling Rate	p. 20
1.6.5 Minimizing Collection Infrastructure and Reducing Data Volume	p. 21
1.6.6 Synthesis of Improved Network Measures	p. 21
1.7 Network Anomaly Detection and Network Anomalies	p. 22
1.7.1 Anomaly Detection Methods	p. 23
1.7.2 Network-Wide Approach to Anomaly Detection	p. 25
1.7.3 Examples of Network Anomalies	p. 26
1.8 Summary	p. 28
2 Graph-Theoretic Concepts	p. 31
2.1 Introduction	p. 31
2.2 Basic Ideas	p. 32
2.3 Connectivity, Walks, and Paths	p. 34
2.4 Trees	p. 37
2.5 Factors, or Spanning Subgraphs	p. 38
2.6 Directed Graphs	p. 38
Part II Event Detection Using Graph Distance
3 Matching Graphs with Unique Node Labels	p. 43
3.1 Introduction	p. 43
3.2 Basic Concepts and Notation	p. 44
3.3 Graphs with Unique Node Labels	p. 45
3.4 Experimental Results	p. 51
3.4.1 Synthetic Network Data	p. 52
3.4.2 Real Network Data	p. 53
3.4.3 Verification of O(n[superscript 2]) Theoretical Computational Complexity for Isomorphism, Subgraph Isomorphism, MCS, and GEO	p. 53
3.4.4 Comparison of Computational Times for Real and Synthetic Data Sets	p. 57
3.4.5 Verification of Theoretical Computational Times for Median Graph	p. 59
3.5 Conclusions	p. 59
4 Graph Similarity Measures for Abnormal Change Detection	p. 63
4.1 Introduction	p. 63
4.2 Representing the Communications Network as a Graph	p. 64
4.3 Graph Topology-Based Distance Measures	p. 65
4.3.1 Using Maximum Common Subgraph	p. 65
4.3.2 Using Graph Edit Distance	p. 67
4.4 Traffic-Based Distance Measures	p. 70
4.4.1 Differences in Edge-Weight Values	p. 70
4.4.2 Analysis of Graph Spectra	p. 72
4.5 Measures Using Graph Structure	p. 73
4.5.1 Graphs Denoting 2-hop Distance	p. 75
4.6 Identifying Regions of Change	p. 75
4.6.1 Symmetric Difference	p. 76
4.6.2 Vertex Neighborhoods	p. 77
4.7 Conclusions	p. 78
5 Median Graphs for Abnormal Change Detection	p. 79
5.1 Introduction	p. 79
5.2 Median Graph for the Generalized Graph Distance Measure d[subscript 2]	p. 80
5.3 Median Graphs and Abnonnal Change Detection in Data Networks	p. 82
5.3.1 Median vs. Single Graph, Adjacent in Time (msa)	p. 83
5.3.2 Median vs. Median Graph, Adjacent in Time (mma)	p. 84
5.3.3 Median vs. Single Graph, Distant in Time (msd)	p. 84
5.3.4 Median vs. Median Graph, Distant in Time (mmd)	p. 84
5.4 Experimental Results	p. 84
5.4.1 Edit Distance and Single Graph vs. Single Graph Adjacent in Time (ssa)	p. 85
5.4.2 Edit Distance and Median Graph vs. Single Graph Adjacent in Time (msa)	p. 86
5.4.3 Edit Distance and Median Graph vs. Median Graph Adjacent in Time (mma)	p. 87
5.4.4 Edit Distance and Median Graph vs. Single Graph Distant in Time (msd)	p. 89
5.4.5 Edit Distance and Median Graph vs. Median Graph Distant in Time (mmd)	p. 89
5.5 Conclusions	p. 90
6 Graph Clustering for Abnormal Change Detection	p. 93
6.1 Introduction	p. 93
6.2 Clustering Algorithms	p. 94
6.2.1 Hierarchical Clustering	p. 94
6.2.2 Nonhierarchical Clustering	p. 97
6.2.3 Cluster Validation	p. 100
6.2.4 Fuzzy Clustering	p. 104
6.3 Clustering in the Graph Domain	p. 105
6.4 Clustering Time Series of Graphs	p. 112
6.5 Conclusion	p. 114
7 Graph Distance Measures based on Intragraph Clustering and Cluster Distance	p. 115
7.1 Introduction	p. 115
7.2 Basic Teiminology and Intragraph Clustering	p. 116
7.3 Distance of Clusterings	p. 118
7.3.1 Rand Index	p. 118
7.3.2 Mutuai Information	p. 119
7.3.3 Bipartite Graph Matching	p. 122
7.4 Novel Graph Distance Measures	p. 123
7.5 Applications to Computer Network Monitoring	p. 128
7.6 Conclusion	p. 130
8 Matching Sequences of Graphs	p. 131
8.1 Introduction	p. 131
8.2 Matching Sequences of Symbols	p. 131
8.2.1 Preliminaries	p. 131
8.2.2 Edit Distance of Sequences of Symbols	p. 132
8.3 Graph Sequence Matching	p. 137
8.4 Applications in Network Behavior Analysis	p. 139
8.4.1 Anomalous Event Detection Using a Library of Past Time Series	p. 139
8.4.2 Prediction of Anomalous Events	p. 141
8.4.3 Recovery of Incomplete Network Knowledge	p. 141
8.5 Conclusions	p. 142
Part III Propertaes of the Underlying Graphs
9 Distances, Clustering, and Small Worlds	p. 147
9.1 Graph Functions	p. 147
9.1.1 Distance	p. 147
9.1.2 Longest Distances	p. 147
9.1.3 Average Distances	p. 148
9.1.4 Characteristic Path Length	p. 148
9.1.5 Clustering Coefficient	p. 149
9.1.6 Directed Graphs	p. 149
9.2 Diameters	p. 149
9.2.1 A Pseudometric	p. 150
9.2.2 Sensitivity Analysis	p. 151
9.3 An Example Network	p. 153
9.3.1 Time Series Using f	p. 154
9.4 Time Series Using D	p. 155
9.5 Characteristic Path Lengths, Clustering Coefficients, and Small Worlds	p. 156
9.5.1 Two Classes of Graphs	p. 156
9.5.2 Small-World Graphs	p. 158
9.6 Enterprise Graphs and Small Worlds	p. 159
9.6.1 Sampling Traffic	p. 159
9.6.2 Results on Enterprise Graphs	p. 160
9.6.3 Discovering Anomalous Behavior	p. 162
10 Tournament Scoring	p. 165
10.1 Introduction	p. 165
10.2 Tournaments	p. 165
10.2.1 Definitions	p. 165
10.2.2 Tournament Matrices	p. 166
10.3 Ranking Tournaments	p. 166
10.3.1 The Ranking Problem	p. 166
10.3.2 Kendall-Wei Ranking	p. 167
10.3.3 The Perron-Frobenius Theorem	p. 168
10.4 Application to Networks	p. 168
10.4.1 Matrix of a Network	p. 168
10.5 Modality Distance	p. 169
10.5.1 Defining the Measure	p. 169
10.5.2 Applying the Distance Measure	p. 170
10.6 Variations in the Weight Function	p. 172
10.7 Conclusion	p. 172
Part IV Prediction and Advanced Distance Measures
11 Recovery of Missing Information in Graph Sequences	p. 177
11.1 Introduction	p. 177
11.2 Recovery of Missing Information in Computer Networks Using Context in Time	p. 177
11.2.1 Basic Concepts and Notation	p. 178
11.2.2 Recovery of Missing Information Using a Voting Procedure	p. 180
11.2.3 Recovery of Missing Information Using Reference Patterns	p. 182
11.2.4 Recovery of Missing Information Using Linear Prediction	p. 187
11.3 Recovery of Missing Information Using a Machine Learning Approach	p. 189
11.3.1 Decision Tree Classifiers	p. 189
11.3.2 Missing Information Recovery by Means of Decision Tree Classifiers: A Basic Scheme	p. 194
11.3.3 Possible Extensions of the Basic Scheme	p. 196
11.4 Conclusions	p. 197
12 Matching Hierarchical Graphs	p. 199
12.1 Introduction	p. 199
12.2 Hierarchical Graph Abstraction	p. 200
12.3 Distance Measures for Hierarchical Graph Abstraction	p. 201
12.4 Application to Computer Network Monitoring	p. 206
12.5 Experimental Results	p. 207
12.6 Conclusions	p. 210
References	p. 211
Index	p. 221

Available:*

On Order

Summary

Summary

Table of Contents