Graph anomaly detection is attracting remarkable multidisciplinary research interests ranging from finance, healthcare, and social network analysis. Recent advances on graph neural networks have substantially improved the detection performance via semi-supervised representation learning. However, prior work suggests that deep graph-based methods tend to learn spurious correlations. As a result, they fail to generalize beyond training data distribution. In this article, we aim to identify structural and contextual anomaly nodes in an attributed graph. Based on our preliminary data analyses, spurious correlations can be eliminated with causal subgraph interventions. Therefore, we propose a new graph-based anomaly detection model that can learn causal relations for anomaly detection while generalizing to new environments. To handle situations with varying environments, we steer the generative model to manufacture synthetic environment features, which are exerted on realistic subgraphs to generate counterfactual subgraphs. Further, these counterfactual subgraphs help a few-shot anomaly detection model learn transferable and causal relations across different environments. The experiments on three real-world attributed graphs show that the proposed approach achieves the best performance compared to the state-of-the-art baselines and learns robust causal representations resistant to noises and spurious correlations.

Supervised learning, while prevalent for information cascade modeling, often requires abundant labeled data in training, and the trained model is not easy to generalize across tasks and datasets. Semi-supervised learning facilitates unlabeled data for cascade understanding in pre-training. It often learns fine-grained feature-level representations, which can easily result in overfitting for downstream tasks. Recently, contrastive self-supervised learning is designed to alleviate these two fundamental issues in linguistic and visual tasks. However, its direct applicability for cascade modeling, especially graph cascade related tasks, remains underexplored. In this work, we present Contrastive Cascade Graph Learning (CCGL), a novel framework for cascade graph representation learning in a contrastive, self-supervised, and task-agnostic way. In particular, CCGL first designs an effective data augmentation strategy to capture variation and uncertainty. Second, it learns a generic model for graph cascade tasks via self-supervised contrastive pre-training using both unlabeled and labeled data. Third, CCGL learns a task-specific cascade model via fine-tuning using labeled data. Finally, to make the model transferable across datasets and cascade applications, CCGL further enhances the model via distillation using a teacher-student architecture. We demonstrate that CCGL significantly outperforms its supervised and semi-supervised counterparts for several downstream tasks.

Understanding in-network information diffusion is a fundamental problem in many applications and one of the primary challenges is to predict the information cascade size. Most of the existing models rely either on hypothesized point process (e.g., Poisson and Hawkes processes), or simply predict the information propagation via deep neural networks. However, they fail to simultaneously capture the underlying global and local structures of a cascade and the propagation uncertainty in the diffusion, which may result in unsatisfactory prediction performance. To address these, in this work we propose a novel probabilistic cascade prediction frameworkCasFlow: Hierarchical Cascade Normalizing Flows. CasFlow allows a non-linear information diffusion inference and models the information diffusion process by learning the latent representation of both the structural and temporal information. It is a pattern-agnostic model leveraging normalizing flows to learn the node-level and cascade-level latent factors in an unsupervised manner. In addition, CasFlow is capable of capturing both the cascade representation uncertainty and node infection uncertainty, while enabling hierarchical pattern learning of information diffusion. Extensive experiments conducted on real-world datasets demonstrate that CasFlow reduces the prediction error to 21.0% by only observing half an hour of cascades, compared to state-of-the-art approaches, while also enabling model interpretability.

Many deep (semi-) supervised neural network-based methods have been proposed for anomaly detection, tackling the issue of limited labeled data. They have shown good performance but still face two major challenges. First, insufficient labeled data limits their flexibility. Second, measuring the uncertainty of the prediction, especially when dealing with objects deviating largely from training data, has not been well studied. Another common reason preventing them from prevailing is that they learn a determined function to make predictions from the input. This usually makes the predicted results uncertain and lacks robustness. To address these problems, we propose a novel framework, incorporating the neural process into the semi-supervised anomaly detection paradigm and efficiently using unlabeled data and a handful of labeled data in training. Different from other methods, ours is equivalent to modeling the distribution of functions representing anomalous patterns according to the labeled data rather than learning a single determined function for anomaly detection. Our approach improves the flexibility and robustness under the condition of insufficient training data, and can measure the uncertainty of prediction results. Extensive experiments under real-world datasets demonstrate that our proposed method can significantly improve anomaly detection performance compared to several cutting-edge benchmarks.

