Continuous influence maximization (CIM) in social networks aims to maximize the expected influence spreading by assigning each user a continuous weight reflecting the likelihood and cost for him becoming a seed. Traditional CIM assumes a budget constrain to limit the total cost of all users. However, this assumption does not tenable in practical applications. In practice, it is not necessary to incur costs for all the users. Instead, the budget should be set only for the cost associated with the seed set. In this article, an extended CIM problem of cost distribution under budget (CDB) is defined, which aims to assign different costs to the customers according to their ability to spread influence, ensuring that the cost of each potential seed set does not exceed the budget, while the expected spreading of the product’s influence is maximized. The NP-hardness of CDB and the monotonicity and submodularity of its objective function are investigated. We formulate the CDB problem into a constrained optimization, and present a greedy descent-based algorithm for the problem. In each iteration of the greedy descent method, the influence increment of each node is calculated according to its estimated influence spreading range. The cost distribution is updated along the direction with the maximum increment. The optimal cost distribution can be obtained after several iterations. Precision of the results obtained by the proposed algorithm is analyzed. To avoid the time-consuming simulations, we design an effective algorithm for estimating the seed influence spreading range. Experiment results on real and synthetic networks show that the proposed algorithm can significantly improve the expected influence spreading.

We are currently in a network era which enables us to communicate more widely and more easily via the social networks. Meanwhile, negative information, such as fake news, rumors and computer viruses, often spread in social network. In order to restrain the propagation of such negative influence, we must find its sources in the network. But in real-world applications, we usually only know the scope of the negative influence spreading, and do not know who first propagates the negative influence. However, we can identify the sources of the negative influence based on the information of some observed nodes which are negatively influenced. This is the problem of influence sources locating. To tackle this problem, we present a latent space mapping-based method for identifying the multiple influence sources in the independent cascade model. The method first detects the candidate sources of the observed nodes based on message passing in a reversed network. An algorithm is presented to calculate the activation probability between nodes according to the influence spreading pattern in the independent cascade model. To evaluate each node’s rationality as the propagation source, we use the difference between the length of the path influencing an observed node and its activation time. We define two latent spaces, namely the influence senders and receivers’ latent spaces, and map the nodes into these two latent spaces to form a model describing the influence propagation. An estimation-maximization-based algorithm is proposed to optimize the propagation model. Based on this model, we propose a latent space mapping-based algorithm to identify the influence sources. The probability for each node to be a source is calculated by its positions in the latent spaces. Finally, k nodes with the largest probabilities are selected as the sources. Empirical results demonstrate that the influence sources identified by the proposed method can influence more observed nodes at more accurate time than other methods.

Summary Vertical data structure is very important for closed frequent itemset mining. All closed frequent itemsets can be found by simply using the operations of AND/OR. However, it consumes a large amount of storage space, especially in the case of large‐size dataset. This paper proposes an algorithm for mining closed frequent itemsets based on a new vertical data structure. The proposed data structure is helpful to save storage space by using a multi‐layer index. At the same time, numerous CPU and graphics processing unit can be employed in parallel to achieve high‐efficiency computing. Especially when dealing with large datasets, the proposed algorithm can obtain a high‐speed computing with the help of graphics processing unit. The improved vertical structure reduces the storage space of the data. The experimental results show that our proposed algorithm requires much less computation time than other related methods. Copyright © 2016 John Wiley & Sons, Ltd.

The problem of link prediction has attracted considerable recent attention from various domains such as sociology, anthropology, information science, and computer sciences. In this paper, we propose a link prediction algorithm based on ant colony optimization. By exploiting the swarm intelligence, the algorithm employs artificial ants to travel on a logical graph. Pheromone and heuristic information are assigned in the edges of the logical graph. Each ant chooses its path according to the value of the pheromone and heuristic information on the edges. The paths the ants traveled are evaluated, and the pheromone information on each edge is updated according to the quality of the path it located. The pheromone on each edge is used as the final score of the similarity between the nodes. Experimental results on a number of real networks show that the algorithm improves the prediction accuracy while maintaining low time complexity. We also extend the method to solve the link prediction problem in networks with node attributes, and the extended method also can detect the missing or incomplete attributes of data. Our experimental results show that it can obtain higher quality results on the networks with node attributes than other algorithms.

Ant colony optimization (ACO), an intelligential optimization algorithm, has been widely used to solve combinational optimization problems. One of the obstacles in applying ACO is that its search process is sometimes biased by algorithm features such

BACKGROUND: Understanding the localization of proteins in cells is vital to characterizing their functions and possible interactions. As a result, identifying the (sub)cellular compartment within which a protein is located becomes an important problem in protein classification. This classification issue thus involves predicting labels in a dataset with a limited number of labeled data points available. By utilizing a graph representation of protein data, random walk techniques have performed well in sequence classification and functional prediction; however, this method has not yet been applied to protein localization. Accordingly, we propose a novel classifier in the site prediction of proteins based on random walks on a graph. RESULTS: We propose a graph theory model for predicting protein localization using data generated in yeast and gram-negative (Gneg) bacteria. We tested the performance of our classifier on the two datasets, optimizing the model training parameters by varying the laziness values and the number of steps taken during the random walk. Using 10-fold cross-validation, we achieved an accuracy of above 61% for yeast data and about 93% for gram-negative bacteria. CONCLUSIONS: This study presents a new classifier derived from the random walk technique and applies this classifier to investigate the cellular localization of proteins. The prediction accuracy and additional validation demonstrate an improvement over previous methods, such as support vector machine (SVM)-based classifiers.

