Search

In this paper, we study the problem of searching k-discriminative paths on road networks. Given a source node src and a destination node dest on a road network, we aim to search k paths between src and dest, where these k paths satisfy the multi-objective goal including the minimization of the path overlapping and the minimization of the path length. Specifically, the requirement of minimizing the overlapping among paths, which is a NP-hard issue, is highly demanded in applications of disaster rescue management such as the evacuation plan. In this paper, we consider the deployment of k-discriminative paths for various applications, including queries for emergency-purpose applications, queries of multi-objective Pareto front for pre-schedule transportation plan, and queries with multiple sources and destinations for the regional evacuation. Due to its NP-hard nature, the heuristic strategy based on the ant colony optimization is devised in this work. As validated by our experimental studies on real road networks, the proposed algorithm can achieve the discovery of k-discriminative paths efficiently and effectively, showing its prominent advantages to be a practicable service for evacuation-related applications.

Location-based social services such as Foursquare and Facebook Place allow users to perform check-ins at places and interact with each other in geography (e.g. check-in together). While existing studies have exhibited that the adversary can accurately infer social ties based on check-in data, the traditional check-in mechanism cannot protect the acquaintance privacy of users. In this work, therefore, we propose a novel shielding check-in system, whose goal is to guide users to check-in at secure places. We accordingly propose a novel research problem, Check-in Shielding against Acquaintance Inference (CSAI), which aims at recommending a list of secure places when users intend to check-ins so that the potential that the adversary correctly identifies the friends of users can be significantly reduced. We develop the Check-in Shielding Scheme (CSS) framework to solve the CSAI problem. CSS consists of two steps, namely estimating the social strength between users and generating a list of secure places. Experiments conducted on Foursquare and Gowalla check-in datasets show that CSS is able to not only outperform several competing methods under various scenario settings, but also lead to the check-in distance preserving and ensure the usability of the new check-in data in Point-of-Interest (POI) recommendation.

In this paper, we explore a new mining paradigm, called spatial-temporal fluctuating patterns (abbreviated as STFs), to discover potentially fluctuating and useful feature sets from the spatial-temporal data. These feature sets have some properties which are variant as time advances. Once STFs are discovered, we can find the turning points of patterns, which enables anomaly detection and transformation discovery over time. For example, the discovery of STFs can possibly figure out the phenomenon of virus variation during the epidemic outbreak, further providing the government with clues for the epidemic control. Therefore, we develop a union-based mining with the downward-closure structure to speed up the spatial-temporal mining process and dynamically compute fluctuating patterns. As shown in our experimental studies, the proposed framework can efficiently discover STFs on a real epidemic disease dataset, showing its prominent advantages to be utilized in real applications.

With the popularity of mobile devices and various sensors, the local geographical activities of human beings can be easily accessed than ever. Yet due to the privacy concern, it is difficult to acquire the social connections among people possessed by services providers, which can benefit applications such as identifying terrorists and recommender systems. In this paper, we propose the location-aware acquaintance inference (LAI) problem, which aims at finding the acquaintances for any given query individual based on solely people’s local geographical activities, such as geo-tagged posts in Instagram and meeting events in Meetup, within a targeted geo-spatial area. We propose to leverage the concept of active learning to tackle the LAI problem. We develop a novel semi-supervised model, active learning-enhanced random walk (ARW), which imposes the idea of active learning into the technique of random walk with restart (RWR) in an activity graph. Specifically, we devise a series of candidate selection strategies to select unlabeled individuals for labeling and perform the different graph refinement mechanisms that reflect the labeling feedback to guide the RWR random surfer. Experiments conducted on Instagram and Meetup datasets exhibit the promising performance, compared with a set of state-of-the-art methods. With a series of empirical settings, ARW is demonstrated to derive satisfying results of acquaintance inference in different real scenarios.

