Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

Shop-floor narratives : how six workers and a researcher describe learning activities

I am a part-time graduate student who works in industry. This study is my narrative about how six workers and I describe shop-floor learning activities, that is learning activities that occur where work is done, outside a classroom. Because this study is narrative inquiry, you wilileam about me, the narrator, more than you would in a more conventional study. This is a common approach in narrative inquiry and it is important because my intentions shape the way that I tell these six workers' stories. I developed a typology of learning activities by synthesizing various theoretical frameworks. This typology categorizes shop-floor learning activities into five types: onthe- job training, participative learning, educational advertising, incidental learning, and self-directed learning. Although learning can occur in each of these activities in isolation, it is often comprised of a mixture of these activities. The literature review contains a number of cases that have been developed from situations described in the literature. These cases are here to make the similarities and differences between the types of learning activities that they represent more understandable to the reader and to ground the typology in practice as well as in theory. The findings are presented as reader's theatre, a dramatic presentation of these workers' narratives. The workers tell us that learning involves "being shown," and if this is not done properly they "learn the hard way." I found that many of their best case lean1ing activities involved on-the-job training, participative learning, incidentalleaming, and self-directed learning. Worst case examples were typically lacking in properly designed and delivered participative learning activities and to a lesser degree lacking carefully planned and delivered on-the-job training activities. Included are two reflective chapters that describe two cases: Learning "Engels" (English), and Learning to Write. In these chapters you will read about how I came to see that my own shop-floor learning-learning to write this thesis-could be enhanced through participative learning activities. I came to see my thesis supervisor as not only my instructor who directed and judged my learning activities, but also as a more experienced researcher who was there to participate in this process with me and to help me begin to enter the research community. Shop-floor learning involves learners and educators participating in multistranded learning activities, which require an organizational factor of careful planning and delivery. As with learning activities, which can be multi-stranded, so too, there can be multiple orientations to learning on the shop floor. In our stories, you will see that these six workers and I didn't exhibit just one orientation to learning in our stories. Our stories demonstrate that we could be behaviorist and cognitivist and humanist and social learners and constructivist in our orientation to learning. Our stories show that learning is complex and involves multiple strands, orientations, and factors. Our stories show that learning narratives capture the essence of learning-the learners, the educators, the learning activities, the organizational factors, and the learning orientations. Learning narratives can help learners and educators make sense of shop-floor learning.