The choice of the best among the shortest routes in transparent optical networks

This work introduces the problem of the best choice among M combinations of the shortest paths for dynamic provisioning of lightpaths in all-optical networks. To solve this problem in an optimized way (shortest path and load balance), a new fixed routing algorithm, named Best among the Shortest Routes (BSR), is proposed. The BSR`s performance is compared in terms of blocking probability and network utilization with Dijkstra`s shortest path algorithm and others algorithms proposed in the literature. The evaluated scenarios include several representative topologies for all-optical networking and different wavelength conversion architectures. For all studied scenarios, BSR achieved superior performance. (C) 2010 Elsevier B.V. All rights reserved.

Chain motifs: The tails and handles of complex networks

A great part of the interest in complex networks has been motivated by the presence of structured, frequently nonuniform, connectivity. Because diverse connectivity patterns tend to result in distinct network dynamics, and also because they provide the means to identify and classify several types of complex network, it becomes important to obtain meaningful measurements of the local network topology. In addition to traditional features such as the node degree, clustering coefficient, and shortest path, motifs have been introduced in the literature in order to provide complementary descriptions of the network connectivity. The current work proposes a different type of motif, namely, chains of nodes, that is, sequences of connected nodes with degree 2. These chains have been subdivided into cords, tails, rings, and handles, depending on the type of their extremities (e.g., open or connected). A theoretical analysis of the density of such motifs in random and scale-free networks is described, and an algorithm for identifying these motifs in general networks is presented. The potential of considering chains for network characterization has been illustrated with respect to five categories of real-world networks including 16 cases. Several interesting findings were obtained, including the fact that several chains were observed in real-world networks, especially the world wide web, books, and the power grid. The possibility of chains resulting from incompletely sampled networks is also investigated.

Communication structure of cortical networks

Large-scale cortical networks exhibit characteristic topological properties that shape communication between brain regions and global cortical dynamics. Analysis of complex networks allows the description of connectedness, distance, clustering, and centrality that reveal different aspects of how the network's nodes communicate. Here, we focus on a novel analysis of complex walks in a series of mammalian cortical networks that model potential dynamics of information flow between individual brain regions. We introduce two new measures called absorption and driftness. Absorption is the average length of random walks between any two nodes, and takes into account all paths that may diffuse activity throughout the network. Driftness is the ratio between absorption and the corresponding shortest path length. For a given node of the network, we also define four related measurements, namely in-and out-absorption as well as in-and out-driftness, as the averages of the corresponding measures from all nodes to that node, and from that node to all nodes, respectively. We find that the cat thalamo-cortical system incorporates features of two classic network topologies, Erdos-Renyi graphs with respect to in-absorption and in-driftness, and configuration models with respect to out-absorption and out-driftness. Moreover, taken together these four measures separate the network nodes based on broad functional roles (visual, auditory, somatomotor, and frontolimbic).

Connection Admission Control for a WDM Optical Network Based on Traffic Monitoring and Bandwidth Release

We proposed a connection admission control (CAC) to monitor the traffic in a multi-rate WDM optical network. The CAC searches for the shortest path connecting source and destination nodes, assigns wavelengths with enough bandwidth to serve the requests, supervises the traffic in the most required nodes, and if needed activates a reserved wavelength to release bandwidth according to traffic demand. We used a scale-free network topology, which includes highly connected nodes ( hubs), to enhance the monitoring procedure. Numerical results obtained from computational simulations show improved network performance evaluated in terms of blocking probability.

On the basic reproduction number and the topological properties of the contact network: An epidemiological study in mainly locally connected cellular automata

We study the spreading of contagious diseases in a population of constant size using susceptible-infective-recovered (SIR) models described in terms of ordinary differential equations (ODEs) and probabilistic cellular automata (PCA). In the PCA model, each individual (represented by a cell in the lattice) is mainly locally connected to others. We investigate how the topological properties of the random network representing contacts among individuals influence the transient behavior and the permanent regime of the epidemiological system described by ODE and PCA. Our main conclusions are: (1) the basic reproduction number (commonly called R(0)) related to a disease propagation in a population cannot be uniquely determined from some features of transient behavior of the infective group; (2) R(0) cannot be associated to a unique combination of clustering coefficient and average shortest path length characterizing the contact network. We discuss how these results can embarrass the specification of control strategies for combating disease propagations. (C) 2009 Elsevier B.V. All rights reserved.