With the rapid development of mobile technology, nowadays, people spend a large amount of time on mobile devices. The locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisements. In this paper, we consider an important location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the${\sf reconciliation\ approach}$, which has an approximation ratio of$(1-\epsilon)\cdot \theta$. In addition, we also address the online scenario, in which customers arrive in a streaming fashion, with one novel online algorithm, namely the${\sf online\ adaptive\ factor-aware\ approach}$, which has a competitive ratio (compared to the optimal solution of the offline scenario) of$\frac{\ln (g)+1}{\theta }$,$g>e$, where$e$is the base of the natural logarithm. Through extensive experiments, we demonstrate the efficiency and effectiveness of our proposed approaches over both real and synthetic datasets.

Traffic bottlenecks identification plays an important role in traffic planning and provides decision-making for prevention of traffic congestion. Although traffic bottlenecks widely exist, they are difficult to predict because of the changing traffic condition and traffic demand. In this paper, we introduce a traffic congestion diffusion (TCD) model with traffic flow influence (TFI) to capture the traffic dynamics and give a panoramic view for the city by cross domain data fusion. We proposed novel definition of bottleneck from the perspective of influence spread under TCD. The bottlenecks identification problem is modeled as an influence maximization problem, i.e., selecting the top K influential nodes in road networks under certain traffic conditions. We establish the submodularity of influence spread and solve the NP-hard optimal seed selection problem by using an efficient heuristic algorithm (TCD-IM) with provable near-optimal performance guarantees. To the best of our knowledge, this should be the first model for a metro-city scale from the influence perspective. The TCD-IM model is able to identify the dynamic traffic bottlenecks.

Nowadays, the locations and contexts of users are easily accessed by mobile advertising brokers, and the brokers can send customers related location-based advertisement. In this paper, we consider a location-based advertising problem, namely maximum utility advertisement assignment (MUAA) problem, with the estimation of the interests of customers and the contexts of the vendors, we want to maximize the overall utility of ads by determining the ads sent to each customer subject to the constraints of the capacities of customers, the distance ranges and the budgets of vendors. We prove that the MUAA problem is NP-hard and intractable. Thus, we propose one offline approach, namely the reconciliation approach, which has an approximation ratio of (1 - ε) · θ, where θ = min(a1/2n1c, a2/n2c, ⋯,am/nmc), and nz is the larger value between the number of valid vendors and the capacity aiof customer ui. Experiments on real data sets confirm the efficiency and effectiveness of our proposed approach.

Profiling driver behaviors and designing appropriate pricing models are essential for auto insurance companies to gain profits and attract customers (drivers). The existing approaches either rely on static demographic information like age, or model only coarse-grained driving behaviors. They are therefore ineffective to yield accurate risk predictions over time for appropriate pricing, resulting in profit decline or even financial loss. Moreover, existing pricing strategies seldom take profit maximization into consideration, especially under the enterprise constraints. The recent growth of vehicle telematics data (vehicle sensing data) brings new opportunities to auto insurance industry, because of its sheer size and fine-grained mobility for profiling drivers. But, how to fuse these sparse, inconsistent and heterogeneous data is still not well addressed. To tackle these problems, we propose a unified PPP (Profile-Price-Profit) framework, working on the real-world large-scale vehicle telematics data and insurance data. PPP profiles drivers' fine-grained behaviors by considering various driving features from the trajectory perspective. Then, to predict drivers' risk probabilities, PPP leverages the group-level insight and categorizes drivers' different temporal risk change patterns into groups by ensemble learning. Next, the pricing model in PPP incorporates both the demographic analysis and the mobility factors of driving risk and mileage, to generate personalized insurance price for supporting flexible premium periods. Finally, the maximal profit problem proves to be NP-Complete. Then, an efficient heuristic-based dynamic programming is proposed. Extensive experimental results demonstrated that, PPP effectively predicts the driver's risk and outperforms the current company's pricing strategy (in industry) and the state-of-the-art approach. PPP also achieves near the maximal profit (difference by only 3%) for the company, and lowers the total price for the drivers.

