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.

Multi-Objective Genetic Algorithms for the Single Allocation Hub Location Problem

Hub Location Problems play vital economic roles in transportation and telecommunication networks where goods or people must be efficiently transferred from an origin to a destination point whilst direct origin-destination links are impractical. This work investigates the single allocation hub location problem, and proposes a genetic algorithm (GA) approach for it. The effectiveness of using a single-objective criterion measure for the problem is first explored. Next, a multi-objective GA employing various fitness evaluation strategies such as Pareto ranking, sum of ranks, and weighted sum strategies is presented. The effectiveness of the multi-objective GA is shown by comparison with an Integer Programming strategy, the only other multi-objective approach found in the literature for this problem. Lastly, two new crossover operators are proposed and an empirical study is done using small to large problem instances of the Civil Aeronautics Board (CAB) and Australian Post (AP) data sets.

New Contig Creation Algorithm for the de novo DNA Assembly Problem

DNA assembly is among the most fundamental and difficult problems in bioinformatics. Near optimal assembly solutions are available for bacterial and small genomes, however assembling large and complex genomes especially the human genome using Next-Generation-Sequencing (NGS) technologies is shown to be very difficult because of the highly repetitive and complex nature of the human genome, short read lengths, uneven data coverage and tools that are not specifically built for human genomes. Moreover, many algorithms are not even scalable to human genome datasets containing hundreds of millions of short reads. The DNA assembly problem is usually divided into several subproblems including DNA data error detection and correction, contig creation, scaffolding and contigs orientation; each can be seen as a distinct research area. This thesis specifically focuses on creating contigs from the short reads and combining them with outputs from other tools in order to obtain better results. Three different assemblers including SOAPdenovo [Li09], Velvet [ZB08] and Meraculous [CHS+11] are selected for comparative purposes in this thesis. Obtained results show that this thesis’ work produces comparable results to other assemblers and combining our contigs to outputs from other tools, produces the best results outperforming all other investigated assemblers.

Perceived Deservingness and the Toleration of Human Rights Violations: The Problem and a Possible Solution

Despite general endorsement of universal human rights, people continue to tolerate specific human rights violations. I conducted a two-part study to investigate this issue. For Part I, I examined whether people tolerated torture (a human rights violation) based on the morality and deservingness of the target. Participants tolerated torture more when the target had committed a highly morally reprehensible transgression. This effect was mediated by the target’s perceived deservingness for harsh treatment, and held over and above participants’ abstract support for the right to humane treatment. For Part II, hypocrisy induction was used in an attempt to reduce participants’ toleration of the torture. Participants were assigned to either the hypocrisy induction or control condition. Unexpectedly, participants who tolerated the torture more in Part I reduced their toleration the most in the control condition, possibly because of consistency and floor effects. Limitations and implications of the findings are discussed.

Investment Under Demand Uncertainty: the Newsboy Problem Revisited.

In this article we study the effect of uncertainty on an entrepreneur who must choose the capacity of his business before knowing the demand for his product. The unit profit of operation is known with certainty but there is no flexibility in our one-period framework. We show how the introduction of global uncertainty reduces the investment of the risk neutral entrepreneur and, even more, that the risk averse one. We also show how marginal increases in risk reduce the optimal capacity of both the risk neutral and the risk averse entrepreneur, without any restriction on the concave utility function and with limited restrictions on the definition of a mean preserving spread. These general results are explained by the fact that the newsboy has a piecewise-linear, and concave, monetary payoff witha kink endogenously determined at the level of optimal capacity. Our results are compared with those in the two literatures on price uncertainty and demand uncertainty, and particularly, with the recent contributions of Eeckhoudt, Gollier and Schlesinger (1991, 1995).

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

The Wage Rate and the Profit Rate in the Price of Production Equation: a New Solution to an Old Problem

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic concusions remain valid.

The Transformation Problem : an Aleternative Solution with an Identical Aggregate Profit Rate in the Labor value and the Monetary Space.

The aim of this paper is to demonstrate that, even if Marx's solution to the transformation problem can be modified, his basic conclusions remain valid. the proposed alternative solution which is presented hare is based on the constraint of a common general profit rate in both spaces and a money wage level which will be determined simultaneously with prices.

Investment Under Demand Uncertainty: the Newsboy Problem Revisited.

In this article we study the effect of uncertainty on an entrepreneur who must choose the capacity of his business before knowing the demand for his product. The unit profit of operation is known with certainty but there is no flexibility in our one-period framework. We show how the introduction of global uncertainty reduces the investment of the risk neutral entrepreneur and, even more, that the risk averse one. We also show how marginal increases in risk reduce the optimal capacity of both the risk neutral and the risk averse entrepreneur, without any restriction on the concave utility function and with limited restrictions on the definition of a mean preserving spread. These general results are explained by the fact that the newsboy has a piecewise-linear, and concave, monetary payoff witha kink endogenously determined at the level of optimal capacity. Our results are compared with those in the two literatures on price uncertainty and demand uncertainty, and particularly, with the recent contributions of Eeckhoudt, Gollier and Schlesinger (1991, 1995).

La monnaie en droit : nature d'une abstraction outre fondée : essai dialectique et logique sur la dualité dans la catégoricité juridique et sur l'abstraction d'hérédité monétaire

"Thèse présentée à la Faculté des études supérieures en vue de l'obtention du grade de Docteur en droit (LL.D.)"

Public Reason that Speaks to People : Iris Marion Young and the Problem of Internal Exclusion

