Hierarchical Approach for Survivable Network Design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.

A Social Network Analysis Of Hamadryas Baboons

The study of animal sociality investigates the immediate and long-term consequences that a social structure has on its group members. Typically, social behavior is observed from interactions between two individuals at the dyadic level. However, a new framework for studying social behavior has emerged that allows the researcher to assess social complexity at multiple scales. Social Network Analysis has been recently applied in the field of ethology, and this novel tool enables an approach of focusing on social behavior in context of the global network rather than limited to dyadic interactions. This new technique was applied to a group of captive hamadryas baboons (Papio hamadryas hamadryas) in order to assess how overall network topology of the social group changes over time with the decline of an aging leader male. Observations on aggressive, grooming, and proximity spatial interactions were collected from three separate years in order to serve as `snapshots¿ of the current state of the group. Data on social behavior were collected from the group when the male was in prime health, when the male was at an old age, and after the male¿s death. A set of metrics was obtained from each time period for each type of social behavior and quantified a change in the patterns of interactions. The results suggest that baboon social behavior varies across context, and changes with the attributes of its individual members. Possible mechanisms for adapting to a changing social environment were also explored.

Visualization Techniques For The Analysis Of Network Simulation Results

The Simulation Automation Framework for Experiments (SAFE) streamlines the de- sign and execution of experiments with the ns-3 network simulator. SAFE ensures that best practices are followed throughout the workflow a network simulation study, guaranteeing that results are both credible and reproducible by third parties. Data analysis is a crucial part of this workflow, where mistakes are often made. Even when appearing in highly regarded venues, scientific graphics in numerous network simulation publications fail to include graphic titles, units, legends, and confidence intervals. After studying the literature in network simulation methodology and in- formation graphics visualization, I developed a visualization component for SAFE to help users avoid these errors in their scientific workflow. The functionality of this new component includes support for interactive visualization through a web-based interface and for the generation of high-quality, static plots that can be included in publications. The overarching goal of my contribution is to help users create graphics that follow best practices in visualization and thereby succeed in conveying the right information about simulation results.