Traffic congestion is a spatio-temporal state of speeds beyond the capacity of road design and congestion may propagate through road networks. Characterizing the diffusion process is of great importance both in congestion relief and traffic condition prediction. Traffic congestion diffusion (TCD) in road networks can be observed, but literature lacks accurate models for characterizing the process. In this paper, we define a concept of Traffic Flow Influence (TFI) as a base for congestion diffusion. A TCD model is designed to characterize not only the traffic flow evolving process in time domain but also the propagation process of TFI through road networks in space domain. The model is for traffic networks in a city, which is divided into grids and each grid is modeled by traffic status of congested or smooth. Different from other diffusion models, the grid status depends on not only its current condition, but also the relative traffic flow from and to its neighbors. We use a gradient descent approach to quantify the traffic flow and TFI intensity of road networks. To the best of our knowledge, this should be the first model for a metro-city scale. The TCD model with TFI is able to predict grid status with an accuracy as high as 89%. Experimental results based on real-world taxi trajectory data in a metro-city show that the TCD approach performs best in comparison with its competitors.

In this paper, we detect communities from trajectories. Existing algorithms for trajectory clustering usually rely on simplex representation and a single proximity-related metric. Unfortunately, additional information markers (e.g., social interactions or semantics in the spatial layout) are ignored, leading to the inability to fully discover the communities in trajectory database. This is especially true for human-generated trajectories, where additional fine-grained markers (e.g., movement velocity at certain locations, or the sequence of semantic spaces visited) are especially useful in capturing latent relationships among community members. To overcome this limitation, we propose TODMIS, a general framework for Trajectory-based community Detection by diffusion modeling on Multiple Information Sources. TODMIS combines additional information with raw trajectory data and construct the diffusion process on multiple similarity metrics. It also learns the consistent graph Laplacians by constructing the multi-modal diffusion process and optimizing the heat kernel coupling on each pair of similarity matrices from multiple information sources. Then, dense sub-graph detection is used to discover the set of distinct communities (including community size) on the coupled multi-graph representation. At last, based on the community information, we propose a novel model for online recommendation. We evaluate TODMIS and our online recommendation methods using different real-life datasets. Experimental results demonstrate the effectiveness and efficiency of our methods.

The conventional crowdsourcing paradigm requires an explicit task description and payment scheme. Requesters can then easily determine whether the crowdsourced results are satisfactory, and workers will have a fairly clear expectation of the monetary reward once the task is accomplished. However, such a paradigm becomes problematic when it is applied to Object Identification (OI) tasks. First, for OI tasks, it is difficult for requesters to evaluate whether sufficient numbers of objects have been found by an individual worker, warranting payment. Second, the same objects can be detected by many workers and ending up being unnecessary workload and inefficient performance. In this paper, we design a new crowdsourcing paradigm for OI tasks. Designing such a paradigm is challenging. Firstly, an easily-detected object can be found by multiple workers, which leads to an unfair situation that the requester has to make extra payments for the duplication. Secondly, there is usually a time limit to finish the overall crowdsourcing process, which demands efficient assignment strategy. To address these challenges, we propose solutions to achieve fairness by a Pay-As-You-Go (PAYG) mechanism and efficiency by a new worker-assignment scheme, Adaptive Worker Assignment (AWA). Extensive experiments are conducted to demonstrate the advantages of this new paradigm.

Information diffusion in social networks is often characterized by huge participating communities and viral cascades of high dynamicity. To observe, summarize, and understand the evolution of dynamic diffusion processes in an informative and insightful way is a challenge of high practical value. However, few existing studies aim to summarize networks for interesting dynamic patterns. Dynamic networks raise new challenges not found in static settings, including time sensitivity, online interestingness evaluation, and summary traceability, which render existing techniques inadequate. We propose dynamic network summarization to summarize dynamic networks with millions of nodes by only capturing the few most interesting nodes or edges overtime. Based on the concepts of diffusion radius and scope, we define interestingness measures for dynamic networks, and we propose OSNet, an online summarization framework for dynamic networks. Efficient algorithms are included in OSNet. We report on extensive experiments with both synthetic and real-life data. The study offers insight into the effectiveness, efficiency, and design properties of OSNet.

One of the most important features of microblogging services such as Twitter is how easy it is to re-share a piece of information across the network through various user connections, forming what we call a "cascade". Business applications such as viral marketing have driven a tremendous amount of research effort predicting whether a certain cascade will go viral. Yet the rarity of viral cascades in real data poses a challenge to all existing prediction methods. One solution is to simulate cascades that well fit the real viral ones, which requires our ability to tell how a certain cascade grows over time. In this paper, we build a general time-aware cascade model for each particular cascade, in which the chance of one user's re-sharing behaviour over time is modelled as a hazard function of time. Based on two key observations on user retweeting behaviour, we design an appropriate hazard function specifically for Twitter network. We evaluate our model on a large real Twitter dataset with over two million retweeting cascades. Our experiment results show our proposed model outperforms other baseline models in terms of model fitting. Further, we make use of our model to simulate viral cascades, which are otherwise few and far in-between, to alleviate the imbalance issue in cascade data, offering a 20% boost in viral cascade discovery.