Investigating relationships within and between category networks in Wikipedia

This work maps and analyses cross-citations in the areas of Biology, Mathematics, Physics and Medicine in the English version of Wikipedia, which are represented as an undirected complex network where the entries correspond to nodes and the citations among the entries are mapped as edges. We found a high value of clustering coefficient for the areas of Biology and Medicine, and a small value for Mathematics and Physics. The topological organization is also different for each network, including a modular structure for Biology and Medicine, a sparse structure for Mathematics and a dense core for Physics. The networks have degree distributions that can be approximated by a power-law with a cut-off. The assortativity of the isolated networks has also been investigated and the results indicate distinct patterns for each subject. We estimated the betweenness centrality of each node considering the full Wikipedia network, which contains the nodes of the four subjects and the edges between them. In addition, the average shortest path length between the subjects revealed a close relationship between the subjects of Biology and Physics, and also between Medicine and Physics. Our results indicate that the analysis of the full Wikipedia network cannot predict the behavior of the isolated categories since their properties can be very different from those observed in the full network. (C) 2011 Elsevier Ltd. All rights reserved.

On the efficiency of data representation on the modeling and characterization of complex networks

Specific choices about how to represent complex networks can have a substantial impact on the execution time required for the respective construction and analysis of those structures. In this work we report a comparison of the effects of representing complex networks statically by adjacency matrices or dynamically by adjacency lists. Three theoretical models of complex networks are considered: two types of Erdos-Renyi as well as the Barabasi-Albert model. We investigated the effect of the different representations with respect to the construction and measurement of several topological properties (i.e. degree, clustering coefficient, shortest path length, and betweenness centrality). We found that different forms of representation generally have a substantial effect on the execution time, with the sparse representation frequently resulting in remarkably superior performance. (C) 2011 Elsevier B.V. All rights reserved.

Resilience of protein-protein interaction networks as determined by their large-scale topological features

The relationship between the structure and function of biological networks constitutes a fundamental issue in systems biology. Particularly, the structure of protein-protein interaction networks is related to important biological functions. In this work, we investigated how such a resilience is determined by the large scale features of the respective networks. Four species are taken into account, namely yeast Saccharomyces cerevisiae, worm Caenorhabditis elegans, fly Drosophila melanogaster and Homo sapiens. We adopted two entropy-related measurements (degree entropy and dynamic entropy) in order to quantify the overall degree of robustness of these networks. We verified that while they exhibit similar structural variations under random node removal, they differ significantly when subjected to intentional attacks (hub removal). As a matter of fact, more complex species tended to exhibit more robust networks. More specifically, we quantified how six important measurements of the networks topology (namely clustering coefficient, average degree of neighbors, average shortest path length, diameter, assortativity coefficient, and slope of the power law degree distribution) correlated with the two entropy measurements. Our results revealed that the fraction of hubs and the average neighbor degree contribute significantly for the resilience of networks. In addition, the topological analysis of the removed hubs indicated that the presence of alternative paths between the proteins connected to hubs tend to reinforce resilience. The performed analysis helps to understand how resilience is underlain in networks and can be applied to the development of protein network models.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests. (C) 2009 Elsevier B.V. All rights reserved.

A hybrid heuristic for the multi-plant capacitated lot sizing problem with setup carry-over

This paper addresses the capacitated lot sizing problem (CLSP) with a single stage composed of multiple plants, items and periods with setup carry-over among the periods. The CLSP is well studied and many heuristics have been proposed to solve it. Nevertheless, few researches explored the multi-plant capacitated lot sizing problem (MPCLSP), which means that few solution methods were proposed to solve it. Furthermore, to our knowledge, no study of the MPCLSP with setup carry-over was found in the literature. This paper presents a mathematical model and a GRASP (Greedy Randomized Adaptive Search Procedure) with path relinking to the MPCLSP with setup carry-over. This solution method is an extension and adaptation of a previously adopted methodology without the setup carry-over. Computational tests showed that the improvement of the setup carry-over is significant in terms of the solution value with a low increase in computational time.

Simulated annealing with adaptive neighborhood: A case study in off-line robot path planning

