The container stowage planning problem is known to be NP-hard and heuristic algorithms have been proposed. Conventionally, the efficiency of the stowage planning algorithms are improved by pruning or reducing the search space. We observe that constraint evaluation is the core of most algorithms. In addition, the order at which the constraints are evaluated can have significant impact on the efficiency of the constraint evaluation engine. We propose random sample model (RSM) and sequential sample model (SSM) for analysis of the problem. We present and evaluate seven strategies in optimizing the constraint evaluation engine. We show how to achieve the optimal constraint ordering with respect to RSM and SSM, respectively. However, the optimal ordering for SSM requires perfect information about the states of the constraint tests, which is impractical. We present an alternative strategy and show empirically that its efficiency is close to the optimal. Experiments show that, compared to a naïve ordering, an average of 2.74 times speed up in the evaluation engine can be achieved.Note to Practitioners—Automated stowage planning has become a trend as the number of mega-scale containerships being deployed has increased drastically over the past decade. Due to the nature of the problem, it is impractical to expect the best stowage plan within a limited amount of time, and hence, many heuristics have been devised to reduce the solution space. Many heuristics algorithms share a common core-repeatedly selecting a stowage slot and a container (selection mechanism) and evaluate whether all of the constraints are satisfied. To improve the efficiency, most studies aim to reduce the number of location-container pairs being considered. We consider an alternative approach that improves the efficiency of the constraint evaluation engine. Specifically, we show how to improve the efficiency by strategically reordering the sequence in which the constraints are evaluated. With the improvements on the efficiency, the stowage algorithm is one step closer to being able to generate solutions in real time. This may enable the shipping companies to take last-minute shipment order and react to changes in demands quickly.

The spread of influence under Independent Cascade model and Linear Threshold model has been studied extensively in the literature. The two models describe the process through which individuals adopt a new product. We study the rumour model, that describes the process through which a news is spread in a network. We consider the task of identifying a collection of seed nodes of minimal size to spread a news such that, within a certain time threshold, the news can be spread to a target number of nodes with certain probability. We show that the problem is NP-hard. Moreover, we show that the function that calculates the probability of achieving the coverage threshold is not submodular, and hence conventional optimization techniques based on the submodularity property cannot be applied directly. Nevertheless, we present an algorithm that can provably approximate the size of the optimal seed set. In addition, we present a Monte-Carlo algorithm for choosing the best node that generates the greatest marginal increment in expected coverage. We compare the size of seed set with other baseline algorithms by using both real and synthetic networks. Our algorithm consistently outperforms other methods. For certain cases, the sizes of seed sets returned by our algorithm are less than a hundredth of that returned by the baseline algorithms compared.

Identifying nodes that play important roles in network dynamics in large scale complex networks is crucial for both characterizing the network and resource management. Under the viral marketing setting, Diffusion Centrality (DC) estimates the influential power of an individual. For the transport and physics communities, a node is considered important in Markov centrality (MC) if it can be quickly reached from the other nodes. Because these networks could contain millions of nodes, any ranking algorithm must have low time requirements to be practically useful. In this paper, we show that both metrics are strongly correlated, and we present a new method to enable fast estimation of the two metrics for large scale networks. The new approach is further validated empirically by using both real and synthetic networks. Our results refined the intuition that the influential power of an individual is largely governed by the local topology, rather than the mere number of contacts (node degree) alone. This allows us to better characterize the properties of the nodes that affect the outcome of the two centrality metrics.

Previous studies suggest that human mobility is highly regular in two respects. Firstly, individual's travels are governed by occasional exploration of new locations and preferential return to most frequently visited locations. Secondly, human mobility sequences exhibit high predictability. The existing model [1] is able to mimic exploration and preferential return, and lit actual mobility data. However, the high predictability issue is not addressed in this model. In this paper, we derive an upper bound of the predictability manifested by this model. Motivated by the incorrigible gap between the bound and the empirical results shown in [2], we further propose a new Markovian model by modifying the rule of preferential return to be conditional on the individuals' current location. We show both theoretically and empirically that the new Markovian model presents high predictability while preserving the desirable scaling properties of the original model in [1], making it the most complete model to date in capturing the essence of human mobility.

Various Markov models have been proposed to model individuals' mobility, i.e., the transitions between locations. Although these studies are able to show high predicting accuracy of individuals' next move, two basic assumptions of these studies, namely the stationarity of individuals' mobility sequence and the dependency of visiting the locations, have never been validated. Moreover, a famous recent research suggests that individuals prefer to revisit the locations merely according to the visitation frequency. In this paper, we study these two presumed properties of individuals' mobility sequence. Specifically, stationarity is validated by analyzing the autocorrelation of the mobility sequences that are encoded under three popular schemes. With appropriate choice of spatial and temporal scale, two types of periodicity, e.g., daily and weekly, are observed. The visiting dependency between the locations is validated by comparing the entropy of the mobility sequence to the entropies generated from either i.i.d. or Markov sources. Based on these two statistical properties, we then construct two Markov models with three revisiting rules to model individuals' mobility. The average log-loss values show that the best revisiting rule for the Markov model is a combination of the visitation frequency and the distance of the next location to the current locations. This finding suggests that individuals' mobility is influenced by both temporal and spatial localities, rather than by either form of locality alone as suggested in the previous study.

The spread of influence in a network is a fundamental issue in many complex systems. For instance, the word of-mouth effect in a social network is crucial to the emerging viral market. The process was previously analyzed with a voter model where an individual weighs the opinions of his acquaintances equally. However, one would expect that an individual's opinion is often more swayed by her/his better connected peers. As such, the influence of a node x on another node should be proportional to x's degree. This paper studies the spread of influence under the latter model - called Preferential Voter Model (PVM) for easier reference. We first present the exact form of the random walk stationary distribution for PVM, based on which, we show that the First Passage Time (FPT) of PVM follows an exponential decay. Furthermore, compared against the conventional (nonpreferential) voter model, we show that nodes with larger degrees exhibit faster decay rate and lower mean First Passage Time in PVM. These new results have applications to network-based complex systems. For instance, in the context of viral marketing in a social network, picking nodes of larger degrees as the starting nodes of a sales campaign not only maximizes the expected number of influenced nodes in the network, but also reduces the expected time to spread the influence. Thus, our result confirms analytically that well-connected individuals indeed exert faster and more effective influences in social networks under the preferential model.

The ability to foresee the next moves of a user is crucial to ubiquitous computing. Disregarding major differences in individuals' routines, recent ground-breaking analysis on mobile phone data suggests high predictability in mobility. By nature, however, mobile phone data offer very low spatial and temporal resolutions. It remains largely unknown how the predictability changes with respect to different spatial/temporal scales. Using high-resolution GPS data, this paper investigates the scaling effects on predictability. Given specified spatial-temporal scales, recorded trajectories are encoded into long strings of distinct locations, and several information-theoretic measures of predictability are derived. Somewhat surprisingly, high predictability is still present at very high spatial/temporal resolutions. Moreover, the predictability is independent of the overall mobility area covered. This suggests highly regular mobility behaviors. Moreover, by varying the scales over a wide range, an invariance is observed which suggests that certain trade-offs between the predicting accuracy and spatial-temporal resolution are unavoidable. As many applications in ubiquitous computing concern mobility, these findings should have direct implications.