Detecting dominant clusters is important in many analytic applications. The state-of-the-art methods find dense subgraphs on the affinity graph as dominant clusters. However, the time and space complexities of those methods are dominated by the construction of affinity graph, which is quadratic with respect to the number of data points, and thus are impractical on large data sets. To tackle the challenge, in this paper, we apply Evolutionary Game Theory (EGT) and develop a scalable algorithm, Approximate Localized Infection Immunization Dynamics (ALID). The major idea is to perform Localized Infection Immunization Dynamics (LID) to find dense subgraphs within local ranges of the affinity graph. LID is further scaled up with guaranteed high efficiency and detection quality by an estimated Region of Interest (ROI) and a Candidate Infective Vertex Search method (CIVS). ALID only constructs small local affinity graphs and has time complexity O ( C ( a * + δ ) n ) and space complexity O ( a * ( a * + δ )), where a * is the size of the largest dominant cluster, and C « n and δ « n are small constants. We demonstrate by extensive experiments on both synthetic data and real world data that ALID achieves the state-of-the-art detection quality with much lower time and space cost on single machine. We also demonstrate the encouraging parallelization performance of ALID by implementing the Parallel ALID (PALID) on Apache Spark. PALID processes 50 million SIFT data points in 2.29 hours, achieving a speedup ratio of 7.51 with 8 executors.

The availability of trajectories tracking the geographical locations of people as a function of time offers an opportunity to study human behaviors. In this article, we study rationality from the perspective of user decision on visiting a point of interest (POI) which is represented as a trajectory. However, the analysis of rationality is challenged by a number of issues, for example, how to model a trajectory in terms of complex user decision processes? and how to detect hidden factors that have significant impact on the rational decision making? In this study, we propose Rationality Analysis Model (RAM) to analyze rationality from trajectories in terms of a set of impact factors. In order to automatically identify hidden factors, we propose a method, Collective Hidden Factor Retrieval (CHFR), which can also be generalized to parse multiple trajectories at the same time or parse individual trajectories of different time periods. Extensive experimental study is conducted on three large-scale real-life datasets (i.e., taxi trajectories, user shopping trajectories, and visiting trajectories in a theme park). The results show that the proposed methods are efficient, effective, and scalable. We also deploy a system in a large theme park to conduct a field study. Interesting findings and user feedback of the field study are provided to support other applications in user behavior mining and analysis, such as business intelligence and user management for marketing purposes.

Social identity linkage across different social media platforms is of critical importance to business intelligence by gaining from social data a deeper understanding and more accurate profiling of users. In this paper, we propose a solution framework, HYDRA, which consists of three key steps: (I) we model heterogeneous behavior by long-term topical distribution analysis and multi-resolution temporal behavior matching against high noise and information missing, and the behavior similarity are described by multi-dimensional similarity vector for each user pair; (II) we build structure consistency models to maximize the structure and behavior consistency on users' core social structure across different platforms, thus the task of identity linkage can be performed on groups of users, which is beyond the individual level linkage in previous study; and (III) we propose a normalized-margin-based linkage function formulation, and learn the linkage function by multi-objective optimization where both supervised pair-wise linkage function learning and structure consistency maximization are conducted towards a unified Pareto optimal solution. The model is able to deal with drastic information missing, and avoid the curse-of-dimensionality in handling high dimensional sparse representation. Extensive experiments on 10 million users across seven popular social networks platforms demonstrate that HYDRA correctly identifies real user linkage across different platforms from massive noisy user behavior data records, and outperforms existing state-of-the-art approaches by at least 20 percent under different settings, and four times better in most settings.

We consider the problem of adaptively routing a fleet of cooperative vehicles within a road network in the presence of uncertain and dynamic congestion conditions. To tackle this problem, we first propose a Gaussian process dynamic congestion model that can effectively characterize both the dynamics and the uncertainty of congestion conditions. Our model is efficient and thus facilitates real-time adaptive routing in the face of uncertainty. Using this congestion model, we develop efficient algorithms for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the system. A key property of our approach is the ability to efficiently reason about the long-term value of exploration, which enables collectively balancing the exploration/exploitation trade-off for entire fleets of vehicles. Our approach is validated by traffic data from two large Asian cities. Our congestion model is shown to be effective in modeling dynamic congestion conditions. Our routing algorithms also generate significantly faster routes compared to standard baselines, and achieve near-optimal performance compared to an omniscient routing algorithm. We also present the results from a preliminary field study, which showcases the efficacy of our approach.