We in this paper explore a new link prediction paradigm, called ‘worship’ prediction, to discover worship links between users and celebrities on social networks. The prediction of ‘worship’ links enables valuable social services, such as viral marketing, popularity estimation, and celebrity recommendation. However, as the concern of business security and personal privacy, only public-accessible statistical social properties, instead of the detailed information of users, can be utilized to predict the ‘worship’ labels. In addition, we observe that friendship properties are not effective to predict the desired links, meaning that most of previous work which rely on the friendship properties cannot be successfully applied in the prediction of worship link. To address these issues, a novel learning framework is devised, including a factor graph with new discovered statistical properties and a Gaussian estimation based learning algorithm with active learning. Our experimental studies on real data, including Instagram, Twitter and DBLP, show that the proposed learning framework can overcome the problem of missing labels and efficiently discover worship links.

In this paper, we study a novel problem of influence maximization on social networks: Given a period of promotion time, a set of target users and a network in which each node can be activated by its neighbors multiple times, we aim at determining the k most influential seeds to maximize the total frequency of activations received by these target users. The promising viral marketing paradigm on social network is different from the current research in two main aspects. First, instead of maximizing the message spread over the entire social network, we focus on the target market since the business vendors almost specify the group of target users before designing its marketing strategy. Second, the status of a user is no longer a binary indicator representing either active or inactive. In the new model, the user status turns to be an integer value reflecting the amount of influences delivered to that user. In this paper, we prove the NP-hard nature of this challenging problem. We further present several strategies, including an efficient heuristic algorithm based on the simulated annealing optimization concept and a greedy algorithm as the baseline, to select the initial k seeds in pursuit of resulting quality close to the optimal one. As demonstrated in the empirical study on real data, instead of only providing the flexibility of striking a compromise between the execution efficiency and the resulting quality, our proposed heuristic algorithm can achieve high efficiency and meanwhile can obtain the target acceptance frequency even better than the greedy result in some cases, demonstrating its prominent feasibility to resolve the challenging problem efficiently.

We explore in this paper a practicably interesting mining task to retrieve top-k (closed) itemsets in the presence of the memory constraint. Specifically, as opposed to most previous works that concentrate on improving the mining efficiency or on reducing the memory size by best effort, we first attempt to specify the available upper memory size that can be utilized by mining frequent itemsets. To comply with the upper bound of the memory consumption, two efficient algorithms, called MTK and MTK_Close, are devised for mining frequent itemsets and closed itemsets, respectively, without specifying the subtle minimum support. Instead, users only need to give a more human-understandable parameter, namely the desired number of frequent (closed) itemsets k. In practice, it is quite challenging to constrain the memory consumption while also efficiently retrieving top-k itemsets. To effectively achieve this, MTK and MTK_Close are devised as level-wise search algorithms, where the number of candidates being generated-and-tested in each database scan will be limited. A novel search approach, called ?-stair search, is utilized in MTK and MTK_Close to effectively assign the available memory for testing candidate itemsets with various itemset-lengths, which leads to a small number of required database scans. As demonstrated in the empirical study on real data and synthetic data, instead of only providing the flexibility of striking a compromise between the execution efficiency and the memory consumption, MTK and MTK_Close can both achieve high efficiency and have a constrained memory bound, showing the prominent advantage to be practical algorithms of mining frequent patterns.

In this paper, we identify and explore that the power-law relationship and the self-similar phenomenon appear in the itemset support distribution. The itemset support distribution refers to the distribution of the count of itemsets versus their supports. Exploring the characteristics of these natural phenomena is useful to many applications such as providing the direction of tuning the performance of the frequent-itemset mining. However, due to the explosive number of itemsets, it is prohibitively expensive to retrieve lots of itemsets before we identify the characteristics of the itemset support distribution in targeted data. As such, we also propose a valid and cost-effective algorithm, called algorithm PPL, to extract characteristics of the itemset support distribution. Furthermore, to fully explore the advantages of our discovery, we also propose novel mechanisms with the help of PPL to solve two important problems: (1) determining a subtle parameter for mining approximate frequent itemsets over data streams; and (2) determining the sufficient sample size for mining frequent patterns. As validated in our experimental results, PPL can efficiently and precisely identify the characteristics of the itemset support distribution in various real data. In addition, empirical studies also demonstrate that our mechanisms for those two challenging problems are in orders of magnitude better than previous works, showing the prominent advantage of PPL to be an important pre-processing means for mining applications.