Simulated annealing (SA) is an optimization technique that can process cost functions with degrees of nonlinearities, discontinuities and stochasticity. It can process arbitrary boundary conditions and constraints imposed on these cost functions. The SA technique is applied to the problem of robot path planning. Three situations are considered here: the path is represented as a polyline; as a Bezier curve; and as a spline interpolated curve. In the proposed SA algorithm, the sensitivity of each continuous parameter is evaluated at each iteration increasing the number of accepted solutions. The sensitivity of each parameter is associated to its probability distribution in the definition of the next candidate. (C) 2010 Elsevier Ltd. All rights reserved.

Path integral representations in noncommutative quantum mechanics and noncommutative version of Berezin-Marinov action

It is known that the actions of field theories on a noncommutative space-time can be written as some modified (we call them theta-modified) classical actions already on the commutative space-time (introducing a star product). Then the quantization of such modified actions reproduces both space-time noncommutativity and the usual quantum mechanical features of the corresponding field theory. In the present article, we discuss the problem of constructing theta-modified actions for relativistic QM. We construct such actions for relativistic spinless and spinning particles. The key idea is to extract theta-modified actions of the relativistic particles from path-integral representations of the corresponding noncommutative field theory propagators. We consider the Klein-Gordon and Dirac equations for the causal propagators in such theories. Then we construct for the propagators path-integral representations. Effective actions in such representations we treat as theta-modified actions of the relativistic particles. To confirm the interpretation, we canonically quantize these actions. Thus, we obtain the Klein-Gordon and Dirac equations in the noncommutative field theories. The theta-modified action of the relativistic spinning particle is just a generalization of the Berezin-Marinov pseudoclassical action for the noncommutative case.

Production and body composition traits of broilers in relation to breast weight evaluated by path analysis

Breast weight has great economic importance in poultry industry, and may be associated with other variables. This work aimed to estimate phenotypic correlations between performance (live body weight at 7 and 28 days, and at slaughter, and depth of the breast muscle measured by ultrasonography), carcass (eviscerated body weight and leg weight) and body composition (heart, liver and abdominal fat weight) traits in a broiler line, and quantify the direct and indirect influence of these traits on breast weight. Path analysis was used by expanding the matrix of partial correlation in coefficients which give the direct influence of one trait on another, regardless the effect of the other traits. The simultaneous maintenance of live body weight at slaughter and eviscerated body weight in the matrix of correlations might be harmful for statistical analysis involving systems of normal equations, like path analysis, due to the observed multicollinearity. The live body weight at slaughter and the depth of the breast muscle as measured by ultrasonography directly affected breast weight and were identified as the most responsible factors for the magnitude of the correlation coefficients obtained between the studied traits and breast weight. Individual pre-selection for these traits could favor an increased breast weight in the future reproducer candidates of this line if the broilers' environmental conditions and housing are maintained, since the live body weight at slaughter and the depth of breast muscle measured by ultrasonography were directly related to breast weight.

O difícil acesso a serviços de média complexidade do SUS: o caso da cidade de São Paulo, Brasil

O acesso aos serviços de média complexidade tem sido apontado, por gestores e pesquisadores, como um dos entraves para a efetivação da integralidade do SUS. Este artigo teve o objetivo de avaliar mecanismos utilizados pela gestão do SUS, no município de São Paulo, para garantir acesso à assistência de média complexidade, durante o período de 2005 a 2008. Optou-se pela estratégia de estudo de caso, utilizando as seguintes fontes de evidência: entrevistas com gestores; grupo focal com usuários e observação participante. Utilizouas técnica de análise temática, a partir do referencial teórico da integralidade da assistência, na dimensão da organização de serviços. Buscou-se descrever os caminhos percorridos pelos usuários para acessar os serviços da média complexidade, a partir da visão dos gestores e dos próprios usuários. A média complexidade foi identificada, pelos gestores, como o "gargalo" do SUS e um dos principais obstáculos para a construção da integralidade. Para enfrentar essa situação, o gestor municipal investiu na informatização dos serviços, como medida isolada e, ainda, sem considerar a necessidade dos usuários. Sendo assim, essa incorporação tecnológica teve pouco impacto na melhoria do acesso, o que se confirmou no relato dos usuários. Discute-se que para o enfrentamento de um problema tão complexo são necessárias ações articuladas, tanto no âmbito da política de saúde, quanto da organização dos serviços, bem como a (re)organização do processo de trabalho em todos os níveis do sistema de saúde.