Far beyond relationship topology, today's online social networks are also characterized by semantically rich text messages exchanged among users as well as GPS locations associated with those messages, as evidenced by Twitter's geotagged tweets. Textual contents help characterize users' personal interests, while geographical features help link users' behaviors in the online world to those in the physical world such as their mobility patterns. In this paper, instead of studying each aspect separately, as done by most previous works, we combine textual contents and spatial features in a joint way using Bayesian latent topic model in order to construct better algorithms for user characterization and social network study. Specifically, the integration of contents and spatial features in a user-centered environment can not only discover geographic topics but also enable the characterization of users' latent interests with geographic semantics. Such a novel characterization can be leveraged to benefit many interesting studies regarding social network heterogeneity and relationships between online networks and physical world. Using a large-scale twitter data set with broad geographical coverage, we systematically evaluate our framework in several typical inference tasks surrounding user, content and location, as well as carry out empirical studies in real world scenarios. Experimental results demonstrate the advantages of our joint modeling approach, as well as its potentials to facilitate user understanding, both in online world and physical world.

With the explosive growth of web data, effective and efficient technologies are in urgent needs for retrieving semantically relevant contents of heterogeneous modalities. Previous studies construct global transformations to project the heterogeneous data into a measurable subspace. However, global projections cannot appropriately adapt to diverse contents, and the naturally existing multi-level semantic relation in web data is ignored. We study the problem of semantic coherent retrieval, where documents from different modalities should be ranked by the semantic relevance to the queries. Accordingly, we propose TINA, a correlation learning method by Adaptive Hierarchical Semantic Aggregation. First, by joint modeling of content and ontology similarities, we build a semantic hierarchy to measure multi-level semantic relevance. Second, with a set of local linear projections aggregated by gating functions, we optimize the structure risk objective function that involves semantic coherence measurement, local projection consistency and the complexity penalty of local projections. Therefore, semantic coherence and a better bias-variance trade-off can be achieved by TINA. Extensive experiments on widely used NUS-WIDE and ICML-Challenge datasets demonstrate that TINA outperforms state-of-the-art, and achieves better adaptation to the multi-level semantic relation and content divergence.

In step with the web being used widely by mobile users, user location is becoming an essential signal in services, including local intent search. Given a large set of spatial web objects consisting of a geographical location and a textual description (e.g., Online business directory entries of restaurants, bars, and shops), how can we find sets of objects that are both spatially and textually relevant to a query? Most of existing studies solve the problem by requiring that all query keywords are covered by the returned objects and then rank the sets by spatial proximity. The needs for identifying sets with more textually relevant objects render these studies inapplicable. We propose locality Search, a query that returns top-k sets of spatial web objects and integrates spatial distance and textual relevance in one ranking function. We show that computing the query is NP-hard, and we present two efficient exact algorithms and one generic approximate algorithm based on greedy strategies for computing the query. We report on findings from an empirical study with three real-life datasets. The study offers insight into the efficiency and effectiveness of the proposed algorithms.

The extraction of macroscopic mobile context reflecting users' personal and social behavior patterns from smartphone sensor data (e.g., GPS/Bluetooth signals) is crucial in building intelligent pervasive systems. Hierarchical Dirichlet Processes (HDP), a well known Bayesian nonparametrics model for grouped data, is a promising option to achieve this objective due to its ability of discovering high-level semantics behind raw signals and establishing connections between individuals. However, applying HDP in a straightforward manner may not work as it does not take certain unique characteristics in mobile context into account. Particularly, while traditional HDP typically models a single aspect (e.g., Word), the characterization of a mobile context normally involves multiple heterogeneous aspects (e.g., Time, location, Bluetooth proximity). In addition, the presence of multiple aspects dictates a flexible way of clustering users and organizing mobile contexts in a hierarchical manner in serving different pervasive applications, a feature that traditional HDP lacks. Therefore, in this paper, we propose several extensions on traditional HDP to adapt it to the task of mobile context discovery. The key features in our extensions are: i) fusing multiple aspects naturally in HDP to achieve effective extraction of complex mobile context, ii) treating different aspects heterogeneously (globally or personally) in HDP to enable flexible user behavior clustering at various granularities in accordance with applications' needs, and iii) organizing mobile contexts in a hierarchical manner for natural behavior representation and overcoming data sparsity. Based on the experiments in a popular real-world mobile data set, we illustrate the ability of the framework in extracting useful mobile contexts such as characterizing personal life routines, discovering dominant temporal habits in a population, and inferring social group patterns, as well as its potential in improving individual mobility prediction under data sparsity.

