Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Discriminating Different Classes of Biological Networks by Analyzing the Graphs Spectra Distribution

The brain's structural and functional systems, protein-protein interaction, and gene networks are examples of biological systems that share some features of complex networks, such as highly connected nodes, modularity, and small-world topology. Recent studies indicate that some pathologies present topological network alterations relative to norms seen in the general population. Therefore, methods to discriminate the processes that generate the different classes of networks (e. g., normal and disease) might be crucial for the diagnosis, prognosis, and treatment of the disease. It is known that several topological properties of a network (graph) can be described by the distribution of the spectrum of its adjacency matrix. Moreover, large networks generated by the same random process have the same spectrum distribution, allowing us to use it as a "fingerprint". Based on this relationship, we introduce and propose the entropy of a graph spectrum to measure the "uncertainty" of a random graph and the Kullback-Leibler and Jensen-Shannon divergences between graph spectra to compare networks. We also introduce general methods for model selection and network model parameter estimation, as well as a statistical procedure to test the nullity of divergence between two classes of complex networks. Finally, we demonstrate the usefulness of the proposed methods by applying them to (1) protein-protein interaction networks of different species and (2) on networks derived from children diagnosed with Attention Deficit Hyperactivity Disorder (ADHD) and typically developing children. We conclude that scale-free networks best describe all the protein-protein interactions. Also, we show that our proposed measures succeeded in the identification of topological changes in the network while other commonly used measures (number of edges, clustering coefficient, average path length) failed.

Architectures, stability and optimization for clock distribution networks

Synchronous telecommunication networks, distributed control systems and integrated circuits have its accuracy of operation dependent on the existence of a reliable time basis signal extracted from the line data stream and acquirable to each node. In this sense, the existence of a sub-network (inside the main network) dedicated to the distribution of the clock signals is crucially important. There are different solutions for the architecture of the time distribution sub-network and choosing one of them depends on cost, precision, reliability and operational security. In this work we expose: (i) the possible time distribution networks and their usual topologies and arrangements. (ii) How parameters of the network nodes can affect the reachability and stability of the synchronous state of a network. (iii) Optimizations methods for synchronous networks which can provide low cost architectures with operational precision, reliability and security. (C) 2011 Elsevier B. V. All rights reserved.

Mistletoes Play Different Roles in a Modular Host-Parasite Network

Antagonistic interactions between host plants and mistletoes often form complex networks of interacting species. Adequate characterization of network organization requires a combination of qualitative and quantitative data. Therefore, we assessed the distribution of interactions between mistletoes and hosts in the Brazilian Pantanal and characterized the network structure in relation to nestedness and modularity. Interactions were highly asymmetric, with mistletoes presenting low host specificity (i.e., weak dependence) and with hosts being highly susceptible to mistletoe-specific infections. We found a non-nested and modular pattern of interactions, wherein each mistletoe species interacted with a particular set of host species. Psittacanthus spp. infected more species and individuals and also caused a high number of infections per individual, whereas the other mistletoes showed a more specialized pattern of infection. For this reason, Psittacanthus spp. were regarded as module hubs while the other mistletoe species showed a peripheral role. We hypothesize that this pattern is primarily the result of different seed dispersal systems. Although all mistletoe species in our study are bird dispersed, the frugivorous assemblage of Psittacanthus spp. is composed of a larger suite of birds, whereas Phoradendron are mainly dispersed by Euphonia species. The larger assemblage of bird species dispersing Psittacanthus seeds may also increase the number of hosts colonized and, consequently, its dominance in the study area. Nevertheless, other restrictions on the interactions among species, such as the differential capacity of mistletoe infections, defense strategies of hosts and habitat types, can also generate or enhance the observed pattern.

Cation Distribution and Local Order in Mixed Sodium Metaphosphate Glasses

