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.

An implicit BEM formulation to model strong discontinuities in solids

A boundary element method (BEM) formulation to predict the behavior of solids exhibiting displacement (strong) discontinuity is presented. In this formulation, the effects of the displacement jump of a discontinuity interface embedded in an internal cell are reproduced by an equivalent strain field over the cell. To compute the stresses, this equivalent strain field is assumed as the inelastic part of the total strain. As a consequence, the non-linear BEM integral equations that result from the proposed approach are similar to those of the implicit BEM based on initial strains. Since discontinuity interfaces can be introduced inside the cell independently on the cell boundaries, the proposed BEM formulation, combined with a tracking scheme to trace the discontinuity path during the analysis, allows for arbitrary discontinuity propagation using a fixed mesh. A simple technique to track the crack path is outlined. This technique is based on the construction of a polygonal line formed by segments inside the cells, in which the assumed failure criterion is reached. Two experimental concrete fracture tests were analyzed to assess the performance of the proposed formulation.

An extended BEM formulation for plates reinforced by rectangular beams

This article presents a BEM formulation developed particularly for analysis of plates reinforced by rectangular beams. This is an extended version of a Previous paper that only took into account bending effects. The problem is now re-formulated to consider bending and membrane force effects. The effects of the reinforcements are taken into account by using a simplified scheme that requires application of ail initial stress field to locally correct the bending and stretching stiffness of the reinforcement regions. The domain integrals due to the presence of the reinforcements are then transformed to the reinforcement/plate interface. To reduce the number of degrees of freedom related to the presence of the reinforcement, the proposed model was simplified to consider only bending and stretching rigidities in the direction of the beams. The complete model can be recovered by applying all six internal force correctors, corresponding to six degrees of freedom per node. Examples are presented to confirm the accuracy of the formulation and to illustrate the level of simplification introduced by this strong reduction in the number of degrees of freedom. (C) 2008 Elsevier Ltd. All rights reserved.

In vitro uptake and antimycobacterial activity of liposomal usnic acid formulation

The cellular uptake and antimycobacterial activity of usnic acid (UA) and usnic acid-loaded liposomes (UA-LIPOs) were assessed on J774 macrophages. The minimal inhibitory concentration (MIC) and the minimal bactericidal concentration (MBC) of UA and UA-LIPO against Mycobacterium tuberculosis were determined. Concentrations required to inhibit 50% of cell proliferation (IC(50)) were 22.5 (+/- 0.60) and 12.5 (+/- 0.26) mu g/ml, for UA and UA-LIPO, respectively. The MICs of UA and UA-LIPO were 6.5 and 5.8 mu g/mL, respectively. The MBC of UA-LIPO was twice as low (16 mu g/mL) as that of UA (32 mu g/mL). An improvement in the intracellular uptake of UA-LIPO was found (21.6 x 10(4) +/- 28.3 x 10(2) c.p.s), in comparison with UA (9.5 x 10(4) +/- 11.4 x 10(2) c.p.s). In addition, UA-LIPO remains much longer inside macrophages (30 hours). All data obtained from the encapsulation of usnic acid into liposomes as a drug delivery system (DDS) indicate a strong interaction between UA-liposomes and J774 macrophages, thereby facilitating UA penetration into cells. Considering such a process as ruling the Mycobacterium-transfection by magrophages, we could state that associating UA with this DDS leads to an improvement in its antimycobacterial activity.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

Data Assimilation and Inverse Methods in Terms of a Probabilistic Formulation

The weak-constraint inverse for nonlinear dynamical models is discussed and derived in terms of a probabilistic formulation. The well-known result that for Gaussian error statistics the minimum of the weak-constraint inverse is equal to the maximum-likelihood estimate is rederived. Then several methods based on ensemble statistics that can be used to find the smoother (as opposed to the filter) solution are introduced and compared to traditional methods. A strong point of the new methods is that they avoid the integration of adjoint equations, which is a complex task for real oceanographic or atmospheric applications. they also avoid iterative searches in a Hilbert space, and error estimates can be obtained without much additional computational effort. the feasibility of the new methods is illustrated in a two-layer quasigeostrophic model.