We study the problem of large-scale social identity linkage across different social media platforms, which is of critical importance to business intelligence by gaining from social data a deeper understanding and more accurate profiling of users. This paper proposes HYDRA, a solution framework which consists of three key steps: (I) modeling heterogeneous behavior by long-term behavior distribution analysis and multi-resolution temporal information matching; (II) constructing structural consistency graph to measure the high-order structure consistency on users' core social structures across different platforms; and (III) learning the mapping function by multi-objective optimization composed of both the supervised learning on pair-wise ID linkage information and the cross-platform structure consistency maximization. Extensive experiments on 10 million users across seven popular social network platforms demonstrate that HYDRA correctly identifies real user linkage across different platforms, and outperforms existing state-of-the-art algorithms by at least 20% under different settings, and 4 times better in most settings.

Increasing volumes of geo-referenced data are becoming available. This data includes so-called points of interest that describe businesses, tourist attractions, etc. by means of a geo-location and properties such as a textual description or ratings. We propose and study the efficient implementation of a new kind of query on points of interest that takes into account both the locations and properties of the points of interest. The query takes a result cardinality, a spatial range, and property-related preferences as parameters, and it returns a compact set of points of interest with the given cardinality and in the given range that satisfies the preferences. Specifically, the points of interest in the result set cover so-called allying preferences and are located far from points of interest that possess so-called alienating preferences. A unified result rating function integrates the two kinds of preferences with spatial distance to achieve this functionality. We provide efficient exact algorithms for this kind of query. To enable queries on large datasets, we also provide an approximate algorithm that utilizes a nearest-neighbor property to achieve scalable performance. We develop and apply lower and upper bounds that enable search-space pruning and thus improve performance. Finally, we provide a generalization of the above query and also extend the algorithms to support the generalization. We report on an experimental evaluation of the proposed algorithms using real point of interest data from Google Places for Business that offers insight into the performance of the proposed solutions.

Anomaly detection (a.k.a., outlier or burst detection) is a well-motivated problem and a major data mining and knowledge discovery task. In this article, we study the problem of population anomaly detection, one of the key issues related to event monitoring and population management within a city. Through studying detected population anomalies, we can trace and analyze these anomalies, which could help to model city traffic design and event impact analysis and prediction. Although a significant and interesting issue, it is very hard to detect population anomalies and retrieve anomaly trajectories, especially given that it is difficult to get actual and sufficient population data. To address the difficulties of a lack of real population data, we take advantage of mobile phone networks, which offer enormous spatial and temporal communication data on persons. More importantly, we claim that we can utilize these mobile phone data to infer and approximate population data. Thus, we can study the population anomaly detection problem by taking advantages of unique features hidden in mobile phone data. In this article, we present a system to conduct Population Anomaly Detection (PAD). First, we propose an effective clustering method, correlation-based clustering , to cluster the incomplete location information from mobile phone data (i.e., from mobile call volume distribution to population density distribution). Then, we design an adaptive parameter-free detection method, R-scan , to capture the distributed dynamic anomalies. Finally, we devise an efficient algorithm, BT-miner , to retrieve anomaly trajectories . The experimental results from real-life mobile phone data confirm the effectiveness and efficiency of the proposed algorithms. Finally, the proposed methods are realized as a pilot system in a city in China.

