Local optima networks of hard combinatorial landscapes

Combinatorial optimization involves finding an optimal solution in a finite set of options; many everyday life problems are of this kind. However, the number of options grows exponentially with the size of the problem, such that an exhaustive search for the best solution is practically infeasible beyond a certain problem size. When efficient algorithms are not available, a practical approach to obtain an approximate solution to the problem at hand, is to start with an educated guess and gradually refine it until we have a good-enough solution. Roughly speaking, this is how local search heuristics work. These stochastic algorithms navigate the problem search space by iteratively turning the current solution into new candidate solutions, guiding the search towards better solutions. The search performance, therefore, depends on structural aspects of the search space, which in turn depend on the move operator being used to modify solutions. A common way to characterize the search space of a problem is through the study of its fitness landscape, a mathematical object comprising the space of all possible solutions, their value with respect to the optimization objective, and a relationship of neighborhood defined by the move operator. The landscape metaphor is used to explain the search dynamics as a sort of potential function. The concept is indeed similar to that of potential energy surfaces in physical chemistry. Borrowing ideas from that field, we propose to extend to combinatorial landscapes the notion of the inherent network formed by energy minima in energy landscapes. In our case, energy minima are the local optima of the combinatorial problem, and we explore several definitions for the network edges. At first, we perform an exhaustive sampling of local optima basins of attraction, and define weighted transitions between basins by accounting for all the possible ways of crossing the basins frontier via one random move. Then, we reduce the computational burden by only counting the chances of escaping a given basin via random kick moves that start at the local optimum. Finally, we approximate network edges from the search trajectory of simple search heuristics, mining the frequency and inter-arrival time with which the heuristic visits local optima. Through these methodologies, we build a weighted directed graph that provides a synthetic view of the whole landscape, and that we can characterize using the tools of complex networks science. We argue that the network characterization can advance our understanding of the structural and dynamical properties of hard combinatorial landscapes. We apply our approach to prototypical problems such as the Quadratic Assignment Problem, the NK model of rugged landscapes, and the Permutation Flow-shop Scheduling Problem. We show that some network metrics can differentiate problem classes, correlate with problem non-linearity, and predict problem hardness as measured from the performances of trajectory-based local search heuristics.

Institutional change and the evolution of the regulatory state: evidence from the Swiss case

This article examines institutional change in a case that was expected to be particularly resilient but showed considerable structural transformation: the institutionalization of the regulatory state in Switzerland. This process is illustrated through the establishment of independent regulatory agencies (IRAs) in four areas: banking and finance; telecommunications; electricity; and competition. The theoretical framework developed by Streeck, Thelen and Mahoney is used to explore hypotheses about the modes of institutional change, with the methodology of diachronic within-case study. Results confirm only partially the expectations, pointing to layering and displacement as the prevalent modes of change. The concluding part discusses the type and the direction of change as additional explanatory factors.

Characterization of Reward Functions in Networks with Costs

In this paper we study network structures in which the possibilities for cooperation are restricted and can not be described by a cooperative game. The benefits of a group of players depend on how these players are internally connected. One way to represent this type of situations is the so-called reward function, which represents the profits obtainable by the total coalition if links can be used to coordinate agents' actions. The starting point of this paper is the work of Vilaseca et al. where they characterized the reward function. We concentrate on those situations where there exist costs for establishing communication links. Given a reward function and a costs function, our aim is to analyze under what conditions it is possible to associate a cooperative game to it. We characterize the reward function in networks structures with costs for establishing links by means of two conditions, component permanence and component additivity. Finally, an economic application is developed to illustrate the main theoretical result.

Promoting the Creation, Share and Use of OERs through Open Repositories and Social Networks

In this paper we discuss and analyze the process of using a learning object repository and building a social network on the top of it, including aspects related to open source technologies, promoting the use of the repository by means of social networks and helping learners to develop their own learning paths.

Role of CD4+CD25+ regulatory T cells in the antigen specific induction of tolerance "via" the nasal route