We tackle the problem of answering maximum probabilistic top-k tuple set queries. We use a sliding-window model on uncertain data streams and present an efficient algorithm for processing sliding-window queries on uncertain streams. In each sliding window, the algorithm selects the k tuples with the highest probabilities from sets of different numbers of the tuples with the highest scores. Then, the algorithm computes existential probability of the top-k tuples, and chooses the set with the highest probability as the top-k query result. We theoretically prove the correctness of the algorithm. Our experimental results show that our algorithm requires lower time and space complexity than other existing algorithms.

Most of the existing algorithms for mining frequent patterns could produce lots of projected databases and short candidate patterns which could increase the time and memory cost of mining. In order to overcome such shortcoming, we propose two fast and efficient algorithms named SBPM and MSPM for mining frequent patterns in single and multiple biological respectively. We first present the concept of primary pattern, and then use prefix tree for mining frequent primary patterns. A pattern growth approach is also presented to mine all the frequent patterns without producing large amount of irrelevant patterns. Our experimental results show that our algorithms not only improve the performance but also achieve effective mining results.

Multiple sequence alignment is an important and difficult problem in molecular biology and bioinformatics. In this paper, we propose a partitioning approach that significantly improves the solution time and quality by utilizing the locality structure of the problem. The algorithm solves the multiple sequence alignment in three stages. First, an automated and suboptimal partitioning strategy is used to divide the set of sequences into several subsections. Then a multiple sequence alignment algorithm based on ant colony optimization is used to align the sequences of each subsection. Finally, the alignment of original sequences can be obtained by assembling the result of each subsection. The ant colony algorithm is highly optimized in order to avoid local optimal traps and converge to global optimal efficiently. Experimental results show that the algorithm can significantly reduce the running time and improve the solution quality on large-scale multiple sequence alignment benchmarks.

BACKGROUND: The problem of inferring the evolutionary history and constructing the phylogenetic tree with high performance has become one of the major problems in computational biology. RESULTS: A new phylogenetic tree construction method from a given set of objects (proteins, species, etc.) is presented. As an extension of ant colony optimization, this method proposes an adaptive phylogenetic clustering algorithm based on a digraph to find a tree structure that defines the ancestral relationships among the given objects. CONCLUSION: Our phylogenetic tree construction method is tested to compare its results with that of the genetic algorithm (GA). Experimental results show that our algorithm converges much faster and also achieves higher quality than GA.

BACKGROUND: Ant colony algorithm has emerged recently as a new meta-heuristic method, which is inspired from the behaviours of real ants for solving NP-hard problems. However, the classical ant colony algorithm also has its defects of stagnation and premature. This paper aims at remedying these problems. RESULTS: In this paper, we propose an adaptive ant colony algorithm that simulates the behaviour of biological immune system. The solutions of the problem are much more diversified than traditional ant colony algorithms. CONCLUSION: The proposed method for improving the performance of traditional ant colony algorithm takes into account the polarization of the colonies, and adaptively adjusts the distribution of the solutions obtained by the ants. This makes the solutions more diverse so as to avoid the stagnation and premature phenomena.

With the advance of microarray technology, clustering analysis has become a key tool to make sense of the massive amounts of genes expression data. An artificial ants sleeping model (ASM) and an adaptive artificial ants clustering algorithm (A/sup 4/C) are presented to solve the clustering problem in data mining by simulating the behaviors of social ant colonies. In the ASM model, each datum is represented by an agent. The agents' environment is a two-dimensional grid. In A/sup 4/C, the agents can form into high-quality clusters by making simple moves according to little local information from its neighborhood and the parameters are selected and adjusted adaptively. Experimental results on clustering benchmarks show the ASM and A/sup 4/C are simpler, easier to implement, and more efficient than previous methods.

Summary form only given. A parallel algorithm for EDT transform on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n/spl times/n pixels, the algorithm can complete the EDT transform in O(nlogn/(c(n)logd(n))) time using n.d(n).c(n) processors, where c(n) and d(n) are parameters satisfying 1/spl les/c(n)/spl les/n , and 1

The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to its distance to the nearest foreground pixel. Two parallel algorithms for EDT on linear array with reconfigurable pipeline bus system (LARPBS) are presented. For an image with n × n pixels, the first algorithm can complete EDT in O[(log n log log n)/(log log log n)] time using n2 processors. The second algorithm can computethe EDT in O(log n log log n) time using n2/(log log n) processors.

A parallel algorithm for Euclidean distance transform (EDT) on linear array with reconfigurable pipeline bus system (LARPBS) is presented. For an image with n/spl times/n pixels, the algorithm can complete EDT transform in O(n log n/c(n) log d(n)) time using n/spl middot/d(n)/spl middot/c(n) processors, where c(n) and d(n) are parameters satisfying 1/spl les/c(n)/spl les/n, and 1