Many real-world relations are networks that can be modelled with a kind of directed hypergraph named a forward hypergraph (F-graph). F-graphs capture the semantics of both conjunctive and disjunctive dependency relations. Logic statements are sometimes represented using AND/OR directed graphs and they directly correspond with F-graphs; we provide algorithms to convert between the two types of graph.
One problem of interest in networks is determining the degree to which the network, with a priority on certain elements, depends upon individual nodes. We address this problem by providing an algorithm, AssetRank, which computes vertex ranks and takes into account network priorities, preferential dependencies, and extra-network influences.
A second problem of interest in networks is optimizing the removal of nodes to separate two subcommunities (source and target) to the greatest practical degree, even when a complete disconnection is impractical. The problem is complicated by the need to consider the cost of removing nodes, a budget that constrains the degree to which separation is possible, cascading effects of removing a node, non-linear effects of removing nodes in combination, and removing nodes with the greatest impact on the subcommunities. To this end, we use F-graphs and introduce the concepts of vertex closures and closure-relation graphs. We created two partial-cut algorithms: the first one computes an optimal solution to this NP-hard optimization problem, and the second one estimates an optimization by exploring the closure-relation graph in a best-first search manner.
Computer network defence provides a ready application area. Network defenders wish to understand which services and hosts are defence priorities (defence goals), and then, which configurations and vulnerabilities are the most useful to attackers in reaching the defence goals. The defenders' resources are constrained in terms of available person-hours, finances, and acceptable impacts to operations. The work in this thesis supports network defenders by providing actionable information that efficiently removes attack enablers and ensures defence priorities. We present an integration of our algorithms with commercial and open-source network security software. / Thesis (Ph.D, Computing) -- Queen's University, 2011-04-30 22:17:52.062
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OKQ.1974/6484 |
| Date | 02 May 2011 |
| Creators | Sawilla, Reginald Elias |
| Contributors | Queen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.)) |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner. |
| Relation | Canadian theses |
Page generated in 0.0025 seconds