Saponins, IL12 and BCG adjuvant in the FML-vaccine formulation against murine visceral leishmaniasis

The FML antigen of Leishmania donovani, in combination with either Riedel de Haen (R), QuilA, QS21 saponins, IL12 or BCG, was used in vaccination of an outbred murine model against visceral leishmaniasis (VL). Significant and specific increases in anti-FML IgG and IgM responses were detected for all adjuvants, and in anti-FML IgG1, IgG2a and IgG2b and delayed type of hypersensitivity to L. donovani lysate (DTH), only for all saponins and IL12. The QS21-FML and QuilA-FML groups achieved the highest IgG2a response. QuilA-FML developed the strongest DTH and QS21-FML animals showed the highest serum IFN-gamma concentrations. The reduction of parasitic load in the liver in response to each FML-vaccine formulation was: 52% (P < 0.025) for BCG-FML, 73% (P < 0.005) for R-FML, 93% (P < 0.005) for QuilA-FML and 79.2% (P < 0.025) for QS21-FML treated animals, respectively. Protection was specific for R-FML and QS21-FML while the QuilA saponin treatment itself induced 69% of LDU reduction. The FML-saponin vaccines promote significant, specific and strong protective effects against murine visceral leishmaniasis. BCG-FML induced minor and non-specific protection while IL 12-FML, although enhancing the specific antibody and IDR response, failed to reduce the parasitic load of infected animals. (C) 2002 Elsevier B.V. Ltd. All rights reserved.

Proliferating cell nuclear antigen (PCNA) in non-Hodgkin's lymphomas: Correlation with working formulation and Kiel classification in formalin-fixed paraffin-embedded material

PCNA is a 36-KD proliferating cell nuclear antigen associated with the cell cycle. The immunocytochemical detection of PCNA represents a useful tool for the study of tumor proliferation activity. This study documents the detection of PCNA, using antibody PC 10 in formalin-fixed, paraffin-embedded tissue, and correlates the proliferative activity of the non-Hodgkin's lymphomas (NHL) with histological grading assessed by the International Working Formulation (WF) and Kiel classification. In 92 cases of NHLs we found a strong correlation between the PCNA index and lymphoma grading. Statistically significant differences were also found between the proliferative index (PI) in low and high grade lymphomas according to the Kiel classification (t = 9.519; p < 0.001) and between low, intermediate and high grade lymphomas according to the WF classification (F = 79.01; p < 0.001). In the Kiel classification the mean of low grade lymphomas was 39.5% and of high grade 75.7%. In the WF the average of low grade lymphomas was 29.7%, intermediate 53.1% and high 75.1%. Although the differences among the groups had been significant, we found variations inside each histological subgroup in both classifications. The intermediate lymphomas were the most heterogeneous group, with PI inside the same histologic subtypes coincident with low and high grade lymphomas. Since PCNA may be used as a marker of cell proliferation in clinical studies to estimate the biological aggressiveness of lymphomas, its determination in intermediate grade NHL could be very useful to evaluate individual cases in this group and determine prognosis and probably the appropriate therapy.

A mathematical framework for finite strain elastoplastic consolidation. Part 1: Balance laws, variational formulation, and linearization