Dossier : In Memoriam, Iris Marion Young (1949-2006)

Significations lexicales et notionnelles dans les domaines de spécialité

Département de linguistique et de traduction

Sequential Machine learning Approaches for Portfolio Management

Cette thèse envisage un ensemble de méthodes permettant aux algorithmes d'apprentissage statistique de mieux traiter la nature séquentielle des problèmes de gestion de portefeuilles financiers. Nous débutons par une considération du problème général de la composition d'algorithmes d'apprentissage devant gérer des tâches séquentielles, en particulier celui de la mise-à-jour efficace des ensembles d'apprentissage dans un cadre de validation séquentielle. Nous énumérons les desiderata que des primitives de composition doivent satisfaire, et faisons ressortir la difficulté de les atteindre de façon rigoureuse et efficace. Nous poursuivons en présentant un ensemble d'algorithmes qui atteignent ces objectifs et présentons une étude de cas d'un système complexe de prise de décision financière utilisant ces techniques. Nous décrivons ensuite une méthode générale permettant de transformer un problème de décision séquentielle non-Markovien en un problème d'apprentissage supervisé en employant un algorithme de recherche basé sur les K meilleurs chemins. Nous traitons d'une application en gestion de portefeuille où nous entraînons un algorithme d'apprentissage à optimiser directement un ratio de Sharpe (ou autre critère non-additif incorporant une aversion au risque). Nous illustrons l'approche par une étude expérimentale approfondie, proposant une architecture de réseaux de neurones spécialisée à la gestion de portefeuille et la comparant à plusieurs alternatives. Finalement, nous introduisons une représentation fonctionnelle de séries chronologiques permettant à des prévisions d'être effectuées sur un horizon variable, tout en utilisant un ensemble informationnel révélé de manière progressive. L'approche est basée sur l'utilisation des processus Gaussiens, lesquels fournissent une matrice de covariance complète entre tous les points pour lesquels une prévision est demandée. Cette information est utilisée à bon escient par un algorithme qui transige activement des écarts de cours (price spreads) entre des contrats à terme sur commodités. L'approche proposée produit, hors échantillon, un rendement ajusté pour le risque significatif, après frais de transactions, sur un portefeuille de 30 actifs.

Didactique des grandeurs en mesure et élèves en difficulté d'apprentissage du 2e cycle du primaire

Le programme -Une école adaptée à tous ses élèves-, qui s'inscrit dans la réforme actuelle de l'éducation au Québec, nous a amenée à nous intéresser aux représentations dans les grandeurs en mesure en mathématiques des élèves en difficulté d'apprentissage. Nous nous sommes proposés de reconduire plusieurs paramètres de la recherche de Brousseau (1987, 1992) auprès de cette clientèle. La théorie des champs conceptuels (TCC) de Vergnaud (1991), appliquée aux structures additives, a été particulièrement utile pour l'analyse et l'interprétation de leurs représentations. Comme méthode de recherche, nous avons utilisé la théorie des situations didactiques en mathématiques (TSDM), réseau de concepts et de méthode de recherche appuyé sur l'ingénierie didactique qui permet une meilleure compréhension de l'articulation des contenus à enseigner. Grâce à la TSDM, nous avons observé les approches didactiques des enseignants avec leurs élèves. Notre recherche est de type exploratoire et qualitatif et les données recueillies auprès de 26 élèves de deux classes spéciales du deuxième cycle du primaire ont été traitées selon une méthode d'analyse de contenu. Deux conduites ont été adoptées par les élèves. La première, de type procédural a été utilisée par presque tous les élèves. Elle consiste à utiliser des systèmes de comptage plus ou moins sophistiqués, de la planification aux suites d'actions. La deuxième consiste à récupérer directement en mémoire à long terme le résultat associé à un couple donné et au contrôle de son exécution. L'observation des conduites révèle que les erreurs sont dues à une rupture du sens. Ainsi, les difficultés d'ordre conceptuel et de symbolisation nous sont apparues plus importantes lorsque l'activité d'échange demandait la compétence "utilisation" et renvoyait à la compréhension de la tâche, soit les tâches dans lesquelles ils doivent eux-mêmes découvrir les rapports entre les variables à travailler et à simuler les actions décrites dans les énoncés. En conséquence, les problèmes d'échanges se sont révélés difficiles à modéliser en actes et significativement plus ardus que les autres. L'étude des interactions enseignants et élèves a démontré que la parole a été presque uniquement le fait des enseignants qui ont utilisé l'approche du contrôle des actes ou du sens ou les deux stratégies pour aider des élèves en difficulté. Selon le type de situation à résoudre dans ces activités de mesurage de longueur et de masse, des mobilisations plurielles ont été mises en oeuvre par les élèves, telles que la manipulation d'un ou des étalon(s) par superposition, par reports successifs, par pliage ou par coupure lorsque l'étalon dépassait; par retrait ou ajout d'un peu de sable afin de stabiliser les plateaux. Nous avons également observé que bien que certains élèves aient utilisé leurs doigts pour se donner une perception globale extériorisée des quantités, plusieurs ont employé des procédures très diverses au cours de ces mêmes séances. Les résultats présentés étayent l'hypothèse selon laquelle les concepts de grandeur et de mesure prennent du sens à travers des situations problèmes liées à des situations vécues par les élèves, comme les comparaisons directes. Eles renforcent et relient les grandeurs, leurs propriétés et les connaissances numériques.