Two structural properties in mixed alkali metal phosphate glasses that seem to be crucial to the development of the mixed ion effect in dc conductivity were systematically analyzed in Na mixed metaphosphates: the local order around the mobile species, and their distribution and mixing in the glass network. The set of glasses considered here, Na1-xMxPO3 with M = Li, Ag, K, Rb, and Cs and 0 <= x <= 1, encompass a broad degree of size mismatch between the mixed cation species. A comprehensive solid-state nuclear magnetic resonance study was carried out using P-31 MAS, Na-23 triple quantum MAS, Rb-87 QCPMG, P-31-Na-23 REDOR, Na-23-Li-7 and Li-7-Li-6 SEDOR, and Na-23 spin echo decay. It was observed that the arrangement of P atoms around Na in the mixed glasses was indistinguishable from that observed in the NaPO3 glass. However, systematic distortions in the local structure of the 0 environments around Na were observed, related to the presence of the second cation. The average Na-O distances show an expansion/compression When Na+ ions are replaced by cations with respectively smaller/bigger radii. The behavior of the nuclear electric quadrupole coupling. constants indicates that this expansion reduces the local symmetry, while the compression produces the opposite effect These effects become marginally small when the site mismatch between the cations is small, as in Na-Ag mixed glasses. The present study confirms the intimate mixing of cation species at the atomic scale, but clear deviations from random mixing were detected in systems with larger alkali metal ions (Cs-Na, K-Na, Rb-Na). In contrast, no deviations from the statistical ion mixture were found in the systems Ag-Na and Li-Na, where mixed cations are either of radii comparable to (Ag+) or smaller than (Li+) Na+. The set of results supports two fundamental structural features of the models proposed to explain the mixed ion effect: the. structural specificity of the sites occupied by each cation species and their mixing at the atomic scale.

Fog- and cloud-induced aerosol modification observed by the Aerosol Robotic Network (AERONET)

Large fine mode-dominated aerosols (submicron radius) in size distributions retrieved from the Aerosol Robotic Network (AERONET) have been observed after fog or low-altitude cloud dissipation events. These column-integrated size distributions have been obtained at several sites in many regions of the world, typically after evaporation of low-altitude cloud such as stratocumulus or fog. Retrievals with cloud-processed aerosol are sometimes bimodal in the accumulation mode with the larger-size mode often similar to 0.4-0.5 mu m radius (volume distribution); the smaller mode, typically similar to 0.12 to similar to 0.20 mu m, may be interstitial aerosol that were not modified by incorporation in droplets and/or aerosol that are less hygroscopic in nature. Bimodal accumulation mode size distributions have often been observed from in situ measurements of aerosols that have interacted with clouds, and AERONET size distribution retrievals made after dissipation of cloud or fog are in good agreement with particle sizes measured by in situ techniques for cloud-processed aerosols. Aerosols of this type and large size range (in lower concentrations) may also be formed by cloud processing in partly cloudy conditions and may contribute to the "shoulder" of larger-size particles in the accumulation mode retrievals, especially in regions where sulfate and other soluble aerosol are a significant component of the total aerosol composition. Observed trends of increasing aerosol optical depth (AOD) as fine mode radius increased suggests higher AOD in the near-cloud environment and higher overall AOD than typically obtained from remote sensing owing to bias toward sampling at low cloud fraction.

Structure and Ionic Conductivity in the Mixed-Network Former Chalcogenide Glass System [Na2S](2/3)[(B2S3)(x)(P2S5)(1-x)](1/3)