A mathematical formulation for finite strain elasto plastic consolidation of fully saturated soil media is presented. Strong and weak forms of the boundary-value problem are derived using both the material and spatial descriptions. The algorithmic treatment of finite strain elastoplasticity for the solid phase is based on multiplicative decomposition and is coupled with the algorithm for fluid flow via the Kirchhoff pore water pressure. Balance laws are written for the soil-water mixture following the motion of the soil matrix alone. It is shown that the motion of the fluid phase only affects the Jacobian of the solid phase motion, and therefore can be characterized completely by the motion of the soil matrix. Furthermore, it is shown from energy balance consideration that the effective, or intergranular, stress is the appropriate measure of stress for describing the constitutive response of the soil skeleton since it absorbs all the strain energy generated in the saturated soil-water mixture. Finally, it is shown that the mathematical model is amenable to consistent linearization, and that explicit expressions for the consistent tangent operators can be derived for use in numerical solutions such as those based on the finite element method.

Singularities in DROMO formulation. Analysis of deep flybys

The singularities in Dromo are characterized in this paper, both from an analytical and a numerical perspective. When the angular momentum vanishes, Dromo may encounter a singularity in the evolution equations. The cancellation of the angular momentum occurs in very speci?c situations and may be caused by the action of strong perturbations. The gravitational attraction of a perturbing planet may lead to rapid changes in the angular momentum of the particle. In practice, this situation may be encountered during deep planetocentric ?ybys. The performance of Dromo is evaluated in di?erent scenarios. First, Dromo is validated for integrating the orbit of Near Earth Asteroids. Resulting errors are of the order of the diameter of the asteroid. Second, a set of theoretical ?ybys are designed for analyzing the performance of the formulation in the vicinity of the singularity. New sets of Dromo variables are proposed in order to minimize the dependency of Dromo on the angular momentum. A slower time scale is introduced, leading to a more stable description of the ?yby phase. Improvements in the overall performance of the algorithm are observed when integrating orbits close to the singularity.

CpG DNA can induce strong Th1 humoral and cell-mediated immune responses against hepatitis B surface antigen in young mice

Successful neonatal immunization of humans has proven difficult. We have evaluated CpG-containing oligonucleotides as an adjuvant for immunization of young mice (1–14 days old) against hepatitis B virus surface antigen. The protein-alum-CpG formulation, like the DNA vaccine, produced seroconversion of the majority of mice immunized at 3 or 7 days of age, compared with 0–10% with the protein-alum or protein-CpG formulations. All animals, from neonates to adults, immunized with the protein-alum vaccine exhibited strong T helper (Th)2-like responses [predominantly IgG1, weak or absent cytotoxic T lymphocytes (CTL)]. Th2-type responses also were induced in young mice with protein-CpG (in 1-, 3-, and 7-day-old mice) and protein-alum-CpG (in 1- and 3-day-old mice) but immunization carried out at older ages gave mixed Th1/Th2 (Th0) responses. DNA vaccines gave Th0-like responses when administered at 1 and 7 days of age and Th1-like (predominantly IgG2a and CTL) responses with 14-day-old or adult mice. Surprisingly, the protein-alum-CpG formulation was better than the DNA vaccine for percentage of seroconversion, speed of appearance, and peak titer of the antibody response, as well as prevalence and strength of CTL. These findings may have important implications for immunization of human infants.

Formulation of multiparticulate systems as lyophilised orally disintegrating tablets

The current study aimed to exploit the electrostatic associative interaction between carrageenan and gelatin to optimise a formulation of lyophilised orally disintegrating tablets (ODTs) suitable for multiparticulate delivery. A central composite face centred (CCF) design was applied to study the influence of formulation variables (gelatin, carrageenan and alanine concentrations) on the crucial responses of the formulation (disintegration time, hardness, viscosity and pH). The disintegration time and viscosity were controlled by the associative interaction between gelatin and carrageenan upon hydration which forms a strong complex that increases the viscosity of the stock solution and forms tablet with higher resistant to disintegration in aqueous medium. Therefore, the levels of carrageenan, gelatin and their interaction in the formulation were the significant factors. In terms of hardness, increasing gelatin and alanine concentration was the most effective way to improve tablet hardness. Accordingly, optimum concentrations of these excipients were needed to find the best balance that fulfilled all formulation requirements. The revised model showed high degree of predictability and optimisation reliability and therefore was successful in developing an ODT formulation with optimised properties that were able deliver enteric coated multiparticulates of omeprazole without compromising their functionality.

