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.

Train scheduling and rolling stock assignment in high speed trains

The Train Timetabling Problem (TTP) has been widely studied for freight and passenger rail systems. A lesser effort has been devoted to the study of high-speed rail systems. A modeling issue that has to be addressed is to model departure time choice of passengers on railway services. Passengers who use these systems attempt to travel at predetermined hours due to their daily life necessities (e.g., commuter trips). We incorporate all these features into TTP focusing on high-speed railway systems. We propose a Rail Scheduling and Rolling Stock (RSch-RS) model for timetable planning of high-speed railway systems. This model is composed of two essential elements: i) an infrastructure model for representing the railway network: it includes capacity constraints of the rail network and the Rolling-Stock constraints; and ii) a demand model that defines how the passengers choose the departure time. The resulting model is a mixed-integer programming model which objective function attempts to maximize the profit for the rail operator

New dimeric supramolecular structure of mixed (phthalocyaninato)(porphyrinato)-europium(III) sandwiches : preparation and spectroscopic characteristics

The mixed double-decker Eu\[Pc(15C5)4](TPP) (1) was obtained by base-catalysed tetramerisation of 4,5-dicyanobenzo-15-crown-5 using the half-sandwich complex Eu(TPP)(acac) (acac = acetylacetonate), generated in situ, as the template. For comparative studies, the mixed triple-decker complexes Eu2\[Pc(15C5)4](TPP)2 (2) and Eu2\[Pc(15C5)4]2(TPP) (3) were also synthesised by the raise-by-one-story method. These mixed ring sandwich complexes were characterised by various spectroscopic methods. Up to four one-electron oxidations and two one-electron reductions were revealed by cyclic voltammetry (CV) and differential pulse voltammetry (DPV). As shown by electronic absorption and infrared spectroscopy, supramolecular dimers (SM1 and SM3) were formed from the corresponding double-decker 1 and triple-decker 3 in the presence of potassium ions in MeOH/CHCl3.

Raman spectroscopic characteristics of phthalocyanine and naphthalocyanine in sandwich-type phthalocyaninato and porphyrinato rare earth complexes Part 5. – Raman spectroscopic characteristics of naphthalocyanine in mixed [tetrakis(4-tert-butylphenyl)porphyrinato]-(naphthalocyaninato) rare earth double-deckers

Raman spectra were recorded in the range 400–1800 cm−1 for a series of 15 mixed \[tetrakis(4-tert-butylphenyl)porphyrinato](2,3-naphthalocyaninato) rare earth double-deckers M(TBPP)(Nc) (M = Y; La–Lu except Pm) using laser excitation at 632.8 and 785 nm. Comparisons with bis(naphthalocyaninato) rare earth counterparts reveal that the vibrations of the metallonaphthalocyanine M(Nc) fragment dominate the Raman features of M(TBPP)(Nc). When excited with radiation of 632.8 nm, the most intense vibration appears at about 1595 cm−1, due to the naphthalene stretching. These complexes exhibit the marker Raman band for Nc•− as a medium-intense band in the range 1496–1507 cm−1, attributed to the coupling of pyrrole and aza stretching, while the marker Raman band of Nc2− in intermediate-valence Ce(TBPP)(Nc) appears as a strong band at 1493 cm−1 and is due to the isoindole stretchings. By contrast, when excited with radiation of 785 nm that is in close resonance with the main Q absorption band of the naphthalocyanine ligand, the ring radial vibrations at ca 680 and 735 cm−1 for MIII(TBPP)(Nc) are selectively intensified and are the most intense bands. For the cerium double-decker, the most intense vibration also acting as the marker Raman band of Nc2− appears at 1497 cm−1 with contributions from both pyrrole CC and aza CN stretches. The same vibrational modes show weak to medium intensity scattering at 1506–1509 cm−1 for MIII(TBPP)(Nc) and this is the marker Raman band of Nc•− when thus excited. The scatterings due to the Nc breathings, ring radial vibration, aza group stretchings, naphthalene stretchings, benzoisoindole stretchings and the coupling of pyrrole CC and aza CN stretchings in MIII(TBPP)(Nc) are all slightly blue shifted along with the decrease in rare earth ionic radius, confirming the effects of increased ring–ring interactions on the Raman characteristics of naphthalocyanine in the mixed ring double-deckers.

Automated Feedback for 'Fill in the Gap' Programming Exercises

Timely feedback is a vital component in the learning process. It is especially important for beginner students in Information Technology since many have not yet formed an effective internal model of a computer that they can use to construct viable knowledge. Research has shown that learning efficiency is increased if immediate feedback is provided for students. Automatic analysis of student programs has the potential to provide immediate feedback for students and to assist teaching staff in the marking process. This paper describes a “fill in the gap” programming analysis framework which tests students’ solutions and gives feedback on their correctness, detects logic errors and provides hints on how to fix these errors. Currently, the framework is being used with the Environment for Learning to Programming (ELP) system at Queensland University of Technology (QUT); however, the framework can be integrated into any existing online learning environment or programming Integrated Development Environment (IDE)