Glasses in the system [Na2S](2/3)[(B2S3)(x)(P2S5)(1-x)](1/3) (0.0 <= x <= 1.0) were prepared by the melt quenching technique, and their properties were characterized by thermal analysis and impedance spectroscopy. Their atomic-level structures were comprehensively characterized by Raman spectroscopy and B-11, P-31, and Na-23 high resolution solid state magic-angle spinning (MAS) NMR techniques. P-31 MAS NMR peak assignments were made by the presence or absence of homonuclear indirect P-31-P-31 spin-spin interactions as detected using homonuclear J-resolved and refocused INADEQUATE techniques. The extent of B-S-P connectivity in the glassy network was quantified by P-31{B-11} and B-11{P-31} rotational echo double resonance spectroscopy. The results clearly illustrate that the network modifier alkali sulfide, Na2S, is not proportionally shared between the two network former components, B and P. Rather, the thiophosphate (P) component tends to attract a larger concentration of network modifier species than predicted by the bulk composition, and this results in the conversion of P2S74-, pyrothiophosphate, Na/P = 2:1, units into PS43-, orthothiophosphate, Na/P = 3:1, groups. Charge balance is maintained by increasing the net degree of polymerization of the thioborate (B) units through the formation of covalent bridging sulfur (BS) units, B S B. Detailed inspection of the B-11 MAS NMR spectra reveals that multiple thioborate units are formed, ranging from neutral BS3/2 groups all the way to the fully depolymerized orthothioborate (BS33-) species. On the basis of these results, a comprehensive and quantitative structural model is developed for these glasses, on the basis of which the compositional trends in the glass transition temperatures (T-g) and ionic conductivities can be rationalized. Up to x = 0.4, the dominant process can be described in a simplified way by the net reaction equation P-1 + B-1 reversible arrow P-0 + B-4, where the superscripts denote the number of BS atoms for the respective network former species. Above x = 0.4, all of the thiophosphate units are of the P-0 type and both pyro-(B-1) and orthothioborate (B-0) species make increasing contributions to the network structure with increasing x. In sharp contrast to the situation in sodium borophosphate glasses, four-coordinated thioborate species are generally less abundant and heteroatomic B-S-P linkages appear to not exist. On the basis of this structural information, compositional trends in the ionic conductivities are discussed in relation to the nature of the charge-compensating anionic species and the spatial distribution of the charge carriers.

LARGE-SCALE DISTRIBUTION OF ARRIVAL DIRECTIONS OF COSMIC RAYS DETECTED ABOVE 10(18) eV AT THE PIERRE AUGER OBSERVATORY

A thorough search for large-scale anisotropies in the distribution of arrival directions of cosmic rays detected above 10(18) eV at the Pierre Auger Observatory is presented. This search is performed as a function of both declination and right ascension in several energy ranges above 10(18) eV, and reported in terms of dipolar and quadrupolar coefficients. Within the systematic uncertainties, no significant deviation from isotropy is revealed. Assuming that any cosmic-ray anisotropy is dominated by dipole and quadrupole moments in this energy range, upper limits on their amplitudes are derived. These upper limits allow us to test the origin of cosmic rays above 10(18) eV from stationary Galactic sources densely distributed in the Galactic disk and predominantly emitting light particles in all directions.

Quantification of Short and Medium Range Order in Mixed Network Former Glasses of the System GeO2-NaPO3: A Combined NMR and X-ray Photoelectron Spectroscopy Study

Glasses in the system xGeO(2)-(1-x)NaPO3 (0 <= x <= 0.50) were prepared by conventional melting quenching and characterized by thermal analysis, Raman spectroscopy, X-ray photoelectron spectroscopy (XPS), and P-31 nuclear magnetic resonance (MAS NMR) techniques. The deconvolution of the latter spectra was aided by homonuclear J-resolved and refocused INADEQUATE techniques. The combined analyses of P-31 MAS NMR and O-1s XPS lineshapes, taking charge and mass balance considerations into account, yield the detailed quantitative speciations of the phosphorus, germanium, and oxygen atoms and their respective connectivities. An internally consistent description is possible without invoking the formation of higher-coordinated germanium species in these glasses, in agreement with experimental evidence in the literature. The structure can be regarded, to a first approximation, as a network consisting of P-(2) and P-(3) tetrahedra linked via four-coordinate germanium. As implied by the appearance of P-(3) units, there is a moderate extent of network modifier sharing between phosphate and germanate network formers, as expressed by the formal melt reaction P-(2) + Ge-(4) -> P-(3) + Ge-(3). The equilibrium constant of this reaction is estimated as K = 0.52 +/- 0.11, indicating a preferential attraction of network modifier by the phosphorus component. These conclusions are qualitatively supported by Raman spectroscopy as well as P-31{Na-23} and P-31{Na-23} rotational echo double resonance (REDOR) NMR results. The combined interpretation of O-1s XPS and P-31 MAS NMR spectra shows further that there are clear deviations from a random connectivity scenario: heteroatomic P-O-Ge linkages are favored over homoatomic P-O-P and Ge-O-Ge linkages.

Groups of services delivered by Brazilian branchless banking and respective network integration models