Influence of microbial antigen formulation and delivery route on the immune response

Recent technological advances have resulted in the production of safe subunit and synthetic small peptide vaccines. Unfortunately, these vaccines are weakly or non-immunogenic in the absence of an immunological adjuvant (agents that can induce strong immunity to antigens). In addition, in order to prevent and/or control infection at the mucosal surface, stimulation of the mucosal immune system is essential. This may be achieved via the common mucosal immune system by exposure to antigen at a mucosal surface remote from the area of infection. Initial studies investigated the potential of multiple emulsions in effecting oral absorption and the subsequent immune responses to a lipopolysaccharide vaccine (LPS) after immunisation. Nasal delivery of LPS was carried out in parallel work using either aqueous solution or gel formulations. Tetanus toxoid vaccine in simple solution was delivered to guinea pigs as free antigen or entrapped in DSPC liposomes. In addition, adsorbed tetanus toxoid vaccine was delivered nasally free or in an aerosil gel formulation. This work was extended to investigate guinea pigs immunised by various mucosal routes with a herpes simplex virus subunit vaccine prepared from virus infected cells and delivered in gels, multiple emulsions and liposomes. Comparable serum antibody responses resulted but failed to produce enhanced protection against vaginal challenge when compared to subcutaneous immunisation with alhydrogel adjuvanted vaccine. Thus, immunisation of the mucosal surface by these methods may have been inadequate. These studies were extended in an attempt to protect against HSV genital challenge by construction of an attenuated Salmonella typhimurium HWSH aroA mutant expressing a cloned glycoprotein D-l gene fused to the Es-cherichia coli lac z promoter. Preliminary work on the colonisation of guinea pigs with S. typhimurium HWSH aroA mutants were carried out, with the aim of using the guinea pig HSV vaginal model to investigate protection.

Formulation and development of cationic liposomes as adjuvants for subunit protein vaccinese

Liposomes remain at the forefront of vaccine design due to their well documented abilities to act as delivery vehicles and adjuvants. Liposomes have been described to initiate an antigen depot-effect, thereby increasing antigen exposure to circulating antigen-presenting cells. More recently, in-depth reviews have focussed on inherent immunostimulatory abilities of various cationic lipids, the use of which is consequently of interest in the development of subunit protein vaccines which when delivered without an adjuvant are poorly immunogenic. The importance of liposomes for the mediation of an antigen depot-effect was examined by use of a dual-radiolabelling technique thereby allowing simultaneous detection of liposomal and antigenic components and analysis of their pharmacokinetic profile. In addition to investigating the biodistribution of these formulations, their physicochemical properties were analysed and the ability of the various liposome formulations to elicit humoral and cell-mediated immune responses was investigated. Our results show a requirement of cationic charge and medium/strong levels of antigen adsorption to the cationic liposome in order for both a liposome and antigen depot-effect to occur at the injection site. The choice of injection route had little effect on the pharmacokinetics or immunogenicity observed. In vitro, cationic liposomes were more cytotoxic than neutral liposomes due to significantly enhanced levels of cell uptake. With regards to the role of bilayer fluidity, liposomes expressing more rigid bilayers displayed increased retention at the injection site although this did not necessarily result in increased antigen retention. Furthermore, liposome bilayer rigidity did not necessarily correlate with improved immunogenicity. In similar findings, liposome size did not appear to control liposome or antigen retention at the injection site. However, a strong liposome size correlation between splenocyte proliferation and production of IL-10 was noted; specifically immunisation with large liposomes lead to increased levels of splenocyte proliferation coupled with decreased IL-10 production.

A New Formulation of the Spectral Energy Budget of the Atmosphere, with Application to Two High-Resolution General Circulation Models

International audience