Mathematical Programming Models for Influence Maximization on Social Networks

In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.

Unsupervised reinforcement learning via state entropy maximization

Reinforcement Learning (RL) provides a powerful framework to address sequential decision-making problems in which the transition dynamics is unknown or too complex to be represented. The RL approach is based on speculating what is the best decision to make given sample estimates obtained from previous interactions, a recipe that led to several breakthroughs in various domains, ranging from game playing to robotics. Despite their success, current RL methods hardly generalize from one task to another, and achieving the kind of generalization obtained through unsupervised pre-training in non-sequential problems seems unthinkable. Unsupervised RL has recently emerged as a way to improve generalization of RL methods. Just as its non-sequential counterpart, the unsupervised RL framework comprises two phases: An unsupervised pre-training phase, in which the agent interacts with the environment without external feedback, and a supervised fine-tuning phase, in which the agent aims to efficiently solve a task in the same environment by exploiting the knowledge acquired during pre-training. In this thesis, we study unsupervised RL via state entropy maximization, in which the agent makes use of the unsupervised interactions to pre-train a policy that maximizes the entropy of its induced state distribution. First, we provide a theoretical characterization of the learning problem by considering a convex RL formulation that subsumes state entropy maximization. Our analysis shows that maximizing the state entropy in finite trials is inherently harder than RL. Then, we study the state entropy maximization problem from an optimization perspective. Especially, we show that the primal formulation of the corresponding optimization problem can be (approximately) addressed through tractable linear programs. Finally, we provide the first practical methodologies for state entropy maximization in complex domains, both when the pre-training takes place in a single environment as well as multiple environments.

Censored Linear Regression Models For Irregularly Observed Longitudinal Data Using The Multivariate-t Distribution.

In acquired immunodeficiency syndrome (AIDS) studies it is quite common to observe viral load measurements collected irregularly over time. Moreover, these measurements can be subjected to some upper and/or lower detection limits depending on the quantification assays. A complication arises when these continuous repeated measures have a heavy-tailed behavior. For such data structures, we propose a robust structure for a censored linear model based on the multivariate Student's t-distribution. To compensate for the autocorrelation existing among irregularly observed measures, a damped exponential correlation structure is employed. An efficient expectation maximization type algorithm is developed for computing the maximum likelihood estimates, obtaining as a by-product the standard errors of the fixed effects and the log-likelihood function. The proposed algorithm uses closed-form expressions at the E-step that rely on formulas for the mean and variance of a truncated multivariate Student's t-distribution. The methodology is illustrated through an application to an Human Immunodeficiency Virus-AIDS (HIV-AIDS) study and several simulation studies.

A equidade no sistema de saúde na visão de bioeticistas brasileiros

OBJETIVO: Conhecer a atribuição de significado dada por bioeticistas brasileiros quanto à equidade no sistema de saúde. MÉTODOS: Pesquisa qualitativa, exploratória. Entre julho de 2007 e julho de 2008, foram entrevistados 20 bioeticistas, dirigentes e ex-dirigentes da Sociedade Brasileira de Bioética e de suas regionais (2005-2008). O tratamento dos dados foi realizado por análise de discurso. RESULTADOS: Os discursos levaram ao estabelecimento das seguintes ideias centrais: tratar desigualmente os desiguais conforme suas necessidades; equidade e desigualdades compensadas; equidade e maximização dos benefícios; equidade e mérito social; equidade e direitos. CONCLUSÃO: Os resultados da pesquisa evidenciam a existência entre os bioeticistas pesquisados de uma diversidade de interpretações sobre equidade no sistema de saúde, reforçando a noção de que é difícil, no mundo contemporâneo, decidir sobre o que seria um sistema justo e equânime.

Produção in vitro de embriões de ovinos: uma visão crítica do método e de seu resultado a campo