Over the last decade, Brazil has pioneered an innovative model of branchless banking, known as correspondent banking, involving distribution partnership between banks, several kinds of retailers and a variety of other participants, which have allowed an unprecedented growth in bank outreach and became a reference worldwide. However, despite the extensive number of studies recently developed focusing on Brazilian branchless banking, there exists a clear research gap in the literature. It is still necessary to identify the different business configurations involving network integration through which the branchless banking channel can be structured, as well as the way they relate to the range of bank services delivered. Given this gap, our objective is to investigate the relationship between network integration models and services delivered through the branchless banking channel. Based on twenty interviews with managers involved with the correspondent banking business and data collected on almost 300 correspondent locations, our research is developed in two steps. First, we created a qualitative taxonomy through which we identified three classes of network integration models. Second, we performed a cluster analysis to explain the groups of financial services that fit each model. By contextualizing correspondents' network integration processes through the lens of transaction costs economics, our results suggest that the more suited to deliver social-oriented, "pro-poor'' services the channel is, the more it is controlled by banks. This research offers contributions to managers and policy makers interested in understanding better how different correspondent banking configurations are related with specific portfolios of services. Researchers interested in the subject of branchless banking can also benefit from the taxonomy presented and the transaction costs analysis of this kind of banking channel, which has been adopted in a number of developing countries all over the world now. (C) 2011 Elsevier B.V. All rights reserved.

Modularity and evolutionary constraints in a baculovirus gene regulatory network

Abstract Background The structure of regulatory networks remains an open question in our understanding of complex biological systems. Interactions during complete viral life cycles present unique opportunities to understand how host-parasite network take shape and behave. The Anticarsia gemmatalis multiple nucleopolyhedrovirus (AgMNPV) is a large double-stranded DNA virus, whose genome may encode for 152 open reading frames (ORFs). Here we present the analysis of the ordered cascade of the AgMNPV gene expression. Results We observed an earlier onset of the expression than previously reported for other baculoviruses, especially for genes involved in DNA replication. Most ORFs were expressed at higher levels in a more permissive host cell line. Genes with more than one copy in the genome had distinct expression profiles, which could indicate the acquisition of new functionalities. The transcription gene regulatory network (GRN) for 149 ORFs had a modular topology comprising five communities of highly interconnected nodes that separated key genes that are functionally related on different communities, possibly maximizing redundancy and GRN robustness by compartmentalization of important functions. Core conserved functions showed expression synchronicity, distinct GRN features and significantly less genetic diversity, consistent with evolutionary constraints imposed in key elements of biological systems. This reduced genetic diversity also had a positive correlation with the importance of the gene in our estimated GRN, supporting a relationship between phylogenetic data of baculovirus genes and network features inferred from expression data. We also observed that gene arrangement in overlapping transcripts was conserved among related baculoviruses, suggesting a principle of genome organization. Conclusions Albeit with a reduced number of nodes (149), the AgMNPV GRN had a topology and key characteristics similar to those observed in complex cellular organisms, which indicates that modularity may be a general feature of biological gene regulatory networks.

The Brazilian Network for HIV-1 Genotyping External Quality Control Assurance Programme

The Brazilian network for genotyping is composed of 21 laboratories that perform and analyze genotyping tests for all HIV-infected patients within the public system, performing approximately 25,000 tests per year. We assessed the interlaboratory and intralaboratory reproducibility of genotyping systems by creating and implementing a local external quality control evaluation. Plasma samples from HIV-1-infected individuals (with low and intermediate viral loads) or RNA viral constructs with specific mutations were used. This evaluation included analyses of sensitivity and specificity of the tests based on qualitative and quantitative criteria, which scored laboratory performance on a 100-point system. Five evaluations were performed from 2003 to 2008, with 64% of laboratories scoring over 80 points in 2003, 81% doing so in 2005, 56% in 2006, 91% in 2007, and 90% in 2008 (Kruskal-Wallis, p = 0.003). Increased performance was aided by retraining laboratories that had specific deficiencies. The results emphasize the importance of investing in laboratory training and interpretation of DNA sequencing results, especially in developing countries where public (or scarce) resources are used to manage the AIDS epidemic.

Multi-objective evolutionary algorithm for single and multiple fault service restoration in large-scale distribution systems

