Dynamics in large scale networks

In this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the Barabási-Albert random graph. We establish some bounds on the number of motifs in this graph.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

Application of thermal ion-molecule reactions in tackling spectroscopic inferences in inductively coupled plasma mass spectrometry

Part I: Ultra-trace determination of vanadium in lake sediments: a performance comparison using O2, N20, and NH3 as reaction gases in ICP-DRC-MS Thermal ion-molecule reactions, targeting removal of specific spectroscopic interference problems, have become a powerful tool for method development in quadrupole based inductively coupled plasma mass spectrometry (ICP-MS) applications. A study was conducted to develop an accurate method for the determination of vanadium in lake sediment samples by ICP-MS, coupled with a dynamic reaction cell (DRC), using two differenvchemical resolution strategies: a) direct removal of interfering C10+ and b) vanadium oxidation to VO+. The performance of three reaction gases that are suitable for handling vanadium interference in the dynamic reaction cell was systematically studied and evaluated: ammonia for C10+ removal and oxygen and nitrous oxide for oxidation. Although it was able to produce comparable results for vanadium to those using oxygen and nitrous oxide, NH3 did not completely eliminate a matrix effect, caused by the presence of chloride, and required large scale dilutions (and a concomitant increase in variance) when the sample and/or the digestion medium contained large amounts of chloride. Among the three candidate reaction gases at their optimized Eonditions, creation of VO+ with oxygen gas delivered the best analyte sensitivity and the lowest detection limit (2.7 ng L-1). Vanadium results obtained from fourteen lake sediment samples and a certified reference material (CRM031-040-1), using two different analytelinterference separation strategies, suggested that the vanadium mono-oxidation offers advantageous performance over the conventional method using NH3 for ultra-trace vanadium determination by ICP-DRC-MS and can be readily employed in relevant environmental chemistry applications that deal with ultra-trace contaminants.Part II: Validation of a modified oxidation approach for the quantification of total arsenic and selenium in complex environmental matrices Spectroscopic interference problems of arsenic and selenium in ICP-MS practices were investigated in detail. Preliminary literature review suggested that oxygen could serve as an effective candidate reaction gas for analysis of the two elements in dynamic reaction cell coupled ICP-MS. An accurate method was developed for the determination of As and Se in complex environmental samples, based on a series of modifications on an oxidation approach for As and Se previously reported. Rhodium was used as internal standard in this study to help minimize non-spectral interferences such as instrumental drift. Using an oxygen gas flow slightly higher than 0.5 mL min-I, arsenic is converted to 75 AS160+ ion in an efficient manner whereas a potentially interfering ion, 91Zr+, is completely removed. Instead of using the most abundant Se isotope, 80Se, selenium was determined by a second most abundant isotope, 78Se, in the form of 78Se160. Upon careful selection of oxygen gas flow rate and optimization ofRPq value, previous isobaric threats caused by Zr and Mo were reduced to background levels whereas another potential atomic isobar, 96Ru+, became completely harmless to the new selenium analyte. The new method underwent a strict validation procedure where the recovery of a suitable certified reference material was examined and the obtained sample data were compared with those produced by a credible external laboratory who analyzed the same set of samples using a standardized HG-ICP-AES method. The validation results were satisfactory. The resultant limits of detection for arsenic and selenium were 5 ng L-1 and 60 ng L-1, respectively.

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.