A metodologia de produção in vitro de embriões de ovinos implica no desenvolvimento de meios de maturação, fertilização e cultivo que permitam aumentar a taxa de clivagem e desenvolvimento, tanto para o investimento biotecnológico em programas comerciais, quanto para sua utilização em clonagem e transgenia dessa espécie animal. Do ponto de vista da pesquisa, os ovócitos podem ser obtidos pelas técnicas de punção e slicing a partir de ovários oriundos de matadouros, ou através de aspiração folicular por laparoscopia. Como vantagem, este método permite o uso de uma mesma doadora estimulada hormonialmente em intervalos periódicos, mantida sob rigoroso controle sanitário, o que é de vital importância para a produção de biofármacos em programas que utilisem os ovinos como modelo biológico. Por outro lado, em nosso país a demanda pela multiplicação de animais de alto valor genético, seja pela produtividade ou pelo elevado valor comercial dos mesmos, impõe o desenvolvimento, adaptação e otimização das diferentes metodologias desenvolvidas ao longo dos ultimos anos em laboratórios de referência mundiais. Nesse contexto, cresce de importância o perfeito conhecimento da fisiologia dessa espécie e das raças criadas em nosso país, e da problemática da produção in vitro de seus embriões. Respeitando essas premissas, gerar o desenvolvimento de protocolos que permitam não apenas aumentar a população de ovócitos passíveis de maturação in vitro, mas de sua competência ao desenvolvimento ao estágio de blastocisto, ou, alternativamente, sua transferência a receptoras em estágios precoces do desenvolvimento, evitando assim as conhecidas perdas durante o desenvolvimento in vitro, e o baixo percentual de gestações que chegam a termo, com cordeiro saudáveis. Trata-se de um desafio, que já apresenta os primeiros resultados em nosso país, tanto na produção comercial de embriões produzidos in vitro, quanto em programas de clonagem e transgenia.

A study of cell disruption of Candida mogii by glass bead mill for the recovery of xylose reductase

The release of xylose reductase (XR) from Candida mogii by cell disruption in a glass beads mill was studied using an experimental design. Statistical analysis of the results indicated that XR volumetric activity increases by using lower glass beads diameter and cell concentration, and by increasing the number of agitation pulses. Based on results attained in experimental design, assays were carried out aiming at the maximization of XR release. Under optimized conditions (300 mu m glass beads, 45 g/l of cell concentration and 50 pulses), the XR volumetric activity reach 0.683 U/ml. Disruption with glass beads showed to be the most efficient method for XR release when compared to sonication process. The highest specific activity (0.175 U/mg of protein) was found in extracts obtained by suspension freezing and thawing, which suggests that this method can be used as a selective process of cell disruption for XR release. (c) 2008 Elsevier B.V. All rights reserved.

Optimization of the AZO dyes decoloration process through neural networks: Determination of the H2O2 addition critical point