ABSTRACT Asthma is a complex inflammatory syndrome caused by environmental factors in predisposed individuals (atopics). Its severity correlates with the presence of activated T lymphocytes and eosinophils in the bronchoalveolar lavage fluid (BALF). Induction of tolerance via the nasal route results in reduced recruitment of eosinophils into BALF upon challenge, inhibition of TH2 pro-inflammatory cytokine secretion and T cell hyporesponsiveness. Recently, CD4+CD25+ natural regulatory T cells (Treg) were proposed as key players in controlling the development of asthma and allergic disease. The objective of the present study is to investigate the role of CD4+CD25+ regulatory T cells in the mechanisms leading to tolerance in an established model of asthma. In this goal we depleted CD4+CD25+ T cells at different times during asthma and tolerance induction protocol in mice and looked at efficiency of tolerization (intranasal application of high dose of allergen) in the absence of natural Tregs. First, ovalbumin-sensitized mice were depleted of CD25+ T cells by intraperitoneal injection of anti-CD25 mAb (PC61) either for along-term (repeated injections of anti-CD25 from day 31 until the end of the protocol) or a short-term period (single injection of anti-CD25 before or after tolerance induction). We demonstrated that the long-term depletion of CD4+CD25+ T cells severely hampered tolerance induction (marked enhancement in eosinophil recruitment into BALF and a vigorous antigen specific T cell response to OVA upon allergen challenge) whereas transient depletions were not sufficient to do so. We then characterized T cell subsets by flow cytometry and observed that a large part of CD4+CD25+ T cells express Foxp3, an established marker of regulatory T cells. We also tested in-vitro suppressor activity of CD4+CD25+ T cells from tolerized mice by cell proliferation assay in coculture and observed a strong suppressive activity. Our data suggest that CD4+CD25+ T cells with regulatory properties play a crucial role in the induction of tolerance via the nasal route. The relationship between CD25+ natural Treg and inducible IL-10+ TRl-type Treg will have to be defined. RESUME L'asthme est un syndrome inflammatoire complexe provoqué par des facteurs environnementaux chez des individus génétiquement prédisposés (atopiques). Sa sévérité corrèle avec la présence des lymphocytes T activés et d'éosinophiles dans le lavage bronchoalvéolaire (BAL). L'induction de la tolérance par la voie nasale résulte en une diminution du recrutement des eosinophils dans le BAL, une inhibition de la sécrétion de cytokines pro-inflammatoires de type TH2 et de l'hypo-réponse des cellules T à l'allergène. Récemment, les cellules régulatrices «naturelles » de type CD4+CD25+ T (Tregs) ont été proposées comme acteurs essentiels dans le développement de l'asthme et de l'allergie. L'objectif de cette étude est d'étudier le rôle des cellules régulatrices CD4+CD25+ T dans les mécanismes menant à la tolérance dans un modèle établi d'asthme. Dans ce but nous avons déplété les cellules de CD4+CD25+ T à différents temps au cours du protocole d'induction d'asthme et de tolérance et nous avons regardé l'efficacité de l'induction de tolérance (application intranasale d'une dose importante d'allergène) en l'absence de Tregs. Dans un premier temps des souris sensibilisées à l'ovalbumine (OVA) ont été déplétées en cellules CD25+ T par l'injection intrapéritonéale d'anti-CD25 mAb (PC61) pour une longue période (injections répétées d'anti-CD25 du jour 31 jusqu'à la fin du protocole) ou pour une courte période (injection unique d'anti-CD25 avant ou après l'induction de tolérance). Nous avons démontré que la déplétion à long t erme des cellules de CD4+CD25+ T a empêché l'induction de tolérance (recrutement accru d'éosinophiles dans le BAL et une réponse vigoureuse des cellules T spécifiques de l'antigène après exposition à l'allergène) tandis des déplétions à court-terme n'ont pas cet effet. Nous avons ensuite caractérisé des sous-populations de cellules T par cytométrie de flux. Nous avons observé que la majorité des cellules CD4+CD25+ T expriment Foxp3, un marqueur établi des cellules régulatrices. Nous avons également examiné in vitro l'activité régulatrice des cellules T CD4+CD25+ issues de souris tolérisées. La prolifération de cellules T en coculture a démontré une forte activité suppressive des cellules CD4+CD25+. Nos données suggèrent que des cellules T CD4+CD25+ ayant des propriétés régulatrices jouent un rôle crucial dans l'induction de la tolérance par la voie nasale. Le rapport entre les cellules régulatrices naturelles CD4+CD25+ et les cellules régulatrices inductible de type TR1 I1-10+ devra être défini. RESUME DESTINE A UN LARGE PUBLIC L'asthme est une maladie inflammatoire des bronches, caractérisée par des crises de dyspnée (gêne respiratoire) témoignant d'une activation brutale des muscles bronchoconstricteurs, auxquelles s'associent un oedème et une hypersécrétion des muqueuses des voies aériennes ainsi qu'une importante production d'anticorps de l'allergie (IgE). Chez la plupart des enfants atteints et chez près de la moitié des adultes concernés par l'asthme, c'est une allergie à des substances présentes dans l'air environnant (acariens, pollens ou poils d'animaux) qui est à l'origine de la maladie. . Le traitement actuel de l'asthme repose d'une part sur le soulagement des symptômes grâce à des produits à base de stéroïdes ou des bronchodilatateurs. D'autre part, l'immunothérapie spécifique (aussi appelée désensibilisation) permet d'améliorer l'asthme et de «reprogrammer» le système immunitaire. C'est à ce jour, le seul moyen connu de faire régresser une allergie. Cependant l'immunothérapie prend beaucoup de temps (3 à 5 ans) et ne marche pas à tous les coups ni pour tous les antigènes. Il est donc important de mieux comprendre les mécanismes impliqués lors d'un tel traitement afin d'en améliorer l'efficacité. Af n de pouvoir investiguer en détail ces mécanismes des modèles d'immunothérapie ont été mis au point chez la souris. Notre étude se base sur un modèle d'asthme allergique chez la souris. Des souris sont rendues allergiques à l'ovalbumine (OVA) et présentent alors les caractéristiques majeures de l'asthme humain (recrutement de cellules inflammatoires dans les poumons, augmentation de la production d'IgE et de la résistance des bronches aux flux respiratoires). Ces souris asthmatiques une fois traitées par l'application nasale d'OVA (forme d'immunothérapie muqueuse) ne développent plus de réaction allergique lors d'une ré-exposition à l'allergène. Notre hypothèse est que cette «guérison» (tolérance) est liée à l'action de cellules (lymphocytes T CD4) dites «régulatrices» et caractérisées par le marqueur CD25. Pour le démontrer, nous avons éliminé ces cellules «régulatrices» CD25 de nos souris asthmatiques grâce à un anticorps monoclonal spécifique. Nous n'avons dès lors plus été en mesure d'induire une tolérance à l'allergène. Ceci suggère donc un rôle clé des cellules «régulatrices» T CD4+CD25+ dans la réussite de l'immunothérapie nasale dans notre modèle. Nos résultats n'excluent pas la participation d'autres cellules telles que les lymphocytes producteurs d'IL-10 (lymphocytes régulateurs induits). Le rôle respectif de ces sous-populations régulatrices devra être examiné dans les études à venir. Une meilleure maîtrise des mécanismes de régulation pourrait s'avérer cruciale pour améliorer les thérapies de l'asthme.

Robust Detection of Incumbents in Cognitive Radio Networks Using Groups

Cognitive radio is a wireless technology aimed at improvingthe efficiency use of the radio-electric spectrum, thus facilitating a reductionin the load on the free frequency bands. Cognitive radio networkscan scan the spectrum and adapt their parameters to operate in the unoccupiedbands. To avoid interfering with licensed users operating on a givenchannel, the networks need to be highly sensitive, which is achieved byusing cooperative sensing methods. Current cooperative sensing methodsare not robust enough against occasional or continuous attacks. This articleoutlines a Group Fusion method that takes into account the behavior ofusers over the short and long term. On fusing the data, the method is basedon giving more weight to user groups that are more unanimous in their decisions.Simulations have been performed in a dynamic environment withinterferences. Results prove that when attackers are present (both reiterativeor sporadic), the proposed Group Fusion method has superior sensingcapability than other methods.

Recipients' Anonymity in Multihop Ad-hoc Networks

Multihop ad-hoc networks have a dynamic topology. Retrieving a route towards a remote peer requires the execution of a recipient lookup, which can publicly reveal sensitive information about him. Within this context, we propose an efficient, practical and scalable solution to guaranteethe anonymity of recipients' nodes in ad-hoc networks.

Anonymous Routing Protocol in decentralized networks

Peer-reviewed

Fully Distributed Cooperative Spectrum Sensing for Cognitive Radio Networks

Cognitive radio networks (CRN) sense spectrum occupancy and manage themselves to operate in unused bands without disturbing licensed users. The detection capability of a radio system can be enhanced if the sensing process is performed jointly by a group of nodes so that the effects of wireless fading and shadowing can be minimized. However, taking a collaborative approach poses new security threats to the system as nodes can report false sensing data to force a wrong decision. Providing security to the sensing process is also complex, as it usually involves introducing limitations to the CRN applications. The most common limitation is the need for a static trusted node that is able to authenticate and merge the reports of all CRN nodes. This paper overcomes this limitation by presenting a protocol that is suitable for fully distributed scenarios, where there is no static trusted node.

A Secure Cooperative Sensing Protocol for Cognitive Radio Networks

Cognitive radio networks sense spectrum occupancyand manage themselves to operate in unused bands without disturbing licensed users. Spectrum sensing is more accurate if jointly performed by several reliable nodes. Even though cooperative sensing is an active area of research, the secureauthentication of local sensing reports remains unsolved, thus empowering false results. This paper presents a distributed protocol based on digital signatures and hash functions, and ananalysis of its security features. The system allows determining a final sensing decision from multiple sources in a quick and secure way.

On an IDS Model for Mobile Ad Hoc Networks

Manet security has a lot of open issues. Due to its character-istics, this kind of network needs preventive and corrective protection. Inthis paper, we focus on corrective protection proposing an anomaly IDSmodel for Manet. The design and development of the IDS are consideredin our 3 main stages: normal behavior construction, anomaly detectionand model update. A parametrical mixture model is used for behav-ior modeling from reference data. The associated Bayesian classi¯cationleads to the detection algorithm. MIB variables are used to provide IDSneeded information. Experiments of DoS and scanner attacks validatingthe model are presented as well.

Reconstruction of networks from their betweenness centrality

In this paper we study the reconstruction of a network topology from the values of its betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. We consider a simple metaheuristic, simulated annealing, as the combinatorial optimization method to generate the network from the values of the betweenness centrality. We compare the performance of this technique when reconstructing different categories of networks –random, regular, small-world, scale-free and clustered–. We show that the method allows an exact reconstruction of small networks and leads to good topological approximations in the case of networks with larger orders. The method can be used to generate a quasi-optimal topology fora communication network from a list with the values of the maximum allowable traffic for each node.