Existing algorithms for trajectory-based clustering usually rely on simplex representation and a single proximity-related distance (or similarity) measure. Consequently, additional information markers (e.g., social interactions or the semantics of the spatial layout) are usually ignored, leading to the inability to fully discover the communities in the trajectory database. This is especially true for human-generated trajectories, where additional fine-grained markers (e.g., movement velocity at certain locations, or the sequence of semantic spaces visited) can help capture latent relationships between cluster members. To address this limitation, we propose TODMIS: a general framework for Trajectory cOmmunity Discovery using Multiple Information Sources. TODMIS combines additional information with raw trajectory data and creates multiple similarity metrics. In our proposed approach, we first develop a novel approach for computing semantic level similarity by constructing a Markov Random Walk model from the semantically-labeled trajectory data, and then measuring similarity at the distribution level. In addition, we also extract and compute pair-wise similarity measures related to three additional markers, namely trajectory level spatial alignment (proximity), temporal patterns and multi-scale velocity statistics. Finally, after creating a single similarity metric from the weighted combination of these multiple measures, we apply dense sub-graph detection to discover the set of distinct communities. We evaluated TODMIS extensively using traces of (i) student movement data in a campus, (ii) customer trajectories in a shopping mall, and (iii) city-scale taxi movement data. Experimental results demonstrate that TODMIS correctly and efficiently discovers the real grouping behaviors in these diverse settings.

Do mobile phone calls at larger granularities behave in the same pattern as in smaller ones? How can we forecast the distribution of a whole month's phone calls with only one day's observation? There are many models developed to interpret large scale social graphs. However, all of the existing models focus on graph at one time scale. Many dynamical behaviors were either ignored, or handled at one scale. In particular new users might join or current users quit social networks at any time. In this paper, we propose HiP, a novel model to capture longitudinal behaviors in modeling degree distribution of evolving social graphs. We analyze a large scale phone call dataset using HiP, and compare with several previous models in literature. Our model is able to fit phone call distribution at multiple scales with 30% to 75% improvement over the best existing method on each scale.

We consider the problem of adaptively routing a fleet of cooperative vehicles within a road network in the presence of uncertain and dynamic congestion conditions. To tackle this problem, we first propose a Gaussian Process Dynamic Congestion Model that can effectively characterize both the dynamics and the uncertainty of congestion conditions. Our model is efficient and thus facilitates real-time adaptive routing in the face of uncertainty. Using this congestion model, we develop an efficient algorithm for non-myopic adaptive routing to minimize the collective travel time of all vehicles in the system. A key property of our approach is the ability to efficiently reason about the long-term value of exploration, which enables collectively balancing the exploration/exploitation trade-off for entire fleets of vehicles. We validate our approach based on traffic data from two large Asian cities. We show that our congestion model is effective in modeling dynamic congestion conditions. We also show that our routing algorithm generates significantly faster routes compared to standard baselines, and achieves near-optimal performance compared to an omniscient routing algorithm. We also present the results from a preliminary field study, which showcases the efficacy of our approach.

Nowadays, there are many taxis traversing around the city searching for available passengers, but their hunts of passengers are not always efficient. To the dynamics of traffic and biased passenger distributions, current offline recommendations based on place of interests may not work well. In this paper, we define a new problem, global-optimal trajectory retrieving (GOTR), as finding a connected trajectory of high profit and high probability to pick up a passenger within a given time period in real-time. To tackle this challenging problem, we present a system, called HUNTS, based on the knowledge from both historical and online GPS data and business data. To achieve above objectives, first, we propose a dynamic scoring system to evaluate each road segment in different time periods by considering both picking-up rate and profit factors. Second, we introduce a novel method, called trajectory sewing, based on a heuristic method and the Skyline technique, to produce an approximate optimal trajectory in real-time. Our method produces a connected trajectory rather than several place of interests to avoid frequent next-hop queries. Third, to avoid congestion and other real-time traffic situations, we update the score of each road segment constantly via an online handler. Finally, we validate our system using a large-scale data of around 15,000 taxis in a large city in China, and compare the results with regular taxis' hunts and the state-of-the-art.

The execution of an agent's complex activities, comprising sequences of simpler actions, sometimes leads to the clash of conflicting functions that must be optimized. These functions represent satisfaction, short-term as well as long-term objectives, costs and individual preferences. The way that these functions are weighted is usually unknown even to the decision maker. But if we were able to understand the individual motivations and compare such motivations among individuals, then we would be able to actively change the environment so as to increase satisfaction and/or improve performance. In this work, we approach the problem of providing highlevel and intelligible descriptions of the motivations of an agent, based on observations of such an agent during the fulfillment of a series of complex activities (called sequential decisions in our work). A novel algorithm for the analysis of observational records is proposed. We also present a methodology that allows researchers to converge towards a summary description of an agent's behaviors, through the minimization of an error measure between the current description and the observed behaviors. This work was validated using not only a synthetic dataset representing the motivations of a passenger in a public transportation network, but also real taxi drivers' behaviors from their trips in an urban network. Our results show that our method is not only useful, but also performs much better than the previous methods, in terms of accuracy, efficiency and scalability.

