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.

Bioenergetic and ecological consequences of diet variability in Atlantic croaker Micropogonias undulatus

Atlantic croaker Micropogonias undulatus is a commercially and ecologically important bottom-associated fish that occurs in marine and estuarine systems from Cape Cod, MA to Mexico. I documented the temporal and spatial variability in the diet of Atlantic croaker in Chesapeake Bay and found that in the summer fish, particularly bay anchovies Anchoa mitchilli, make up at least 20% of the diet of croaker by weight. The use of a pelagic food source seems unusual for a bottom-associated fish such as croaker, but appears to be a crepuscular feeding habit that has not been previously detected. Thus, I investigated the bioenergetic consequences of secondary piscivory to the distribution of croaker, to the condition of individuals within the population and to the ecosystem. Generalized additive models revealed that the biomass of anchovy explained some of the variability in croaker occurrence and abundance in Chesapeake Bay. However, physical factors, specifically temperature, salinity, and seasonal dynamics were stronger determinants of croaker distribution than potential prey availability. To better understand the bioenergetic consequences of diet variability at the individual level, I tested the hypothesis that croaker feeding on anchovies would be in better condition than those feeding on polychaetes using a variety of condition measures that operate on multiple time scales, including RNA:DNA, Fulton's condition factor (K), relative weight (Wr), energy density, hepatosomatic index (HSI), and gonadosomatic index (GSI). Of these condition measures, several morphometric measures were significantly positively correlated with each other and with the percentage (by weight) of anchovy in croaker diets, suggesting that the type of prey eaten is important in improving the overall condition of individual croaker. To estimate the bioenergetic consequences of diet variability on growth and consumption in croaker, I developed and validated a bioenergetic model for Atlantic croaker in the laboratory. The application of this model suggested that croaker could be an important competitor with weakfish and striped bass for food resources during the spring and summer when population abundances of these three fishes are high in Chesapeake Bay. Even though anchovies made up a relatively small portion of croaker diet and only at certain times of the year, croaker consumed more anchovy at the population level than striped bass in all simulated years and nearly as much anchovy as weakfish. This indicates that weak trophic interactions between species are important in understanding ecosystem processes and should be considered in ecosystem-based management.