The concentration of hydrogen peroxide is an important parameter in the azo dyes decoloration process through the utilization of advanced oxidizing processes, particularly by oxidizing via UV/H2O2. It is pointed out that, from a specific concentration, the hydrogen peroxide works as a hydroxyl radical self-consumer and thus a decrease of the system`s oxidizing power happens. The determination of the process critical point (maximum amount of hydrogen peroxide to be added) was performed through a ""thorough mapping"" or discretization of the target region, founded on the maximization of an objective function objective (constant of reaction kinetics of pseudo-first order). The discretization of the operational region occurred through a feedforward backpropagation neural model. The neural model obtained presented remarkable coefficient of correlation between real and predicted values for the absorbance variable, above 0.98. In the present work, the neural model had, as phenomenological basis the Acid Brown 75 dye decoloration process. The hydrogen peroxide addition critical point, represented by a value of mass relation (F) between the hydrogen peroxide mass and the dye mass, was established in the interval 50 < F < 60. (C) 2007 Elsevier B.V. All rights reserved.

Response surface methodology as an approach to determine optimal activities of lipase entrapped in sol-gel matrix using different vegetable oils

The conditions for maximization of the enzymatic activity of lipase entrapped in sol-gel matrix were determined for different vegetable oils using an experimental design. The effects of pH, temperature, and biocatalyst loading on lipase activity were verified using a central composite experimental design leading to a set of 13 assays and the surface response analysis. For canola oil and entrapped lipase, statistical analyses showed significant effects for pH and temperature and also the interactions between pH and temperature and temperature and biocatalyst loading. For the olive oil and entrapped lipase, it was verified that the pH was the only variable statistically significant. This study demonstrated that response surface analysis is a methodology appropriate for the maximization of the percentage of hydrolysis, as a function of pH, temperature, and lipase loading.

Performance of the Equivalent Reservoir Modelling Technique for Multi-Reservoir Hydropower Systems

This paper investigates the validity of a simplified equivalent reservoir representation of a multi-reservoir hydroelectric system for modelling its optimal operation for power maximization. This simplification, proposed by Arvanitidis and Rosing (IEEE Trans Power Appar Syst 89(2):319-325, 1970), imputes a potential energy equivalent reservoir with energy inflows and outflows. The hydroelectric system is also modelled for power maximization considering individual reservoir characteristics without simplifications. Both optimization models employed MINOS package for solution of the non-linear programming problems. A comparison between total optimized power generation over the planning horizon by the two methods shows that the equivalent reservoir is capable of producing satisfactory power estimates with less than 6% underestimation. The generation and total reservoir storage trajectories along the planning horizon obtained by equivalent reservoir method, however, presented significant discrepancies as compared to those found in the detailed modelling. This study is motivated by the fact that Brazilian generation system operations are based on the equivalent reservoir method as part of the power dispatch procedures. The potential energy equivalent reservoir is an alternative which eliminates problems with the dimensionality of state variables in a dynamic programming model.

Cost functions and duality for stochastic technologies

Cost functions dual to stochastic production technologies are derived and their properties are discussed. These cost functions are shown to be consistent with expected-utility maximization without placing serious structural restrictions on the underlying technology.

Analyses of Individual and Organizational Competences Associated with Knowledge Management Practice

The research analyzed critical aspects of the knowledge management process based on the analyses of knowledge, abilities and attitudes required to individual knowledge workers and to organizations responsible for the management process. In the present work a characterization of the knowledge management process was developed and information and knowledge wokers defined. Competence concept was discussed and specialists gave opinions about critical competences to knowledge management process. The opinions were organized and analyzed by the Delphi method. The results aggregate to the management context by discussing an extremely important resource to organizations - knowledge - and because they support its management process. The research identified wide critical aspects that are compatible with current organizational challenges, directing the process management to important themes as: the worker able to create, the organization able to convert individual knowledge into organizational knowledge, knowledge sharing while still tacit, the maximization organizational knowledge use, information and knowledge generation and preservation, among others important topics to be observed by knowledge workers and by administrators responsible for the knowledge management process.

Association of haplotypes in the IL8 gene with susceptibility to chronic periodontitis in a Brazilian population

Background: Interleukin 8 (IL-8) is a chemokine related to the initiation and amplification of acute and chronic inflammatory processes. Polymorphisms in the IL8 gene have been associated with inflammatory diseases. We investigated whether the - 845(T/C) and - 738(T/A) single nucleotide polymorphisms (SNPs) in the IL8 gene, as well as the haplotypes they form together with the previously investigated -353(A/T), are associated with susceptibility to chronic periodontitis. Methods: DNA was extracted from buccal epithelial cells of 400 Brazilian individuals (control n =182, periodontitis n=218). SNPs were genotyped by the polymerase chain reaction-restriction fragment length polymorphism (PCR-RFLP) method. Disease associations were analyzed by the chi(2) test, Exact Fisher test and Clump program. Haplotypes were reconstructed using the expectation-maximization algorithm and differences in haplotype distribution between the groups were analyzed to estimate genetic susceptibility for chronic periodontitis development. Results: When analyzed individually, no SNPs showed different distributions between the control and chronic periodontitis groups. Although, nonsmokers carrying the TTA/CAT (OR = 2.35, 95% CI = 1.03-5.36) and TAT/CTA (OR= 6.05, 95% CI = 1.32-27.7) haplotypes were genetically susceptible to chronic periodontitis. The ITT/TAA haplotype was associated with protection against the development of periodontitis (for nonsmokers OR= 0.22, 95% CI = 0.10-0.46). Conclusion: Although none of the investigated SNPs in the IL8 gene was individually associated with periodontitis, some haplotypes showed significant association with susceptibility to, or protection against, chronic periodontitis in a Brazilian population. (C) 2010 Elsevier B.V. All rights reserved.

Altered loading patterns and femoral bone mineral density in children with unilateral Legg-Calve-Perthes disease

Maximization of bone accrual during the growing years is thought to be an important factor in minimizing fracture risk in old age. Mechanical loading through physical activity has been recommended as a modality for the conservation of bone mineral in adults; however, few studies have evaluated the impact of different loading regimes in growing children. The purpose of this study was to compare bone mineral density (BMD) in weight-bearing and non-weight-bearing limbs in 17 children with unilateral Legg Calve Perthes Disease (LCPD). Children with this condition have an altered weight-bearing pattern whereby there is increased mechanical loading on the noninvolved normal hip and reduced loading on the involved painful hip. Thus, these children provide a unique opportunity to study the impact of differential mechanical loading on BMD during the growing years while controlling for genetic disposition. BMD at four regions of the proximal femur (trochanter, intertrochanter, femoral neck, total of the regions) was measured using dual energy x-ray absorptiometry (DXA), and the values were compared between the involved and noninvolved sides of the children with LCPD. The BMD of both sides also were compared with normative values based on both chronological and skeletal age data. A significantly higher BMD was found on the noninvolved side over the involved side for all regions (P

Evaluation of computational methods for the reconstruction of HLA haplotypes

Human leukocyte antigen (HLA) haplotypes are frequently evaluated for population history inferences and association studies. However, the available typing techniques for the main HLA loci usually do not allow the determination of the allele phase and the constitution of a haplotype, which may be obtained by a very time-consuming and expensive family-based segregation study. Without the family-based study, computational inference by probabilistic models is necessary to obtain haplotypes. Several authors have used the expectation-maximization (EM) algorithm to determine HLA haplotypes, but high levels of erroneous inferences are expected because of the genetic distance among the main HLA loci and the presence of several recombination hotspots. In order to evaluate the efficiency of computational inference methods, 763 unrelated individuals stratified into three different datasets had their haplotypes manually defined in a family-based study of HLA-A, -B, -DRB1 and -DQB1 segregation, and these haplotypes were compared with the data obtained by the following three methods: the Expectation-Maximization (EM) and Excoffier-Laval-Balding (ELB) algorithms using the arlequin 3.11 software, and the PHASE method. When comparing the methods, we observed that all algorithms showed a poor performance for haplotype reconstruction with distant loci, estimating incorrect haplotypes for 38%-57% of the samples considering all algorithms and datasets. We suggest that computational haplotype inferences involving low-resolution HLA-A, HLA-B, HLA-DRB1 and HLA-DQB1 haplotypes should be considered with caution.

Fitting mixtures of Kent distributions to aid in joint set identification

When examining a rock mass, joint sets and their orientations can play a significant role with regard to how the rock mass will behave. To identify joint sets present in the rock mass, the orientation of individual fracture planer can be measured on exposed rock faces and the resulting data can be examined for heterogeneity. In this article, the expectation-maximization algorithm is used to lit mixtures of Kent component distributions to the fracture data to aid in the identification of joint sets. An additional uniform component is also included in the model to accommodate the noise present in the data.