Nowadays, big cities are suffering from severe traffic congestion as a result of the continuing increase in vehicles. Taxis equipped with GPS can be viewed as sensors of the traffic situation in city. However, trajectory data generated by taxi's GPS traces are often high-dimensional and contain large spatial and temporal attributes, which pose challenges for analysts. In this paper, based on taxi trajectory data, we present an interactive visual analytics system, T-Watcher, for monitoring and analyzing complex traffic situations in big cities. Users are able to use a carefully designed interface to monitor and inspect data interactively from three levels (region, road and vehicle views). We develop a visualization method to monitor and analyze traffic patterns for abnormal behaviors detection. In the region view of our system, global temporal changes in spatial evolution will be presented to users and can be interactively explored. The road view shows temporal changes to the traffic situations of significant segments of roads. The vehicle view uses a novel visualization method to track individual vehicles. Furthermore, the three views integrate important statistical and historical information related to traffic, which illustrate temporal changes of the traffic. We find that this design can help users explore historical information while monitoring traffic. We test our system on a real-life vehicle dataset collected from thousands of taxis and obtained some interesting findings. The experimental results confirm the effectiveness and efficiency of the proposed visual detection method. The analysis of the results also shows that our system is capable of effectively monitoring traffic and detecting abnormal traffic patterns.

An accurate and sufficient vehicle trajectory data set is the basis to many trajectory-based data mining tasks and applications. However, vehicle trajectories sampled by GPS devices are usually at a relatively low sampling rate and contain notable location errors. To address these two problems in GPS trajectory data, we propose WI-matching, the first vehicle trajectory calibration framework to take advantage of road networks topology and geometry information and trajectory historical information in large scale. WI-matching consists of a Weighting-based map matching algorithm and a trajectory Interpolation-based matching algorithm. In our WI-matching framework, we first integrate the vehicle GPS data with digital road networks data, to identify the roads where a vehicle traveled and the vehicle locations along the roads. Then our weighting-based map matching algorithm considers (1) the geometric and topological information of the road networks and (2) the spatiotemporal trajectory information to efficiently and effectively calibrate the GPS data points. Finally, our interpolation algorithm identifies paths between consecutive GPS points, and adds points with estimated vehicle status (location and time stamp) along the paths to construct sufficient vehicle trajectories. We have evaluated our algorithms on a large-scale real life data set in comparison with the state of the art. Our extensive and empirical results indicate that our WI-matching achieves a high accuracy as well as a high efficiency on real-world data which beats the state of the art.

With the increasing availability of metropolitan transportation data, such as those from vehicle GPSs (Global Positioning Systems) and road-side sensors, it becomes viable for authorities, operators, as well as individuals to analyze the data for a better understanding of the transportation system and possibly improved utilization and planning of the system. We report our experience in building the VAST (Visual Analytics for Smart Transportation) system. Our key observation is that metropolitan transportation data are inherently visual as they are spatio-temporal around road networks. Therefore, we visualize traffic data together with digital maps and support analytical queries through this interactive visual interface. As a case study, we demonstrate VAST on real-world taxi GPS and meter data sets from 15, 000 taxis running two months in a Chinese city of over 10 million population. We discuss the technical challenges in data cleaning, storage, visualization, and query processing, and offer our first-hand lessons learned from developing the system.

Identifying hot spots of moving vehicles in an urban area is essential to many smart city applications. The practical research on hot spots in smart city presents many unique features, such as highly mobile environments, supremely limited size of sample objects, and the non-uniform, biased samples. All these features have raised new challenges that make the traditional density-based clustering algorithms fail to capture the real clustering property of objects, making the results less meaningful. In this paper we propose a novel, non-density-based approach called mobility-based clustering. The key idea is that sample objects are employed as "sensors" to perceive the vehicle crowdedness in nearby areas using their instant mobility, rather than the "object representatives". As such the mobility of samples is naturally incorporated. Several key factors beyond the vehicle crowdedness have been identified and techniques to compensate these effects are proposed. We evaluate the performance of mobility-based clustering based on real traffic situations. Experimental results show that using 0.3% of vehicles as the samples, mobility-based clustering can accurately identify hot spots which can hardly be obtained by the latest representative algorithm UMicro.