Network reconfiguration for service restoration (SR) in distribution systems is a complex optimization problem. For large-scale distribution systems, it is computationally hard to find adequate SR plans in real time since the problem is combinatorial and non-linear, involving several constraints and objectives. Two Multi-Objective Evolutionary Algorithms that use Node-Depth Encoding (NDE) have proved able to efficiently generate adequate SR plans for large distribution systems: (i) one of them is the hybridization of the Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) with NDE, named NSGA-N; (ii) the other is a Multi-Objective Evolutionary Algorithm based on subpopulation tables that uses NDE, named MEAN. Further challenges are faced now, i.e. the design of SR plans for larger systems as good as those for relatively smaller ones and for multiple faults as good as those for one fault (single fault). In order to tackle both challenges, this paper proposes a method that results from the combination of NSGA-N, MEAN and a new heuristic. Such a heuristic focuses on the application of NDE operators to alarming network zones according to technical constraints. The method generates similar quality SR plans in distribution systems of significantly different sizes (from 3860 to 30,880 buses). Moreover, the number of switching operations required to implement the SR plans generated by the proposed method increases in a moderate way with the number of faults.

Middleware for quality-based context distribution in mobile systems

The continuous advancements and enhancements of wireless systems are enabling new compelling scenarios where mobile services can adapt according to the current execution context, represented by the computational resources available at the local device, current physical location, people in physical proximity, and so forth. Such services called context-aware require the timely delivery of all relevant information describing the current context, and that introduces several unsolved complexities, spanning from low-level context data transmission up to context data storage and replication into the mobile system. In addition, to ensure correct and scalable context provisioning, it is crucial to integrate and interoperate with different wireless technologies (WiFi, Bluetooth, etc.) and modes (infrastructure-based and ad-hoc), and to use decentralized solutions to store and replicate context data on mobile devices. These challenges call for novel middleware solutions, here called Context Data Distribution Infrastructures (CDDIs), capable of delivering relevant context data to mobile devices, while hiding all the issues introduced by data distribution in heterogeneous and large-scale mobile settings. This dissertation thoroughly analyzes CDDIs for mobile systems, with the main goal of achieving a holistic approach to the design of such type of middleware solutions. We discuss the main functions needed by context data distribution in large mobile systems, and we claim the precise definition and clean respect of quality-based contracts between context consumers and CDDI to reconfigure main middleware components at runtime. We present the design and the implementation of our proposals, both in simulation-based and in real-world scenarios, along with an extensive evaluation that confirms the technical soundness of proposed CDDI solutions. Finally, we consider three highly heterogeneous scenarios, namely disaster areas, smart campuses, and smart cities, to better remark the wide technical validity of our analysis and solutions under different network deployments and quality constraints.

Quantifying the OH radical by global scale NMHC measurements from the NOAA - ESRL cooperative flask sampling network

Summary PhD Thesis Jan Pollmann: This thesis focuses on global scale measurements of light reactive non-methane hydrocarbon (NMHC), in the volatility range from ethane to toluene with a special focus on ethane, propane, isobutane, butane, isopentane and pentane. Even though they only occur at the ppt level (nmol mol-1) in the remote troposphere these species can yield insight into key atmospheric processes. An analytical method was developed and subsequently evaluated to analyze NMHC from the NOAA – ERSL cooperative air sampling network. Potential analytical interferences through other atmospheric trace gases (water vapor and ozone) were carefully examined. The analytical parameters accuracy and precision were analyzed in detail. It was proven that more than 90% of the data points meet the Global Atmospheric Watch (GAW) data quality objective. Trace gas measurements from 28 measurement stations were used to derive the global atmospheric distribution profile for 4 NMHC (ethane, propane, isobutane, butane). A close comparison of the derived ethane data with previously published reports showed that northern hemispheric ethane background mixing ratio declined by approximately 30% since 1990. No such change was observed for southern hemispheric ethane. The NMHC data and trace gas data supplied by NOAA ESRL were used to estimate local diurnal averaged hydroxyl radical (OH) mixing ratios by variability analysis. Comparison of the variability derived OH with directly measured OH and modeled OH mixing ratios were found in good agreement outside the tropics. Tropical OH was on average two times higher than predicted by the model. Variability analysis was used to assess the effect of chlorine radicals on atmospheric oxidation chemistry. It was found that Cl is probably not of significant relevance on a global scale.