Large Language Model-based Multi-Agent Systems (LLM-based MAS), where multiple LLM agents collaborate to solve complex tasks, have shown impressive performance in many areas. However, MAS are typically distributed across different devices or environments, making them vulnerable to perturbations such as agent failures. While existing works have studied the adversarial attacks and corresponding defense strategies, they mainly focus on reactively detecting and mitigating attacks after they occur rather than proactively designing inherently resilient systems. In this work, we study the resilience of LLM-based MAS under perturbations and find that both the communication topology and prompt design significantly influence system resilience. Motivated by these findings, we propose ResMAS: a two-stage framework for enhancing MAS resilience. First, we train a reward model to predict the MAS’s resilience, based on which we train a topology generator to automatically design resilient topology for specific tasks through reinforcement learning. Second, we introduce a topology-aware prompt optimization method that refines each agent’s prompt based on its connections and interactions with other agents. Extensive experiments across a range of tasks show that our approach substantially improves MAS resilience under various constraints. Moreover, our framework demonstrates strong generalization ability to new tasks and models, highlighting its potential for building resilient MASs.

Urban spatio-temporal flow prediction, encompassing traffic flows and crowd flows, is crucial for optimizing city infrastructure and managing traffic and emergency responses. Traditional approaches have relied on separate models tailored to either grid-based data, representing cities as uniform cells, or graph-based data, modeling cities as networks of nodes and edges. In this paper, we build UniFlow, a foundational model for general urban flow prediction that unifies both grid-based and graph based data. We first design a multi-view spatio-temporal patching mechanism to standardize different data into a consistent sequential format and then introduce a spatio-temporal transformer architecture to capture complex correlations and dynamics. To leverage shared spatio-temporal patterns across different data types and facilitate effective cross-learning, we propose Spatio Temporal Memory Retrieval Augmentation (ST-MRA). By creating structured memory modules to store shared spatio-temporal patterns, ST-MRA enhances predictions through adaptive memory retrieval. Extensive experiments demonstrate that UniFlow outperforms existing models in both grid-based and graph-based f low prediction, excelling particularly in scenarios with limited data availability, showcasing its superior performance and broad applicability. The datasets and code implementation have been released on https://github.com/YuanYuan98/UniFlow.

Click-Through Rate (CTR) prediction, which estimates the probability of a user clicking on a given item, is a critical task for online information services. Existing approaches often make strong assumptions that training and test data come from the same distribution. However, the data distribution varies since user interests are constantly evolving, resulting in the Out-of-Distribution (OOD) issue. In addition, users tend to have multiple interests, some of which evolve faster than others. Toward this end, we propose Disentangled Click-Through Rate Prediction (DiseCTR), which introduces a causal perspective of recommendation and disentangles multiple aspects of user interests to alleviate the OOD issue in recommendation. We conduct a causal factorization of CTR prediction involving user interest, exposure model, and click model, based on which we develop a deep learning implementation for these three causal mechanisms. Specifically, we first design an interest encoder with sparse attention which maps raw features to user interests and then introduce a weakly supervised interest disentangler to learn independent interest embeddings, which are further integrated by an attentive interest aggregator for prediction. Experimental results on three real-world datasets show that DiseCTR achieves the best accuracy and robustness in OOD recommendation against state-of-the-art approaches, significantly improving AUC and GAUC by over 0.02 and reducing logloss by over 13.7%. Further analyses demonstrate that DiseCTR successfully disentangles user interests, which is the key to OOD generalization for CTR prediction. We have released the code and data at https://github.com/DavyMorgan/DiseCTR/ .

Longer historical behaviors often improve recommendation accuracy but bring efficient problems. As sequences get longer, the following two main challenges have not been addressed: (1) efficient modeling under increasing sequence length and (2) interest drifting within historical items. In this paper, we propose Iterative Sparse Attention for Long-sequence Recommendation (ISA) with Sparse Attention Layer and Iterative Attention Layer to efficiently capture sequential pattern and expand the receptive field of each historical items. We take the pioneering step to address the efficient and interest drifting challenges for the long-sequence recommendation simultaneously. The theoretical analysis illustrates that our proposed iterative method can approximate full attention efficiently. Experiments on two real-world datasets show the superiority of our proposed method against state-of-the-art baselines.

Symbolic regression, a task discovering the formula best fitting the given data, is typically based on the heuristical search. These methods usually update candidate formulas to obtain new ones with lower prediction errors iteratively. However, since formulas with similar function shapes may have completely different symbolic forms, the prediction error does not decrease monotonously as the search approaches the target formula, causing the low recovery rate of existing methods. To solve this problem, we propose a novel search objective based on the minimum description length, which reflects the distance from the target and decreases monotonically as the search approaches the correct form of the target formula. To estimate the minimum description length of any input data, we design a neural network, MDLformer, which enables robust and scalable estimation through large-scale training. With the MDLformer's output as the search objective, we implement a symbolic regression method, SR4MDL, that can effectively recover the correct mathematical form of the formula. Extensive experiments illustrate its excellent performance in recovering formulas from data. Our method successfully recovers around 50 formulas across two benchmark datasets comprising 133 problems, outperforming state-of-the-art methods by 43.92%. Experiments on 122 unseen black-box problems further demonstrate its generalization performance. We release our code at https://github.com/tsinghua-fib-lab/SR4MDL .

Training reinforcement learning (RL) agents requires extensive trials and errors, which becomes prohibitively time-consuming in systems with costly reward evaluations. To address this challenge, we propose adaptive reward modeling (AdaReMo) which accelerates RL training by decomposing the complicated reward function into multiple localized fast reward models approximating direct reward evaluation with neural networks. These models dynamically adapt to the agent’s evolving policy by fitting the currently explored subspace with the latest trajectories, ensuring accurate reward estimation throughout the entire training process while significantly reducing computational overhead. We empirically show that AdaReMo not only achieves over 1,000 times speedup but also improves the performance by 14.6% over state-of-the-art approaches across three expensive-to-evaluate systems---molecular generation, epidemic control, and spatial planning. Code and data for the project are provided at https://github.com/tsinghua-fib-lab/AdaReMo.

The urban environment is characterized by complex spatio-temporal dynamics arising from diverse human activities and interactions. Effectively modeling these dynamics is essential for understanding and optimizing urban systems. In this work, we introduce UrbanDiT, a foundation model for open-world urban spatio-temporal learning that successfully scales up diffusion transformers in this field. UrbanDiT pioneers a unified model that integrates diverse data sources and types while learning universal spatio-temporal patterns across different cities and scenarios. This allows the model to unify both multi-data and multi-task learning, and effectively support a wide range of spatio-temporal applications. Its key innovation lies in the elaborated prompt learning framework, which adaptively generates both data-driven and task-specific prompts, guiding the model to deliver superior performance across various urban applications. UrbanDiT offers three advantages: 1) It unifies diverse data types, such as grid-based and graph-based data, into a sequential format; 2) With task-specific prompts, it supports a wide range of tasks, including bi-directional spatio-temporal prediction, temporal interpolation, spatial extrapolation, and spatio-temporal imputation; and 3) It generalizes effectively to open-world scenarios, with its powerful zero-shot capabilities outperforming nearly all baselines with training data. UrbanDiT sets up a new benchmark for foundation models in the urban spatio-temporal domain. Code and datasets are publicly available at \url{https://github.com/tsinghua-fib-lab/UrbanDiT}.

Synthesized human trajectories are crucial for a large number of applications. Existing solutions are mainly based on the generative adversarial network (GAN), which is limited due to the lack of modeling the human decision-making process. In this article, we propose a novel imitation learning-based method to synthesize human trajectories. This model utilizes a novel semantics-based interaction mechanism between the decision-making strategy and visitations to diverse geographical locations to model them in the semantic domain in a uniform manner. To augment the modeling ability to the real-world human decision-making policy, we propose a feature extraction model to extract the internal latent factors of variation of different individuals and then propose a novel self-attention-based policy net to capture the long-term correlation of mobility and decision-making patterns. Then, to better reward users’ mobility behavior, we propose a novel multi-scale reward net combined with mutual information to model the instant reward, long-term reward, and individual characteristics in a cohesive manner. Extensive experimental results on two real-world trajectory datasets show that our proposed model can synthesize the most high-quality trajectory data compared with six state-of-the-art baselines in terms of a number of key usability metrics and can well support practical applications based on trajectory data, demonstrating its effectiveness. Furthermore, our proposed method can learn explainable knowledge automatically from data, including explainable statistical features of trajectories and statistical relation between decision-making policy and features.

Urban spatio-temporal prediction is crucial for informed decision-making, such as traffic management, resource optimization, and emergency response. Despite remarkable breakthroughs in pretrained natural language models that enable one model to handle diverse tasks, a universal solution for spatio-temporal prediction remains challenging. Existing prediction approaches are typically tailored for specific spatio-temporal scenarios, requiring task-specific model designs and extensive domain-specific training data. In this study, we introduce UniST, a universal model designed for general urban spatio-temporal prediction across a wide range of scenarios. Inspired by large language models, UniST achieves success through: (i) utilizing diverse spatio-temporal data from different scenarios, (ii) effective pre-training to capture complex spatio-temporal dynamics, (iii) knowledge-guided prompts to enhance generalization capabilities. These designs together unlock the potential of building a universal model for various scenarios. Extensive experiments on more than 20 spatio-temporal scenarios, including grid-based data and graph-based data, demonstrate UniST’s efficacy in advancing state-of-the-art performance, especially in few-shot and zero-shot prediction.

Accurately predicting mobile traffic and accessed user amount is of great importance to network resource allocation, energy saving, etc. However, due to the complicated environmental contexts and complex interaction between mobile traffic and connected users, mobile network prediction is still challenging. Besides, the existing works could not be applied to large-scale networks because of the limited hardware resources and unacceptable time cost. In this work, we propose the spatiotemporal transformer framework for the multi-task mobile network prediction. Our proposed model contains three key parts. First, to capture the complex interaction between mobile traffic and connected users, we propose the temporal cross-attention encoder. Then, to identify and extract the most relevant information from various semantic relationships, we propose the hierarchical spatial encoder. This information is then used to create a more comprehensive representation of the network. Finally, the subgraph sampling method could significantly reduce the amount of computing power required and have comparable performance to the methods that input the whole network, enabling the model for real-world applications. Extensive experiments demonstrate that our proposed model significantly outperforms the state-of-the-art models by over 17% in both mobile traffic prediction and connected user prediction.

Large language models (LLMs) have recently garnered significant attention in various domains, including recommendation systems. Recent research leverages the capabilities of LLMs to improve the performance and user modeling aspects of recommender systems. These studies primarily focus on utilizing LLMs to interpret textual data in recommendation tasks. However, it's worth noting that in ID-based recommendations, textual data is absent, and only ID data is available. The untapped potential of LLMs for ID data within the ID-based recommendation paradigm remains relatively unexplored. To this end, we introduce a pioneering approach called “LLM for ID-based recommendation” (LLM4IDRec). This innovative approach integrates the capabilities of LLMs while exclusively relying on ID data, thus diverging from the previous reliance on textual data. The basic idea of LLM4IDRec is that by employing LLM to augment ID data, if augmented ID data can improve recommendation performance, it demonstrates the ability of LLM to interpret ID data effectively, exploring an innovative way for the integration of LLM in ID-based recommendation. Specifically, we first define a prompt template to enhance LLM's ability to comprehend ID data and the ID-based recommendation task. Next, during the process of generating training data using this prompt template, we develop two efficient methods to capture both the local and global structure of ID data. We feed this generated training data into the LLM and employ LoRA for fine-tuning LLM. Following the fine-tuning phase, we utilize the fine-tuned LLM to generate ID data that aligns with users’ preferences. We design two filtering strategies to eliminate invalid generated data. Thirdly, we can merge the original ID data with the generated ID data, creating augmented data. Finally, we input this augmented data into the existing ID-based recommendation models without any modifications to the recommendation model itself. We evaluate the effectiveness of our LLM4IDRec approach using three widely used datasets. Our results demonstrate a notable improvement in recommendation performance, with our approach consistently outperforming existing methods in ID-based recommendation by solely augmenting input data.

The facility location problem (FLP) is a classical combinatorial optimization challenge aimed at strategically laying out facilities to maximize their accessibility. In this paper, we propose a reinforcement learning method tailored to solve large-scale urban FLP, capable of producing near-optimal solutions at superfast inference speed. We distill the essential swap operation from local search, and simulate it by intelligently selecting edges on a graph of urban regions, guided by a knowledge-informed graph neural network, thus sidestepping the need for heavy computation of local search. Extensive experiments on four US cities with different geospatial conditions demonstrate that our approach can achieve comparable performance to commercial solvers with less than 5% accessibility loss, while displaying up to 1000 times speedup. We deploy our model as an online geospatial application at https://huggingface.co/spaces/tsinghua-fib-lab/MFLP.

Spatio-temporal modeling is foundational for smart city applications, yet it is often hindered by data scarcity in many cities and regions. To bridge this gap, we propose a novel generative pre-training framework, GPD, for spatio-temporal few-shot learning with urban knowledge transfer. Unlike conventional approaches that heavily rely on common feature extraction or intricate few-shot learning designs, our solution takes a novel approach by performing generative pre-training on a collection of neural network parameters optimized with data from source cities. We recast spatio-temporal few-shot learning as pre-training a generative diffusion model, which generates tailored neural networks guided by prompts, allowing for adaptability to diverse data distributions and city-specific characteristics. GPD employs a Transformer-based denoising diffusion model, which is model-agnostic to integrate with powerful spatio-temporal neural networks. By addressing challenges arising from data gaps and the complexity of generalizing knowledge across cities, our framework consistently outperforms state-of-the-art baselines on multiple real-world datasets for tasks such as traffic speed prediction and crowd flow prediction. The implementation of our approach is available: https://github.com/tsinghua-fib-lab/GPD.

Stance detection automatically detects the stance in a text towards a target, vital for content analysis in web and social media research. Despite their promising capabilities, LLMs encounter challenges when directly applied to stance detection. First, stance detection demands multi-aspect knowledge, from deciphering event-related terminologies to understanding the expression styles in social media platforms. Second, stance detection requires advanced reasoning to infer authors' implicit viewpoints, as stances are often subtly embedded rather than overtly stated in the text. To address these challenges, we design a three-stage framework COLA (short for Collaborative rOle-infused LLM-based Agents) in which LLMs are designated distinct roles, creating a collaborative system where each role contributes uniquely. Initially, in the multidimensional text analysis stage, we configure the LLMs to act as a linguistic expert, a domain specialist, and a social media veteran to get a multifaceted analysis of texts, thus overcoming the first challenge. Next, in the reasoning-enhanced debating stage, for each potential stance, we designate a specific LLM-based agent to advocate for it, guiding the LLM to detect logical connections between text features and stance, tackling the second challenge. Finally, in the stance conclusion stage, a final decision maker agent consolidates prior insights to determine the stance. Our approach avoids extra annotated data and model training and is highly usable. We achieve state-of-the-art performance across multiple datasets. Ablation studies validate the effectiveness of each role design in handling stance detection. Further experiments have demonstrated the explainability and the versatility of our approach. Our approach excels in usability, accuracy, effectiveness, explainability and versatility, highlighting its value.

Urban spatio-temporal prediction is crucial for informed decision-making, such as traffic management, resource optimization, and emergence response. Despite remarkable breakthroughs in pretrained natural language models that enable one model to handle diverse tasks, a universal solution for spatio-temporal prediction remains challenging. Existing prediction approaches are typically tailored for specific spatio-temporal scenarios, requiring task-specific model designs and extensive domain-specific training data. In this study, we introduce UniST, a universal model designed for general urban spatio-temporal prediction across a wide range of scenarios. Inspired by large language models, UniST achieves success through: (i) utilizing diverse spatio-temporal data, (ii) effective pre-training to capture complex spatio-temporal relationships, (iii) spatio-temporal knowledge-guided prompts to enhance generalization capabilities. These designs together unlock the potential of building a universal model for various scenarios. Extensive experiments on more than 20 spatio-temporal scenarios demonstrate UniST's efficacy in advancing state-of-the-art performance, especially in few-shot and zero-shot prediction. The datasets and code implementation are released on https://github.com/tsinghua-fib-lab/UniST.

In modern recommender systems, sequential recommendation leverages chronological user behaviors to make effective next-item suggestions, which suffers from data sparsity issues, especially for new users. One promising line of work is the cross-domain recommendation, which trains models with data across multiple domains to improve the performance in data-scarce domains. Recent proposed cross-domain sequential recommendation models such as PiNet and DASL have a common drawback relying heavily on overlapped users in different domains, which limits their usage in practical recommender systems. In this paper, we propose a M ixed A ttention N etwork (MAN) with local and global attention modules to extract the domain-specific and cross-domain information. Firstly, we propose a local/global encoding layer to capture the domain-specific/cross-domain sequential pattern. Then we propose a mixed attention layer with item similarity attention, sequence-fusion attention, and group-prototype attention to capture the local/global item similarity, fuse the local/global item sequence, and extract the user groups across different domains, respectively. Finally, we propose a local/global prediction layer to further evolve and combine the domain-specific and cross-domain interests. Experimental results on two real-world datasets (each with two domains) demonstrate the superiority of our proposed model. Further study also illustrates that our proposed method and components are model-agnostic and effective, respectively. The code and data are available at https://github.com/Guanyu-Lin/MAN.

Modern personalized recommendation services often rely on user feedback, either explicit or implicit, to improve the quality of services. Explicit feedback refers to behaviors like ratings, while implicit feedback refers to behaviors like user clicks. However, in the scenario of full-screen video viewing experiences like Tiktok and Reels, the click action is absent, resulting in unclear feedback from users, hence introducing noises in modeling training. Existing approaches on de-noising recommendation mainly focus on positive instances while ignoring the noise in a large amount of sampled negative feedback. In this paper, we propose a meta-learning method to annotate the unlabeled data from loss and gradient perspectives, which considers the noises in both positive and negative instances. Specifically, we first propose anInverse Dual Loss (IDL) to boost the true label learning and prevent the false label learning. Then we further propose anInverse Gradient (IG) method to explore the correct updating gradient and adjust the updating based on meta-learning. Finally, we conduct extensive experiments on both benchmark and industrial datasets where our proposed method can significantly improve AUC by 9.25% against state-of-the-art methods. Further analysis verifies the proposed inverse learning framework is model-agnostic and can improve a variety of recommendation backbones. The source code, along with the best hyper-parameter settings, is available at this link: https://github.com/Guanyu-Lin/InverseLearning.

The recommender systems on online platforms assist users in finding personalized information, yet this also leads to the issue of limited diversity, potentially giving rise to societal issues such as filter bubbles. Despite significant progress in diversified recommendation algorithms, they have not been extensively experimented with and evaluated for effectiveness in large-scale, full-stage industrial recommender systems. Specifically, industrial recommenders usually consist of three stages of matching, ranking, and re-ranking, in which specific characteristics lead to critical challenges for promoting both recommendation diversity and user engagement. First, user interests are partially observed due to only relevance maximization. Second, item-side feature-aware bias causes imbalanced recommendations. Last, the impact of diversity perception on user engagement stresses the necessity of explicit diversity modeling. To address these challenges in industrial systems, in this work, we deploy several existing diversified algorithms in a real-world short-video platform, including exploration-exploitation, feature-aware debiasing, and diversity optimization. We conduct large-scale online A/B testing for evaluation via online metrics of user engagement and recommendation diversity. Performance improvement across full stages demonstrates the effectiveness of these simple solutions. From comparing performance across different stages and algorithms, we identify that the ranking stage is the most suitable for real-world deployment, and the combination of debiasing and diversity optimization is a promising direction in terms of diversified recommendations. This work provides experiential guidance for the large-scale deployment of diversified algorithms and the construction of a more inclusive platform on the Web.

Multimodal recommender systems have acquired applications in broad web scenarios such as e-commerce businesses and short-video platforms. Existing multimodal recommendation methods generally boost performance by introducing item-side multimodal content as supplement information. However, the common training paradigm, i.e., encoding unimodal content respectively and fusing them to fit user preference scores, makes the model biased towards items with prevailing modality content under non-uniform training data. This results in a serious item-side unfairness issue, i.e., some items with prevailing modality content are over-recommended while a large number of items don't receive adequate recommendation opportunities, leaving corresponding content providers at great disadvantage. Aiming to eliminate such modality bias and promote item-side fairness, we propose a fairness-aware modality debiasing framework based on counterfactual inference. In the training stage, we additionally introduce unimodal prediction branches to capture the modality bias. In the inference stage, we conduct a fairness-aware counterfactual inference to adaptively eliminate the modality bias. The proposed framework is model-agnostic and flexible to be implemented in various multimodal recommendation models. Extensive experiments on two datasets demonstrate that the proposed method can significantly enhance item-side fairness while providing competitive recommendation accuracy. Our proposed framework is expected to help mitigate the unfair treatment experienced by vulnerable content providers on multimedia web platforms. Codes are available in https://github.com/tsinghua-fib-lab-WWW2024-Modality-Debiasing.

Understanding and accurately predicting cellular traffic data is vital for communication operators and device users, as it facilitates efficient resource allocation and ensures superior service quality. However, large-scale cellular traffic data forecasting remains challenging due to intricate temporal variations and complex spatial relationships. This article proposes a Knowledge Graph Driven Decomposition Approach (KGDA) for precise cellular traffic prediction. The KGDA breaks down the impact of static environmental factors and dynamic autocorrelations of cellular traffic time series, enabling the capture of overall traffic changes and understanding of traffic dependence on past values. Specifically, we propose an urban knowledge graph to capture the static environmental context of base stations, mapping these entities into the same latent space while retaining static environmental knowledge. The cellular traffic is divided into a regular pattern and fluctuating residual components, with the KGDA comprising four modules: a Knowledge Graph Representation Learning model, a traffic regular pattern prediction module, a traffic residual dynamic prediction module, and an attentional fusion module. The first leverages graph neural networks to extract spatial contexts and predict regular patterns, the second utilizes the Bi-directional Long Short-Term Memory (Bi-LSTM) model to capture autocorrelations of traffic time series, and the final module integrates the patterns and residuals to produce the final prediction result. Comprehensive experiments demonstrate that our proposed model outperforms state-of-the-art models by more than 10% in forecasting cellular traffic.

Recovering the fine-grained working process of couriers is becoming one of the essential problems for improving the express delivery systems because knowing the detailed process of how couriers accomplish their daily work facilitates the analyzing, understanding, and optimizing of the working procedure. Although coarse-grained courier trajectories and waybill delivery time data can be collected, this problem is still challenging due to noisy data with spatio-temporal biases, lacking ground truth of couriers’ fine-grained behaviors, and complex correlations between behaviors. Existing works typically focus on a single dimension of the process such as inferring the delivery time and can only yield results of low spatio-temporal resolution, which cannot address the problem well. To bridge the gap, we propose a digital-twin-based iterative calibration system (DTRec) for fine-grained courier working process recovery. We first propose a spatio-temporal bias correction algorithm, which systematically improves existing methods in correcting waybill addresses and trajectory stay points. Second, to model the complex correlations among behaviors and inherent physical constraints, we propose an agent-based model to build the digital twin of couriers. Third, to further improve recovery performance, we design a digital-twin-based iterative calibration framework, which leverages the inconsistency between the deduction results of the digital twin and the recovery results from real-world data to improve both the agent-based model and the recovery results. Experiments show that DTRec outperforms state-of-the-art baselines by 10.8% in terms of fine-grained accuracy on real-world datasets. The system is deployed in the industrial practices in JD Logistics with promising applications. The code is available at https://github.com/tsinghua-fib-lab/Courier-DTRec .

Daily activity data recording individuals’ various activities in daily life are widely used in many applications such as activity scheduling, activity recommendation, and policymaking. Though with high value, its accessibility is limited due to high collection costs and potential privacy issues. Therefore, simulating human activities to produce massive high-quality data is of great importance. However, existing solutions, including rule-based methods with simplified behavior assumptions and data-driven methods directly fitting real-world data, both cannot fully qualify for matching reality. In this article, motivated by the classic psychological theory, Maslow’s need theory describing human motivation, we propose a knowledge-driven simulation framework based on generative adversarial imitation learning. Our core idea is to model the evolution of human needs as the underlying mechanism that drives activity generation in the simulation model. Specifically, a hierarchical model structure that disentangles different need levels and the use of neural stochastic differential equations successfully capture the piecewise-continuous characteristics of need dynamics. Extensive experiments demonstrate that our framework outperforms the state-of-the-art baselines regarding data fidelity and utility. We also present the insightful interpretability of the need modeling. Moreover, privacy preservation evaluations validate that the generated data does not leak individual privacy. The code is available at https://github.com/tsinghua-fib-lab/Activity-Simulation-SAND .

Generally speaking, we can easily specify many causal relationships in the prediction tasks of ubiquitous computing, such as human activity prediction, mobility prediction, and health prediction. However, most of the existing methods in these fields failed to take advantage of this prior causal knowledge. They typically make predictions only based on correlations in the data, which hinders the prediction performance in real-world scenarios, because a distribution shift between training data and testing data generally exists. To fill in this gap, we proposed a Generative Adversarial Network (GAN)-based Causal Information Learning prediction framework, which can effectively leverage causal information to improve the prediction performance of existing ubiquitous computing deep learning models. Specifically, faced with a unique challenge that the treatment variable, referring to the intervention that influences the target in a causal relationship, is generally continuous in ubiquitous computing, the framework employs a representation learning approach with a GAN-based deep learning model. By projecting all variables except the treatment into a latent space, it effectively minimizes confounding bias and leverages the learned latent representation for accurate predictions. In this way, it deals with the continuous treatment challenge, and in the meantime, it can be easily integrated with existing deep learning models to lift their prediction performance in practical scenarios with causal information. Extensive experiments on two large-scale real-world datasets demonstrate its superior performance over multiple state-of-the-art baselines. We also propose an analytical framework together with extensive experiments to empirically show that our framework achieves better performance gain under two conditions: when the distribution differences between the training data and the testing data are more significant and when the treatment effects are larger. Overall, this work suggests that learning causal information is a promising way to improve the prediction performance of ubiquitous computing tasks. We open both our dataset and code 1 and call for more research attention in this area.

Mobile user traffic facilitates diverse applications, including network planning and optimization, whereas large-scale mobile user traffic is hardly available due to privacy concerns. One alternative solution is to generate mobile user traffic data for downstream applications. However, existing generation models cannot simulate the multi-scale temporal dynamics in mobile user traffic on individual and aggregate levels. In this work, we propose a multi-scale hierarchical generative adversarial network (MSH-GAN) containing multiple generators and a multi-class discriminator. Specifically, the mobile traffic usage behavior exhibits a mixture of multiple behavior patterns, which are called micro-scale behavior patterns and are modeled by different pattern generators in our model. Moreover, the traffic usage behavior of different users exhibits strong clustering characteristics, with the co-existence of users with similar and different traffic usage behaviors. Thus, we model each cluster of users as a class in the discriminator’s output, referred to as macro-scale user clusters. Then, the gap between micro-scale behavior patterns and macro-scale user clusters is bridged by introducing the switch mode generators, which describe the traffic usage behavior in switching between different patterns. All users share the pattern generators. In contrast, the switch mode generators are only shared by a specific cluster of users, which models the multi-scale hierarchical structure of the traffic usage behavior of massive users. Finally, we urge MSH-GAN to learn the multi-scale temporal dynamics via a combined loss function, including adversarial loss, clustering loss, aggregated loss, and regularity terms. Extensive experiment results demonstrate that MSH-GAN outperforms state-of-art baselines by at least 118.17% in critical data fidelity and usability metrics. Moreover, observations show that MSH-GAN can simulate traffic patterns and pattern switch behaviors.

Nowadays, the explosive growth of personalized web applications and the rapid development of artificial intelligence technology have flourished the recent research on mobile user profiling, i.e., inferring the user profile from mobile behavioral data. Particularly, existing studies mainly follow the data-driven paradigm to develop feature engineering and representation learning on such data, which however suffer from the robustness issue, i.e., generalizing poorly across datasets and profiles without considering semantic knowledge therein. In comparison, the rising knowledge-driven paradigm built upon the knowledge graph (KG) offers a potential solution to mitigate such weakness. Therefore, in this article, we propose a Knowledge Graph aided framework for Mobile User Profiling (KG-MUP). Specifically, to distil semantic knowledge among data, we firstly construct an urban knowledge graph (UrbanKG) with domain entities like users, regions, point of interests (POIs), and so on. identified, as well as semantic relations for home, workplace, spatiality, and so on. extracted. Moreover, we leverage tensor decomposition and graph neural network to obtain knowledgeable user representations from UrbanKG. In addition, we introduce several customized features to quantify individual mobility characteristics for mobile user profiling. Extensive experiments on three real-world mobility datasets demonstrate that KG-MUP achieves state-of-the-art performance on user profile inference tasks. Moreover, further results also reveal the importance of various semantic knowledge to user profile inference, which provides meaningful insights on user modeling with mobile behavioral data.

A considerable amount of mobility data has been accumulated due to the proliferation of location-based services. Nevertheless, compared with mobility data from transportation systems like the GPS module in taxis, this kind of data is commonly sparse in terms of individual trajectories in the sense that users do not access mobile services and contribute their data all the time. Consequently, the sparsity inevitably weakens the practical value of the data even if it has a high user penetration rate. To solve this problem, we propose a novel attentional neural network-based model, named AttnMove, to densify individual trajectories by recovering unobserved locations at a fine-grained spatial-temporal resolution. To tackle the challenges posed by sparsity, we design various intra- and inter- trajectory attention mechanisms to better model the mobility regularity of users and fully exploit the periodical pattern from long-term history. In addition, to guarantee the robustness of the generated trajectories to avoid harming downstream applications, we also exploit the Bayesian approximate neural network to estimate the uncertainty of each imputation. As a result, locations generated by the model with high uncertainty will be excluded. We evaluate our model on two real-world datasets, and extensive results demonstrate the performance gain compared with the state-of-the-art methods. In-depth analyses of each design of our model have been conducted to understand their contribution. We also show that, by providing high-quality mobility data, our model can benefit a variety of mobility-oriented downstream applications.

With the rapid development of location acquisition technologies, massive mobile trajectories have been collected and made available to us, which support a fantastic way of understanding and modeling individuals’ mobility. However, existing data-driven methods either fail to capture the long-range dependency or suffer from a high computational cost. To overcome these issues, we propose a knowledge-driven framework for mobility prediction, which leverages knowledge graphs (KG) to formulate the mobility prediction task into the KG completion problem through integrating the structured “knowledge” from the mobility data. However, most related mobility prediction works only focus on the structured information encoded in existing triples, which ignores the rich semantic information of relation paths composed of multiple relation triples. In this article, we apply a dedicated module to extract the supplementary semantic structure of paths in KG, which contributes to the interpretability and accuracy of our model. Specifically, the extracted rules are applied to capture the dependencies between relational facts. Moreover, by incorporating user information in the entity-relation space with the corresponding hyperplane, our method could capture diverse user mobility patterns and model the personal characteristics of users to improve the accuracy of mobility prediction. Extensive evaluations illustrate that our proposed model beats state-of-the-art mobility prediction algorithms, which verifies the superiority of utilizing logical rules and user hyperplanes. Our implementation code is available at https://github.com/tsinghua-fib-lab/RulekG-MobiPre.git

Synthesized human trajectories are instrumental for a large number of applications. However, existing trajectory synthesizing models are limited in either modeling variable-length trajectories with continuous temporal distribution or incorporating multi-dimensional context information. In this paper, we propose a novel probabilistic model based on the variational temporal point process to synthesize human trajectories. This model combines the classical temporal point process with the novel neural variational inference framework, leading to its strong ability to model human trajectories with continuous temporal distribution, variable length, and multi-dimensional context information. Extensive experimental results on two real-world trajectory datasets show that our proposed model can synthesize trajectories most similar to real-world human trajectories compared with four representative baseline algorithms in terms of a number of usability metrics, demonstrating its effectiveness.

5G networks, with their notable energy consumption, pose a significant challenge. Traditional energy-saving methods, effective for 4G, struggle in heterogeneous 4G and 5G networks. In this paper, we propose the pRoactivE Data-drivEn Energy Saving Method (REDEEM) to mitigate energy consumption in heterogeneous 4G and 5G mobile networks. REDEEM spatially divides the network into meshes based on cell overlaps, predicts cell traffic for proactive control, and selects active cells within each mesh. Our framework includes energy efficiency profiling for each mesh and offloads 5G traffic onto overlapping 4G cells to reduce 5G energy usage. Experiments based on the Nanchang mobile networks validate REDEEM’s effectiveness, yielding energy savings of 3442.72 MWh over a week. Notably, our approach achieves a 53.10% energy-saving rate, surpassing threshold-based methods by 38.85%, optimization-based methods by 18.15%, and fluid capacity engine by 14.79%. It minimally impacts service quality, with less than four parts per million traffic missed. Experimental results also demonstrate REDEEM’s robustness across various temporal, spatial, and traffic load scenarios.

Knowledge graphs (KGs) can help enhance recommendations, especially for the data-sparsity scenarios with limited user-item interaction data. Due to the strong power of representation learning of graph neural networks (GNNs), recent works of KG-based recommendation deploy GNN models to learn from both knowledge graph and user-item bipartite interaction graph. However, these works have not well considered the hierarchical structure of knowledge graph, leading to sub-optimal results. Despite the benefit of hierarchical structure, leveraging it is challenging since the structure is always partly-observed. In this work, we first propose to reveal unknown hierarchical structures with a supervised signal detection method and then exploit the hierarchical structure with disentangling representation learning. We conduct experiments on two large-scale datasets, of which the results well verify the superiority and rationality of the proposed method. Further experiments of ablation study with respect to key model designs have demonstrated the effectiveness and rationality of our proposed model. The code is available at https://github.com/tsinghua-fib-lab/HIKE .

Micro-video platforms such as TikTok are extremely popular nowadays. One important feature is that users no longer select interested videos from a set; instead, they either watch the recommended video or skip to the next one. As a result, the time length of users’ watching behavior becomes the most important signal for identifying preferences. However, our empirical data analysis has shown a video-length effect that long videos can more easily receive a higher value of average view time, and thus adopting such view-time labels for measuring user preferences can easily induce a biased model that favors the longer videos. In this article, we propose a V ideo L ength D ebiasing Rec ommendation (VLDRec) method to alleviate such an effect for micro-video recommendation. VLDRec designs the data labeling approach and the sample generation module that better capture user preferences in a view-time-oriented manner. It further leverages the multi-task learning technique to jointly optimize the above samples with the original biased ones. Extensive experiments show that VLDRec can improve users’ view time by 1.81% and 11.32% on two real-world datasets, given a recommendation list of a fixed overall video length, compared with the best baseline method. Moreover, VLDRec is also more effective in matching users’ interests in terms of the video content.

Accurately and efficiently modeling wireless channels, especially estimating path loss value, is crucial to wireless system design and performance optimization. This paper proposes a knowledge and data jointly driven path loss estimation method named PEFNet. PEFNet can predict the total electric field based on its mathematical relationship with the incident field by introducing the Volume Integration Equation into the loss function and scenario environmental information as input. Then, we let PEFNet learn in a supervised manner to compensate for residual error against measured data for refinement. We conduct extensive experiments on two publicly available path loss datasets, RadioMapSeer and RSRPSet, to exhibit the superiority of PEFNet over other state-of-the-art baselines. By comparing overall estimation performance, carrying out ablation study, testing estimation efficiency, and evaluating generalization ability, the results prove that PEFNet is an accurate and efficient method for estimating path loss.

Generating human mobility trajectories is of great importance to solve the lack of large-scale trajectory data in numerous applications, which is caused by privacy concerns. However, existing mobility trajectory generation methods still require real-world human trajectories centrally collected as the training data, where there exists an inescapable risk of privacy leakage. To overcome this limitation, in this paper, we propose PateGail, a privacy-preserving imitation learning model to generate mobility trajectories, which utilizes the powerful generative adversary imitation learning model to simulate the decision-making process of humans. Further, in order to protect user privacy, we train this model collectively based on decentralized mobility data stored in user devices, where personal discriminators are trained locally to distinguish and reward the real and generated human trajectories. In the training process, only the generated trajectories and their rewards obtained based on personal discriminators are shared between the server and devices, whose privacy is further preserved by our proposed perturbation mechanisms with theoretical proof to satisfy differential privacy. Further, to better model the human decision-making process, we propose a novel aggregation mechanism of the rewards obtained from personal discriminators. We theoretically prove that under the reward obtained based on the aggregation mechanism, our proposed model maximizes the lower bound of the discounted total rewards of users. Extensive experiments show that the trajectories generated by our model are able to resemble real-world trajectories in terms of five key statistical metrics, outperforming state-of-the-art algorithms by over 48.03%. Furthermore, we demonstrate that the synthetic trajectories are able to efficiently support practical applications, including mobility prediction and location recommendation.

As mobile communication technologies advance, mobile networks become increasingly complex, and user requirements become increasingly diverse. To satisfy the diverse demands of users while improving the overall performance of the network system, the limited wireless network resources should be efficiently and dynamically allocated to them based on the magnitude of their demands and their relative location to the base stations. We separated the problem into four constrained subproblems, which we then solved using a safe reinforcement learning method. In addition, we design a reward mechanism to encourage agent cooperation in distributed training environments. We test our methodology in a simulated scenario with thousands of users and hundreds of base stations. According to experimental findings, our method guarantees that over 95% of user demands are satisfied while also maximizing the overall system throughput.

Short-video recommendation is one of the most important recommendation applications in today's industrial information systems. Compared with other recommendation tasks, the enormous amount of feedback is the most typical characteristic. Specifically, in short-video recommendation, the easiest-to-collect user feedback is theskipping behavior, which leads to two critical challenges for the recommendation model. First, the skipping behavior reflects implicit user preferences, and thus, it is challenging for interest extraction. Second, this kind of special feedback involves multiple objectives, such as total watching time and skipping rate, which is also very challenging. In this paper, we present our industrial solution in Kuaishou1, which serves billion-level users every day. Specifically, we deploy a feedback-aware encoding module that extracts user preferences, taking the impact of context into consideration. We further design a multi-objective prediction module which well distinguishes the relation and differences among different model objectives in the short-video recommendation. We conduct extensive online A/B tests, along with detailed and careful analysis, which verify the effectiveness of our solution.

Heterogeneous graph neural networks (HGNNs) have achieved remarkable development recently and exhibited superior performance in various tasks. However, recently HGNNs have been shown to have robustness weakness towards adversarial perturbations, which brings critical pitfalls for real applications, e.g. node classification and recommender systems. In particular, the transfer-based black-box attack is the most practical method to attack unknown models and poses a great threat to the reliability of HGNNs. In this work, we take the first step to explore the transferability of adversarial examples of HGNNs. Due to the overfitting of the source model, the adversarial perturbations generated by traditional methods usually exhibit unpromising transferability. To address this problem and boost adversarial transferability, we expect to seek common vulnerable directions of different models to attack. Inspired by the observation of the notable commonality of edge attention distribution between different HGNNs, we propose to guide the perturbation generation toward disrupting edge attention distribution. This edge attention-guided attack prioritizes the perturbation on edges that are more likely to be given common attention by different models, which benefits the transferability of adversarial perturbations. Finally, we develop two edge attention-guided attack methods towards heterogeneous relations tailored for HGNNs, called EA-FGSM and EA-PGD. Extensive experiments on six representative models and two datasets verify the effectiveness of our methods and form an unprecedented transfer robustness benchmark for HGNNs.

For walking pedestrians, when they are blocked by obstacles or other pedestrians, they adjust their speeds and directions to avoid colliding with them, which is called collision avoidance behavior. This behavior is the most complex part of pedestrians' walking processes and its modeling and simulation are the keys to realistic crowd simulation, which serves as the foundation for various applications. However, most existing methods either lack the representation power to accurately model the complex collision behavior or do not model it explicitly, which leads to a poor level of realism of the simulation. To realize realistic crowd simulation, we propose to analyze, understand, and model the collision avoidance behavior in a data-driven way. First, to automatically detect collision avoidance behavior for further analysis, we propose a domain transformation algorithm that detects it by transforming the trajectories in the spatial domain into a new domain where the behavior is much more apparent and is thus easier to detect. The new domain also provides a new perspective for understanding collision avoidance behavior. Second, since there are no mature metrics to evaluate the level of realism, we propose a new evaluation metric based on the least-effort theory, which evaluates the realism of collision avoidance behavior by its physical and mental consumption. This evaluation metric also provides the foundation of modeling. Third, for realistic crowd simulation, we design a reinforcement learning model. It trains agents with our proposed reward function that models pedestrians' intrinsic needs of "reducing effort consumption'' and thus can guide agents to behave realistically when avoiding collisions. Extensive experiments show our model is 55.9% and 52.5% more realistic in collision avoidance behavior than the best baselines on two real-world datasets. We release our codes at https://github.com/tsinghua-fib-lab/TECRL.

Accurately predicting base station traffic volumes and understanding mobile traffic patterns is essential for smart city development, enabling efficient resource allocation and ensuring high-quality communication services. However, existing works have limitations in capturing spatial information, though the surrounding environment plays a critical role in mobile traffic prediction. In this paper, we utilize a spatial knowledge graph to represent spatial information and add important urban components to augment it making it a more effective tool for capturing environmental information. we further propose a multi-relational knowledge graph convolutional network model for mobile traffic prediction, which consists of three parts. The environmental context modelling captures spatial information from the augmented spatial knowledge graph using tucker decomposition and relational graph convolutional network. The semantic relationship modelling extracts semantic relationships between base stations and employs transformer and causal convolution to capture temporal features. The inter-attentional fusion modelling utilizes the self-attention mechanism to further capture base station relationships and predict future traffic volumes. Extensive experiments demonstrate that our proposed model significantly outperforms the state-of-the-art models by over 10% in mobile traffic prediction. The code is available at https://github.com/tsinghua-fiblab/Mobile-Traffic-Prediction-sigspatial23

Traffic congestion has a negative impact on our daily life. Predicting the trend of traffic congestion can provide a valuable guideline to address such problems. Most existing approaches focus on the tasks of predicting traffic volume or traffic speed, which do not effectively address the challenges of traffic congestion prediction. First, traffic congestion exhibits daily and weekly temporal patterns, but these patterns are not strictly the same, which indicates complicated long-term periodicity. Second, traffic congestion sparsely distributes over different periods of time, which leads to complex short-term and mid-term temporal dependencies. Third, since traffic congestion will propagate to adjacent road segments over time, it exhibits complex spatio-temporal correlations. To address them, we propose a periodic shift and event-aware spatio-temporal graph convolutional network for traffic congestion prediction. Specifically, we propose to capture the differences and similarities of long-term periodic temporal patterns to handle the complicated long-term periodicity. To effectively capture short-term and mid-term temporal dependencies, we regard a continuous time sequence of the congested condition as a traffic congestion event, and then adopt the widely-used long short-term memory model to learn the sequential dependencies of traffic congestion events. Finally, we integrate the graph convolutional network into the modeling of temporal dependencies to capture the complex spatio-temporal correlations. Extensive experiments demonstrate the superiority of our model. In addition, we deploy our model in production at Amap, and it achieves great performance improvement in terms of the F1-score compared to the production baseline. This confirms that our model is a practical solution for real-world congestion prediction services.

Frequent traffic congestion has a detrimental effect on our travel experience and the overall quality of urban life. Accurate prediction of traffic congestion plays a pivotal role in alleviating the congestion problem. However, existing traffic prediction approaches primarily focus on extracting its local changing patterns, overlooking the importance of incorporating global dynamic patterns. This presents three challenges: 1) Complicated spatial and temporal information exists in local (microscopic) traffic patterns; 2) The propagation and dissipation patterns of global (macroscopic) traffic congestion exhibit complex dynamics across time and space; 3) Modeling the interactions between macro and micro changing patterns of congestion remains unknown. In this paper, we present a novel framework for traffic congestion prediction that integrates microscopic and macroscopic cross-scale spatiotemporal modeling. Our approach utilizes contagion dynamics to characterize congestion propagation and recovery at the network-wide scale. Additionally, we employ a spatio-temporal graph neural network to capture local traffic patterns. A key contribution is the introduction of a differentiable micro-macro transformation mechanism, enabling the aggregation of microscopic states into macroscopic ones in a differentiable manner during model training. Further, we utilize the knowledge derived from macro contagion dynamics to constrain the micro traffic patterns by employing the physics-informed neural network. Experiments on three real-world datasets of traffic congestion demonstrate that our prediction model consistently outperforms the state-of-the-art baselines.

Although generative AI has been successful in many areas, its ability to model geospatial data is still underexplored. Urban flow, a typical kind of geospatial data, is critical for a wide range of applications from public safety and traffic management to urban planning. Existing studies mostly focus on predictive modeling of urban flow that predicts the future flow based on historical flow data, which may be unavailable in data-sparse areas or newly planned regions. Some other studies aim to predict OD flow among regions but they fail to model dynamic changes of urban flow over time. In this work, we study a new problem of urban flow generation that generates dynamic urban flow for regions without historical flow data. To capture the effect of multiple factors on urban flow, such as region features and urban environment, we employ diffusion model to generate urban flow for regions under different conditions. We first construct an urban knowledge graph (UKG) to model the urban environment and relationships between regions, based on which we design a knowledge-enhanced spatio-temporal diffusion model (KSTDiff) to generate urban flow for each region. Specifically, to accurately generate urban flow for regions with different flow volumes, we design a novel diffusion process guided by a volume estimator, which is learnable and customized for each region. Moreover, we propose a knowledge-enhanced denoising network to capture the spatio-temporal dependencies of urban flow as well as the impact of urban environment in the denoising process. Extensive experiments on four real-world datasets validate the superiority of our model over state-of-the-art baselines in urban flow generation. Further in-depth studies demonstrate the utility of generated urban flow data and the ability of our model for long-term flow generation and urban flow prediction. Our code is released at: https://github.com/tsinghua-fib-lab/KSTDiff-Urban-flow-generation.

Spatio-temporal point process (STPP) is a stochastic collection of events accompanied with time and space. Due to computational complexities, existing solutions for STPPs compromise with conditional independence between time and space, which consider the temporal and spatial distributions separately. The failure to model the joint distribution leads to limited capacities in characterizing the spatio-temporal entangled interactions given past events. In this work, we propose a novel parameterization framework for STPPs, which leverages diffusion models to learn complex spatio-temporal joint distributions. We decompose the learning of the target joint distribution into multiple steps, where each step can be faithfully described by a Gaussian distribution. To enhance the learning of each step, an elaborated spatio-temporal co-attention module is proposed to capture the interdependence between the event time and space adaptively. For the first time, we break the restrictions on spatio-temporal dependencies in existing solutions, and enable a flexible and accurate modeling paradigm for STPPs. Extensive experiments from a wide range of fields, such as epidemiology, seismology, crime, and urban mobility, demonstrate that our framework outperforms the state-of-the-art baselines remarkably. Further in-depth analyses validate its ability to capture spatio-temporal interactions, which can learn adaptively for different scenarios. The datasets and source code are available online: https://github.com/tsinghua-fib-lab/Spatio-temporal-Diffusion-Point-Processes.

The two-dimensional bin packing problem (2DBP) is a critical optimization problem in the furniture production and glass cutting industries, where the objective is to cut smaller-sized items from a minimum number of large standard-sized raw materials. In practice, factories manufacture hundreds of customer orders (sets of items) every day, and to relieve pressure in management, a common practice is to group the orders into batches for production, ensuring that items from one order are in the same batch instead of scattered across the production line. In this work, we formulate this problem as the grouped 2D bin packing problem, a bi-level problem where the upper level partitions orders into groups and the lower level solves 2DBP for items in each group. The main challenges are (1) the coupled optimization of upper and lower levels and (2) the high computational efficiency required for practical application. To tackle these challenges, we propose an iteration-based hierarchical reinforcement learning framework, which can learn to solve the optimization problem in a data-driven way and provide fast online performance after offline training. Extensive experiments demonstrate that our method not only achieves the best performance compared to all baselines but is also robust to changes in dataset distribution and problem constraints. Finally, we deployed our method in the ARROW Home factory in China, resulting in a 4.1% reduction in raw material costs. We have released the source code and datasets to facilitate future research.

With the rapid development of the cellular network, network planning is increasingly important. Generating large-scale urban cellular traffic contributes to network planning via simulating the behaviors of the planned network. Existing methods fail in simulating the long-term temporal behaviors of cellular traffic while cannot model the influences of the urban environment on the cellular networks. We propose a knowledge-enhanced GAN with multi-periodic patterns to generate large-scale cellular traffic based on the urban environment. First, we design a GAN model to simulate the multi-periodic patterns and long-term aperiodic temporal dynamics of cellular traffic via learning the daily patterns, weekly patterns, and residual traffic between long-term traffic and periodic patterns step by step. Then, we leverage urban knowledge to enhance traffic generation via constructing a knowledge graph containing multiple factors affecting cellular traffic in the surrounding urban environment. Finally, we evaluate our model on a real cellular traffic dataset. Our proposed model outperforms three state-of-art generation models by over 32.77%, and the urban knowledge enhancement improves the performance of our model by 4.71%. Moreover, our model achieves good generalization and robustness in generating traffic for urban cellular networks without training data in the surrounding areas.

Understanding and characterizing the vulnerability of urban infrastructures, which refers to the engineering facilities essential for the regular running of cities and that exist naturally in the form of networks, is of great value to us. Potential applications include protecting fragile facilities and designing robust topologies, etc. Due to the strong correlation between different topological characteristics and infrastructure vulnerability and their complicated evolution mechanisms, some heuristic and machine assisted analysis fall short in addressing such a scenario. In this paper, we model the interdependent network as a heterogeneous graph and propose a system based on graph neural network with reinforcement learning, which can be trained on real-world data, to characterize the vulnerability of the city system accurately. The presented system leverages deep learning techniques to understand and analyze the heterogeneous graph, which enables us to capture the risk of cascade failure and discover vulnerable infrastructures of cities. Extensive experiments with various requests demonstrate not only the expressive power of our system but also transferring ability and necessity of the specific components. All source codes and models including those that can reproduce all figures analyzed in this work are publicly available at this link: https://github.com/tsinghua-fib-lab/KDD2023-ID546-UrbanInfra.

The problem of cellular traffic generation in cities without historical traffic data is critical and urgently needs to be solved to assist 5G base station deployments in mobile networks. In this paper, we propose ADAPTIVE, a deep transfer learning framework for city-scale cellular traffic generation through the urban knowledge graph. ADAPTIVE leverages historical data from other cities that have deployed 5G networks to assist cities that are newly deploying 5G networks through deep transfer learning. Specifically, ADAPTIVE can align the representations of base stations in the target city and source city while considering the environmental factors of cities, spatial and environmental contextual relations between base stations, and traffic temporal patterns at base stations. We next design a feature-enhanced generative adversarial network, which is trained based on the historical traffic data and representations of base stations in the source city. By feeding the aligned target city's base station representations into the trained model, we can then obtain the generated traffic data for the target city. Extensive experiments on real-world cellular traffic datasets show that ADAPTIVE generally outperforms state-of-the-art baselines by more than 40% in terms of Jensen-Shannon divergence and root-mean-square error. Also, ADAPTIVE has strong robustness based on the results of various cross-city experiments. ADAPTIVE has been successfully deployed on the 'Jiutian' Artificial Intelligence Platform of China Mobile to support cellular traffic generation and assist in the construction and operation of mobile networks.

Millions of slum dwellers suffer from poor accessibility to urban services due to inadequate road infrastructure within slums, and road planning for slums is critical to the sustainable development of cities. Existing re-blocking or heuristic methods are either time-consuming which cannot generalize to different slums, or yield sub-optimal road plans in terms of accessibility and construction costs. In this paper, we present a deep reinforcement learning based approach to automatically layout roads for slums. We propose a generic graph model to capture the topological structure of a slum, and devise a novel graph neural network to select locations for the planned roads. Through masked policy optimization, our model can generate road plans that connect places in a slum at minimal construction costs. Extensive experiments on real-world slums in different countries verify the effectiveness of our model, which can significantly improve accessibility by 14.3% against existing baseline methods. Further investigations on transferring across different tasks demonstrate that our model can master road planning skills in simple scenarios and adapt them to much more complicated ones, indicating the potential of applying our model in real-world slum upgrading. The code and data are available at https://github.com/tsinghua-fib-lab/road-planning-for-slums.

Recently multi-modal recommender systems have been widely applied in real scenarios such as e-commerce businesses. Existing multi-modal recommendation methods exploit the multi-modal content of items as auxiliary information and fuse them to boost performance. Despite the superior performance achieved by multi-modal recommendation models, there's currently no understanding of their robustness to adversarial attacks. In this work, we first identify the vulnerability of existing multi-modal recommendation models. Next, we show the key reason for such vulnerability is modality imbalance, i.e., the prediction score margin between positive and negative samples in the sensitive modality will drop dramatically facing adversarial attacks and fail to be compensated by other modalities. Finally, based on this finding we propose a novel defense method to enhance the robustness of multi-modal recommendation models through modality balancing. Specifically, we first adopt an embedding distillation to obtain a pair of content-similar but prediction-different item embeddings in the sensitive modality and calculate the score margin reflecting the modality vulnerability. Then we optimize the model to utilize the score margin between positive and negative samples in other modalities to compensate for the vulnerability. The proposed method can serve as a plug-and-play module and is flexible to be applied to a wide range of multi-modal recommendation models. Extensive experiments on two real-world datasets demonstrate that our method significantly improves the robustness of multi-modal recommendation models with nearly no performance degradation on clean data.

Digital Twin brings a new realization approach to the modeling of mobile networks. Mobile networks, as complex systems comprising multiple components, such as mobile users, base stations, and wireless environments, have intricate interactions and relationships with each other. By creating a virtual replica of each physical mobile network entity in a virtual space, we build a scalable digital twin system for mobile networks with generative AI. The system can interact with multiple optimizers to evaluate and display real-time simulation results. A companion video can be accessed using the link below. https://youtu.be/xtcBIXPzvkc

Sequential recommendation is one of the most important tasks in recommender systems, which aims to recommend the next interacted item with historical behaviors as input. Traditional sequential recommendation always mainly considers the collected positive feedback such as click, purchase, etc. However, in short-video platforms such as TikTok, video viewing behavior may not always represent positive feedback. Specifically, the videos are played automatically, and users passively receive the recommended videos. In this new scenario, users passively express negative feedback by skipping over videos they do not like, which provides valuable information about their preferences. Different from the negative feedback studied in traditional recommender systems, this passive-negative feedback can reflect users’ interests and serve as an important supervision signal in extracting users’ preferences. Therefore, it is essential to carefully design and utilize it in this novel recommendation scenario. In this work, we first conduct analyses based on a large-scale real-world short-video behavior dataset and illustrate the significance of leveraging passive feedback. We then propose a novel method that deploys the sub-interest encoder, which incorporates positive feedback and passive-negative feedback as supervision signals to learn the user’s current active sub-interest. Moreover, we introduce an adaptive fusion layer to integrate various sub-interests effectively. To enhance the robustness of our model, we then introduce a multi-task learning module to simultaneously optimize two kinds of feedback – passive-negative feedback and traditional randomly-sampled negative feedback. The experiments on two large-scale datasets verify that the proposed method can significantly outperform state-of-the-art approaches. The code is released at https://github.com/tsinghua-fib-lab/RecSys2023-SINE to benefit the community.

Graph Neural Network (GNN)-based models have become the mainstream approach for recommender systems. Despite the effectiveness, they are still suffering from the cold-start problem, i.e., recommend for few-interaction items. Existing GNN-based recommendation models to address the cold-start problem mainly focus on utilizing auxiliary features of users and items, leaving the user-item interactions under-utilized. However, embeddings distributions of cold and warm items are still largely different, since cold items' embeddings are learned from lower-popularity interactions, while warm items' embeddings are from higher-popularity interactions. Thus, there is a seesaw phenomenon, where the recommendation performance for the cold and warm items cannot be improved simultaneously. To this end, we proposed a Uncertainty-aware Consistency learning framework for Cold-start item recommendation (shorten as UCC) solely based on user-item interactions. Under this framework, we train the teacher model (generator) and student model (recommender) with consistency learning, to ensure the cold items with additionally generated low-uncertainty interactions can have similar distribution with the warm items. Therefore, the proposed framework improves the recommendation of cold and warm items at the same time, without hurting any one of them. Extensive experiments on benchmark datasets demonstrate that our proposed method significantly outperforms state-of-the-art methods on both warm and cold items, with an average performance improvement of 27.6%.

Recent years have witnessed the rapid development of online micro-video platforms, in which the recommender system plays an essential role in overcoming the information overloading problem and providing personalized content for users. Although some progress has been achieved in the micro-video recommendation, there are still some limitations in learning the representations of user interests and video features. Specifically, the user modeling in existing works is performed at a coarse-grained level, i.e., video level. However, in micro-video recommendation, the user feedback is at a continuous form---users can skip over a video at each frame---which reveals fine-grained user preferences. In this work, we approach the problem of learning fine-grained user preferences for micro-video recommendation by first collecting two real-world datasets. To address the challenges of preference modeling and weak supervision signal, we propose a solution named FRAME (short for Fine-gRAined preference-modeling for Micro-video rEcommendation). Specifically, we first adopt visual feature extraction and transformation to maintain the fine-grained video embeddings. We then propose graph convolution layers to learn the user preference from complex and fine-grained user-clip relations, and hybrid-supervision objectives for enhancing the supervision signal. The experimental results on two collected real-world datasets demonstrate the effectiveness of our proposed model. We release the datasets and codes in https://github.com/tsinghua-fib-lab/FRAME, which we believe can benefit the community.

Daily activity data that records individuals’ various types of activities in daily life are widely used in many applications such as activity scheduling, activity recommendation, and policymaking. Though with high value, its accessibility is limited due to high collection costs and potential privacy issues. Therefore, simulating human activities to produce massive high-quality data is of great importance to benefit practical applications. However, existing solutions, including rule-based methods with simplified assumptions of human behavior and data-driven methods directly fitting real-world data, both cannot fully qualify for matching reality. In this paper, motivated by the classic psychological theory, Maslow’s need theory describing human motivation, we propose a knowledge-driven simulation framework based on generative adversarial imitation learning. To enhance the fidelity and utility of the generated activity data, our core idea is to model the evolution of human needs as the underlying mechanism that drives activity generation in the simulation model. Specifically, this is achieved by a hierarchical model structure that disentangles different need levels, and the use of neural stochastic differential equations that successfully captures piecewise-continuous characteristics of need dynamics. Extensive experiments demonstrate that our framework outperforms the state-of-the-art baselines in terms of data fidelity and utility. Besides, we present the insightful interpretability of the need modeling. The code is available at https://github.com/tsinghua-fib-lab/Activity-Simulation-SAND.

Accurate user interest modeling is vital for recommendation scenarios. One of the effective solutions is the sequential recommendation that relies on click behaviors, but this is not elegant in the video feed recommendation where users are passive in receiving the streaming contents and return skip or no-skip behaviors. Here skip and no-skip behaviors can be treated as negative and positive feedback, respectively. With the mixture of positive and negative feedback, it is challenging to capture the transition pattern of behavioral sequence. To do so, FeedRec has exploited a shared vanilla Transformer, which may be inelegant because head interaction of multi-heads attention does not consider different types of feedback. In this paper, we propose Dual-interest Factorization-heads Attention for Sequential Recommendation (short for DFAR) consisting of feedback-aware encoding layer, dual-interest disentangling layer and prediction layer. In the feedback-aware encoding layer, we first suppose each head of multi-heads attention can capture specific feedback relations. Then we further propose factorization-heads attention which can mask specific head interaction and inject feedback information so as to factorize the relation between different types of feedback. Additionally, we propose a dual-interest disentangling layer to decouple positive and negative interests before performing disentanglement on their representations. Finally, we evolve the positive and negative interests by corresponding towers whose outputs are contrastive by BPR loss. Experiments on two real-world datasets show the superiority of our proposed method against state-of-the-art baselines. Further ablation study and visualization also sustain its effectiveness. We release the source code here: https://github.com/tsinghua-fib-lab/WWW2023-DFAR.

Graph Neural Network (GNN) based social recommendation models improve the prediction accuracy of user preference by leveraging GNN in exploiting preference similarity contained in social relations. However, in terms of both effectiveness and efficiency of recommendation, a large portion of social relations can be redundant or even noisy, e.g., it is quite normal that friends share no preference in a certain domain. Existing models do not fully solve this problem of relation redundancy and noise, as they directly characterize social influence over the full social network. In this paper, we instead propose to improve graph based social recommendation by only retaining the informative social relations to ensure an efficient and effective influence diffusion, i.e., graph denoising. Our designed denoising method is preference-guided to model social relation confidence and benefits user preference learning in return by providing a denoised but more informative social graph for recommendation models. Moreover, to avoid interference of noisy social relations, it designs a self-correcting curriculum learning module and an adaptive denoising strategy, both favoring highly-confident samples. Experimental results on three public datasets demonstrate its consistent capability of improving three state-of-the-art social recommendation models by robustly removing 10-40% of original relations. We release the source code at https://github.com/tsinghua-fib-lab/Graph-Denoising-SocialRec.

Dynamic link prediction is essential for a wide range of domains, including social networks, bioinformatics, knowledge bases, and recommender systems. Existing works have demonstrated that structural information and temporal information are two of the most important information for this problem. However, existing works either focus on modeling them independently or modeling the temporal dynamics of a single structural scale, neglecting the complex correlations among them. This paper proposes to model the inherent correlations among the evolving dynamics of different structural scales for dynamic link prediction. Following this idea, we propose an Attentional Multi-scale Co-evolving Network (AMCNet). Specifically, We model multi-scale structural information by a motif-based graph neural network with multi-scale pooling. Then, we design a hierarchical attention-based sequence-to-sequence model for learning the complex correlations among the evolution dynamics of different structural scales. Extensive experiments on four real-world datasets with different characteristics demonstrate that AMCNet significantly outperforms the state-of-the-art in both single-step and multi-step dynamic link prediction tasks.

Socioeconomic indicators reflect location status from various aspects such as demographics, economy, crime and land usage, which play an important role in the understanding of location-based social networks (LBSNs). Especially, several existing works leverage multi-source data for socioeconomic indicator prediction in LBSNs, which however fail to capture semantic information as well as distil comprehensive knowledge therein. On the other hand, knowledge graph (KG), which distils semantic knowledge from multi-source data, has been popular in recent LBSN research, which inspires us to introduce KG for socioeconomic indicator prediction in LBSNs. Specifically, we first construct a location-based KG (LBKG) to integrate various kinds of knowledge from heterogeneous LBSN data, including locations and other related elements like point of interests (POIs), business areas as well as various relationships between them, such as spatial proximity and functional similarity. Then we propose a hierarchical KG learning model to capture both global knowledge from LBKG and domain knowledge from several sub-KGs. Extensive experiments on three datasets demonstrate our model’s superiority over state-of-the-art methods in socioeconomic indicators prediction. Our code is released at: https://github.com/tsinghua-fib-lab/KG-socioeconomic-indicator-prediction.

With the prevalence of social media, rewarding users to invite their friends to use an application or adopt a service has become one of the most successful designs in recent years. As the application or service spreads, a diffusion process driven by incentivized invitation forms. However, despite the extensive attention from both industry and academia, this newly-emerging diffusion process remains under-explored. To bridge this gap between academic research and industrial practice, we set out to examine the influence of social hubs, i.e., people with a considerable number of social ties, in the diffusion process driven by incentivized friend invitation. Through a large-scale empirical data analysis, we found that under three different measures, the influence of social hubs on the growth of the diffusion process is saturated as their number of contacts increases. Following this observation, we further explored possible causes of this phenomenon by a mixed method that combines a large-scale empirical data analysis and a semi-structured interview to deepen our understanding of social hubs’ influence in the diffusion process. We revealed two main causes. First, large social hubs lacked the will to keep engaging in sending invitations, and the anchoring effects on the cost-utility trade-off could explain their behaviors. Second, social hubs’ broadcasting capability decreased in the invitation-based diffusion process because hubs are better at informing rather than persuading compared with non-hubs. Our findings provide in-depth insights into the understanding of the nature of social hubs’ influence, and we further discuss practical implications for designs to facilitate invitation-based online diffusion processes.

Traffic congestion incurs long delay in travel time, which seriously affects our daily travel experiences. Exploring why traffic congestion occurs is significantly important to effectively address the problem of traffic congestion and improve user experience. Traditional approaches to mine the congestion causes depend on human efforts, which is time consuming and cost-intensive. Hence, we aim at discovering the known and unknown causes of traffic congestion in a systematic way. However, to achieve it, there are three challenges: (1) traffic congestion is affected by several factors with complex spatio-temporal relations; (2) there are a few samples of congestion data with known causes due to the limitation of human label; (3) more unknown congestion causes are unexplored since several factors contribute to traffic congestion. To address above challenges, we design a congestion cause discovery system consisting of two modules: (1) congestion feature extraction module, which extracts the important features distinguishing between different causes of congestion; and (2) congestion cause discovery module, which designs a deep semi-supervised learning based framework to discover the causes of traffic congestion with limited labeled data. Specifically, in pre-training stage, it first leverages a few labeled data as prior knowledge to pre-train the model. Then, in clustering stage, we propose two different clustering methods to discover the congestion causes. For the first clustering method, we extend the classic deep embedded clustering model to produce clusters via soft assignment. For the second one, we iteratively usek-means to group the latent features extracted from the pre-trained model, and use the cluster results as pseudo-labels to fine-tune the network. Extensive experiments show that the performance of our methods is superior to the state-of-the-art baselines, which demonstrates the effectiveness of the proposed cause discovery system. Additionally, our system is deployed and used in the practical production environment at Amap.

Street view data is one of the most common data sources for urban prediction tasks, such as estimating socioeconomic status, sensing physical urban changes, and identifying urban villages. Typical research in this field consists of two steps: acquiring a dataset with a street view image sampling algorithm and designing a prediction algorithm for urban prediction tasks. However, most of the previous research focuses on the prediction algorithms, leaving the sampling algorithms underexplored. To fill this gap, we set out to investigate how different street view image sampling algorithms affect the performance of the follow-up tasks and develop an effective street view image sampling algorithm for urban prediction. Through a comprehensive analysis of the performance of different sampling algorithms in three of the most common urban prediction tasks, including commercial activeness prediction, urban liveliness prediction, and urban population prediction, we provide solid empirical evidence that the sampling algorithm significantly affects the performance of the prediction model. Specifically, the performance differences of different sampling algorithms can reach over 25%. Further, we revealed that the sampling step size and the sampling quality are two important factors that affect the performance of a sampling algorithm, while the sampling angle has little influence. Inspired by our analysis results, we propose an effective street view image sampling algorithm, DAS, which contains a denoising module and an adaptive sampling module. It can dynamically adjust the sampling step size to adapt to the optimal size for each region and get rid of the impact of noise images in the meantime. Experiments on three large-scale datasets demonstrate its superior performance over multiple state-of-the-art baselines, and further ablation study shows the effectiveness of each module. Finally, through a thorough discussion of our findings and experimental results, we provide insights into the street view image sampling algorithm design, and we call for more researches in this blank area.

Federated optimization (FedOpt), which targets at collaboratively training a learning model across a large number of distributed clients, is vital for federated learning. The primary concerns in FedOpt can be attributed to the model divergence and communication efficiency, which significantly affect the performance. In this article, we propose a new method, i.e., LoSAC, to learn from heterogeneous distributed data more efficiently. Its key algorithmic insight is to locally update the estimate for the global full gradient after each regular local model update. Thus, LoSAC can keep clients’ information refreshed in a more compact way. In particular, we have studied the convergence result for LoSAC. Besides, the bonus of LoSAC is the ability to defend the information leakage from the recent technique Deep Leakage Gradients (DLG). Finally, experiments have verified the superiority of LoSAC comparing with state-of-the-art FedOpt algorithms. Specifically, LoSAC significantly improves communication efficiency by more than 100% on average, mitigates the model divergence problem, and equips with the defense ability against DLG.

In real-world express systems, couriers need to satisfy not only the delivery demands but also the pick-up demands of customers. Delivery and pickup tasks are usually mixed together within integrated routing plans. Such a mixed routing problem can be abstracted and formulated as Vehicle Routing Problem with Mixed Delivery and Pickup (VRPMDP), which is an NP-hard combinatorial optimization problem. To solve VRPMDP, there are three major challenges as below. (a) Even though successive pickup and delivery tasks are independent to accomplish, the inter-influence between choosing pickup task or delivery task to deal with still exists. (b) Due to the two-way flow of goods between the depot and customers, the loading rate of vehicles leaving the depot affects routing decisions. (c) The proportion of deliveries and pickups will change due to the complex demand situation in real-world scenarios, which requires robustness of the algorithm. To solve the challenges above, we design an encoder-decoder based framework to generate high-quality and robust VRPMDP solutions. First, we consider a VRPMDP instance as a graph and utilize a GNN encoder to extract the feature of the instance effectively. The detailed routing solutions are further decoded as a sequence by the decoder with attention mechanism. Second, we propose a Coordinated Decision of Loading and Routing (CDLR) mechanism to determine the loading rate dynamically after the vehicle returns to the depot, thus avoiding the influence of improper loading rate settings. Finally, the model equipped with a GNN encoder and CDLR simultaneously can adapt to the changes in the proportion of deliveries and pickups. We conduct the experiments to demonstrate the effectiveness of our model. The experiments show that our method achieves desirable results and generalization ability.

Traffic prediction is the cornerstone of intelligent transportation system. Accurate traffic forecasting is essential for the applications of smart cities, i.e., intelligent traffic management and urban planning. Although various methods are proposed for spatio-temporal modeling, they ignore the dynamic characteristics of correlations among locations on road network. Meanwhile, most Recurrent Neural Network based works are not efficient enough due to their recurrent operations. Additionally, there is a severe lack of fair comparison among different methods on the same datasets. To address the above challenges, in this article, we propose a novel traffic prediction framework, named Dynamic Graph Convolutional Recurrent Network (DGCRN). In DGCRN, hyper-networks are designed to leverage and extract dynamic characteristics from node attributes, while the parameters of dynamic filters are generated at each time step. We filter the node embeddings and then use them to generate dynamic graph, which is integrated with pre-defined static graph. As far as we know, we are first to employ a generation method to model fine topology of dynamic graph at each time step. Furthermore, to enhance efficiency and performance, we employ a training strategy for DGCRN by restricting the iteration number of decoder during forward and backward propagation. Finally, a reproducible standardized benchmark and a brand new representative traffic dataset are opened for fair comparison and further research. Extensive experiments on three datasets demonstrate that our model outperforms 15 baselines consistently. Source codes are available at https://github.com/tsinghua-fib-lab/Traffic-Benchmark .

Bundle recommendation aims to recommend a bundle of items for a user to consume as a whole. Related work can be divided into two categories: 1) to recommend the platforms prebuilt bundles to users; 2) generate personalized bundles for users. These two problems are not well solved. In this work, we propose two graph neural network models, a BGCN model for prebuilt bundle recommendation, and a BGGN model for personalized bundle generation. First, BGCN unifies the user-item interaction, the user-bundle interaction and the bundle-item affiliation into a heterogeneous graph. With item nodes as the bridge, graph convolutional propagation between user and bundle nodes makes the learned representations capture the item-level semantics. Second, BGGN re-constructs bundles into graphs based on the item co-occurrence pattern and the users supervision signal. The complex and high-order item-item relationships in the bundle graph are explicitly modeled through graph generation. Empirical results demonstrate the substantial performance gains of BGCN and BGGN. We have released the datasets and codes at this link: https://github.com/cjx0525/BGCN.

Social e-commerce uses social media as a new prevalent platform for online shopping. In this paper, we address the problem of cross-platform recommendation for social e-commerce, i.e., recommending products to users when they are shopping through social media. To the best of our knowledge, this is a new and important problem for all e-commerce companies (e.g. Amazon, Alibaba), but has never been studied before. Existing cross-platform and social related recommendation methods cannot be applied directly to this problem since they do not co-consider the social information and the cross-platform characteristics together. To study this problem, we collect two real-world datasets from social e-commerce services. We first investigate the heterogeneous shopping behaviors between traditional e-commerce app and social media. Based on these observations from data, we propose CROSS (Cross-platform Recommendation for Online Shopping in Social Media), a recommendation framework utilizing not only user-item interaction data on both platforms, but also social relation data on social media. The framework is general and we propose two variants, CROSS-MF and CROSS-NCF. Extensive experiments on two real-world social e-commerce datasets demonstrate that our proposed CROSS significantly outperforms existing state-of-the-art methods.

Social recommendation leverages social information to alleviate data sparsity and cold-start issues of collaborative filtering (CF) methods. Most existing works model user interests following the assumption ofsocial homophilybased on social-relation data. The explicit modeling ofsocial influence, which also largely affects user behaviors, has not been well explored. Considering user behaviors may be driven by social factors in today’s information services (e.g., purchasing products shared by close friends on social e-commerce applications), these methods will be suboptimal. In this work, we propose a method modeling both social homophily-aware user interests and social influence as two essential effects on user behaviors for social recommendation, named as DISGCN (short forDISentangled modeling of Social homophily and influence withGraphConvolutionalNetwork). Specifically, we devise a disentangled embedding layer to encode these two effects. Furthermore, two tailored graph convolutional layers are developed to disentangle them refinedly, leveraging the high-order embedding propagation in social-network graph from two aspects. Technically, first, the operation of attentive embedding propagation is adopted for capturing personalized social homophily-aware interests, and second, the item-gate-based embedding propagation is proposed for capturing item-specific social influence. In addition, to ensure the disentanglement of social influence, we propose a contrastive learning framework that endows corresponding embeddings with explicit semantics. Extensive experiments on two real-world datasets demonstrate the effectiveness of our proposed model. Further studies also verify the rationality and necessity of our designs. We have released the datasets and codes at this link:https://github.com/tsinghua-fib-lab/DISGCN.

Point-of-Interest (POI) recommendation has drawn a lot of attention in both academia and industry. It utilizes user check-in data, aiming at recommending unvisited POIs to users. To address the data-sparsity problem, geographical information of POIs is often incorporated into recommender systems. However, most of the existing approaches model geographical impact in an implicit way, in which geographical information is encoded as auxiliary vectors for learning unified representations of users and POIs. Following this paradigm, the embedding of POIs can not reflect geographical similarity directly; thus, an explicit modeling approach is needed as geography is of great importance in POI recommendation. To address challenges in disentangling geographical effect, we proposed a disentangled representation learning method named DIG (short for Disentangled embedding of user Interest and POIs' Geographical information). Aiming at decoupling the geographical factor and the user interest factor thoroughly, we first proposed a geo-constrained negative sampling strategy, which helps to find reliable negative samples for the two factors. Second, a geo-enhanced soft-weighted loss function was proposed to quantify the trade-off between the two factors in loss computation. Extensive experiments have been conducted on two real-world datasets, and results have demonstrated the significant improvement of DIG at 3.92% - 20.32% 3.92% - 20.32% on recall, and 2.53% - 11.48% 2.53% - 11.48% on hit ratio, compared with other state-of-the-art approaches.

In recent years, due to the prevalence of online textual advertisements, increasing businesses recognize their huge potential in product promotion. The high-quality textual content has been empirically shown to have a substantial impact on consumers’ attitudes and decisions. As a result, persuasive tactics play an essential role in online textual advertisements, which are employed to increase the attractiveness, and sequentially increase the conversion rate and sales volume. As the context of persuasion, product attributes, e.g., category and price, also greatly influence the persuasion outcomes. However, they are largely overlooked by existing works. In this paper, we propose a novel framework to study context-aware persuasion by designing a multi-task learning model and performing extensive causal analysis. First, the prediction model recognizes the persuasive tactics employed in an advertising text and predicts their promotion effectiveness. Specifically, we design a disentangled representation learning algorithm to capture the persuasive tactics, and then develop a novel context-aware attention module to model the relationships between persuasive tactics and product attributes. Experiments on a large-scale real-world dataset demonstrate the superior performance of our proposed model over state-of-the-art baselines. Then we show its great practical value by conducting an in-depth causal analysis of context-aware results that our model learns, which offers insightful interpretations and guidelines for marketers to employ persuasive tactics in textual advertisements.

In this work, we aim at developing an effective method to predict user purchase intention with the focus on the price factor in recommender systems. The main difficulties are two-fold: 1) the preference and sensitivity of a user on item price are unknown, which are only implicitly reflected in the items that the user has purchased, and 2) how the item price affects a users intention depends largely on the product category, that is, the perception and affordability of a user on item price could vary significantly across categories. Towards the first difficulty, we propose to model the transitive relationship between user-to-item and item-to-price, taking the inspiration from the recently developed Graph Convolution Networks (GCN). The key idea is to propagate the influence of price on users with items as the bridge, so as to make the learned user representations be price-aware. For the second difficulty, we further integrate item categories into the propagation progress and model the possible pairwise interactions for predicting user-item interactions. We conduct extensive experiments on two real-world datasets, demonstrating the effectiveness of our GCN-based method in learning the price-aware preference of users.

Recommender system is one of the most important information services on today’s Internet. Recently, graph neural networks have become the new state-of-the-art approach to recommender systems. In this survey, we conduct a comprehensive review of the literature on graph neural network-based recommender systems. We first introduce the background and the history of the development of both recommender systems and graph neural networks. For recommender systems, in general, there are four aspects for categorizing existing works: stage, scenario, objective, and application. For graph neural networks, the existing methods consist of two categories: spectral models and spatial ones. We then discuss the motivation of applying graph neural networks into recommender systems, mainly consisting of the high-order connectivity, the structural property of data and the enhanced supervision signal. We then systematically analyze the challenges in graph construction, embedding propagation/aggregation, model optimization, and computation efficiency. Afterward and primarily, we provide a comprehensive overview of a multitude of existing works of graph neural network-based recommender systems, following the taxonomy above. Finally, we raise discussions on the open problems and promising future directions in this area. We summarize the representative papers along with their code repositories in https://github.com/tsinghua-fib-lab/GNN-Recommender-Systems .

Cooperative Pickup and Delivery Problem (PDP), as a variant of the typical Vehicle Routing Problems (VRP), is an important formulation in many real-world applications, such as on-demand delivery, industrial warehousing, etc. It is of great importance to efficiently provide high-quality solutions of cooperative PDP. However, it is not trivial to provide effective solutions directly due to two major challenges: 1) the structural dependency between pickup and delivery pairs require explicit modeling and representation. 2) the cooperation between different vehicles is highly related to the solution exploration and difficult to model. In this paper, we propose a novel multi-agent reinforcement learning based framework to solve the cooperative PDP (MAPDP). First, we design a paired context embedding to well measure the dependency of different nodes considering their structural limits. Second, we utilize cooperative multi-agent decoders to leverage the decision dependence among different vehicle agents based on a special communication embedding. Third, we design a novel cooperative A2C algorithm to train the integrated model. We conduct extensive experiments on a randomly generated dataset and a real-world dataset. Experiments result shown that the proposed MAPDP outperform all other baselines by at least 1.64\% in all settings, and shows significant computation speed during solution inference.

Session-based recommendation (SBR) aims to recommend items based on user behaviors in a session. For the online life service platforms, such as Meituan, both the user's location and the current time primarily cause the different patterns and intents in user behaviors. Hence, spatiotemporal context plays a significant role in the recommendation on those platforms, which motivates an important problem of spatiotemporal-aware session-based recommendation (STSBR). Since the spatiotemporal context is introduced, there are two critical challenges: 1) how to capture session-level relations of spatiotemporal context (inter-session view), and 2) how to model the complex user decision-making process at a specific location and time (intra-session view). To address them, we propose a novel solution named STAGE in this paper. Specifically, STAGE first constructs a global information graph to model the multi-level relations among all sessions, and a session decision graph to capture the complex user decision process for each session. STAGE then performs inter-session and intra-session embedding propagation on the constructed graphs with the proposed graph attentive convolution (GAC) to learn representations from the above two perspectives. Finally, the learned representations are combined with spatiotemporal-aware soft-attention for final recommendation. Extensive experiments on two datasets from Meituan demonstrate the superiority of STAGE over state-of-the-art methods. Further studies also verify that each component is effective.

Traffic prediction plays an important role in many intelligent transportation systems. Many existing works design static neural network architecture to capture complex spatio-temporal correlations, which is hard to adapt to different datasets. Although recent neural architecture search approaches have addressed this problem, it still adopts a coarse-grained search with pre-defined and fixed components in the search space for spatio-temporal modeling. In this paper, we propose a novel neural architecture search framework, entitled AutoSTS, for automated spatio-temporal synchronous modeling in traffic prediction. To be specific, we design a graph neural network (GNN) based architecture search module to capture localized spatio-temporal correlations, where multiple graphs built from different perspectives are jointly utilized to find a better message passing way for mining such correlations. Further, we propose a convolutional neural network (CNN) based architecture search module to capture temporal dependencies with various ranges, where gated temporal convolutions with different kernel sizes and convolution types are designed in search space. Extensive experiments on six public datasets demonstrate that our model can achieve 4%-10% improvements compared with other methods.

With the increase of computing power and the development of data science, modeling and simulation are becoming indispensable tools in urban science research. Cities, as complex systems made up of many aspects such as mobility, infrastructure, have complex interactions and relationships among multiple elements. In order to provide researchers with tools to model and simulate complex urban systems, we first propose a city model that focuses on three key concepts: human, thing and space. According to the city model, we design and develop Mirage, an efficient and extensible city simulation framework and also implement an efficient mobility module as Mirage's necessary module. To show the extensibility of Mirage, we build application cases about urban vulnerability and decision making. We also conduct extensive experiments to verify the efficiency of Mirage and its mobility module.

With the widespread use of mobile devices in recent years, accurate prediction of base station traffic is vital for maintaining a good quality of mobile network services. In this paper, we propose an ensemble learning framework to predict the cellular traffic of base stations. Specifically, we introduce the Granger causality test to find the causal relationship in the base stations and model the spatial relationship between them simultaneously. We also employ a temporal convolutional network (TCN) to extract the sequential temporal features of base station traffic. Aiming at modelling the long-tail characteristics of the traffic distribution of base stations, we use the technique of redundant encoding to refine the prediction task to learn the base station traffic of different scales combined with ensemble learning. Extensive experimental results demonstrate that our method can predict base station traffic precisely and outperforms the best baseline by nearly 13% on average in terms of NMSE and NRMSE.

Consumption intent, defined as the decision-driven force of consumption behaviors, is crucial for improving the explainability and performance of user-modeling systems, with various downstream applications like recommendation and targeted marketing. However, consumption intent is implicit, and only a few known intents have been explored from the user consumption data in Meituan. Hence, discovering new consumption intents is a crucial but challenging task, which suffers from two critical challenges: 1) how to encode the consumption intent related to multiple aspects of preferences, and 2) how to discover the new intents with only a few known ones. In Meituan, we designed the AutoIntent system, consisting of the disentangled intent encoder and intent discovery decoder, to address the above challenges. Specifically, for the disentangled intent encoder, we construct three groups of dual hypergraphs to capture the high-order relations under the three aspects of preferences and then utilize the designed hypergraph neural networks to extract disentangled intent features. For the intent discovery decoder, we propose to build intent-pair pseudo labels based on the denoised feature similarities to transfer knowledge from known intents to new ones. Extensive offline evaluations verify that AutoIntent can effectively discover unknown consumption intents. Moreover, we deploy AutoIntent in the recommendation engine of the Meituan APP, and the further online evaluation verifies its effectiveness.

In online information systems, users make decisions based on factors of several specific aspects, such as brand, price, etc. Existing recommendation engines ignore the explicit modeling of these factors, leading to sub-optimal recommendation performance. In this paper, we focus on the real-world scenario where these factors can be explicitly captured (the users are exposed with decision factor-based persuasion texts, i.e., persuasion factors). Although it allows us for explicit modeling of user-decision process, there are critical challenges including the persuasion factor's representation learning and effect estimation, along with the data-sparsity problem. To address them, in this work, we present our POEM (short for Persuasion factOr Effect Modeling) system. We first propose the persuasion-factor graph convolutional layers for encoding and learning representations from the persuasion-aware interaction data. Then we develop a prediction layer that fully considers the user sensitivity to the persuasion factors. Finally, to address the data-sparsity issue, we propose a counterfactual learning-based data augmentation method to enhance the supervision signal. Real-world experiments demonstrate the effectiveness of our proposed framework of modeling the effect of persuasion factors.

Human daily activities, such as working, eating out, and traveling, play an essential role in contact tracing and modeling the diffusion patterns of the COVID-19 pandemic. However, individual-level activity data collected from real scenarios are highly limited due to privacy issues and commercial concerns. In this paper, we present a novel framework based on generative adversarial imitation learning, to generate artificial activity trajectories that retain both the fidelity and utility of the real-world data. To tackle the inherent randomness and sparsity of irregular-sampled activities, we innovatively capture the spatiotemporal dynamics underlying trajectories by leveraging neural differential equations. We incorporate the dynamics of continuous flow between consecutive activities and instantaneous updates at observed activity points in temporal evolution and spatial transformation. Extensive experiments on two real-world datasets show that our proposed framework achieves superior performance over state-of-the-art baselines in terms of improving the data fidelity and data utility in facilitating practical applications. Moreover, we apply the synthetic data to model the COVID-19 spreading, and it achieves better performance by reducing the simulation MAPE over the baseline by more than 50%. The source code is available online: https://github.com/tsinghua-fib-lab/Activity-Trajectory-Generation.

Crowd simulation acts as the basic component in traffic management, urban planning, and emergency management. Most existing approaches use physics-based models due to their robustness and strong generalizability, yet they fall short in fidelity since human behaviors are too complex and heterogeneous for a universal physical model to describe. Recent research tries to solve this problem by deep learning methods. However, they are still unable to generalize well beyond training distributions. In this work, we propose to jointly leverage the strength of the physical and neural network models for crowd simulation by a Physics-Infused Machine Learning (PIML) framework. The key idea is to let the two models learn from each other by iteratively going through a physics-informed machine learning process and a machine-learning-aided physics discovery process. We present our realization of the framework with a novel neural network model, Physics-informed Crowd Simulator (PCS), and tailored interaction mechanisms enabling the two models to facilitate each other. Specifically, our designs enable the neural network model to identify generalizable signals from real-world data better and yield physically consistent simulations with the physical model's form and simulation results as a prior. Further, by performing symbolic regression on the well-trained neural network, we obtain improved physical models that better describe crowd dynamics. Extensive experiments on two publicly available large-scale real-world datasets show that, with the framework, we successfully obtain a neural network model with strong generalizability and a new physical model with valid physical meanings at the same time. Both models outperform existing state-of-the-art simulation methods in accuracy, fidelity, and generalizability, which demonstrates the effectiveness of the PIML framework for improving simulation performance and its capability for facilitating scientific discovery and deepening our understandings of crowd dynamics. We release the codes at https://github.com/tsinghua-fib-lab/PIML.

Recommender systems are prone to be misled by biases in the data. Models trained with biased data fail to capture the real interests of users, thus it is critical to alleviate the impact of bias to achieve unbiased recommendation. In this work, we focus on an essential bias in micro-video recommendation, duration bias. Specifically, existing micro-video recommender systems usually consider watch time as the most critical metric, which measures how long a user watches a video. Since videos with longer duration tend to have longer watch time, there exists a kind of duration bias, making longer videos tend to be recommended more against short videos. In this paper, we empirically show that commonly-used metrics are vulnerable to duration bias, making them NOT suitable for evaluating micro-video recommendation. To address it, we further propose an unbiased evaluation metric, called WTG (short for Watch Time Gain). Empirical results reveal that WTG can alleviate duration bias and better measure recommendation performance. Moreover, we design a simple yet effective model named DVR (short for Debiased Video Recommendation) that can provide unbiased recommendation of micro-videos with varying duration, and learn unbiased user preferences via adversarial learning. Extensive experiments based on two real-world datasets demonstrate that DVR successfully eliminates duration bias and significantly improves recommendation performance with over 30% relative progress. Codes and datasets are released at https://github.com/tsinghua-fib-lab/WTG-DVR.

Session-based recommendation (SBR) aims at the next-item prediction with a short behavior session. Existing solutions fail to address two main challenges: 1) user interests are shown as dynamically coupled intents, and 2) sessions always contain noisy signals. To address them, in this paper, we propose a hypergraph-based solution, HIDE. Specifically, HIDE first constructs a hypergraph for each session to model the possible interest transitions from distinct perspectives. HIDE then disentangles the intents under each item click in micro and macro manners. In the micro-disentanglement, we perform intent-aware embedding propagation on session hypergraph to adaptively activate disentangled intents from noisy data. In the macro-disentanglement, we introduce an auxiliary intent-classification task to encourage the independence of different intents. Finally, we generate the intent-specific representations for the given session to make the final recommendation. Benchmark evaluations demonstrate the significant performance gain of our HIDE over the state-of-the-art methods.

Widely applied in today's recommender systems, sequential recommendation predicts the next interacted item for a given user via his/her historical item sequence. However, sequential recommendation suffers data sparsity issue like most recommenders. To extract auxiliary signals from the data, some recent works exploit self-supervised learning to generate augmented data via dropout strategy, which, however, leads to sparser sequential data and obscure signals. In this paper, we propose D ual C ontrastive N etwork (DCN) to boost sequential recommendation, from a new perspective of integrating auxiliary user-sequence for items. Specifically, we propose two kinds of contrastive learning. The first one is the dual representation contrastive learning that minimizes the distances between embeddings and sequence-representations of users/items. The second one is the dual interest contrastive learning which aims to self-supervise the static interest with the dynamic interest of next item prediction via auxiliary training. We also incorporate the auxiliary task of predicting next user for a given item's historical user sequence, which can capture the trends of items preferred by certain types of users. Experiments on benchmark datasets verify the effectiveness of our proposed method. Further ablation study also illustrates the boosting effect of the proposed components upon different sequential models.

Accurate churn prediction for retaining users is keenly important for online services because it determines their survival and prosperity. Recent research has specified social influence to be one of the most important reasons for user churn, and thereby many works start to model its effects on user churn to improve the prediction performance. However, existing works only use the data's correlational information while neglecting the problem's causal nature. Specifically, the fact that a user's churn is correlated with some social factors does not mean he/she is actually influenced by his/her friends, which results in inaccurate and unexplainable predictions of the existing methods. To bridge this gap, we develop a counterfactual modeling framework for churn prediction, which can effectively capture the causal information of social influence for accurate and explainable churn predictions. Specifically, we first propose a backbone framework that uses two separate embeddings to model users' endogenous churn intentions and the exogenous social influence. Then, we propose a counterfactual data augmentation module to introduce the causal information to the model by providing partially labeled counterfactual data. Finally, we design a three-headed counterfactual prediction framework to guide the model to learn causal information to facilitate churn prediction. Extensive experiments on two large-scale datasets with different types of social relations show our model's superior prediction performance compared with the state-of-the-art baselines. We further conduct an in-depth analysis of the prediction results demonstrating our proposed method's ability to capture causal information of social influence and give explainable churn predictions, which provide insights into designing better user retention strategies.

Network traffic data facilitates understanding the Internet of Things (IoT) behaviors and improving IoT service quality in the real world. However, large-scale IoT traffic data is rarely accessible, and privacy issues also impede realistic data sharing even with anonymous personal identifiable information. Researchers propose to generate synthetic IoT traffic but fail to cover the multiple services provided by widespread real-world IoT devices. In this work, we take the first step to generate large-scale IoT traffic via a knowledge-enhanced generative adversarial network (GAN) framework, which introduces both the semantic knowledge (e.g., location and environment information) and the network structure knowledge for various IoT devices via a knowledge graph. We use a condition mechanism to incorporate the knowledge and device category for IoT traffic generation. Then, we adopt LSTM and a self-attention mechanism to capture the temporal correlation in the traffic series. Extensive experiment results show that the synthetic IoT traffic datasets generated by our proposed model outperform state-of-art baselines in terms of data fidelity and applications. Moreover, our proposed model is able to generate realistic data by only training on small real datasets with knowledge enhanced.

Modeling user’s long-term and short-term interests is crucial for accurate recommendation. However, since there is no manually annotated label for user interests, existing approaches always follow the paradigm of entangling these two aspects, which may lead to inferior recommendation accuracy and interpretability. In this paper, to address it, we propose a Contrastive learning framework to disentangle Long and Short-term interests for Recommendation (CLSR) with self-supervision. Specifically, we first propose two separate encoders to independently capture user interests of different time scales. We then extract long-term and short-term interests proxies from the interaction sequences, which serve as pseudo labels for user interests. Then pairwise contrastive tasks are designed to supervise the similarity between interest representations and their corresponding interest proxies. Finally, since the importance of long-term and short-term interests is dynamically changing, we propose to adaptively aggregate them through an attention-based network for prediction. We conduct experiments on two large-scale real-world datasets for e-commerce and short-video recommendation. Empirical results show that our CLSR consistently outperforms all state-of-the-art models with significant improvements: GAUC is improved by over 0.01, and NDCG is improved by over 4%. Further counterfactual evaluations demonstrate that stronger disentanglement of long and short-term interests is successfully achieved by CLSR. The code and data are available at https://github.com/tsinghua-fib-lab/CLSR.

Internet of Things (IoT) devices are increasingly growing in mobile networks with the ubiquity of various IoT services. They share the same infrastructure with smartphones while having different requirements for communication resources and security defense mechanisms. Distinguishing IoT devices from smartphones has far-reaching implications on effective network design, resource allocation scheme, pricing scheme, etc. In this article, we distinguish between 12 107 IoT devices and 12 693 smartphones in the real world via characterizing their network traffic. The IoT devices fall into five categories, namely, locating, monitoring, portable, point of sale (POS), and vehicle. We analyze the device behaviors from the network domain, physical domain, and time domain, make comparisons between each kind of IoT devices and smartphones, and design effective features based on the distinguishable network behavior characteristics at packet level, traffic level, and mobility level. Then, we train several classifiers based on our feature set to identify different kinds of mobile devices. Specifically, the accuracy of identifying IoT devices from smartphones achieves 95.86%, and the accuracies of distinguishing IoT devices in each category from smartphones are all over 95%. In the trained classifiers, feature importance verifies the discriminability of different network traffic characteristics observed in our multidomain measurement. Our study reveals the network traffic behavior characteristics for IoT devices, and successfully distinguishes them from smartphones, which paves the way for better network design, resource allocation, pricing scheme, and security defense mechanisms.

It is essential to predict crowd flow precisely in a city, which is practically partitioned into irregular regions based on road networks and functionality. However, prior works mainly focus on grid-based crowd flow prediction, where a city is divided into many regular grids. Although Convolutional Neural Netwok (CNN) is powerful to capture spatial dependence from grid-based Euclidean data, it fails to tackle non-Euclidean data, which reflect the correlations among irregular regions. Besides, prior works fail to jointly capture the hierarchical spatio-temporal dependence from both regular and irregular regions. Finally, the correlations among regions are time-varying and functionality-related. However, the combination of dynamic and semantic attributes of regions are ignored by related works. To address the above challenges, in this article, we propose a novel model to tackle the flow prediction task for irregular regions. First, we employ CNN and Graph Neural Network (GNN) to capture micro and macro spatial dependence among grid-based regions and irregular regions, respectively. Further, we think highly of the dynamic inter-region correlations and propose a location-aware and time-aware graph attention mechanism named Semantic Graph Attention Network (Semantic-GAT), based on dynamic node attribute embedding and multi-view graph reconstruction. Extensive experimental results based on two real-life datasets demonstrate that our model outperforms 10 baselines by reducing the prediction error around 8%.

Crowd flow prediction is of great importance in a wide range of applications from urban planning, traffic control to public safety. It aims at predicting the inflow (the traffic of crowds entering a region in a given time interval) and outflow (the traffic of crowds leaving a region for other places) of each region in the city with knowing the historical flow data. In this article, we propose DeepSTN+, a deep learning-based convolutional model, to predict crowd flows in the metropolis. First, DeepSTN+ employs the ConvPlus structure to model the long-range spatial dependence among crowd flows in different regions. Further, PoI distributions and time factor are combined to express the effect of location attributes to introduce prior knowledge of the crowd movements. Finally, we propose a temporal attention-based fusion mechanism to stabilize the training process, which further improves the performance. Extensive experimental results based on four real-life datasets demonstrate the superiority of our model, i.e., DeepSTN+ reduces the error of the crowd flow prediction by approximately 10%–21% compared with the state-of-the-art baselines.

Web systems that provide the same functionality usually share a certain amount of items. This makes it possible to combine data from different websites to improve recommendation quality, known as the cross-domain recommendation task. Despite many research efforts on this task, the main drawback is that they largely assume the data of different systems can be fully shared . Such an assumption is unrealistic different systems are typically operated by different companies, and it may violate business privacy policy to directly share user behavior data since it is highly sensitive. In this work, we consider a more practical scenario to perform cross-domain recommendation. To avoid the leak of user privacy during the data sharing process, we consider sharing only the information of the item side, rather than user behavior data. Specifically, we transfer the item embeddings across domains, making it easier for two companies to reach a consensus (e.g., legal policy) on data sharing since the data to be shared is user-irrelevant and has no explicit semantics. To distill useful signals from transferred item embeddings, we rely on the strong representation power of neural networks and develop a new method named as NATR (short for N eural A ttentive T ransfer R ecommendation ). We perform extensive experiments on two real-world datasets, demonstrating that NATR achieves similar or even better performance than traditional cross-domain recommendation methods that directly share user-relevant data. Further insights are provided on the efficacy of NATR in using the transferred item embeddings to alleviate the data sparsity issue.

The wide adoption of mobile devices has provided us with a massive volume of human mobility records. However, a large portion of these records is unlabeled, i.e., only have GPS coordinates without semantic information (e.g., Point of Interest (POI)). To make those unlabeled records associate with more information for further applications, it is of great importance to annotate the original data with POIs information based on the external context. Nevertheless, semantic annotation of mobility records is challenging due to three aspects: the complex relationship among multiple domains of context, the sparsity of mobility records, and difficulties in balancing personal preference and crowd preference. To address these challenges, we propose CAP, a context-aware personalized semantic annotation model, where we use a Bayesian mixture model to model the complex relationship among five domains of context—location, time, POI category, personal preference, and crowd preference. We evaluate our model on two real-world datasets, and demonstrate that our proposed method significantly outperforms the state-of-the-art algorithms by over 11.8%.

Human mobility prediction is of great importance for a wide spectrum of location-based applications. However, predicting mobility is not trivial because of four challenges: 1) the complex sequential transition regularities exhibited with time-dependent and high-order nature; 2) the multi-level periodicity of human mobility; 3) the heterogeneity and sparsity of the collected trajectory data; and 4) the complicated semantic motivation behind the mobility. In this paper, we propose DeepMove, an attentional recurrent network for mobility prediction from lengthy and sparse trajectories. In DeepMove, we first design a multi-modal embedding recurrent neural network to capture the complicated sequential transitions by jointly embedding the multiple factors that govern human mobility. Then, we propose a historical attention model with two mechanisms to capture the multi-level periodicity in a principle way, which effectively utilizes the periodicity nature to augment the recurrent neural network for mobility prediction. Furthermore, we design a context adaptor to capture the semantic effects of Point-Of-Interest (POI)-based activity and temporal factor (e.g., dwell time). Finally, we use the multi-task framework to encourage the model to learn comprehensive motivations with mobility by introducing the task of the next activity type prediction and the next check-in time prediction. We perform experiments on four representative real-life mobility datasets, and extensive evaluation results demonstrate that our model outperforms the state-of-the-art models by more than 10 percent. Moreover, compared with the state-of-the-art neural network models, DeepMove provides intuitive explanations into the prediction and sheds light on interpretable mobility prediction.

Online services are playing critical roles in almost all aspects of users’ life. Users usually have multiple online identities (IDs) in different online services. In order to fuse the separated user data in multiple services for better business intelligence, it is critical for service providers to link online IDs belonging to the same user. On the other hand, the popularity of mobile networks and GPS-equipped smart devices have provided a generic way to link IDs, i.e., utilizing themobility tracesof IDs. However, linking IDs based on their mobility traces has been a challenging problem due to the highly heterogeneous, incomplete and noisy mobility data across services. In this paper, we proposeDPLink, an end-to-end deep learning based framework, to complete the user identity linkage task for heterogeneous mobility data collected from different services with different properties.DPLinkis made up by afeature extractorincluding a location encoder and a trajectory encoder to extract representative features from trajectory and acomparatorto compare and decide whether to link two trajectories as the same user. Particularly, we propose a pre-training strategy with a simple task to train theDPLinkmodel to overcome the training difficulties introduced by the highly heterogeneous nature of different source mobility data. Besides, we introduce a multi-modal embedding network and a co-attention mechanism inDPLinkto deal with the low-quality problem of mobility data. By conducting extensive experiments on two real-life ground-truth mobility datasets with eight baselines, we demonstrate thatDPLinkoutperforms the state-of-the-art solutions by more than 15 percent in terms of hit-precision. Moreover, it is expandable to add external geographical context data and works stably with heterogeneous noisy mobility traces.

Social commerce, which is different from traditional e-commerce where people purchase products via initiative searching or recommendations from the platform, transforms a social community into an inclusive place to do business by enabling people to share products with their friends. A user (sharer), can share a link of a product to their social-connected friends (receiver). Once a receiver purchases the product, the sharer can earn commission provided by the platform. To promote sales, the platform can also assist sharers by providing product candidates which are more likely to be purchased during the social sharing. We define this task of generating sharing suggestions as item recommendation for word-of-mouth scenario, and to the best of our knowledge, this is a new task that has never been explored. In this article, we propose aTriM(short forTriad based word-of-Mouth recommendation) model that can capture both the sharer’s influence and the receiver’s interest at the same time, which are two significant factors that determine whether the receiver will buy the product or not. Furthermore, with joint learning on two parts of interaction data to address data sparsity issue, our proposed TriM-Joint further improves the recommendation performance. By conducting experiments, we show that our proposed models achieve the best results compared to state-of-the-art models with significant improvements by at least$7.4\% \sim 14.4\%$respectively.

Social recommendation, which utilizes social relations to enhance recommender systems, has been gaining increasing attention recently with the rapid development of online social networks. Existing social recommendation methods are based on the assumption, so-calledsocial-trust, that users’ preference or decision is influenced by their social-connected friends’ purchase behaviors. However, they assume that the influences of social relationships are always the same, which violates the fact that users are likely to share preference on different products with different friends. More precisely, friends’ behaviors do not necessarily affect a user’s preferences, and the influence is diverse among different items. In this paper, we contribute a new solution, CSR (short forCharacterizedSocialRegularization) model by designing a universal regularization term for modeling variable social influence. This regularization term captures the finely grained similarity of social-connected friends. We further introduce two variants of our model with different optimization manners. Our proposed model can be applied to both explicit and implicit interaction due to its high generality. Extensive experiments on three real-world datasets demonstrate that our CSR can outperform state-of-the-art social recommendation methods. Further experiments show that CSR can improve recommendation performance for those users with sparse social relations or behavioral interactions.

Obtaining crowd flow distribution with recognized human intention is extremely valuable for a series of applications for metropolitan cities. Previous solutions look at spatial correlation and temporal periodicity based on historical crowd flow information to calculate future crowd flow distribution. However, these mechanisms cannot recognize the intention behind crowd flow. We address this problem by leveraging a key insight – people's intention behind their movement is highly correlated with the point-of-interest (POI) distribution of the corresponding regions and adjacent regions. Therefore, we proposeDeepFlowGento model the complicated relationship between crowd flow, POI, check-ins, and time to generate intention-aware crowd flow. Specifically, we solve the conflict between dynamic crowd flow and static POI distribution by fusing the information in both time and POI domains. Besides, we employ a sequence of residual blocks inDeepFlowGento address the challenges of modeling the diverse temporal rhythms and heterogeneous influence of POI. Furthermore, we examine the generated intention-aware crowd flow from two aspects to substantiate the reasonability ofDeepFlowGen. Extensive experiments demonstrate that our model outperforms the state-of-the-art solutions by at most 30 percent in terms of NRMSE of total crowd flow. Moreover, the correlation between the generated intention-aware crowd flow and the check-in distribution across different categories of POIs is as high as 0.90 and 0.80 in Beijing and Shanghai. Combined with extensive case studies, we demonstrate the strong ability of our model in generating intention-aware crowd flow.

As a fundamental component in map service, map matching is of great importance for many trajectory-based applications, e.g., route optimization, traffic scheduling, and fleet management. In practice, Hidden Markov Model and its variants are widely used to provide accurate and efficient map matching service. However, HMM-based methods fail to utilize the knowledge (e.g., the mobility pattern) of enormous trajectory big data, which are useful for intelligent map matching. Furthermore, with many following-up works, they are still easily influenced by the common noisy and sparse records in the reality. In this paper, we revisit the map matching task from the data perspective and propose to utilize the great power of massive data and deep learning to solve these problems. Based on the seq2seq learning framework, we build a trajectory2road model with attention mechanism to map the sparse and noisy trajectory into the accurate road network. Different from previous algorithms, our deep learning based model complete the map matching in the latent space, which provides the high tolerance to the noisy trajectory and also enhances the matching with the knowledge of mobility pattern. Extensive experiments demonstrate that the proposed model outperforms the widely used HMM-based methods by more than 10 percent (absolute accuracy) in various situations especially the noisy and sparse settings.

Internet of Thing (IoT) devices are rapidly becoming an indispensable part of our life with their increasing deployment in many promising areas, including tele-health, smart city, intelligent agriculture. Understanding the mobility of IoT devices is essential to improve quality of service in IoT applications, such as route planning in logistic management, infrastructure deployment, cellular network update and congestion detection in intelligent traffic. Despite its importance, there are not many results pertaining to the mobility of IoT devices. In this article, we aim to answer three research questions: (i) what are the mobility patterns of IoT device? (ii) what are the differences between IoT device and smartphone mobility patterns? (iii) how the IoT device mobility patterns differ among device types and usage scenarios? We present a comprehensive characterization of IoT device mobility patterns from the perspective of cellular data networks, using a 36-days long signal trace, including 1.5 million IoT devices and 0.425 million smartphones, collected from a nation-wide cellular network in China. We first investigate the basic patterns of IoT devices from two perspectives: temporal and spatial characteristics. Our study finds that IoT device mobility exhibits significantly different patterns compared with smartphones in multiple aspects. For instance, IoT devices move more frequently and have larger radius of gyration. Then we explore the essential mobility of IoT devices by utilizing two models that reveal the nature of human mobility, i.e., exploration and preferential return (EPR) model and entropy based predictability model. We find that IoT devices, with few exceptions, behave totally different from human, and we further derive a new formulation to describe their movement. We also find the gap mobility predictability and predictability limit between IoT and human is not as big as people expected.

Group buying, as an emerging form of purchase in social e-commerce websites, such as Pinduoduo1, has recently achieved great success. In this new business model, users, initiator, can launch a group and share products to their social networks, and when there are enough friends, participants, join it, the deal is clinched. Group-buying recommendation for social e-commerce, which recommends an item list when users want to launch a group, plays an important role in the group success ratio and sales. However, designing a personalized recommendation model for group buying is an entirely new problem that is seldom explored. In this work, we take the first step to approach the problem of group-buying recommendation for social e-commerce and develop a GBGCN method (short for Group-Buying Graph Convolutional Network). Considering there are multiple types of behaviors (launch and join) and structured social network data, we first propose to construct directed heterogeneous graphs to represent behavioral data and social networks. We then develop a graph convolutional network model with multi-view embedding propagation, which can extract the complicated high-order graph structure to learn the embeddings. Last, since a failed group-buying implies rich preferences of the initiator and participants, we design a double-pairwise loss function to distill such preference signals. We collect a real-world dataset of group-buying and conduct experiments to evaluate the performance. Empirical results demonstrate that our proposed GBGCN can significantly outperform baseline methods by 2.69%-7.36%. The codes and the dataset are released at https://github.com/Sweetnow/group-buying-recommendation.

Collaborative filtering (CF), as a fundamental approach for recommender systems, is usually built on the latent factor model with learnable parameters to predict users' preferences towards items. However, designing a proper CF model for a given data is not easy, since the properties of datasets are highly diverse. In this paper, motivated by the recent advances in automated machine learning (AutoML), we propose to design a data-specific CF model by AutoML techniques. The key here is a new framework that unifies state-of-the-art (SOTA) CF methods and splits them into disjoint stages of input encoding, embedding function, interaction function, and prediction function. We further develop an easy-to-use, robust, and efficient search strategy, which utilizes random search and a performance predictor for efficient searching within the above framework. In this way, we can combinatorially generalize data-specific CF models, which have not been visited in the literature, from SOTA ones. Extensive experiments on five real-world datasets demonstrate that our method can consistently outperform SOTA ones for various CF tasks. Further experiments verify the rationality of the proposed framework and the efficiency of the search strategy. The searched CF models can also provide insights for exploring more effective methods in the future.

For online life service platforms, such as Meituan, user consumption intention, as the internal driving force of consumption behaviors, plays a significant role in understanding and predicting users' demand and purchase. However, user consumption intention prediction is quite challenging. Different from consumption behaviors, consumption intention is implicit and always not reflected by behavioral data. Moreover, it is affected by both user intrinsic preference and spatio-temporal context. To overcome these challenges, in Meituan, we design a real-world system consisting of two stages, intention detection and prediction. Specifically, at the intention-detection stage, we combine the knowledge of human experts and consumption information to obtain explicit intentions and match consumption with intentions based on user review data. At the intention-prediction stage, to collectively exploit the rich heterogeneous influencing factors, we design a graph neural network-based intention prediction model GRIP, which can capture user intrinsic preference and spatio-temporal context. Extensive offline evaluations demonstrate that our prediction model outperforms the best baseline by 10.26% and 33.28% for two metrics and online A/B tests on millions of users validate the effectiveness of our system.

Deep sparse networks (DSNs), of which the crux is exploring the high-order feature interactions, have become the state-of-the-art on the prediction task with high-sparsity features. However, these models suffer from low computation efficiency, including large model size and slow model inference, which largely limits these models' application value. In this work, we approach this problem with neural architecture search by automatically searching the critical component in DSNs, the feature-interaction layer. We propose a distilled search space to cover the desired architectures with fewer parameters. We then develop a progressive search algorithm for efficient search on the space and well capture the order-priority property in sparse prediction tasks. Experiments on three real-world benchmark datasets show promising results of PROFIT in both accuracy and efficiency. Further studies validate the feasibility of our designed search space and search algorithm.

Sequential recommendation aims to leverage users' historical behaviors to predict their next interaction. Existing works have not yet addressed two main challenges in sequential recommendation. First, user behaviors in their rich historical sequences are often implicit and noisy preference signals, they cannot sufficiently reflect users' actual preferences. In addition, users' dynamic preferences often change rapidly over time, and hence it is difficult to capture user patterns in their historical sequences. In this work, we propose a graph neural network model called SURGE (short forSeqUential Recommendation with Graph neural nEtworks) to address these two issues. Specifically, SURGE integrates different types of preferences in long-term user behaviors into clusters in the graph by re-constructing loose item sequences into tight item-item interest graphs based on metric learning. This helps explicitly distinguish users' core interests, by forming dense clusters in the interest graph. Then, we perform cluster-aware and query-aware graph convolutional propagation and graph pooling on the constructed graph. It dynamically fuses and extracts users' current activated core interests from noisy user behavior sequences. We conduct extensive experiments on both public and proprietary industrial datasets. Experimental results demonstrate significant performance gains of our proposed method compared to state-of-the-art methods. Further studies on sequence length confirm that our method can model long behavioral sequences effectively and efficiently.

The phenomenal success of the newly-emerging social e-commerce has demonstrated that utilizing social relations is becoming a promising approach to promote e-commerce platforms. In this new scenario, one of the most important problems is to predict the value of a community formed by closely connected users in social networks due to its tremendous business value. However, few works have addressed this problem because of 1) its novel setting and 2) its challenging nature that the structure of a community has complex effects on its value. To bridge this gap, we develop a Multi-scale Structure-aware Community value prediction network (MSC) that jointly models the structural information of different scales, including peer relations, community structure, and inter-community connections, to predict the value of given communities. Specifically, we first proposed a Masked Edge Learning Graph Convolutional Network (MEL-GCN) based on a novel masked propagation mechanism to model peer influence. Then, we design a Pair-wise Community Pooling (PCPool) module to capture critical community structures. Finally, we model the inter-community connections by distinguishing intra-community edges from inter-community edges and employing a Multi-aggregator Framework (MAF). Extensive experiments on a large-scale real-world social e-commerce dataset demonstrate our method’s superior performance over state-of-the-art baselines, with a relative performance gain of 11.40%, 10.01%, and 10.97% in MAE, RMSE, and NRMSE, respectively. Further ablation study shows the effectiveness of our designed components. Our code and dataset are available1.

These years much effort has been devoted to improving the accuracy or relevance of the recommendation system. Diversity, a crucial factor which measures the dissimilarity among the recommended items, received rather little scrutiny. Directly related to user satisfaction, diversification is usually taken into consideration after generating the candidate items. However, this decoupled design of diversification and candidate generation makes the whole system suboptimal. In this paper, we aim at pushing the diversification to the upstream candidate generation stage, with the help of Graph Convolutional Networks (GCN). Although GCN based recommendation algorithms have shown great power in modeling complex collaborative filtering effect to improve the accuracy of recommendation, how diversity changes is ignored in those advanced works. We propose to perform rebalanced neighbor discovering, category-boosted negative sampling and adversarial learning on top of GCN. We conduct extensive experiments on real-world datasets. Experimental results verify the effectiveness of our proposed method on diversification. Further ablation studies validate that our proposed method significantly alleviates the accuracy-diversity dilemma.

Recommendation models are usually trained on observational interaction data. However, observational interaction data could result from users’ conformity towards popular items, which entangles users’ real interest. Existing methods tracks this problem as eliminating popularity bias, e.g., by re-weighting training samples or leveraging a small fraction of unbiased data. However, the variety of user conformity is ignored by these approaches, and different causes of an interaction are bundled together as unified representations, hence robustness and interpretability are not guaranteed when underlying causes are changing. In this paper, we present DICE, a general framework that learns representations where interest and conformity are structurally disentangled, and various backbone recommendation models could be smoothly integrated. We assign users and items with separate embeddings for interest and conformity, and make each embedding capture only one cause by training with cause-specific data which is obtained according to the colliding effect of causal inference. Our proposed methodology outperforms state-of-the-art baselines with remarkable improvements on two real-world datasets on top of various backbone models. We further demonstrate that the learned embeddings successfully capture the desired causes, and show that DICE guarantees the robustness and interpretability of recommendation.

Driven by the soaring traffic demand and the growing diversity of mobile services, wireless networks are evolving to be increasingly dense and heterogeneous. Accordingly, in such large-scale and complicated wireless networks, optimal controlling is reaching unprecedented levels of complexity while its traditional solutions of handcrafted offline algorithms become inefficient due to high complexity, low robustness, and high overhead. Therefore, reinforcement learning (RL), which enables network entities to learn from their actions and consequences in the interactive network environment, attracts significant attention. In this article, we comprehensively review the applications of RL in wireless networks from a layering perspective. First, we present an overview of the principle, fundamentals, and several advanced models of RL. Then, we review the up-to-date applications of RL in various functionality blocks of different network layers, ranging from the low-level physical layer to the high-level application layer. Finally, we outline a broad spectrum of challenges, open issues, and future research directions of RL-empowered wireless networks.

Privacy leakage of Internet of Things (IoT) has become a great challenge with the popularity of IoT services through mobile networks, such as smart homes, wearables, and healthcare. While previous work summarized general structures to analyze IoT privacy and provide case studies of specific devices or scenarios, it is still challenging to conduct a comprehensive and systematic quantification study of large-scale IoT privacy leakage in real world. To combine systematic analyses with real-world measurements, we provide a method to quantify IoT privacy leakage on a large-scale mobile network traffic data set containing 47651 IoT devices. We generate privacy fingerprints and attribute them to a privacy quantification framework. The framework is constructed based on the semantics of multiple privacy sensitive markers selected from the traffic along with the involved network entity types in IoT (i.e., user, device, and platform), and the fingerprints are generated from sensitive information extracted in the traffic via their markers. Our quantification shows that IoT users, devices, and platforms have considerable risks, respectively. Moreover, IoT devices have a larger scale of privacy leakage than users and platforms, and they perform different daily patterns on privacy leakage following their working conditions. In addition, we present three case studies on the leakage of location information, application calling, and voice service, which illustrate that a third party can profile a network entity in both cyberspace and physical space.

Accurate human mobility prediction is important for many applications in wireless networks, including intelligent content caching and prefetching, network optimization, etc. However, modeling mobility patterns has been a challenging problem due to the complicated human mobility patterns influenced by the long-term correlation with historical trajectories and context information, and the long time interval between consecutive mobility records. In this paper, we integrate the novel attention technique into the Markov model to predict future locations. This model allows us to consider the time context of users' mobility behavior, which overcomes the disadvantage of the traditional Markov model in modeling the periodicity of trajectories. We conducted extensive evaluations using two different mobility datasets, which involve over 20,000 users. Our evaluations show that our proposed solution outperforms the state-of-the-art algorithms by over 6.6% on average. In addition, compared with the method based on deep recurrent neural networks achieving the same performance, our proposed model runs significantly faster, i.e., reducing the computation time by over 170 times, demonstrating the effeteness of our proposed model.

Video accounts for a large proportion of traffic on the Internet. Understanding its geographical viewing patterns is extremely valuable for the design of Internet ecosystems for content delivery, recommendation and ads. While previous works have addressed this problem at coarse-grain scales (e.g., national), the urban-scale geographical patterns of video access have never been revealed. To this end, this article aims to investigate the problem that whether there exists distinct viewing patterns among the neighborhoods of a large-scale city. To achieve this, we need to address several challenges including unknown of patterns profiles, complicate urban neighborhoods, and comprehensive viewing features. The contributions of this article include two aspects. First, we design a framework to automatically identify geographical video viewing patterns in urban neighborhoods. Second, by using a dataset of two months real video requests in Shanghai collected from one major ISP of China, we make a rigorous analysis of video viewing patterns in Shanghai. Our study reveals the following important observations. First, there exists four prevalent and distinct patterns of video access behavior in urban neighborhoods, which are corresponding to four different geographical contexts: downtown residential, office, suburb residential and hybrid regions. Second, there exists significant features that distinguish different patterns, e.g., the probabilities of viewing TV plays at midnight, and viewing cartoons at weekends can distinguish the two viewing patterns corresponding to downtown and suburb regions.

Understanding the linkability of online user identifiers (IDs) is critical to both service providers (for business intelligence) and individual users (for assessing privacy risks). Existing methods are designed to match IDs across two services but face key challenges of matching multiple services in practice, particularly when users have multiple IDs per service. In this article, we propose a novel system to link IDs across multiple services by exploring the spatial-temporal features of user activities, of which the core idea is that the same user's online IDs are more likely to repeatedly appear at the same location. Specifically, we first utilize a contact graph to capture the “co-location” of all IDs across multiple services. Based on this graph, we propose a set-wise matching algorithm to discover candidate ID sets and use Bayesian inference to generate confidence scores for candidate ranking, which is proved to be optimal. We evaluate our system using two real-world ground-truth datasets from an Internet service provider (4 services, 815K IDs) and Twitter-Foursquare (2 services, 770 IDs). Extensive results show that our system significantly outperforms the state-of-the-art algorithms in accuracy (AUC is higher by 0.1–0.2), and it is highly robust against data quality, matching order, and number of services.

Both app developers and service providers have strong motivations to understandwhenandwherecertain apps are used by users. However, it has been a challenging problem due to the highly skewed and noisy app usage data. Moreover, apps are regarded as independent items in existing studies, which fail to capture the hidden semantics in app usage traces. In this article, we propose App2Vec, a powerful representation learning model to learn the semantic embedding of apps with the consideration of spatio-temporal context. Based on the obtained semantic embeddings, we develop a probabilistic model based on the Bayesian mixture model and Dirichlet process to capturewhen,where, andwhatsemantics of apps are used to predict the future usage. We evaluate our model using two different app usage datasets, which involve over 1.7 million users and 2,000+ apps. Evaluation results show that our proposed App2Vec algorithm outperforms the state-of-the-art algorithms in app usage prediction with a performance gap of over 17.0%.

Crowd flow prediction is an essential task benefiting a wide range of applications for the transportation system and public safety. However, it is a challenging problem due to the complex spatio-temporal dependence and the complicated impact of urban structure on the crowd flow patterns. In this article, we propose a novel framework, 3- D imensional G raph C onvolution N etwork (3DGCN), to predict citywide crowd flow. We first model it as a dynamic spatio-temporal graph prediction problem, where each node represents a region with time-varying flows, and each edge represents the origin–destination (OD) flow between its corresponding regions. As such, OD flows among regions are treated as a proxy for the spatial interactions among regions. To tackle the complex spatio-temporal dependence, our proposed 3DGCN can model the correlation among graph spatial and temporal neighbors simultaneously. To learn and incorporate urban structures in crowd flow prediction, we design the GCN aggregator to be learned from both crowd flow prediction and region function inference at the same time. Extensive experiments with real-world datasets in two cities demonstrate that our model outperforms state-of-the-art baselines by 9.6%∼19.5% for the next-time-interval prediction.

Bayesian Personalized Ranking (BPR) is a representative pairwise learning method for optimizing recommendation models. It is widely known that the performance of BPR depends largely on the quality of negative sampler. In this paper, we make two contributions with respect to BPR. First, we find that sampling negative items from the whole space is unnecessary and may even degrade the performance. Second, focusing on the purchase feedback of E-commerce, we propose a negative sampler for BPR by leveraging the additional view data. In our proposed sampler, users' viewed interactions are considered as an intermediate feedback between the purchased and unobserved interactions. We jointly learn the pairwise rankings of user preference among these three types of interactions and design a user-oriented weighting strategy during learning process, which is more effective and flexible. Compared to the vanilla BPR that applies a uniform sampler on all candidates, our view-enhanced sampler enhances BPR with a relative improvement over 36.64 and 16.40 percent on Beibei and Tmall datasets, respectively. Empirical studies demonstrate the importance of considering users' additional feedback when modeling their preference on different items, which can effectively improve the quality of sampled negative items towards learning a better personalized ranking function. Our implementation is available at https://github.com/dingjingtao/NegativeSamplerBPR.

Most existing recommender systems leverage user behavior data of one type only, such as the purchase behavior in E-commerce that is directly related to the business Key Performance Indicator (KPI) of conversion rate. Besides the key behavioral data, we argue that other forms of user behaviors also provide valuable signal, such as views, clicks, adding a product to shopping carts and so on. They should be taken into account properly to provide quality recommendation for users. In this work, we contribute a new solution named short for Neural Multi-Task Recommendation (NMTR) for learning recommender systems from user multi-behavior data. We develop a neural network model to capture the complicated and multi-type interactions between users and items. In particular, our model accounts for the cascading relationship among different types of behaviors (e.g., a user must click on a product before purchasing it). To fully exploit the signal in the data of multiple types of behaviors, we perform a joint optimization based on the multi-task learning framework, where the optimization on a behavior is treated as a task. Extensive experiments on two real-world datasets demonstrate that NMTR significantly outperforms state-of-the-art recommender systems that are designed to learn from both single-behavior data and multi-behavior data. Further analysis shows that modeling multiple behaviors is particularly useful for providing recommendation for sparse users that have very few interactions.

With the ever-increasing urbanization process, systematically modeling people's activities in the urban space is being recognized as a crucial socioeconomic task. It is extremely challenging due to the lack of reliable data and suitable methods, yet the emergence of population-scale urban mobility data sheds new light on it. However, recent works on discovering activity patterns from urban mobility data are still limited in terms of concisely and specifically modeling the temporal dynamics of people's urban activities. To bridge the gap, we present a State-sharing Hidden Markov Model (SSHMM), a novel time-series modeling method that uncovers urban dynamics with massive urban mobility data. SSHMM models the urban dynamics from two aspects. First, it extracts the urban states from the whole city, which captures the volume of population flows as well as the frequency of each type of Point of Interests (PoIs) visited. Second, it characterizes the urban dynamics of each urban region as the state transition on the shared-states, which reveals distinct daily rhythms of urban activities. We evaluate our method via large-scale real-life mobility dataset. The results demonstrate that SSHMM learns semantics-rich urban dynamics, which are highly correlated with the functions of the region. Besides, it recovers the urban dynamics in different time slots with RMSE of 0.0793 when only learn limited states for the whole city, which outperforms the general HMM by 54.2 percent.

As online video service continues to grow in popularity, video content providers compete hard for more eyeball engagement. Some users visit multiple video sites to enjoy videos of their interest while some visit exclusively one site. However, due to the isolation of data, mining and exploiting user behaviors in multiple video websites remain unexplored so far. In this work, we try to model user preferences in six popular video websites with user viewing records obtained from a large ISP in China. The empirical study shows that users exhibit both consistent cross-site interests as well as site-specific interests. To represent this dichotomous pattern of user preferences, we propose a generative model of Multi-site Probabilistic Factorization (MPF) to capture both the cross-site as well as site-specific preferences. Besides, we discuss the design principle of our model by analyzing the sources of the observed site-specific user preferences, namely, site peculiarity and data sparsity. Through conducting extensive recommendation validation, we show that our MPF model achieves the best results compared to several other state-of-the-art factorization models with significant improvements of F-measure by 12.96, 8.24 and 6.88 percent, respectively. Our findings provide insights on the value of integrating user data from multiple sites, which stimulates collaboration between video service providers.

Human mobility trajectories are increasingly collected by ISPs to assist academic research and commercial applications. Meanwhile, there is a growing concern that individual trajectories can be de-anonymized when the data is shared, using information from external sources (e.g., online social networks). To understand this risk, prior works either estimate the theoretical privacy bound or simulate de-anonymization attacks on synthetically created datasets. However, it is not clear how well the theoretical estimations are preserved in practice. In this article, we collected a large-scale ground-truth trajectory dataset from 2,161,500 users of a cellular network, and two matched external trajectory datasets from a large social network (56,683 users) and a check-in/review service (45,790 users) on the same user population. The two sets of large ground-truth data provide a rare opportunity to extensively evaluate a variety of de-anonymization algorithms (nine in total). We find that their performance in the real-world dataset is far from the theoretical bound. Further analysis shows that most algorithms have under-estimated the impact of spatio-temporal mismatches between the data from different sources, and the high sparsity of user generated data also contributes to the under-performance. Based on these insights, we propose four new algorithms that are specially designed to tolerate spatial or temporal mismatches (or both) and model location contexts and time contexts. Extensive evaluations show that our algorithms achieve more than 17 percent performance gain over the best existing algorithms, confirming our insights. Further, we propose two new location-privacy preserving mechanisms utilizing the spatio-temporal mismatches to better protect users' privacy against the de-anonymization attack. Evaluation results show that our proposed mechanisms can reduce the performance of de-anonymization attacks by over 8.0 percent, demonstrating the effectiveness of our insights.

In the modern information society, analysis of human mobility becomes increasingly essential in various areas such as city planning and resource management. With users' historical trajectories, the inherent patterns of their movements can be extracted and utilized to accurately predict the future movements. Plenty of previous work adopted traditional Markov model, which suffers when the trajectory becomes sparse or it shows distinct mobility patterns in different time of day. In this paper, based on an app-collected dataset of 100,000 individuals' actively uploaded location information, we comprehensively analyze the mobility and predictability of each user. To approach the theoretical predictability and overcome the shortcomings of traditional Markov model, we propose a time-variant Markov model based on Gibbs sampling for mobility prediction. Specifically, we model human mobility as several interconnected Markov chains, each chain corresponds to a movement pattern of a period of time. Then, we adopt Gibbs sampling method to simultaneously recover the missing part of trajectories and train the Markov chains, in order to solve the unevenly distribution and the high missing rate. Results show that our prediction algorithm can achieve 11.2 percent higher prediction accuracy than the benchmark method, especially on sparse trajectories. In addition, we discover a high correlation between prediction accuracy and predictability, with correlation coefficient reaching 0.81. Finally, we investigate various factors including spatial and temporal resolution, orders of Markov models, and radius of gyration, in order to further explore the predictability under different circumstances.

Today’s video streaming market is crowded with various content providers (CPs). For individual CPs, understanding user behavior, in particular how users migrate among different CPs, is crucial for improving users’ on-site experience and the CP’s chance of success. In this article, we take a data-driven approach to analyze and model user migration behavior in video streaming, i.e., users switching content provider during active sessions. Based on a large ISP dataset over two months (6 major content providers, 3.8 million users, and 315 million video requests), we study common migration patterns and reasons of migration. We find that migratory behavior is prevalent: 66% of users switch CPs with an average switching frequency of 13%. In addition, migration behaviors are highly diverse: regardless large or small CPs, they all have dedicated groups of users who like to switch to them for certain types of videos. Regarding reasons of migration, we find CP service quality rarely causes migration, while a few popular videos play a bigger role. Nearly 60% of cross-site migrations are landed to 0.14% top videos. Finally, we validate our findings by building an accurate regression model to predict user migration frequency as well as user survey, and discuss the implications of our results to CPs.

With the rapid growth of mobile networks and smart devices, a large number of people prefer to visiting video services via mobile devices. This generates massive data traffic, and thus increases the load of cellular networks. To deal with it, we need to investigate the usage patterns in the video consumption. In this article, we take a data-driven analysis of mobile video services by classifying them into three major types: traditional video portals, user-generated video services and personalized livestreaming. We collect a large dataset of 25,937,758 logs from 455 thousand users, and we find that 1) for the same kind of video services, users exhibit high loyalty; 2) in consecutive days, the traffic peaks have differences among different service types; 3) more video traffic is generated from personalized livestreaming services, and it keeps increasing after midnight at weekdays in the downtown; 4) traffic consumption of user-generated service exhibits great differences under different functional regions; 5) individual users are prone to click within the same service type but possible different time gaps during the consecutive views. Lastly, we utilize these findings to discuss the potential applications in the improvements of cellular networks and video services.

Online ad targeting can be formulated as a problem of learning the relevance ranking among possible audiences for a given ad. It has to deal with the massive number of negative,i.e., non-interacted, instances in impression data due to the nature of this service, and thus suffers from data imbalance problem. In this work, we tackle this problem by improving the quality of negative instances used in training the targeting model. We propose to enhance the generalization capability by introducing unobserved data as possible negative instances, and extract more reliable negative instances from the observed negatives in impression data. However, this idea is non-trivial to implement because of the limited learning signal and existing noise signal. To this end, we design a novel RNIG method (short for Representative Negative Instance Generator) to leverage feature matching technique. It aims to generate reliable negative instances that are similar to the observed negatives and further improves the representativeness of generated negatives by matching the most important feature. Extensive experiments on the real-world ad targeting dataset show that our RNIG model has achieved a relative improvement of more than 5%.

In recent years, much research effort on recommendation has been devoted to mining user behaviors, i.e., collaborative filtering, along with the general information which describes users or items, e.g., textual attributes, categorical demographics, product images, and so on. Price, an important factor in marketing - which determines whether a user will make the final purchase decision on an item - surprisingly, has received relatively little scrutiny. In this work, we aim at developing an effective method to predict user purchase intention with the focus on the price factor in recommender systems. The main difficulties are twofold: 1) the preference and sensitivity of a user on item price are unknown, which are only implicitly reflected in the items that the user has purchased, and 2) how the item price affects a user's intention depends largely on the product category, that is, the perception and affordability of a user on item price could vary significantly across categories. Towards the first difficulty, we propose to model the transitive relationship between user-to-item and item-to-price, taking the inspiration from the recently developed Graph Convolution Networks (GCN). The key idea is to propagate the influence of price on users with items as the bridge, so as to make the learned user representations be price-aware. For the second difficulty, we further integrate item categories into the propagation progress and model the possible pairwise interactions for predicting user-item interactions. We conduct extensive experiments on two real-world datasets, demonstrating the effectiveness of our GCN-based method in learning the price-aware preference of users. Further analysis reveals that modeling the price awareness is particularly useful for predicting user preference on items of unexplored categories.

Negative sampling approaches are prevalent in implicit collaborative filtering for obtaining negative labels from massive unlabeled data. As two major concerns in negative sampling, efficiency and effectiveness are still not fully achieved by recent works that use complicate structures and overlook risk of false negative instances. In this paper, we first provide a novel understanding of negative instances by empirically observing that only a few instances are potentially important for model learning, and false negatives tend to have stable predictions over many training iterations. Above findings motivate us to simplify the model by sampling from designed memory that only stores a few important candidates and, more importantly, tackle the untouched false negative problem by favouring high-variance samples stored in memory, which achieves efficient sampling of true negatives with high-quality. Empirical results on two synthetic datasets and three real-world datasets demonstrate both robustness and superiorities of our negative sampling method. The implementation is available at https://github.com/dingjingtao/SRNS.

Bundle recommendation aims to recommend a bundle of items for a user to consume as a whole. Existing solutions integrate user-item interaction modeling into bundle recommendation by sharing model parameters or learning in a multi-task manner, which cannot explicitly model the affiliation between items and bundles, and fail to explore the decision-making when a user chooses bundles. In this work, we propose a graph neural network model named BGCN (short forBundle Graph Convolutional Network ) for bundle recommendation. BGCN unifies user-item interaction, user-bundle interaction and bundle-item affiliation into a heterogeneous graph. With item nodes as the bridge, graph convolutional propagation between user and bundle nodes makes the learned representations capture the item level semantics. Through training based on hard-negative sampler, the user's fine-grained preferences for similar bundles are further distinguished. Empirical results on two real-world datasets demonstrate the strong performance gains of BGCN, which outperforms the state-of-the-art baselines by 10.77% to 23.18%.

Most existing recommender systems leverage users' complete original behavioral logs, which are collected from mobile devices and stored by the service provider and further fed into recommendation models. This may lead to a high risk of privacy leakage since the recommendation service provider may be trustless. Despite many research efforts on privacy-aware recommendation, the problem of building an effective recommender system completely preserving user privacy is still open.

Traditional recommendation models that usually utilize only one type of user-item interaction are faced with serious data sparsity or cold start issues. Multi-behavior recommendation taking use of multiple types of user-item interactions, such as clicks and favorites, can serve as an effective solution. Early efforts towards multi-behavior recommendation fail to capture behaviors' different influence strength on target behavior. They also ignore behaviors' semantics which is implied in multi-behavior data. Both of these two limitations make the data not fully exploited for improving the recommendation performance on the target behavior.

Smartphone mobile application (App) usage prediction, i.e., which Apps will be used next, is beneficial for user experience improvement. Through an in-depth analysis on a real-world dataset, we find that App usage is highly spatio-temporally correlated and personalized. Given the ability to model complex spatio-temporal contexts, we aim to apply deep learning to achieve high prediction accuracy. However, the personalization yields a problem: training one network for each individual suffers from data scarcity, yet training one deep neural network for all users often fails to uncover user preference. In this article, we propose a novel App usage prediction framework, named DeepApp , to achieve context-aware prediction via multi-task learning. To tackle the challenge of data scarcity, we train one general network for multiple users to share common patterns. To better utilize the spatio-temporal contexts, we supplement a location prediction task in the multi-task learning framework to learn spatio-temporal relations. As for the personalization, we add a user identification task to capture user preference. We evaluate DeepApp on the large-scale dataset by extensive experiments. Results demonstrate that DeepApp outperforms the start-of-the-art baseline by 6.44%.

With the rapid development of mobile applications, mobile edge computing (MEC), which provides various cloud resources (e.g., computation and storage resources) closer to mobile and IoT devices for computation offloading, has been broadly studied in both academia and industry. However, due to the limited coverage of static edge servers, the traditional MEC technology performs badly in a nowadays environment. To adapt the diverse demands, in this paper, we propose a novel mobile edge mechanism with a vehicle-mounted edge (V-edge) deployed. Aiming at maximizing completed tasks of V-edge with sensitive deadline, the problem of joint path planning and resource allocation is formulated into a mixed integer nonlinear program (MINLP). By utilizing the piecewise linear approximation and linear relaxation, we transform the MINLP into a mixed integer linear program (MILP). To obtain the nearoptimal solution, we further develop a gap-adjusted branch & bound algorithm, also called GA-B&B algorithm. Moreover, we propose a low-complexity L-step lookahead branch scheme (referred to as L-step scheme) for efficient scheduling in large-scale scenarios. Extensive evaluations demonstrate the superior performance of the proposed scheme compared with the traditional static edge mechanism. Furthermore, the proposed L-step scheme achieves close performance to the near-optimal solution, and significantly improves the task completion percentage of state-of-the-art schemes by over 10 percent.

The diversity of personal interest and preference of mobile users results in a wide spectrum of mobile app usage, and it is important to predict such app preference in order to provide personalized services. However, currently available individual app usage data is very limited, which does not cover a large user base. In this paper, we demonstrate that it is possible to make personalized app usage estimation by learning user's app preference from the social media, i.e., public accessible tweets, which can also reflect user's interest and make up for the sparsity of app usage data. By proposing a novel generative model named IMCF+ to transfer user interest from rich tweet information to sparse app usage, we achieve personalized app recommendations via learning the interest's correlation between apps and tweets. Based on a real-world app usage and tweet dataset over a large population, we evaluate the performance of IMCF+ with a variety of scenarios and parameters. With only 10 percent training data, our IMCF+ approach achieves 82.5 percent hitrate in predicting the top ten apps. Moreover, IMCF+ outperforms the other six state-of-the-art algorithms by 4.7 percent and 10 percent in high sparsity case and user cold-start scenario, indicating the effectiveness of our method. All these results demonstrate that our technique can reliably learn user's interest from tweets to help solve the personalized app recommendation problem. Our study is the first step forward for transferring user's interest learned from social media to app preference, which paves the way for providing higher-quality personalized app recommendation and services for mobile users.

It is well-known that online services resort to various cookies to track users through users' online service identifiers (IDs) - in other words, when users access online services, various “fingerprints” are left behind in the cyberspace. As they roam around in the physical world while accessing online services via mobile devices, users also leave a series of “footprints” - i.e., hints about their physical locations - in the physical world. This poses a potent new threat to user privacy: one can potentially correlate the “fingerprints” left by the users in the cyberspace with “footprints” left in the physical world to infer and reveal leakage of user physical world privacy, such as frequent user locations or mobility trajectories in the physical world - we refer to this problem as user physical world privacy leakage via user cyberspace privacy leakage. In this paper we address the following fundamental question: what kind - and how much - of user physical world privacy might be leaked if we could get hold of such diverse network datasets even without any physical location information. In order to conduct an in-depth investigation of these questions, we utilize the network data collected via a DPI system at the routers within one of the largest Internet operator in Shanghai, China over a duration of one month. We decompose the fundamental question into the three problems: i) linkage of various online user IDs belonging to the same person via mobility pattern mining; ii) physical location classification via aggregate user mobility patterns over time; and iii) tracking user physical mobility. By developing novel and effective methods for solving each of these problems, we demonstrate that the question of user physical world privacy leakage via user cyberspace privacy leakage is not hypothetical, but indeed poses a real potent threat to user privacy.

Most existing recommender systems leverage the primary feedback only, despite the fact that users also generate a large amount of auxiliary feedback. These feedback usually indicate different user preferences when comparing to the primary feedback directly used to optimize the system performance. For example, in E-commerce sites, view data is easily accessible, which provides a valuable yet weaker signal than the primary feedback of purchase. In this work, we improve implicit feedback-based recommender systems (dubbed Implicit Recommender Systems ) by integrating auxiliary view data into matrix factorization (MF). To exploit different preference levels, we propose both pointwise and pairwise models in terms of how to leverage users’ viewing behaviors. The latter model learns the pairwise ranking relations among purchased, viewed, and non-viewed interactions, being more effective and flexible than the former pointwise MF method. However, such a pairwise formulation poses a computational efficiency problem in learning the model. To address this problem, we design a new learning algorithm based on the element-wise Alternating Least Squares (eALS) learner. Notably, our designed algorithm can efficiently learn model parameters from the whole user-item matrix (including all missing data), with a rather low time complexity that is dependent on the observed data only. Extensive experiments on two real-world datasets demonstrate that our method outperforms several state-of-the-art MF methods by 6.43%∼ 6.75%. Our implementation is available at https://github.com/dingjingtao/Auxiliary_enhanced_ALS.

Because of severe network congestion experienced during peak hours in the urban area, dynamic time-dependent pricing has been proposed by some mobile operators to shift users' data usage from peak hours to off-peak time slots. We look at the performance of time-dependent pricing on a large scale cellular network comprising ten thousand base stations. Our investigation reveals two important observations. First, time-dependent pricing performs well in reducing the peak-average ratio of the overall traffic of the network. However, the single price used by the network does not achieve good performance when we look at base stations in specific regions, such as office regions. Second, we observe that location is another important factor that affects the traffic profile of a base station. Therefore, location information should be considered for designing a pricing strategy as well. We propose a framework that combines both spatial and temporal traffic patterns for data pricing. Our simulation on ten thousand base stations suggests that our proposed scheme is able to achieve an average of 16 percent smaller peak-to-average ratio. With over 15 percent smaller peak-to-average ratio of more than half of base stations in office regions, the performance is 2× better than that achieved by the state of the art time-dependent data pricing systems.

Crowd flow prediction is of great importance in a wide range of applications from urban planning, traffic control to public safety. It aims to predict the inflow (the traffic of crowds entering a region in a given time interval) and outflow (the traffic of crowds leaving a region for other places) of each region in the city with knowing the historical flow data. In this paper, we propose DeepSTN+, a deep learning-based convolutional model, to predict crowd flows in the metropolis. First, DeepSTN+ employs the ConvPlus structure to model the longrange spatial dependence among crowd flows in different regions. Further, PoI distributions and time factor are combined to express the effect of location attributes to introduce prior knowledge of the crowd movements. Finally, we propose an effective fusion mechanism to stabilize the training process, which further improves the performance. Extensive experimental results based on two real-life datasets demonstrate the superiority of our model, i.e., DeepSTN+ reduces the error of the crowd flow prediction by approximately 8%∼13% compared with the state-of-the-art baselines.

Map matching is important in many trajectory based applications like route optimization and traffic schedule, etc. As the widely used methods, Hidden Markov Model and its variants are well studied to provide accurate and efficient map matching service. However, HMM based methods fail to utilize the value of enormous trajectory big data, which are useful for the map matching task. Furthermore, with many following-up works, they are still easily influenced by the noisy records, which are very common in the real system. To solve these problems, we revisit the map matching task from the data perspective, and propose to utilize the great power of data to help solve these problems. We build a deep learning based model to utilize all the trajectory data for joint training and knowledge sharing. With the help of embedding techniques and sequence learning model with attention enhancement, our system does the map matching in the latent space, which is tolerant to the noise in the physical space. Extensive experiments demonstrate that our model outperforms the widely used HMM based methods more than 10% (absolute accuracy) and works robustly in the noisy settings in the meantime.

Most existing recommender systems leverage user behavior data of one type, such as the purchase behavior data in E-commerce. We argue that other types of user behavior data also provide valuable signal, such as views, clicks, and so on. In this work, we contribute a new solution named NMTR (short for Neural Multi-Task Recommendation) for learning recommender systems from user multi-behavior data. In particular, our model accounts for the cascading relationship among different types of behaviors (e.g., a user must click on a product before purchasing it). We perform a joint optimization based on the multi-task learning framework, where the optimization on a behavior is treated as a task. Extensive experiments on the real-world dataset demonstrate that NMTR significantly outperforms state-of-the-art recommender systems that are designed to learn from both single-behavior data and multi-behavior data.

In implicit feedback-based recommender systems, user exposure data, which record whether or not a recommended item has been interacted by a user, provide an important clue on selecting negative training samples. In this work, we improve the negative sampler by integrating the exposure data. We propose to generate high-quality negative instances by adversarial training to favour the difficult instances, and by optimizing additional objective to favour the real negatives in exposure data. However, this idea is non-trivial to implement since the distribution of exposure data is latent and the item space is discrete. To this end, we design a novel RNS method (short for Reinforced Negative Sampler) that generates exposure-alike negative instances through feature matching technique instead of directly choosing from exposure data. Optimized under the reinforcement learning framework, RNS is able to integrate user preference signals in exposure data and hard negatives. Extensive experiments on two real-world datasets demonstrate the effectiveness and rationality of our RNS method. Our implementation is available at: https://github. com/dingjingtao/ReinforceNS.

Existing web video systems recommend videos according to users' viewing history from its own website. However, since many users watch videos in multiple websites, this approach fails to capture these users' interests across sites. In this paper, we investigate the user viewing behavior in multiple sites based on a large scale real dataset. We find that user interests are comprised of cross-site consistent part and site-specific part with different degrees of the importance. Existing linear matrix factorization recommendation model has limitation in modeling such complicated interactions. Thus, we propose a model of Deep Attentive Probabilistic Factorization (DeepAPF) to exploit deep learning method to approximate such complex user-video interaction. DeepAPF captures both cross-site common interests and site-specific interests with non-uniform importance weights learned by the attentional network. Extensive experiments show that our proposed model outperforms by 17.62%, 7.9% and 8.1% with the comparison of three state-of-the-art baselines. Our study provides insight to integrate user viewing records from multiple sites via the trusted third party, which gains mutual benefits in video recommendation.

As a comprehensive information carrier, the short video is gaining increasing attention for a user to spread information, read the news and conduct interpersonal communication. Consequently, short video recommendation problem has been a hot spot in the field of the recommender system. However, current short video recommendation algorithms have to tackle with data sparsity and cold start problem, which is caused by the small amounts of data that the recommender system has accumulated and massive video data while limited users' access.Aiming at the problem of data sparsity and cold start, the paper proposes a short video recommendation algorithm Social Weak-tie Bayesian Personalized Ranking (SWTBPR). Social weak-tie refers to the following relation in online social network, which means they are not real-world friends, somehow it can reflect users' preference. Experimental results demonstrate that SWTBPR outperforms other existing video recommendation algorithms and solves the data sparsity and cold start problem with a real-world dataset collected from Sina Weibo.

Hidden Markov Model (HMM) is a powerful tool that has been widely adopted in sequence modeling tasks, such as mobility analysis, healthcare informatics, and online recommendation. However, using HMM for modeling personalized sequences remains a challenging problem: training a unified HMM with all the sequences often fails to uncover interesting personalized patterns; yet training one HMM for each individual inevitably suffers from data scarcity. We address this challenge by proposing a state-sharing sparse hidden Markov model (S3HMM) that can uncover personalized sequential patterns without suffering from data scarcity. This is achieved by two design principles: (1) all the HMMs in the ensemble share the same set of latent states; and (2) each HMM has its own transition matrix to model the personalized transitions. The result optimization problem for S3HMM becomes nontrivial, because of its two-layer hidden state design and the non-convexity in parameter estimation. We design a new Expectation-Maximization algorithm based, which treats the difference of convex programming as a sub-solver to optimize the non-convex function in the M-step with convergence guarantee. Our experimental results show that, S3HMM can successfully uncover personalized sequential patterns in various applications and outperforms baselines significantly in downstream prediction tasks.

Online services are playing critical roles in almost all aspects of users' life. Users usually have multiple online identities (IDs) in different online services. In order to fuse the separated user data in multiple services for better business intelligence, it is critical for service providers to link online IDs belonging to the same user. On the other hand, the popularity of mobile networks and GPS-equipped smart devices have provided a generic way to link IDs, i.e., utilizing the mobility traces of IDs. However, linking IDs based on their mobility traces has been a challenging problem due to the highly heterogeneous, incomplete and noisy mobility data across services.

Web systems that provide the same functionality usually share a certain amount of items. This makes it possible to combine data from different websites to improve recommendation quality, known as the cross-domain recommendation task. Despite many research efforts on this task, the main drawback is that they largely assume the data of different systems can be fully shared. Such an assumption is unrealistic - different systems are typically operated by different companies, and it may violate business privacy policy to directly share user behavior data since it is highly sensitive.

Modeling people's activities in the urban space is a crucial socio-economic task but extremely challenging due to the deficiency of suitable methods. To model the temporal dynamics of human activities concisely and specifically, we present State-sharing Hidden Markov Model (SSHMM). First, it extracts the urban states from the whole city, which captures the volume of population flows as well as the frequency of each type of Point of Interests (PoIs) visited. Second, it characterizes the urban dynamics of each urban region as the state transition on the shared-states, which reveals distinct daily rhythms of urban activities. We evaluate our method via a large-scale real-life mobility dataset and results demonstrate that SSHMM learns semantics-rich urban dynamics, which are highly correlated with the functions of the region. Besides, it recovers the urban dynamics in different time slots with an error of 0.0793, which outperforms the general HMM by 54.2%.

Compensating for the considerable propagation loss, millimetre‐wave communication systems adopt large antenna arrays and beamforming technologies to obtain high antenna gains. The beamforming training is rather time‐consuming especially in multi‐user cases. To reduce the training overhead, a new fast multi‐user training scheme based on Compressed Sensing theory is proposed. This scheme includes a multi‐user training algorithm and a corresponding semi‐fixed semi‐random codebook design strategy. The base station (BS) simultaneously broadcasts the training pilots to all user equipments (UEs). Then all UEs independently conduct the proposed training algorithm from channel responses. Finally, all UEs send back the training results to the BS. Compared to the exhaustive search algorithm's training overhead , the cost of the proposed scheme is only , where and denote the number of beam patterns in the receiver and the transmitter. Simulation results show that the proposed scheme achieves excellent performance in high SNR (signal‐to‐noise ratio) cases with only performance difference from the theoretical bound. And in contrast with other Compressed Sensing schemes with random codebooks, the proposed scheme reduces the sensitivity to transmission SNR and improves approximately 3 dB performance in low SNR cases.

Accurate and comprehensive end-to-end network performance measurement is critical for the automatic troubleshooting and optimized provision of various services in Cloud. However, cloud providers and tenants still rely on rudimentary and separate tools for end-to-end performance measurement, which are inflexible, tedious, and error-prone. In this paper, we present NetWatch, a system that provides measurement as a service through open APIs for both cloud providers and tenants to measure end-to-end performance on-demand. In this system, measurement requests are first delivered to NetWatch Controller by open APIs, which transforms the request to configure specific Probes to fulfill the requests by active measurement. We make delicate design choices and address several challenges to enable NetWatch offering accurate and low-overhead measurement service for multiple users simultaneously and efficiently. A prototype implementation and experiments with diverse network settings link and traffic demonstrate that NetWatch can support flexible and accurate measurement of end-to-end network performance with small overhead.

Live migration is a key technique for virtual machine (VM) management in data center networks, which enables flexibility in resource optimization, fault tolerance, and load balancing. Despite its usefulness, the live migration still introduces performance degradations during the migration process. Thus, there has been continuous efforts in reducing the migration time in order to minimize the impact. From the network's perspective, the migration time is determined by the amount of data to be migrated and the available bandwidth used for such transfer. In this paper, we examine the problem of how to schedule the migrations and how to allocate network resources for migration when multiple VMs need to be migrated at the same time. We consider the problem in the Software-defined Network (SDN) context since it provides flexible control on routing. More specifically, we propose a method that computes the optimal migration sequence and network bandwidth used for each migration. We formulate this problem as a mixed integer programming, which is NP-hard. To make it computationally feasible for large scale data centers, we propose an approximation scheme via linear approximation plus fully polynomial time approximation, and obtain its theoretical performance bound and computational complexity. Through extensive simulations, we demonstrate that our fully polynomial time approximation (FPTA) algorithm has a good performance compared with the optimal solution of the primary programming problem and two state-of-the-art algorithms. That is, our proposed FPTA algorithm approaches to the optimal solution of the primary programming problem with less than 10 percent variation and much less computation time. Meanwhile, it reduces the total migration time and service downtime by up to 40 and 20 percent compared with the state-of-the-art algorithms, respectively.

Various dedicated web services in the cyberspace, e.g., social networks, e-commerce, and instant communications, play a significant role in people's daily-life. Billions of people around the world access these services through multiple online identifiers (IDs), and interact with each other in both the cyberspace and the physical world. Thanks to the rapid development of wireless and mobile technologies, nowadays these two kinds of interactions are highly relevant with each other. In order to link between the cyberspace and the physical world, we propose a new type of social network, i.e., co-location social network (CLSN). A CLSN contains online IDs describing people's online presence and offline “encountering” events when people come across each other. By analyzing real data collected from a mainstream ISP in China, which contains 32.7 million IDs across the most popular web services, we build a large-scale CLSN, and explore its unique properties from various aspects. The results indicate that the CLSN is quite different from existing online and offline social networks in terms of classic graph metrics. Moreover, we propose a community-based user identification algorithm to find all online IDs belonging to the same physical user. Using some ground-truth data, we demonstrate that our proposed algorithm achieves a high accuracy in user identification. Finally, we perform a user-centric analysis, and we demonstrate the behavioral difference among different types of users.

As the largest microblogging service in China, Sina Weibo, is associated with a huge amount of traffic to and from other major websites. Thanks to a massive set of anonymized data from a major operator covering a large-scale metropolitan area, we extract the click-based transitions between Weibo and other websites. Such transitions have not been looked into in most studies that rely on the visible hyper-links among websites. Based on this unique dataset, we show that 38% of the outgoing transitions (leaving Weibo) go to video clip services. Comparatively, links related to news and long videos are clicked less but posted more. This indicates that photograph and text-sharing in microblog have been gradually replaced by video clip sharing. Also, ignoring video clip sharing, 53% of the transitions go to five of the largest Chinese websites, showing how closely connected Weibo has become in the Chinese Web ecosystem. We further look at users' click behavior in transitions, and find that through co-clustering there do exist a number of prevalent and distinct behavior patterns, suggesting that only seven co-clusters can capture the click behavior of 192 000 studied users. Overall, our work is the first to unveil the significant role of microblogging platforms in the Web ecosystem. Considering the massive user base of Weibo, our findings can aid the design of more personalized link recommendation in Weibo, thus generating more referral traffic, i.e., user visits, from Weibo to other major websites.

Nowadays, human trajectories are widely collected and utilized for scientific research and business purpose. However, publishing trajectory data without proper handling might cause severe privacy leakage. A large body of works is dedicated to merging one’s trajectory with others’, so as to avoid any individual trajectory being re-identified. Yet their solutions do not provide enough protection since they cannot prevent semantic attack, which means the attackers are able to acquire individual’s private information by using the semantics features of frequently visited locations in the trajectory even without re-identification. In this paper, we are the first to recognize the semantic attack, which is another severe privacy problem in publishing trajectory datasets. We propose an algorithm providing strong privacy protection against both the semantic and re-identification attack while reserving high data utility. Extensive evaluations based on two real-world datasets demonstrate that our solution improves the quality of privacy protection by three times, sacrificing only 36% and 10% of spatial and temporal resolution, respectively.

With the rise of social networking and the awareness of privacy protection, the large-scale positioning data is getting harder to access while the clickstream data of social networking is accumulating. It is necessary to conduct a comprehensive study on the temporal property and spatial distribution of social network's clickstream to determine the latent relationship between clickstream and location semantics which semantically annotate locations to help us understand the purpose of a social network user at a certain location and a particular time. In this paper, we first infer the location semantics from Internet logs as our baseline which is a large scale, imprecise positioning mobile dataset through combining the utilization of derived time pattern and speed pattern. Then we design a method to reconstruct location semantics through the social network. We are the first to our knowledge that define “click motif” of social network's clickstream which is the combination of clicks in clickstream that occurs repeatedly and has significance. Click motif not only can help us to classify location semantics but also enhance the user experience of social networking. Besides, we propose a completed process to extract typical click motifs from a large-scale complicated clickstream data via embedding and clustering method. By extensive experiments and analysis, we demonstrate that different combination of click motifs can convey the users' location semantics, therefore clickstream may disclose location privacy.

Trajectory data has been widely collected via mobile devices and publicly released for academic research and commercial purposes. One primary concern of publishing such a dataset is the privacy issue. Previous protection schemes mainly focus on preventing re-identification attack, which utilizes the uniqueness of trajectories. However, the correlation between trajectories, which has not been given much attention to before, could also give rise to serious privacy leakage. Recent studies have proved that it is possible to identify social relationship, de-anonymize trajectories or even infer user’s locations by analyzing the correlation between users’ trajectories. We identify the serious privacy problem of social relationship leakage caused by what we call social relationship attack and aim to protect social relationship information, which cannot be protected by existing algorithms. We contribute to the design of a new privacy model and an effective system to deal with social relationship attack and re-identification attack simultaneously while maintaining high data utility. We propose aSlidingWindowalgorithm to merge trajectories according to theirsocial-aware distance, which concerns both the spatiotemporal distance and social proximity. Evaluations of two trajectory datasets under different scenarios demonstrate that our system provides more than 1.84 times privacy protection at the cost of only 2.5% data utility loss.

Fog computing is a promising solution for new emerging applications requiring intensive computation resources and low latency. Devices at the edge of network can share idle resources and collaboratively accomplish the computing tasks in fog computing. Thus, task publishers have heterogeneous options when offloading computing tasks considering the quality of transmission links, energy consumption and other hardware constraints of fog nodes. To incentivize these devices to participate in computation offloading, effective incentive mechanisms are needed. In this paper, utilizing the framework of contract theory, we formulate the negotiation between task publisher and fog nodes as an optimization problem. The optimal contract is the Nash equilibrium solution achieved by task publisher and fog nodes. Simulation results show that an optimal contract can maximize the utility of task publisher meanwhile guarantee the individual rationality and incentive compatibility of fog nodes. Therefore, edge devices can be incentivized effectively to involve in the computation offloading.

Most existing recommender systems leverage the primary feedback data only, such as the purchase records in E-commerce. In this work, we additionally integrate view data into implicit feedback based recommender systems (dubbed as Implicit Recommender Systems). We propose to model the pairwise ranking relations among purchased, viewed, and non-viewed interactions, being more effective and flexible than typical pointwise matrix factorization (MF) methods. However, such a pairwise formulation poses efficiency challenges in learning the model. To address this problem, we design a new learning algorithm based on the element-wise Alternating Least Squares (eALS) learner. Notably, our algorithm can efficiently learn model parameters from the whole user-item matrix (including all missing data), with a rather low time complexity that is dependent on the observed data only. Extensive experiments on two real-world datasets demonstrate that our method outperforms several state-of-the-art MF methods by 10% ∼ 28.4%. Our implementation is available at: https://github.com/ dingjingtao/View_enhanced_ALS.

Micro-video has recently become an important form of user generated contents in the social media of microblogging. It is propagated by sharing and reaches the other users through being clicked and watched. Besides the traditional popularity metric for a micro-video such as click (or view) count, share count can indicate its virality in social domain. Understanding the differences between clicking and sharing behaviors is fundamental when evaluating the actual influence of micro-videos in social media. However, since that click data is usually not public available, above question has not been investigated in most studies. Thanks to a massive set of anonymized data from a major operator covering the whole China, we jointly study both clicking and sharing behaviors of over 10,000 micro-videos in Sina Weibo, the largest microblogging service and micro-video platform in China. Having extracted a rich set of features covering micro-video publishers, description texts and those shared users, we are able to identify the most influential features for click and share. From our studies, we observe that publisher-related features (post and followee counts) as well as the video duration have more impact on click, while video-description-related features including topical features and emoticon count are more correlated to share. Impacted by different features, the received clicks and shares of a micro-video may differ a lot from each other. Based on above observations, we build a prediction model for existing deviations among these two metrics, which can aid the development of a more effective and attractive micro-video platform.

Understanding the linkability of online user identifiers (IDs) is critical to both service providers (for business intelligence) and individual users (for assessing privacy risks). Existing methods are designed to match IDs across two services, but face key challenges of matching multiple services in practice, particularly when users have multiple IDs per service. In this paper, we propose a novel system to link IDs across multiple services by exploring the spatial-temporal locality of user activities. The core idea is that the same user's online IDs are more likely to repeatedly appear at the same location. Specifically, we first utilize a contact graph to capture the “co-location” of all IDs across multiple services. Based on this graph, we propose a set-wise matching algorithm to discover candidate ID sets, and use Bayesian inference to generate confidence scores for candidate ranking, which is proved to be optimal. We evaluate our system using two real-world ground-truth datasets from an ISP (4 services, 815K IDs) and Twitter-Foursquare (2 services, 770 IDs). Extensive results show that our system significantly outperforms the state-of-the-art algorithms in accuracy (AUC is higher by 0.1–0.2), and it is highly robust against matching order and number of services.

Human mobility prediction is of great importance for a wide spectrum of location-based applications. However, predicting mobility is not trivial because of three challenges: 1) the complex sequential transition regularities exhibited with time-dependent and high-order nature; 2) the multi-level periodicity of human mobility; and 3) the heterogeneity and sparsity of the collected trajectory data. In this paper, we propose DeepMove, an attentional recurrent network for mobility prediction from lengthy and sparse trajectories. In DeepMove, we first design a multi-modal embedding recurrent neural network to capture the complicated sequential transitions by jointly embedding the multiple factors that govern the human mobility. Then, we propose a historical attention model with two mechanisms to capture the multi-level periodicity in a principle way, which effectively utilizes the periodicity nature to augment the recurrent neural network for mobility prediction. We perform experiments on three representative real-life mobility datasets, and extensive evaluation results demonstrate that our model outperforms the state-of-the-art models by more than 10%. Moreover, compared with the state-of-the-art neural network models, DeepMove provides intuitive explanations into the prediction and sheds light on interpretable mobility prediction.

Recent proliferation of mobile networks and smart devices drives the rapid growth of mobile video traffic. Caching popular video content at any possible place of the network near to users could significantly increase their delivery efficiency. However, fundamental problems of how cache behaves and what is the principle for cache deployment in a mobile network under large-scale video views are still unknown, which include three closely relevant problems: 1) what is the best scale of regions to deploy cache appliances; 2) how many contents should be cached; and 3) which contents should be cached. In this paper, we synthetically study these problems by analyzing 10 million video view requests of six most popular content providers, in the city of Shanghai, China. We first aggregate videos from different providers by topics to measure user interests, and divide the city into nonoverlapping regions of different sizes to investigate the influence of scale. Then, we define metrics of view concentration, popular topic number, cache revenue, and popular topic similarity to quantitatively characterize cache behaviors and consequently answer the three problems. Our studies reveal that: 1) it is effective to deploy cache in regions of a wide range of different scales; 2) the larger scale region and the regions with more views should cache more contents; and 3) different regions, especially small scale ones, should cache different contents. Furthermore, based on trace-driven evaluation, we show that the overall cache hit ratio can increase by up to 30% when we apply above guidelines for cache deployment.

In the diverse usage scenarios of mobile networks, we have different performance requirements on connection density and user experienced data rate, and modeling such diversity is crucial to the strategy evaluation in addressing the problem of high traffic load and scalability of network resources. Therefore, it is necessary to build a network capability model in two dimensions of connection density and user experienced data rate. This paper aims at addressing this challenge based on an investigation of network capability in large-scale urban environments. First, our statistical study shows that the spatial distribution of these two parameters can be accurately modelled by the log-normal mixture distribution. Second, we find that only six basic capability patterns exist among the 9,000 cellular base stations, which indicates different levels of network capabilities. More importantly, these discoveries are similar in a cellular network deployed in a different city. Therefore, based on these two discoveries, we build a network capability model that can generate synthetic base stations with diverse connection density and user experienced data rate. We believe that this methodology of modeling network capability, with accuracy, generality, and flexibility, can help telecommunication operators to design and standardize mobile networks of the next generation.

Watching videos online has become prevalent in our daily activities. While there are extensive measurements studying about video on demand, IPTV, live streaming, etc., most of them focus their analysis on a single content provider (CP). Various user behaviors over multiple different CPs are yet to be explored. In this paper, we collect about ten million viewing records of the six most popular video CPs through a major Internet service provider (ISP) in Shanghai, China, and examine the user behaviors and access patterns with an emphasis on comparing them among different CPs in the same environments. Our analysis reveals the day-scale temporal patterns, the diversified device-wise preferences, and the city-scale geographical features of the different CPs, and identifies the high relevance between the user behaviors and the contents of the videos. Moreover, we find that user migration across multiple CPs is prevalent and highly influenced by different features of CPs. We believe that our observations and findings can provide valuable insights for CPs to enhance their user experience as well as ISPs to optimize the network architecture.

With the popularity of watching mobile videos, a major form of multimedia contents, many works focus on the geographic features of user viewing behaviors, but few study them in the context of an entire metropolitan city. Different regions of a large city have different intensity of economy activities with respect to their different distances to the downtown, and how this will influence video popularity and similarity is still unclear. To quantitatively study the spatial popularity and similarity of watching videos in a large urban environment, we collect a dataset with two-month video view requests from the largest network provider in Shanghai, containing the top six content providers, and study the spatial features of video access in regions of different scales. We find that: 1) video popularity and similarity exist at different scales of city division; 2) the concentration of video popularity becomes higher as the region is closer to downtown; and 3) when comparing the regions of same scale, the similarity of popular videos becomes lower as the region is farther away from the downtown. Finally, we correlate our findings with cache deployment, advertising, and video recommendation to illustrate the implications.

With the popularity of proximity-based services, device-to-device (D2D) communication underlaying cellular networks is a promising technology to cope with the growing demands by improving network resource utilization. However, the wireless communication's broadcast nature is vulnerable to eavesdropping, and thus, ensuring a secrecy communication for both cellular user equipments (CUEs) and D2D pairs in an underlay network is a challenging issue. We investigate the problem of physical-layer secure transmission jointly with resource allocation in D2D communications. Different from existing works, we framed overlapping (partial) coalitional game where each D2D pair can access multiple CUEs' spectral resources. Moreover, the multiple D2D pairs can share single CUE subchannel in multiple eavesdroppers scenario to ensure information security for both CUEs and D2D pairs and to maximize system sum rate in a socially aware D2D network. We incorporate the mutual interference and propose different transmission modes for a secrecy-ensured resource allocation-based overlapping coalition formation scheme with transferable utility to obtain a final stable partition. We further prove the proposed algorithm stability, convergence, and computational complexity. Both analytical and numerical results demonstrate the effectiveness of our proposed scheme, which ensures a system-wide security and at the same time improves the performance by maximizing the system sum rate.

With the explosive growth of mobile traffic, diverse mobile applications with high throughput demands have gained considerable attention from both academia and industry. However, dynamics due to human mobility impose serious issues on high throughput communications. Although millimeter-wave (mm-wave), relays, and concurrent transmission have been applied for throughput improvement, how to achieve high throughput transmission in mobility-aware scenarios is still challenging. In this paper, we propose a throughput-efficient service scheduling (TESS) scheme, which exploits multi-hop relay and concurrent transmissions with the consideration of human mobility. In TESS, we first propose a mobility-aware transmission scheduling scheme in single mm-wave cell. The proposed scheduling scheme consists of a relay path planning algorithm and a global time scheduling algorithm. In the relay path planning algorithm, we establish multi-hop relay transmission paths from base station to service points. In the global time scheduling algorithm, we schedule concurrent transmission in relay paths. Furthermore, the proposed TESS scheme is extended for multi-cell scenarios. Through extensive performance evaluations under realistic human mobility trajectories, we demonstrate the superior performance of TESS in terms of system throughput compared with the state-of-the-art schemes.

Physical layer security (PLS) is a promising technology in device-to-device (D2D) communications by exploiting reciprocity and randomness of wireless channels, which attracts considerable research attention in the D2D communications community. In this paper, we investigated PLS for secure key generation rate (SKGR) in D2D communications based on cooperative trusted and non-trusted relays. By leveraging social ties, we exploit three social phenomena for secure communications, i.e., trusted scenario (social trust), non-trusted scenario (social reciprocity), and partially trusted scenario (mixed social trust and social reciprocity). The coalition game theory is further utilized to select the optimal relay pairs for improving SKGR. On the basis of social ties, we develop an algorithm for SKGR that protects the keys secret from both eavesdropper and non-trusted selected relays. We incorporate secure relays selection and system wide security for D2D communications. The stability and convergence of the proposed algorithm are also proved in this paper. Both numerical and analytical results verify effectiveness and consistency of our proposed scheme, which ensures better SKGR performance in D2D communications.

It is well-known that online services resort to various cookies to track users through users' online service identifiers (IDs) - in other words, when users access online services, various "fingerprints" are left behind in the cyberspace. As they roam around in the physical world while accessing online services via mobile devices, users also leave a series of "footprints" -- i.e., hints about their physical locations - in the physical world. This poses a potent new threat to user privacy: one can potentially correlate the "fingerprints" left by the users in the cyberspace with "footprints" left in the physical world to infer and reveal leakage of user physical world privacy, such as frequent user locations or mobility trajectories in the physical world - we refer to this problem as user physical world privacy leakage via user cyberspace privacy leakage. In this paper we address the following fundamental question: what kind - and how much - of user physical world privacy might be leaked if we could get hold of such diverse network datasets even without any physical location information. In order to conduct an in-depth investigation of these questions, we utilize the network data collected via a DPI system at the routers within one of the largest Internet operator in Shanghai, China over a duration of one month. We decompose the fundamental question into the three problems: i) linkage of various online user IDs belonging to the same person via mobility pattern mining; ii) physical location classification via aggregate user mobility patterns over time; and iii) tracking user physical mobility. By developing novel and effective methods for solving each of these problems, we demonstrate that the question of user physical world privacy leakage via user cyberspace privacy leakage is not hypothetical, but indeed poses a real potent threat to user privacy.

Today's video streaming market is crowded with various content providers (CPs). For individual CPs, understanding user behavior, in particular how users migrate among different CPs, is crucial for improving users' on-site experience and the CP's chance of success. In this paper, we take a data-driven approach to analyze and model user migration behavior in video streaming, i.e., users switching content provider during active sessions. Based on a large ISP dataset over two months (6 major content providers, 3.8 million users, and 315 million video requests), we study common migration patterns and reasons of migration. We find that migratory behavior is prevalent: 66% of users switch CPs with an average switching frequency of 13%. In addition, migration behaviors are highly diverse: regardless large or small CPs, they all have dedicated groups of users who like to switch to them for certain types of videos. Regarding reasons of migration, we find CP service quality rarely causes migration, while a few popular videos play a bigger role. Nearly 60% of cross-site migrations are landed to 0.14% top videos. Finally, we validate our findings by building an accurate regression model to predict user migration frequency, and discuss the implications of our results to CPs.

Due to the proliferation of mobile networks and services, accessing online video services via mobile devices becomes increasingly popular, which generates huge data traffic and increases the cellular network load. It is valuable to characterize the usage patterns of different video services for network optimization and user experience enhancement. In this paper, we adopt a data-driven approach to investigate the usage patterns of three newly popular and major kinds of mobile video services: personalized livestreaming, user- generated video service, and traditional video portals. Based on the empirical analysis of a large dataset including 0.45 million users and 25 million logs, we find that 1) users have high loyalty in the same type of video services; 2) difference on the traffic peaks in consecutive days exists among different kinds of services; 3) personalized livestreaming services contributes a larger portion of video traffic, which still increases after midnight at weekday in the downtown. Finally, based on these findings, we discuss their implications and insights for network optimization and video service enhancement.

Enhancing throughput gain is an important target in the development of millimeter-wave (mmWave) communications. Spatial reuse is an important approach for throughput enhancement, which works well in mmWave networks due to directional links. In addition, multicast transmissions are highly desirable in mmWave systems, and become feasible with recent advances in antenna technology. In this paper, we address the problem of spatial reuse scheduling with multicast transmissions for mmWave communications. We formulate the problem as a Mixed Integer Non-Linear Programming (MINLP) problem and propose a low-computational-complexity heuristic algorithm, where potential links are fully utilized to exploit spatial reuse gain by dividing multicast demands into multiple unicast/multicast transmissions. Extensive simulation results demonstrate that the proposed scheme achieves near-optimal performance, and obtains high throughput gain with low packet loss rate.

In the modern information society, accurate prediction of human mobility becomes increasingly essential in various areas such as city planning and resource management. With users' historical trajectories, the inherent patterns of their movements can be extracted and utilized to accurately predict the future movements. In this paper, based on a dataset of 100,000 individuals' actively uploaded location information collected by apps, we discover the average theoretical limits of the predictability to be as high as 93%. Since the app-collected data contains the physical context of the location, we implement a clustering method based on the contextual information that cluster the locations into three divisions, street, district and region. In order to solve the unevenly distribution and the high missing rate of the application collected location data, we firstly use the Gibbs sampling algorithm to complete the missing data of the trajectory and then employ a high-order Markov chain model to predict the most likely locations visited by each user. Result shows that our prediction algorithm can achieve accuracy as high as 67%, 78%, 87% for the three context-based divisions respectively, which are 10% higher on average than the divisions without context. In addition, the correlation coefficient between prediction accuracy and predictability reaches as high as 0.86. Finally, we investigate various factors including spatial and temporal resolution, orders of Markov models, radius of gyration, in order to explore the predictability under different circumstances.

Nowadays, human trajectories are widely collected and utilized for scientific research and business purpose. However, publishing trajectory data without proper handling might cause severe privacy leakage. A large body of works are dedicated to merging one's trajectory with others', so as to avoid any individual trajectory being re-identified. Yet their solutions do not provide enough protection since they cannot prevent semantic attack, which means the attackers are able to acquire individual's private information by using the semantics features of frequently- visited locations in the trajectory even without re- identification. In this work, we are the first to recognize the semantic attack, which is another severe privacy problem in publishing trajectory datasets. We propose an algorithm providing strong privacy protection against both the semantic and re- identification attack while reserving high data utility. Extensive evaluations based on two real-world datasets demonstrate that our solution improves the quality of privacy protection by 3 times, sacrificing only 36% and 30% of spatial and temporal resolution, respectively.

Human mobility data has been ubiquitously collected through cellular networks and mobile applications, and publicly released for academic research and commercial purposes for the last decade. Since releasing individual's mobility records usually gives rise to privacy issues, datasets owners tend to only publish aggregated mobility data, such as the number of users covered by a cellular tower at a specific timestamp, which is believed to be sufficient for preserving users' privacy. However, in this paper, we argue and prove that even publishing aggregated mobility data could lead to privacy breach in individuals' trajectories. We develop an attack system that is able to exploit the uniqueness and regularity of human mobility to recover individual's trajectories from the aggregated mobility data without any prior knowledge. By conducting experiments on two real-world datasets collected from both mobile application and cellular network, we reveal that the attack system is able to recover users' trajectories with accuracy about 73%~91% at the scale of tens of thousands to hundreds of thousands users, which indicates severe privacy leakage in such datasets. Through the investigation on aggregated mobility data, our work recognizes a novel privacy problem in publishing statistic data, which appeals for immediate attentions from both academy and industry.

Understanding mobile traffic patterns of large scale cellular towers in urban environment is extremely valuable for Internet service providers, mobile users, and government managers of modern metropolis. This paper aims at extracting and modeling the traffic patterns of large scale towers deployed in a metropolitan city. To achieve this goal, we need to address several challenges, including lack of appropriate tools for processing large scale traffic measurement data, unknown traffic patterns, as well as handling complicated factors of urban ecology and human behaviors that affect traffic patterns. Our core contribution is a powerful model which combines three dimensional information (time, locations of towers, and traffic frequency spectrum) to extract and model the traffic patterns of thousands of cellular towers. Our empirical analysis reveals the following important observations. First, only five basic time-domain traffic patterns exist among the 9600 cellular towers. Second, each of the extracted traffic pattern maps to one type of geographical locations related to urban ecology, including residential area, business district, transport, entertainment, and comprehensive area. Third, our frequency-domain traffic spectrum analysis suggests that the traffic of any tower among 9600 can be constructed using a linear combination of four primary components corresponding to human activity behaviors. We believe that the proposed traffic patterns extraction and modeling methodology, combined with the empirical analysis on the mobile traffic, pave the way toward a deep understanding of the traffic patterns of large scale cellular towers in modern metropolis.

Previous works have proposed various approaches to implement service chaining by routing traffic through the desired middleboxes according to pre-defined policies. However, no matter what routing scheme is used, the performance of service chaining depends on where these middleboxes are placed. Thus, in this paper, we study middlebox placement problem, i.e., given network information and policy specifications, we attempt to determine the optimal locations to place the middleboxes so that the performance is optimized. The performance metrics studied in this paper include the end-to-end delay and the bandwidth consumption, which cover both users’ and network providers’ interests. We first formulate it as 0-1 programming problem, and prove it is NP-hard. We then propose two heuristic algorithms to obtain the sub-optimal solutions. The first algorithm is a greedy algorithm, and the second algorithm is based on simulated annealing. Through extensive simulations, we show that in comparison with a baseline algorithm, the proposed algorithms can reduce 22 percent end-to-end delay and save 38 percent bandwidth consumption on average. The formulation and proposed algorithms have no special assumption on network topology or policy specifications, therefore, they have broad range of applications in various types of networks such as enterprise, data center and broadband access networks.

Various dedicated web services in the cyberspace, e.g., social networks, e-commerce, and instant communications, play a significant role in people's daily-life. Billions of people around the world access them through multiple online identifiers (IDs), and interact with each other in both the cyberspace and the physical world. These two kinds of interactions are highly relevant to each other. In order to link between the cyberspace and the physical world, we propose a new type of social network, i.e., co-location social network (CLSN). A CLSN contains online IDs describing people's online presence and offline interactions when people come across each other. By analyzing real data collected from a mainstream ISP in China, which contains 32.7 million IDs across most popular web services, we build a large-scale CLSN, and evaluate its unique properties. The results verify that the CLSN is quite different from existing online and offline social networks in terms of different classic graph metrics. This paper is the first research to study CLSN at scale and paves the way for future studies of this new type of social network.

With the popularity of watching mobile videos, many works focus on the geographic features of user viewing behaviors, but few study them in the context of an entire metropolitan city. Different regions of a large city have different intensity of economy activities with respect to their different distances to the downtown, and how this will influence video popularity and similarity is still unclear. To quantitatively study the spatial popularity and similarity of watching videos in a large urban environment, we collect a dataset with two-month video view requests from the largest network provider in Shanghai, containing top six content providers, and study the spatial features of video access in regions of different scales. We find that 1) video popularity and similarity exist at different scales of city division; 2) the concentration of video popularity becomes higher as the region is closer to downtown; 3) when comparing the regions of same scale, the similarity of popular videos becomes lower as the region is farther away from the downtown. Finally, we correlate our findings with cache deployment, advertising and video recommendation to illustrate the implications.

With the explosive growth of mobile data demand, small cells densely deployed underlying the homogeneous macro-cells are emerging as a promising candidate for the fifth generation (5G) mobile network. The backhaul communication for small cells poses a significant challenge, and with huge bandwidth available in the mmWave band, the wireless backhaul at mmWave frequencies can be a promising backhaul solution for small cells. In this paper, we propose the Maximum QoS-aware Independent Set (MQIS) based scheduling algorithm for the mmWave backhaul network of small cells to maximize the number of flows with their QoS requirements satisfied. In the algorithm, concurrent transmissions and the QoS aware priority are exploited to achieve more successfully scheduled flows and higher network throughput. Simulations in the 73 GHz band are conducted to demonstrate the superior performance of our algorithm in terms of the number of successfully scheduled flows and the system throughput compared with other existing schemes.

For mobile networks diverse usage scenarios have different capability requirements on connection density and user experienced data rate, and modeling such capability diversity is crucial to the strategy evaluation in addressing the problem of high traffic load and scalability of network resources. Therefore, it is necessary to build a capability model in two dimensions of connection density and user experienced data rate. This paper aims at addressing this challenge based on an investigation of network capability in large-scale urban environment. First, our statistical study shows that the spatial distribution of these two parameters can be accurately fitted by log-normal mixture model. Second, we find that only six basic capability patterns exist among the 9,000 cellular base stations. Their connections with the urban functions of geographical locations are also explored in our work. Based on these two discoveries, we build a network capability model which can generate synthetic base stations with diverse connection density and user experienced data rate. We believe that this flexible and powerful model can help telecommunication operators to design and standardize mobile network in the future.

60‐GHz millimetre‐wave (mm‐wave) communication is gradually becoming a promising candidate for the next generation wireless system to meet the demands of mobile applications. To compensate for high path loss, directional links are established in mm‐wave communication system, which adds opportunity for spatial reuse. As one of its most promising protocols for commercial production, IEEE 802.11ad standard provides a mechanism to support space‐time division multiple access (STDMA) within a single network. However, the interference level among different co‐channel networks is much lower than that inside a network, which provides greater potential for spatial reuse. In this study, based on the architecture and timing structure of IEEE 802.11ad, the authors propose a spatial reuse strategy among multiple co‐channel networks. They formulate the problem as a mixed‐integer non‐linear programming problem, and then propose an inter‐network STDMA scheduling algorithm, which considers clustering frame structure in IEEE 802.11ad, and combines greedy principle and mutual interference avoidance strategy. Extensive simulation results have shown that the proposed scheme enlarges total throughput in comparison with STDMA inside each network, as well as non‐STDMA scheme. Meanwhile, it achieves the lowest packet loss rate under heavy traffic load.

With the emergence of demands for local area services, device-to-device (D2D) communication is proposed as a vital technology component for the next generation cellular communication to increase spectral efficiency and enhance system capacity. In a D2D underlaying cellular system, through carefully coordinated dynamic scheduling, some base stations can be shut down and the corresponding load can be transferred to the D2D communication, which provides significant energy savings without much impact on the overall system performance. In this paper, we study the base station scheduling in D2D communication given a large scale of users. By formulating this problem into a flow maximization problem that optimizes the data transmission from the base stations to the users, we obtain the optimal base station scheduling solution. Through extensive simulations with real human mobility traces, we demonstrate the effectiveness of our proposed scheme, which significantly enhances the system throughput compared with existing strategies.

As power consumption of the Internet has been growing quickly in recent years, saving energy has become an important problem of networking research, for which the most promising solution is to find the minimum-power network subsets and shut down other unnecessary network devices and links to satisfy changing traffic loads. However, in traditional networks, it is difficult to implement a coordinated strategy among the network devices due to their distributed network control. On the other hand, the new networking paradigm-software defined network (SDN) provides us an efficient way of having a centralized controller with a global network view to control the power states. As an emerging technology, SDNs usually coexist with traditional networks at present. Therefore, we need to investigate how to save energy in partially deployed SDNs. In this paper, we formulate the optimization problem of finding minimum-power network subsets in partially deployed SDNs. After proving the problem is NP-hard, we propose a heuristic solution to approach its exact solution. Through extensive simulations, we demonstrate that our heuristic algorithm has a good performance; that is, on average we can save about 50 percent of total power consumption in the full SDN, having a distance less than 5 percent of the exact solution's power consumption. Moreover, it also achieves good performance in the partially deployed SDN, on average saving about 40 percent of the total power consumption when there are about 60 percent SDN nodes in the network. Meanwhile, it runs significantly faster than a general linear solver of this problem, by reducing the computation time of the network containing hundreds of nodes by 100× at least.

Recently, cloud computing technology has been utilized to make vehicles on roads smarter and to offer better driving experience. Consequently, the concept of mobile vehicular cloudlet (MVC) was born, where nearby smart vehicles were connected to provide cloud computing services locally. Existing researches focus on MVC system models and architectures, and no work to date addresses the critical question of what is the potential, i.e., level of local cloud computing service, achievable by MVCs in real-world large-scale urban environments. This issue is fundamental to the practical implementation of MVC technology. Answering this question is also challenging because MVCs operate in highly complicated and dynamic environments. In this paper, we directly address this challenging issue and we introduce the concept of serviceability to measure the ability of an MVC to provide cloud computing service. In particular, we evaluate this measure in practical environments through a real-world vehicular mobility trace of Beijing. Using the time-varying graph model for mobile cloud computing under different scenarios, we find that the serviceability has a relationship with the delay tolerance of the undertaken computational task, which can be described by two characteristic parameters. The evolution of serviceability through a day and the influence of network congestion are also analyzed. We also portray the spatial distribution of the serviceability and analyze the influence of connectivity and mobility in both MVC and vehicle levels. Our observations are valuable to assist designing vehicular cloud computing systems and applications, as well as to help make offloading decisions.

Roadside units (RSUs), which enable vehicles-to-infrastructure communications, are deployed along roadsides to handle the ever-growing communication demands caused by explosive increase of vehicular traffics. How to efficiently utilize them to enhance the vehicular delay tolerant network (VDTN) performance are the important problems in designing RSU-aided VDTNs. In this work, we implement an extensive experiment involving tens of thousands of operational vehicles in Beijing city. Based on this newly collected Beijing trace and the existing Shanghai trace, we obtain some invariant properties for communication contacts of large scale RSU-aided VDTNs. Specifically, we find that the contact time between RSUs and vehicles obeys an exponential distribution, while the contact rate between them follows a Poisson distribution. According to these observations, we investigate the problem of communication contact-aware mobile data replication for RSU-aided VDTNs by considering the mobile data dissemination system that transmits data from the Internet to vehicles via RSUs through opportunistic communications. In particular, we formulate the communication contact-aware RSU-aided vehicular mobile data dissemination problem as an optimization problem with realistic VDTN settings, and we provide an efficient heuristic solution for this NP-hard problem. By carrying out extensive simulation using realistic vehicular traces, we demonstrate the effectiveness of our proposed heuristic contact-aware data replication scheme, in comparison with the optimal solution and other existing schemes.

Abstract Millimeter wave (mmWave) communications in 60 GHz band have become a hot topic in wireless communications. New medium access control (MAC) protocols are needed because of the fundamental differences between mmWave communications and existing other communication systems. In mmWave wireless personal area networks, the channel transmission rates of links vary significantly because of the difference in the distance between nodes, the accuracy of beamforming, and the existence of obstructions. Owning to the directivity of mmWave links, spatial reuse should be exploited to improve network capacity. In this paper, we develop a channel transmission rate aware directional MAC protocol, termed RDMAC, in which both the multirate capability of links and spatial reuse are exploited to improve network performance. RDMAC has two stages. The first stage measures the channel transmission rates of links, and a heuristic algorithm is proposed to compute near‐optimal measurement schedules with respect to the total number of measurements. The second stage accommodates the traffic demand of links, and a heuristic transmission scheduling algorithm is proposed to compute near‐optimal transmission schedules with respect to the total transmission time. Simulations under various traffic modes show that compared with existing protocols, RDMAC has lower network latency, higher network throughput, and also a good fairness performance. Copyright © 2014 John Wiley & Sons, Ltd.

Due to the requirement of establishing several independent links, multi-device multi-path beamforming (BF) training becomes rather time-consuming in 60-GHz millimeterwave communications. To reduce training overhead, a novel BF training scheme is proposed in this paper. The scheme includes a simultaneous training strategy for multiple devices and multiple paths, and a corresponding multi-path beam-pair detection algorithm. The training pilot of the source device is broadcasted to all destination devices. Subsequently, in each destination device, the proposed detection is separately conducted to detect significant-path-related beam pairs from the channel responses, via exploiting the time resolvability and space sparsity of physical paths. Finally, the training results are successively fed back to the source device. The proposed scheme achieves simultaneous training of multiple devices and multiple paths, and obtains significant reduction of overhead. Comprehensive simulations are presented to verify the effectiveness of this scheme.

Understanding mobile traffic patterns of large scale cellular towers in urban environment is extremely valuable for Internet service providers, mobile users, and government managers of modern metropolis. This paper aims at extracting and modeling the traffic patterns of large scale towers deployed in a metropolitan city. To achieve this goal, we need to address several challenges, including lack of appropriate tools for processing large scale traffic measurement data, unknown traffic patterns, as well as handling complicated factors of urban ecology and human behaviors that affect traffic patterns. Our core contribution is a powerful model which combines three dimensional information (time, locations of towers, and traffic frequency spectrum) to extract and model the traffic patterns of thousands of cellular towers. Our empirical analysis reveals the following important observations. First, only five basic time-domain traffic patterns exist among the 9,600 cellular towers. Second, each of the extracted traffic pattern maps to one type of geographical locations related to urban ecology, including residential area, business district, transport, entertainment, and comprehensive area. Third, our frequency domain traffic spectrum analysis suggests that the traffic of any tower among the 9,600 can be constructed using a linear combination of four primary components corresponding to human activity behaviors. We believe that the proposed traffic patterns extraction and modeling methodology, combined with the empirical analysis on the mobile traffic, pave the way toward a deep understanding of the traffic patterns of large scale cellular towers in modern metropolis.

Live migration is a key technique for virtual machine (VM) management in data center networks, which enables flexibility in resource optimization, fault tolerance, and load balancing. Despite its usefulness, the live migration still introduces performance degradations during the migration process. Thus, there has been continuous efforts in reducing the migration time in order to minimize the impact. From the network's perspective, the migration time is determined by the amount of data to be migrated and the available bandwidth used for such transfer. In this paper, we examine the problem of how to schedule the migrations and how to allocate network resources for migration when multiple VMs need to be migrated at the same time. We consider the problem in the Software-defined Network (SDN) context since it provides flexible control on routing. More specifically, we propose a method that computes the optimal migration sequence and network bandwidth used for each migration. We formulate this problem as a mixed integer programming, which is NP-hard. To make it computationally feasible for large scale data centers, we propose an approximation scheme via linear approximation plus fully polynomial time approximation, and obtain its theoretical performance bound. Through extensive simulations, we demonstrate that our fully polynomial time approximation (FPTA) algorithm has a good performance compared with the optimal solution and two state-of-the-art algorithms. That is, our proposed FPTA algorithm approaches to the optimal solution with less than 10% variation and much less computation time. Meanwhile, it reduces the total migration time and the service downtime by up to 40% and 20% compared with the state-of-the-art algorithms, respectively.

Owing to the requirement of power‐hungry ultra‐high‐speed analogue‐to‐digital converters (ADCs), 60 GHz wireless local area network systems face the challenge of high energy consumption in idle listening (IL). To cope with this problem, a 1 bit‐sampling IL (1BS‐IL) scheme is proposed in this paper. This scheme includes a mixed 1/ M ‐bit‐sampling receiver, and a corresponding packet detection algorithm termed 1BS generalised likelihood ratio test (1BS‐GLRT). The receiver enables packet detection in IL with a 1 bit ADC, which considerably lowers down the energy consumption; besides, the 1BS‐GLRT algorithm guarantees promising performance on packet detection. Once detecting the arrival of a packet, the receiver switches to an original multi‐bit sampling precision, that is, M ‐bit, ADC to demodulate the packet, which maintains the demodulation performance. Comparisons show that 1BS‐IL not only significantly reduces energy consumption, but also achieves competitive detection performance.

With the explosive growth of mobile data demand, there has been an increasing interest in deploying small cells of higher frequency bands underlying the conventional homogeneous macrocell network, which is usually referred to as heterogeneous cellular networks, to significantly boost the overall network capacity. With vast amounts of spectrum available in the millimeter-wave (mmWave) band, small cells at mmWave frequencies are able to provide multigigabit access data rates, whereas the wireless backhaul in the mmWave band is emerging as a cost-effective solution to provide high backhaul capacity to connect access points of the small cells. In order to operate the mobile network optimally, it is necessary to jointly design the radio access and backhaul networks. Meanwhile, direct transmissions between devices should be also considered to improve system performance and enhance user experience. In this paper, we propose a joint transmission scheduling scheme for the radio access and backhaul of small cells in the mmWave band, termed D2DMAC, where a path selection criterion is designed to enable device-to-device transmissions for performance improvement. In D2DMAC, a concurrent transmission scheduling algorithm is proposed to fully exploit spatial reuse in mmWave networks. Through extensive simulations under various traffic patterns and user deployments, we demonstrate that D2DMAC achieves near-optimal performance in some cases and outperforms other protocols significantly in terms of delay and throughput. Furthermore, we also analyze the impact of path selection on the performance improvement of D2DMAC under different selected parameters.

We investigate Tx/Rx joint beamforming in millimeter-wave communications (MMWC). As the multipath components (MPCs) have different steering angles and independent fadings, beamforming aims at achieving array gain and diversity gain in this scenario. A sub-optimal beamforming scheme is proposed to find the antenna weight vectors (AWVs) at Tx/Rx via iterative eigenvalue decomposition (EVD), provided that full channel state information (CSI) is available at both the transmitter and receiver. To make this scheme practically feasible in MMWC, a corresponding training approach is suggested to avoid the channel estimation and iterative EVD computation. As in fast fading scenario, the training approach may be time-consuming due to frequent training; another beamforming scheme, which exploits the quasi-static steering angles in MMWC, is proposed to reduce the overhead and increase the system reliability by multipath grouping (MPG). The scheme first groups the MPCs and then concurrently beamforms toward multiple steering angles of the grouped MPCs, so that both array gain and diversity gain are achieved. Performance comparisons show that, compared with the corresponding state-of-the-art schemes, the iterative EVD scheme with the training approach achieves the same performance with a reduced overhead and complexity, whereas the MPG scheme achieves better performance with approximately equivalent complexity.

With emerging demands for local area services, device-to-device (D2D) communication is conceived as a vital component for the next-generation cellular networks to improve spectral reuse, bring hop gains, and enhance system capacity. Ripening these benefits depends on efficiently solving several main technical problems, among which peer discovery aiming to probe the D2D communication contacts is critically challenging. In this paper, we propose a social-aware peer discovery scheme for D2D communications, which exploits social network characteristics for assisting the ad hoc peer discovery. In this scheme, the D2D users in the network are first divided into groups according to their social metrics of community and centralities, and then optimal beacons probing rate with constant intervals is decided for each group of users. Through extensive simulations with real human mobility traces, we demonstrate the effectiveness of our proposed scheme, which significantly increases the peer discovery ratio and enhances the data transmission performance compared with the existing schemes.

Groups of people with mobile phones using short-range connections such as WiFi and Bluetooth to propagate messages can be modeled as, with regard to regular absence of end-to-end connection, mobile social networks (MSNs), which can be exploited to offload a significant amount of mobile content from the overloaded infrastructure networks such as 3G. The study of content transmission delay for the applications of mobile content dissemination in MSNs is an important problem, because to enhance the network capacity, the traffic is offloaded at the cost of inducing longer delay. In contrast to existing works, which ignore the factors of contact duration limits and large content size, we present a contact duration aware framework to model the content dissemination process in MSNs, give an explicit expression for the average content dissemination delay, and reveals its relationship with various system parameters of content size, users' selfishness, number of involved subscribers, infecting ratio, and so on. We apply our proposed model to real-life traces to assess its reliability by comparing the theoretical results with measured statistics and present extensive upshots to evaluate the influence of various parameters on system performance. The results demonstrate the accuracy of our proposed framework and reveal that system parameters of content size, system infecting ratio and intragroup transmission are the most important factors to influence the content dissemination delay.

Various network optimization and management goals in cloud data centers can be achieved by re-mapping VMs to the substrate servers. Live VM migration is used to implement such re-mapping by moving VMs from the initial servers to the target ones. For efficiency and usability considerations, these migration tasks are expected to be completed as soon as possible, which can be achieved by planning multiple VMs to be migrated simultaneously. However, the available resources of computation and bandwidth limits the number of VMs that can be migrated at the same time. Besides, the available resources change with the progress of migration process, which makes VM migration planning a challenge problem. Considering both resources constraints and the dependence between the migration plan and the total migration time, in this paper, we investigate the problem of virtual machine migration planning to minimize the total migration time. We formulate VM migration planning as an optimization problem considering both computation and bandwidth constraints. Our formulation is based on a step-by-step migration scheme, where multiple VMs can be migrated simultaneously as long as the resource constraints are satisfied. The solution of the optimization problem outputs the migration plan which achieves the minimum time to finish the migration task. Moreover, we verify the effectiveness of the optimal migration plan through extensive simulations and comparison with the best algorithm in existing works.

With the emerging demands for extensive mobile applications, Device-to-Device (D2D) communication is viewed as an important technology for the next-generation cellular communication and mobile networks to increase spectral efficiency and enhance network capacity. Existing works usually study D2D communications under a network consisting of four nodes. In this paper, we jointly investigate the problems of optimal system resource allocation and mode selection for large scale networks. Specifically, by formulating a max-flow optimization problem that maximizes the system throughput through any possible of transmission modes with the decisions of resource allocations, we obtain the optimal system performance. Under realistic scenario driven simulations, we demonstrate the efficiency of our proposed scheme for combined mode selection and resource allocation.

In mobile delay tolerant networks (DTNs), energy-efficient probing schemes are vital to prolong the limited battery life of mobile devices. Current solutions mainly focus on optimizing the probing interval during contacts by assuming the contact rate between devices are exponentially distributed. However, extensive experimental measurements have shown the contact rate follows a power law distribution, which indicates the current solutions not optimal while on the other hand dramatically increases the difficulty to analyze this problem. In this paper, we propose an adaptive wakeup schedule based on power-law distributed contacts. Our approach requires nodes stay asleep when a contact is unlikely to happen and wake up only when the possibility that it can successfully contact another node is relatively high. By predicting node contacts in the future, our approach significantly reduce energy consumption without degrading the performance of opportunistic networks. Extensive simulations with real-life human traces have demonstrated the outstanding performance of our approach, which are able to save 30 percent energy while keeping the same performance in most scenarios.

Recently, millimeter wave communications in 60 GHz band have attracted considerable attention from academia, industry, and standards bodies. To overcome huge propagation loss, high gain directional antennas are used. Consequently, concurrent transmissions (spatial reuse) are enabled within a basic service set (BSS) and even among BSSs, which provides huge potential to improve the network capacity. In this paper, we propose a software-defined mmWave network architecture, where a centralized controller is introduced by abstracting the cross-layer control functions from the network layer to physical layer. Efficient coordination is achieved in this architecture to maximize the spatial reuse.

No abstract available.

Due to the requirement of power-hungry multi-Gsps analog-to-digital converters (ADCs), 60-GHz wireless local-area network (WLAN) systems face the challenge of high power consumption in idle listening (IL). To cope with this problem, a 1-bit-sampling IL (1BS-IL) scheme is proposed in this paper. This scheme includes a mixed 1/M-bit-sampling receiver, and a corresponding packet detection algorithm termed 1-bit-sampling generalized likelihood ratio test (1BS-GLRT). The receiver enables packet detection in IL with a 1-bit ADC, which considerably lowers down the power consumption; besides, the 1BS-GLRT algorithm guarantees promising performance on packet detection. Once detecting the arrival of a packet, the receiver switches to an original sampling precision (i.e., M-bit) ADC to demodulate the packet, which maintains the demodulation performance. Comparisons show that 1BS-IL not only significantly reduces power consumption, but also achieves competitive detection performance.

Multicast services are highly desirable in 60-GHz millimeter-wave communications, but multicast beamforming remains a challenge due to special structure of high frequency system. To solve this problem, a transmit and receive multicast beamforming scheme has been proposed in this paper. Unlike conventional multicast models in LTE/EMBMS, every device in proposed system is equipped with a multi-antenna array, which helps enhance beam directivity and reduce interference. Two stages are put forward to generate transmit and receive beams for multicasting. Performance evaluations have shown that the total throughput of the network has been improved largely by using the proposed scheme compared with unicast beamforming. Additionally, the designed algorithm has a minor performance loss compared with previous quasi-optimal algorithm, but with much lower complexity, which makes it advantageous for practical use.

Due to human blockage and device mobility, 60GHz wireless local-area network (WLAN) faces the challenge of communication-link outage. To cope with this problem, a double-link beam tracking scheme is proposed in this paper. This scheme includes a search strategy of transmission and alternative links, and an in-packet double-link tracking and switching method. The transmission and alternative links are simultaneously tracked against device mobility, through probing neighboring beams; once the human blockage is detected in transmission link, the system can thus switch to the alternative link directly. Besides, the proposed scheme finds the finish of human blockage quickly through in-packet double-link tracking, and enables the system to communication in the maximal received-power link. The comparison between the proposed scheme and the IEEE 802.11ad scheme is conducted. The comparison shows that the proposed scheme significantly reduces the probability of outage, and achieves an improved throughput.

Wireless Virtualization enables multiple concurrent virtual networks running on shared wireless substrate resource, which makes networks more flexible, efficient and customizable. Efficiently allocating physical wireless spectrum to multiple virtual networks to enhance the resource utilization is a fundamental challenge. Different from previous works focusing on only one physical wireless network, we study the problem under the multiple physical networks scenario, which makes the problem more general and practical. Furthermore, after analyzing the fluctuation feature in wireless virtualization, we introduce an opportunistic spectrum sharing method to increase spectrum allocation efficiency. First, we formulate the problem of opportunistic spectrum sharing with multiple physical wireless networks and prove it as an NP-Hard problem. Then, we propose a genetic algorithm and heuristic algorithm to solve the problem. Simulations show that opportunistic spectrum sharing conspicuously improves the performance of spectrum utilization and confirm the advantage of our proposed algorithms.

Estimation of the multipath channel in 60‐GHz communications is challenging, because the channel may be sparse or dense during beam training. Specifically, because of the variation of the number of non‐zero taps, it is hard for common estimators to obtain robust and prominent performance. In order to address this problem, the authors propose a sparse/dense channel estimation with non‐zero tap detection (SDCE‐NTD). The estimation is conducted in a three‐stage fashion, including initial estimation with the unstructured least‐square (LS) algorithm, non‐zero‐tap detection with the generalised likelihood ratio test approach, and posterior estimation with the structured LS algorithm. The false‐alarm and detection probability of the tap detector, as well as the mean square error (MSE) of SDCE‐NTD, are derived and confirmed via simulations. Comparisons are conducted between SDCE‐NTD and the common estimators in the beam training scenarios, where both dense and sparse channels exist. Results show that SDCE‐NTD reveals a significant gain in terms of MSE over both the conventional LS algorithm, which does not exploit the sparse nature of the channel, and the matching pursuit algorithm, which endeavours to exploit the sparsity. In addition, it is also demonstrated that the proposed estimator can approach the lower bound with high signal‐to‐noise ratio.

Power amplifier (PA) non‐linearity is extremely significant for 60 GHz millimetre‐wave communications, which distorts signal constellation seriously. In dealing with this problem, the commonly used digital predistortion (DPD) becomes unaffordable for 60 GHz systems in both power consumption and price. This study proposes to handle PA non‐linearity with distorted constellation (DCS) estimation and demodulation for 60 GHz systems with single‐carrier frequency‐domain equalisation transmission, which has a low implementation cost. Employing the least‐square (LS) algorithm, the DCS is estimated both before and after equalisation, where LS after equalisation has a lower computational complexity than LS before equalisation. Subsequently, the estimated DCS, instead of the standard constellation, is used as a criterion for demodulation, which is shown to achieve a significant improvement on the symbol‐error‐rate (SER) performance, especially when the non‐linear distortion is severe. Moreover, compared with DPD, the proposed method achieves a better SER performance and behaves more robustly in the low range of input power back‐off (IBO), whereas achieving a close SER performance in the high‐IBO range.

Key challenges in vehicular transportation and communication systems are understanding vehicular mobility and utilizing mobility prediction, which are vital for both solving the congestion problem and helping to build efficient vehicular communication networking. Most of the existing works mainly focus on designing algorithms for mobility prediction and exploring utilization of these algorithms. However, the crucial questions of how much the mobility is predictable and how the mobility predictability can be used to enhance the system performance are still the open and unsolved problems. In this paper, we consider the fundamental problem of the predictability limits of vehicular mobility. By using two large-scale urban city vehicular traces, we propose an intuitive but effective model of areas transition to describe the vehicular mobility among the areas divided by the city intersections. Based on this model, we examine the predictability limits of large-scale urban vehicular networks and obtain the maximal predictability based on the methodology of entropy theory. Our study finds that about 78%-99% of the location and above 70% of the staying time, respectively, are predicable. Our findings thus reveal that there is strong regularity in the daily vehicular mobility, which can be exploited in practical prediction algorithm design.

To cope with explosive vehicular traffic and ever-increasing application demands in the vehicular cellular network, opportunistic vehicular networks are used to disseminate mobile data by high-capacity device-to-device communication, which offloads significant traffic from the cellular network. In the current opportunistic vehicular data transmission, coding-based schemes are proposed to address the challenge of opportunistic contact. However, whether coding techniques can be beneficial in the context of vehicular mobile data offloading is still an open question. In this paper, we establish a mathematical framework to study the problem of coding-based mobile data offloading under realistic network assumptions, where 1) mobile data items are heterogeneous in terms of size; 2) mobile users have different interests to different data; and 3) the storage of offloading participants is limited. We formulate the problem as a users' interest satisfaction maximization problem with multiple linear constraints of limited storage. Then, we propose an efficient scheme to solve the problem, by providing a solution that decides when the coding should be used and how to allocate the network resources in terms of contact rate and offloading helpers' storage. Finally, we show the effectiveness of our algorithm through extensive simulations using two real vehicular traces.

As malware attacks become more frequently in mobile networks, deploying an efficient defense system to protect against infection and to help the infected nodes to recover is important to prevent serious spreading and outbreaks. The technical challenges are that mobile devices are heterogeneous in terms of operating systems, the malware infects the targeted system in any opportunistic fashion via local and global connectivity, while the to-be-deployed defense system on the other hand would be usually resource limited. In this paper, we investigate the problem of how to optimally distribute the content-based signatures of malware, which helps to detect the corresponding malware and disable further propagation, to minimize the number of infected nodes. We model the defense system with realistic assumptions addressing all the above challenges that have not been addressed in previous analytical work. Based on the framework of optimizing the system welfare utility, which is the weighted summation of individual utility depending on the final number of infected nodes through the signature allocation, we propose an encounter-based distributed algorithm based on Metropolis sampler. Through theoretical analysis and simulations with both synthetic and realistic mobility traces, we show that the distributed algorithm achieves the optimal solution, and performs efficiently in realistic environments.

Vehicular networks have been attracting increasing attention recently from both the industry and research communities. One of the challenges in this area is understanding vehicular mobility, which is vital for developing accurate and realistic mobility models to aid the vehicular communication and network design and evaluation. Most of the existing works mainly focus on designing microscopic level models that describe the individual mobility behaviors. In this paper, we explore the use of Markov jump process to model the macroscopic level vehicular mobility. Our proposed simple model can accurately describe the vehicular mobility and, moreover, it can predict various measures of network-level performance, such as the vehicular distribution, and vehicular-level performance, such as average sojourn time in each area and the number of sojourned areas in the networks. Model validation based on two large scale urban city vehicular motion traces confirms that this simple model can accurately predict a number of system metrics crucial for vehicular network performance evaluation. Furthermore, we propose two applications to illustrate that the proposed model is effective in analysis of system-level performance and dimensioning for vehicular networks.

To cope with explosive traffic demands on current cellular networks of limited capacity, Disruption Tolerant Networking (DTN) is used to offload traffic from cellular networks to high capacity and free device-to-device networks. Current DTN-based mobile data offloading models are based on simple and unrealistic network assumptions which do not take into account the heterogeneity of mobile data and mobile users. We establish a mathematical framework to study the problem of multiple-type mobile data offloading under realistic assumptions, where (i) mobile data are heterogeneous in terms of size and lifetime; (ii) mobile users have different data subscribing interests; and (iii) the storages of offloading helpers are limited. We formulate the objective of achieving maximum mobile data offloading as a submodular function maximization problem with multiple linear constraints of limited storage, and propose three algorithms, suitable for the generic and more specific offloading scenarios, respectively, to solve this challenging optimization problem. We show that the designed algorithms effectively offload data to the DTN by using both the theoretical analysis and simulation investigations which employ both real human and vehicular mobility traces.

With emergency of demands for local area services, device-to-device (D2D) communication is proposed as a vital technology component for the next generation cellular communication system to improve spectral reuse and enhance system capacity. These benefits depend on efficient interference management and resource allocation. Existing works usually consider these problems under a restricted cellular system consisting of a pair of D2D users and a cellular user. In this paper, we address the uplink resource allocation problem for multiple D2D and cellular users from a game theory point of view. Combing different transmission modes, mutual interferences, and resource sharing policy in a single utility function, we propose a coalition formation game based scheme. By theoretical analysis, we prove that it converges to Nash-stable equilibrium and further approaches to the system optimal solution with geometric rate. By extensive simulations, we demonstrate the effectiveness of our proposed scheme, which achieves the close optimum solution obtained by the centralized exhaustive algorithm and enhances the system sum rate by about 20%-65% without sacrifice of resource sharing fairness compared with several other practical strategies.

With the emerging demands for local area services of popular content downloading, device-to-device (D2D) communication is conceived as a vital technological component for next-generation cellular communication networking to increase the spectral efficiency and to enhance the system capacity. Targeting the application of mobile content downloading, we investigate the fundamental problems of how D2D communication improves the system performance of cellular networks and what is the potential effect of D2D communication, with the aid of the optimal solutions for the system resource allocation and mode selection obtained under the realistic user and mobility conditions. Specifically, by formulating a max-flow optimization problem that maximizes the content downloading flows from all the cellular base stations to the content downloaders through any possible ways of transmission, we obtain the theoretical upper bound to system content-downloading performance. Using realistic mobility model and trace driven simulations, we evaluate the effects of the different system settings on the performance of the mobile content-downloading system, and reveal the fundamental influence of D2D communication.

Owing to the uncertainty of transmission opportunities between mobile nodes, the routing in delay tolerant networks (DTNs) exploits the mechanism of store-carry-and-forward. In this routing mechanism, mobility plays an important role, and we need to control the mobility of nodes around the network to help with carrying messages from the source to the destination. This is a difficult problem because the nodes in the network may move arbitrarily and it is difficult for us to determine when the nodes should move faster to help the data transmission while considering the complicated energy consumption in such a network. At the same time, for most DTNs, the system energy is limited, and energy efficient algorithms are crucial to maximizing the message delivery probability while reducing the delivery cost. In this paper, we investigate the problem of energy efficient mobility speed control in epidemic routing of DTN. We model the message dissemination process under variable mobility speed by a continuous-time Markov model. With this model, we then formulate the optimization problem of the optimal mobility control for epidemic routing and obtain the optimal policy from the solution of this optimization problem. Furthermore, extensive numerical results demonstrate that the proposed optimal policy significantly outperforms the static policy with constant speed, in terms of energy saving. Copyright © 2012 John Wiley & Sons, Ltd.

In this paper, a novel lower-power multigigabit Viterbi decoder architecture is proposed for 60 GHz wireless personal-area network (WPAN) systems. Since add-compare-select (ACS) computation is the main bottleneck in decoding speed of Viterbi decoders, a balanced add-select-register-compare (BASIC) architecture is put forward to reduce critical path of ACS with low complexity. This work develops an 8-parallel BASIC Viterbi decoder for IEEE 802.15.3c standard to accomplish high-throughput and low-power goals. Based on synthesized results in 0.13 μm CMOS technology, the proposed decoder achieves up to 4 Gb/s throughput with energy efficiency 0.104 nJ/bit at 1.2 V.

In millimeter-wave communications (MMWC), multipath components (MPCs) have different steering angles and independent fadings. Park and Pan recently proposed a simple scheme for both transmitter and receiver to concurrently beamform towards multiple steering angles of MPCs to achieve both array gain and diversity gain. However, when the number of MPCs is greater than that of the transmit or receive antennas, a solution of antenna weight vector (AWV) does not exist. To cope with this problem, two multipath grouping (MPG) schemes, namely MPG-steering vector grouping and MPG-channel vector grouping, are proposed. These schemes group the MPCs that have close steering angles, and define an equivalent MPC for each non-empty group in both the transmitter and receiver. As the number of non-empty groups is always no larger than that of antennas in both the transmitter and receiver, a solution of AWV is guaranteed. Moreover, performance comparisons show that the two proposed MPG schemes achieve not only full diversity, but also an even better array gain than that of the scheme proposed by Park and Pan.

Opportunistic contact between moving vehicles is one of the key features in vehicular delay tolerant networks (VDTNs) that critically influences the design of routing schemes and the network throughput. Due to prohibitive costs to collect enough realistic contact recodes, to the best of our knowledge, little experiment work has been conducted to study the opportunistic contact patterns in large scale urban vehicular mobility environment. In this work, we carry out an extensive experiment involving tens of thousands of operational taxis in Beijing city. Based on studying this newly collected Beijing trace and the existing Shanghai trace, we find some invariant characteristics of the opportunistic contacts for large scale urban VDTN. Specifically, in terms of contact duration, we find that there exists a characteristic time point, up to which and including at least 80% of the distribution, the contact duration obeys an exponential distribution, while beyond which it decays as a power law one. This property is in sharp contrast to the recent empirical data studies based on human mobility, where the contact duration exhibits a power law distribution. In terms of contact interval, we find that its distribution can be modelled by a three-segmented distribution, and there exists a characteristic time point, up to which the contact interval obeys a power law distribution, while beyond which it decays as an exponential one. Our observations thus reveal fundamental patterns for large scale vehicular mobility, and further provide useful guidelines for the design of new urban VDTN' routing protocols and their performance evaluation.

Roadside Units (RSUs), which enable the vehicles-to-infrastructure communication, are deployed along the roadside to handle the growing communication demands as the number of vehicles increases. How to optimally deploy the RSUs and efficiently use them to enhance the vehicular network performance are important problems in the RSU-aided opportunistic networks. In order to solving these problems, we need to understand fundamental laws and properties of the opportunistic contacts. Due to the prohibitive costs to collect enough realistic contact records, to the best of our knowledge, little experiment work has been conducted to study the communication contact patterns in RSU-aided opportunistic networks. In this work, we carry out an extensive experiment involving tens of thousands of operational taxis in Beijing city. Based on this newly collected Beijing trace and the existing Shanghai trace, we find some invariant characters for the communication contacts for large scale RSU-aided vehicular opportunistic networks. In terms of inter-contact time between the RSUs and vehicles, we find it obeys exponential distribution, while in terms of contact rate, it follows Poisson distribution. Our observations reveal fundamental patterns for large scale vehicular mobility, and further provide useful guidelines for the design of new routing protocols and their performance evaluation for RSU-aided vehicular opportunistic networks.

Data plane programmability is regarded as an essential feature of future Internet. However, the flexibility of programmability has not been carefully considered. We present GrainFlow, a hardware-based packet processing platform supporting customization on every header bit's processing and adapting to packet header length variation. We evaluate GrainFlow on a Virtex-5 FPGA board. Experiment results show that users can flexibly redefine the data plane with only 10-20 rules and data plane forwarding rate can achieve wire-speed with acceptable latency increase.

Due to the extremely high oscillation frequency of 60 GHz systems, phase noise (PN) imported at both transmitter (Tx) and receiver (Rx) is significant, which degrades the transmission performance. This paper proposes an architecture employing iterative Tx and Rx PN compensation (ITR-PNC) for 60 GHz systems with single-carrier frequency-domain equalization (SC-FDE) transmission. The ITR-PNC iteratively performs PNC before equalization (PNC-BE) and PNC after equalization (PNC-AE), which are mainly set to manage Rx PN (RPN) and Tx PN (TPN), respectively. The PNC-BE and PNC-AE both exploit the one-tap least mean square (LMS) algorithm for PN extraction (PNE). In PNC-AE, the decision feedback result is used as the reference signal for PNE. And in PNC-BE, the reference signal is the signal replica, which is generated via the decision result and the estimated TPN of last iteration, and the estimated channel response. Comprehensive simulations indicate that the proposed architecture employing the proposed ITR-PNC achieves competitive bit-error-rate (BER) performance with only two iterations, for the cases whether only RPN or both TPN and RPN are taken into consideration.

Despite of various benefits such as load balance and energy saving virtual machine (VM) migration promises to provide, its application in realistic data centers is still limited due to the limitation of migration in the LAN environment and the unpredictable performance. Through separation of control plane and data plane, software defined network (SDN) provides the possibility for an alternate solution to overcome these limitations. In this work, we aim at designing and implementing a software defined approach for live VM migration to experiment the possibility. This paper presents the key challenges and our preliminary design result to address these challenges.

Understanding and characterizing the properties of vehicular networks has become hugely important because of their wide applications and fast development. Due to the unique property of vehicular networks that nodes change their locations at high speed in anytime, their connectivity is an important and unique property. In this poster, based on realistic vehicular mobility traces, we reveal the opportunistic connectivity property of large-scale urban vehicular networks. Moreover, through analysis, we unveil the fundamental relationships and tradeoffs between the opportunistic connectivity and network parameters in terms of data size, delivery delay, transmission energy, etc.

Knowledge of where vehicles will be in near future helps users in daily planning, traffic monitors in vehicles scheduling, advertisers in fixed point advertising, and especially helps in communication network source provisioning. In this paper, we analyze the predictability of taxi mobility based on their locations and time period records and we present a prediction method of taxis for their next locations in 15 seconds using Markov predictor. The historical location trace of each taxi is used to train the transition probability matrix of next location for our predictor, and we use 3 different scenarios to predict. Based on records from over 2,000 taxis in Shanghai, and over 14,000 taxis in Beijing, we are able to predict the next vehicular location with an accuracy of 82%.

A significant concern for cloud operators is to provide global network performance isolation for concurrent tenants. To address this, we propose M2cloud, a software defined framework providing scalable network control for multi-site data centers (DCs). M2cloud employs two-level controllers with decoupled functions, providing each tenant with flexible virtualization support in both intra- and inter-DC networks.

With the rapid growth of the demands for mobile data, wireless network faces several challenges, such as lack of efficient interconnection among heterogeneous wireless networks, and shortage of customized QoS guarantees between services. The fundamental reason for these challenges is that the radio access network (RAN) is closed and ossified. We propose OpenRAN, an architecture for software-defined RAN via virtualization. It achieves complete virtualization and programmability vertically, and benefits the convergence of heterogeneous network horizontally. It provides open, controllable, flexible and evolvable wireless networks.

Beamforming is necessary in 60GHz millimeter-wave communications in order to compensate for high path loss. A complete beamforming algorithm includes codebook design and beam training. The existing beamforming protocol of IEEE 802.15.3c standard has following flaws: (1) Not all three beamforming pattern types (quasi-omni pattern, sector and beam) have their own codebooks; (2) Almost every beam points to two directions, one of which is expected but the other one is unwanted; (3) Setup time of beam training is long. This paper proposes a codebook design and corresponding training procedure based on circular antenna array with a two-layer-structure. It allows every pattern type to own its corresponding codebook and highly directional antenna radiation pattern. The training setup time is reduced to around half of 3c training time. Performance evaluations also manifest that the proposed algorithm leads to less antenna gain loss and more robust performance than the 3c standard.

60 GHz communication supporting multigigabit data rate is a popular choice of industry for next generation short distance wireless communications. However, multi-Gsps ADC becomes a challenge in 60 GHz systems which have ultra wide Nyquist bandwidth. To reduce sampling rate of ADC in the estimation stage, we propose a joint signal-to-noise ratio (SNR) and channel estimation algorithm using compressed sensing (CS) theory. In 60 GHz systems, CS encoding and decoding strategies are optimized to maximize benefits from the design of pilots and estimators. For pilot design, m-sequence rather than conventional Bernoulli random sequence is selected owning to a better average restricted isometry property; for estimator design, a quasi-optimal channel and noise power estimation is put forward underlying signal subspace provided by CS algorithm. Simulation results show that the proposed algorithm reduces the sampling rate of ADC to 9.1% Nyquist bandwidth of 60 GHz communication. Moreover, the algorithm with this compressed sampling efficiently outperforms classical least square algorithm with Nyquist sampling as SNR exceeds 7 dB.

Modeling complicated vehicular mobility behavior and the associated network connectivity in large scale vehicular ad hoc network has been a challenging problem for the past several years. In this paper, we carry out extensive experiments involving thousands of operational taxies in Shanghai and Beijing cities. Studying the taxi traces on the vehicular connectivity, we observe that the vehicle isolation probability exhibits an exponential decay with the increase of transmission range. This observation is in sharp contrast to the most widely used system models such as Random Way Point and Random Walk, where the vehicle isolation probability changes with transmission range as exp(-λR2), where R is the transmission range. We propose a simple theoretical model to explain the exponential decay of vehicle isolation. Validation of our model is carried through comparisons between the synthetic trace and the real trace, and the results show that our mobility model has a good approximation to the real scenario. Our results give insights on the behavior of connectivity, thus providing fundamental guidelines on design of new vehicular mobility models, new data forwarding protocols and their performance analysis.

The newly emerged vehicular communication network is seen as a key technology for solving the increasingly serious vehicular traffic congestion as well as improving road safety, and applications of vehicular networks are also emerging at the same time. Predicting vehicular visiting time is vital to both solving the vehicular system problem and building efficient vehicular networking. It is an open and unsolved problem that how much the vehicular staying duration of visits to different areas can be predicted. In this paper, we use real vehicular traces in Beijing and Shanghai and an area partition model to explore the limit of predictability of the vehicular visiting time in different areas in large scale cities and analyze the effect of different precision and slot time on predictability. We conclude that using a proper time slot is an efficient way of prediction and a higher predictability can be achieved if the requirement for precision is reduced. Among all the cases we study, we find the highest potential predictability in Beijing and Shanghai in the case with smallest slot time and lowest requirement for precision.

The direct-conversion transceiver is an attractive architecture for 60 GHz wireless systems to meet the low-cost and low-power-consumption requirements, but it suffers from the IQ imbalance problem seriously. This paper adopts secondorder moment estimation to extract frequency-independent IQ imbalance parameters, and performs IQ compensation based on the estimation results. In order to achieve robust estimation, we employ a specific preamble sequence, where adjacent symbols have a fixed phase difference of π/2. The proposed estimation excels in the following aspects: (1) it completely eliminates the impact of inter-symbol interference (ISI) and carrier phase offset (CPO); (2) it is not degraded by carrier frequency offset (CFO), since the impact of which only lies in the negligible phase offset during only a symbol duration; (3) it has low computational complexity and can be implemented on hardware platform expediently. Simulation results indicate that the estimation algorithm has competitive performance over a large range of IQ imbalance, and with IQ compensation the bit-error-rate (BER) performance can be improved to that of the ideal case.

Contact duration between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs), that critically influences the design of routing schemes and network throughput. Due to prohibitive costs to collect enough realistic contact records, little experimental work has been conducted to study the contact duration in urban VANETs. In this work, we carry out an extensive experiment involving tens of thousands of operational taxis in Beijing city. Based on studying this newly collected Beijing trace and the existing Shanghai trace, we find an invariant characteristic that there exists a characteristic time point, up to which the contact duration obeys an exponential distribution that includes at least 80% of the whole distribution, while beyond which it decays as a power law one. This property is in sharp contrast to the recent empirical data studies based on human mobility, where the contact duration exhibits a power law distribution. Our observations thus provide fundamental guidelines for the design of new urban VANETs' routing protocols and their performance evaluation.

Rapid detection of the arrival of a packet is challenging in burst wireless communications, where many parameters are unknown, such as signal power, noise power and carrier phase offset. Due to the unknown noise power, it is hard to set appropriate thresholds for the existing common detectors under the Neyman-Pearson criterion, which results in vulnerable acquisition and poor performance. In order to solve this problem, we propose the generalized likelihood-ratio test (GLRT) approach for sequence-aided packet acquisition in this paper. GLRT detection is formulated under multipath channel. Moreover, false alarm probability and detection probability of GLRT are derived and confirmed via simulations. Comparisons are conducted between GLRT and the common detectors, as well as GLRT under different channels. Results show that GLRT basically reveals more competitive and robust performance than the common detectors in practice, with only a little extra hardware cost by using the provided recursive computation structure. Additionally, it is shown that fading results in significant deterioration for GLRT; whereas GLRT has ability to exploit multipath diversity to reduce fading effect and improve acquisition performance.

The signal constellation of 60 GHz millimeter wave (mmWave) communications is distorted by power amplifier (PA) nonlinearity seriously and the bit error rate (BER) performance declines, due to the huge bandwidth and high equivalent isotropic radiated power (EIRP), especially for quadrature amplitude modulation (QAM) signals. This paper aims at non-data-aided (NDA) distorted constellation (DC) estimation and demodulation to deal with PA nonlinearity. An estimation algorithm of expectation-maximization (EM) is proposed and the corresponding Cramer-Rao lower bounds (CRLBs) are calculated, then the estimated DC is used as reference for demodulation. Simulation results indicate that the means of the estimation results are unbiased and the mean square errors (MSEs) reach the CRLBs under easy requirements on signal-to-noise ratio (SNR) and output power back-off (OBO). Additionally, with PA nonlinearity, the BER performance of the presented DC demodulation is close to that of the ideal PA case, and much superior to that of the traditional standard constellation (SC) demodulation.

Vehicular Delay Tolerant Networks (VDTN) are used to distribute a large amount of mobile data by high-capacity device-to-device communication. Given a number of available vehicles in VDTN, the current vehicular data sharing models always utilize all of them to achieve the best effect, failing to balance the performance gained and cost of employing them. Taking the cost into account, we study the problem of the optimal number of vehicles to be deployed in the data sharing system, which considers using erasure codes to further increase the system efficiency if possible. By establishing the system goal which consists both the effectiveness and the cost of the vehicular network mathematically, we formulate the above problem as a utility function minimization problem. Finally, we solve the problem by theoretical derivation, and demonstrate the efficiency of the obtained solution through simulations using real vehicular traces of Beijing and Shanghai.

Network virtualization provides an alternative for wireless testbed to support multiple experiments simultaneously, as its properties of isolation, customization and efficiency are able to improve network resources utilization significantly. However, complex radio environment makes the employment of virtualization in wireless networks become a difficult problem, in which strict isolation across different experiments is hard to maintain. What is more, present radio experimental systems mostly exploit only Time Division Multiplexing, which may cause resources waste when the scale of experiments is relatively small. In this paper, we propose a time-space combined resources allocation scheme by taking advantage of both Time Division Multiplexing and Space Division Multiplexing. In this scheme, we first select a new time slot and some unscheduled experiments. Then we adopt Space Division Multiplexing to fit in as many experiments as possible in a time slot while ensuring required isolation across them. Extensive simulation shows that our scheme improves experimental resources utilization effectively, while each experiment in the same time slot have enough bandwidth among all nodes and the fairness of resources utility is also ensured.

Currently, Delay Tolerant Networking (DTN) research community urgently needs a credible and flexible platform to setup large scale DTN networks to accurately evaluate the performance of algorithms and protocols. In this work, we present such an emulation testbed. By using network virtualization and OpenFlow technologies to generate virtual DTN nodes and to simulate the opportunistic links controlled by mobility scenarios, our designed testbed is a realistic DTN protocol evaluation environment composing realistic networks and applications, which provide high credibility, flexible controlling, and supporting for large scale experiments.

Wireless traffic has two features: people have common interests in the hottest contents, and a large amount of traffic belongs to non-realtime services. Exploiting these two features, we propose a content dissemination system, integrating broadcast network and opportunistic network. In the proposed system, popular contents are broadcasted through broadcast network and then disseminated to users through opportunistic network. Such system can significantly reduces the same contents repeated transmission and efficiently delivers contents to their clients. Using a Markov model, we theoretically analyze content dissemination delay of the proposed system.

Contact interval between moving vehicles is one of the key metrics in vehicular ad hoc networks (VANETs), which is important to routing schemes and network capacity. In this work, by carrying out an extensive experiment involving tens of thousands of operational taxis in Beijing city, we find an invariant character that the contact interval can be modeled by a three-segmented distribution, and there exists a characteristic time point, up to which the contact interval obeys a power law distribution, while beyond which it decays as an exponential one. This property is in sharp contrast to the recent empirical data studies based on Shanghai vehicular mobility, where the contact interval exhibits only exponential distribution.

Groups of people with mobile phones using short range connections like WiFi and Bluetooth to propagate messages can be modeled as, with regard to regular absence of end-to-end connection, Delay Tolerant Networks (DTNs). The study of message transmission speed in such kind of networks has attracted increasing attention in recent years. In this paper, we present a realistic framework to model the message propagation process, and give a detailed expression of average information dissemination delay based on message size, users' selfishness, number of involved subscribers and other related parameters. We apply our model to real-life traces to assess its reliability by comparing the theoretical results with measured statistics, and present extensive upshots to evaluate the influence of various parameters on system performance.

The nonlinear distortion caused by power amplifier (PA) nonlinearity distorts the constellation and degrades the bit error rate (BER) performance of 60 GHz millimeter wave (mmWave) wireless local area network (WLAN) easily, due to the huge bandwidth and high equivalent isotropic radiated power (EIRP), especially for quadrature amplitude modulation (QAM) signals. This paper aims at data-aided (DA) distorted constellation (DC) estimation and demodulation to resist PA nonlinearity. A maximum likelihood (ML) estimation algorithm is proposed, and the corresponding Cramer-Rao lower bounds (CRLBs) are computed. Furthermore, we implement the demodulation based on the DC rather than the standard constellation (SC). Simulation results indicate that the means of the estimated parameters are unbiased and the mean square errors (MSEs) approach the CRLBs. Meanwhile, the proposed DC demodulation with PA nonlinearity achieves BER performance close to the ideal PA case, and evidently outperforms the traditional SC demodulation especially in the high-code-rate or uncoded case.

In network virtualisation, which enables multiple virtual routers to share one physical router, how to ensure the scalability and performance of concurrent virtual routers is a challenging problem in virtual router design. Since physical router only has limited memory resource, it is significant to efficiently store multiple forwarding tables for virtual routers. Motivated by the idea of diminishing the dissimilarities in forwarding tables, the authors propose a novel trie shifting scheme with depth adjusting, and finally obtain a memory-efficient shared trie for all forwarding tables. In this scheme, by diminishing the dissimilarity in the depth and in the shape, memory is saved by reducing the trie nodes needed in the shared trie. In the simulation, the scheme needs only 10% of trie nodes, compared with storing forwarding tables separately. Extensive simulation based on three sets of forwarding tables, which are collected from five backbone routers, shows that the scheme saves memory by reducing the number of trie nodes between 4.7 and 7.8%, compared with the latest scheme in related work. Moreover, this scheme achieves more improvement when the dissimilarity is increasing.

We study the performance of collaborative vehicular content dissemination, where the content is distributed within the network by vehicle-to-vehicle opportunistic communications and the vehicle nodes are equipped with directional antennas. Through analysing a large real-world vehicle trace, we adopt an accurate mobility model of Levy-walk to set up the realistic vehicular network simulation environment. Using a fluid approximation, we derive a theoretical model to depict the system performance of content dissemination time. The accuracy of the proposed analysis is confirmed by simulation results, which also show that the directional antenna performs better than the omni-directional antenna in our considered scenario, especially when the antenna beam is well scheduled with small beamwidth and high beam steering rate.

Some new medical applications, such as wireless endoscopy system for the diagnoses of whole human digestive tract and real-time endoscopic image monitoring, demand high speed transmission in wireless body sensor network (WBSN). This paper proposes a heterogeneous high speed wireless body sensor network based on ZIGBEE and single carrier ultra wideband (SC-UWB). Our system can choose high speed mode or low speed mode automatically according to the type of data source. Several measures are taken to miniaturize the nodes, lower the system complexity and reduce power consumption, offering system users great mobility and flexibility. We develop and validate a prototype WBSN, supporting four real-time high speed video streams and six low speed sensor data. The performance of the developed system is experimentally evaluated using prototype WBSN, and the ASIC has been designed and fabricated in the standard 0.18im CMOS technology, occupying a die area of 3.0mm * 3.0mm and consuming a dynamic power of 43.4280mw.

Network community needs a flexible platform for network experiment of new architectures, algorithms and protocols in the process of network innovation. However, building such a platform faces lots of challenges due to complicate requirements. In this paper, we present ExpoNet, a platform for rapid concurrent experiment of network innovation on the virtualized programmable infrastructure. ExpoNet integrates both software- and hardware-based router virtualization technologies to provide a flexible approach to configure and customize both the control plane and data plane while satisfying various experiment requirements. We implement ExpoNet, and design a management system to efficiently provide the users with convenient interface to access the platform. Based on its implementation, we present a live network experiment of Network Tomography, which infers the network inner performance according to the observed results of outside nodes. The experiment design and related results show the flexibility and effectiveness of our ExpoNet.

Due to the uncertainty of transmission opportunities between mobile nodes, Delay Tolerant Networks (DTNs) exploits the opportunistic forwarding mechanism. This mechanism requires nodes to forward messages in a cooperative and selfish way. However, in the real word, most of the nodes exhibit selfish behaviors such as individual and social selfishness. At the same time, the energy is usually limited in such networks. In this paper, we investigate how the selfish behaviors affect the performance of two-hop relaying multicast in energy-constrained DTN. We model the message delivery process under selfish behaviors and system energy constraint by a three- dimensional continuous time Markov chain. In terms of multicast performance, we investigate the average message transmission delay and transmission cost. Numerical results show that different selfish behaviors may have opposite impacts on different performance metrics in the energy-constrained DTN.

Mobility plays an important role in the message transmission of Disruption Tolerant Networks (DTNs), and we need to control the mobility of nodes around the network to efficiently carry and relay messages around the network. This is a challenging problem since the nodes in the network may move arbitrarily and it is hard for us to determine how the nodes should move, faster or slower, to help with the data transmission. Moreover, in such network, the energy is usually limited, and we need to consider its complicated energy consumption. In this paper, we investigate the problem of energy-constrained mobility velocity control in epidemic routing of DTN. We first model the message dissemination process under variable mobility velocity by a continuous-time Markov model, then formulate the optimal mobility control problem, and finally obtain the optimal threshold policy from the solution of this optimization problem. Furthermore, extensive numerical results demonstrate that the proposed optimal threshold policy significantly outperforms the static policy with constant velocity, in terms of energy saving.

This paper presents channel measurements for wireless body area network (WBAN) and provides performance evaluation using the model derived from measurement and the model in the final document of the IEEE802.15.6 channel modeling subcommittee. We measure the radio propagation from 3.0GHz to 5.0GHz which falls in ultra-wideband (UWB) frequency range in an anechoic chamber and give out a static model. 10 positions for medical entertainment and sports application are chosen to conduct measurement on a fat body, a normal body and a thin body in order to compare different path loss of different types of body for Chinese people. Moreover, we compare the bit error ratio (BER) of a single carrier UWB (SC-UWB) system which employs different receiving policies such as rake, equalizer and channel coding. The results show that slimmer people cause less path loss in the valid distance from 100mm to 1000mm. The measured model we derived has less multi-path effect than that of the model in the final report given by IEEE802.15.6 channel modeling subcommittee. Even though, rake receiver, equalizer and channel coding are needed to get a satisfying system performance.

In order to provide communication services in Delay Tolerant Networks (DTNs) where it lacks of end-to-end paths between the communication sources and destinations, a variety of routing schemes have been proposed. Consequently it is significant to accurately evaluate their performance to show their advantages and inferiority. At the same time, the energy is very limited in a large number of DTNs, such as sparse mobile sensor networks and emergency ad hoc networks, and it impacts the routing performance significantly. However, current related works ignore the influence of the energy constraint on the routing. In this paper, we investigate the performance of routing schemes for the energy-constrained DTNs. First, we model the two-hop relaying, epidemic routing and K-hop forwarding with energy constraint based on a two-dimensional continuous time Markov chain. Then, we obtain the system performance of message delivery delay and delivery cost by explicit expressions. By both simulation and numerical results, we demonstrate the accuracy of our proposed model and reveal that the energy constraint can actually avoid the message storms which are harmful to the systems in term of delivery cost and transmission contention.

In Delay Tolerant Networks (DTNs), there exists only intermittent connectivity between communication sources and destinations. In order to provide successful communication services for these challenged networks, a variety of relaying and routing algorithms have been proposed with the assumption that nodes are homogeneous in terms of contact rate and delivery cost. However, various applications of DTN have shown that mobile nodes can be divided into different classes in terms of their energy requirements and communication ability, and real application data have revealed the heterogeneous contact rates between node pairs. In this paper, we design an optimal relaying scheme for DTNs, which takes into account nodes' heterogeneous contact rates and delivery costs when selecting relays to minimise the delivery cost while satisfying the required message delivery probability. Extensive results based on real traces demonstrate that our relaying scheme requires the least delivery cost and achieves the largest maximum delivery probability, compared with the schemes that neglect nodes' heterogeneity.

The applications of dynamic content updates for a group of users, for example weather report and traffic congestion broadcast, have been shown to benefit significantly from Delay Tolerant Networks (DTN) communication mechanisms such as opportunistic contact and user sharing. In this paper, we study the dynamic content updates over energy-constrained DTN, and focus on its asymptotic properties about stability and scalability on the time and network size dimensions respectively. By introducing a continuous time Markov framework, we characterize the content dissemination system by both the source update & node sharing process and energy constraint. Based on this framework, we prove the system is stable when the time t approaches to infty, and the convergence rate is exponential. At the same time, by simulation we find that the content's average stable age decreases as Θ(√N) as the number of users N increases. Moreover, through extensive numerical results, we demonstrate the correctness of the theoretically obtained properties of stability.

We present TUNIE, a network platform for rapid concurrent experiment of network innovation on virtualized programmable infrastructure. TUNIE integrates both software-and hardware-based router virtualization technologies to provide a flexible approach to configure and customize both the control plane and data plane, and at the same time satisfied various experiment designing requirements. We implement TUNIE, and deploy it in Tsinghua University. Early experiment of algorithm evaluation verifies the efficiency TUNIE.

We collect data trace from taxis with GPS devices installed to study some important metrics of vehicle mobile networks. Such study may contribute to the future intelligent transportation systems and wireless communication protocols or algorithms designs. To our knowledge, only a few works in this area have been done before since such experiment is usually a huge cost. We took experiments on operative taxis in Beijing, who sent the geographical informations to the console automatically. In this paper, we focus on two of the most important metrics called flight length and pause time distribution in vehicle networks. Through analyzing our own trace datas as well as those collected by Shanghai Jiaotong University, we draw a conclusion that vehicle moving pattern actually shares some resemblances with the previous achievements on Levy-walk nature in human walk. In another word, cars run like human. Index Terms—Flight length; pause time; truncated pareto; Vehicle networks

In the Wireless Body Area Network (WBAN), the wireless channel is complex and distinctive because of the irregular shape of human body. The channel modeling methods and results are different from those in traditional narrow-band communication environments. In this paper, we present channel models for WBAN in Ultra wide band (UWB) frequency range 3-9 GHz. The channels are modeled statistically and the channel model parameters are derived from actual measured data in an office environment. An interesting common result is that different shape people have significantly differences in multipath parameters. Taking into account the characteristics of body shape, we provide a new classified small-scale channel model which has three kind of channel models: sparse, medium and dense multipath channel models. These models can be applied to different scenarios and improve the system design. We evaluated these models by delays and average number of mUltipaths with the measured data. Results prove the effectiveness of our models.

As malware attacks become more frequent in mobile networks, deploying an efficient defense system to protect against infection and to help the infected nodes to recover is important to contain serious spreading and outbreaks. The technical challenges are that mobile devices are heterogeneous in terms of operating systems, and the malware can infect the targeted system in any opportunistic fashion via local and global connectivity, while the to-be-deployed defense system on the other hand would be usually resource limited. In this paper, we investigate the problem of optimal distribution of content-based signatures of malware to minimize the number of infected nodes, which can help to detect the corresponding malware and to disable further propagation. We model the defense system with realistic assumptions addressing all the above challenges, which have not been addressed in previous analytical work. Based on the proposed framework of optimizing the system welfare utility through the signature allocation, we provide an encounter-based distributed algorithm based on Metropolis sampler. Through extensive simulations with both synthetic and real mobility traces, we show that the distributed algorithm achieves the optimal solution, and performs efficiently in realistic environments.

With the development of mobile networks, terminals' locations become increasingly valuable for both the whole system performance and terminals' applications or services. As knowing the knowledge of terminals' location information in advance would provide extern preparation time to accelerate response to terminals' requirements, location prediction plays a quite important role. Since most of the mobile terminals are human-carried devices, terminals' location prediction is actually the persons' location prediction. On the other hand, the research on social networks has experienced a fast development and provided a new kind of view on prediction. In our paper, we propose a location prediction scheme based on the idea of social correlation which is a kind of link between different terminals weighted by statistic results of history information.We also model topologies as sequences of snapshots to guide prediction. Few limits on the format of history location information record makes sure a strong adaptiveness of our scheme to various application's requirements.

Due to the lack of end-to-end paths between the communication sources and destinations, the routing of Delay Tolerant Networks (DTN) exploits the store-carry-and-forward mechanism. In this new routing mechanism, how to efficiently integrate forwarding and replication mechanisms is significant for achieving high message delivery ratio while requiring low delivery cost. In this paper, by using famous social properties such as communities and centrality, we design a routing scheme efficiently Integrating Forwarding and Replication (IFR), which allow node to replicate messages in the same community and to forward messages outside the community according to delivery weight obtained from node centrality. Realistic traces based simulations show that our scheme IFR is efficient in improving the message delivery performance on the tradeoff between the delivery success ratio and total delivery cost.

In order to provide communication service in the Intermittently Connected Mobile Networks (ICMN) where there is only intermittent connectivity between mobile nodes, a variety of epidemic-style routing algorithms have been proposed to achieve high message delivery probability. However, current works do not address the realistic environment that a message is split into multi frames to be transmitted. In this paper, we investigate the problem of optimal multi-frame message transmission for the ICMN. First, we formulate the optimization problem by introducing a continuous time Markov framework. Then, we theoretically derive the optimal policies for the message transmission by solving the formulated problem. Finally, we investigate the performance of the proposed optimal policies through extensive numerical results. We conclude that our optimal policies give the best performance in the multi-frame message transmission.

Traditional Delay-Locked-Loop (DLL) method can be hardly used in high-rate Direct-Sequence Ultra-Wideband (DS-UWB) systems due to dense multipath environment, low spreading factor and high-frequency clock. Most of the existing researches on tracking in UWB scenario focus on low-rate Impulse-Radio UWB (IR-UWB). In this paper, a non-Numerical Controlled Oscillator (NCO) periodical-pilot-assisted tracking method is proposed for practical high-rate DS-UWB systems. Analytical expressions of Equivalent Probability Density Function (EPDF) of timing error in locked state, Mean Square Error (MSE, or termed timing jitter) and Mean Time to Lose Lock (MTLL) are derived. Numerical results are presented, and then confirmed by means of extensive computer simulation results. These results corroborate our theoretical analysis, and show performance superiority of the proposed method over traditional DLL. Additionally, this proposed method has been used and justified in our practical DS-UWB system.

Running multiple virtual networks over a shared physical network is a promising way to support diverse applications, consequently network virtualization is viewed as the keystone of the next-generation architecture. However, decoupling the role of traditional ISPs into Infrastructure Providers (InPs) and Service Providers (SPs), also brings some new challenges to us. For example, how to fairly and efficiently share the sacred physical resources of InPs among multiple SPs is a key problem. The interaction between InPs and SPs, such as cooperation and competition, makes this topic even more complicated. In this paper, we develop a novel approach to encourage efficient behavior in solving the interaction between InPs and SPs by introducing economic incentives, in the form of Game Theory. Based on the non-cooperative game model, a bandwidth allocation scheme in the network virtualization environment is established, using the concept of the Nash Equilibrium. Then we propose an iterative algorithm to find the Nash Equilibrium and solve the bandwidth allocation problem. Finally, we demonstrate the convergence and the effectiveness of our scheme in the experiments.

Tracking constitutes a major challenge in Ultra-Wideband (UWB)communications due to dense multipath environment and low power consumption. Most of the existing studies on tracking fall within low rate Impulse Radio UWB (IR-UWB) scope, with the assumption that Inter-Frame Interference (IFI) or Inter-Symbol Interference (ISI) is absent. In this paper, we settle on high rate Direct-Sequence UWB (DS-UWB) systems, in which ISI is inevitable. A Periodical-Pilot-Assisted Tracking Loop with RAKE combining, which we termed PPATL, is proposed for high rate DS-UWB scenario. The proposed tracking loop can effectively combat ISI and capture multipath energy. Analytical expressions of Probability Density Function (PDF) of timing error in locked state, Mean Square Error (MSE, or termed timing jitter) and Mean Time to Lose Lock (MTLL) are derived. Numerical results are presented and then confirmed by means of extensive computer simulation results. These results corroborate our theoretical analysis. Additionally, this proposed PPATL has been used and justified in our realistic DS-UWB system.

Due to the uncertainty of transmission opportunities between mobile nodes, Delay Tolerant Networks (DTN) routing exploits the opportunistic forwarding mechanism. Optimal policies for opportunistic forwarding are crucial to maximizing the message delivery probability while reducing the forwarding cost. In this paper, we investigate the optimal opportunistic forwarding policies for the energy- constrained DTN by introducing a continuous time Markov framework to model the message dissemination. Based on this framework, we obtain the optimal static and dynamic policies by theoretical analysis and proof. Through extensive numerical results, we conclude that the performance of the optimal dynamic policy is better than that of the static policy. Among the dynamic policies, we find that the negative power function based optimal policy provides the best performance.

Topology information plays an important role in network management. The existing methods for topology inference based on end-to-end measurements need a threshold for general topologies, which is difficult to select to ensure the inference accuracy. In this paper, we propose a sort-based approach, named SBA, to infer the general topologies without using a threshold. First, a sort-based clustering algorithm, named SBC-AL, is proposed to cluster a group of nodes in which every node has at least one sibling. In the SBA, the nodes are classified into disjoint groups by a fan-out decrement mechanism. Then the SBA uses the SBC-AL to cluster the nodes group by group from the bottom up to infer the topology. We prove that the SBA is consistent and suitable for general topologies. The simulation results show that the SBA has a good performance in both accuracy and efficiency.

Many acquisition schemes have been proposed and investigated for Ultra-Wideband (UWB) systems, however, most of them setup for low duty-cycle Impulse Radio UWB (IR-UWB) signals, with the assumption that the pulse repetition time is greater than the maximum excess delay of channels, so that intra- and inter-frame interference can be bypassed. This assumption limits the transmission rate and cannot hold in high-rate Direct-Sequence UWB (DS-UWB) systems. In this paper, we propose a two-step data-aided acquisition scheme for high-rate DS-UWB systems. The first step is to quickly acquire an arbitrary train sequence; a two-stage correlation architecture is employed to combat Inter-Symbol Interference (ISI) and collect multipath energy, so as to speed up acquisition. Correspondingly, the second step is to search for the first arriving path with a maximum gap based search method (also new proposed), so as to improve Bit Error Rate (BER) performance. Closed-form expressions of Mean Acquisition Time (MAT), Overall Acquisition Probability (OAP) and False Alarm Rate (FAR) are derived. Based on them, parameter selections that minimize MAT and maximize OAP are discussed under certain FAR constrain. Simulations corroborate our theoretical results.

Resilience issue in Ethernet is becoming even more important when Ethernet is becoming more pervasive. The authors propose a local recovery scheme, named Ethernet ultra-fast switching (EUFS), to address this issue. EUFS is based on the multiple spanning tree protocol, which is the basics of both load balancing and fast recovery mechanisms in large-scale Ethernet networks. For each node, the authors construct a pair of protection trees rooted at this node. Normally, the traffic is forwarded along the working trees. When a link or node fails, the immediate upstream node switches the traffic, which intends to pass through the failed link or node, from the working trees to one of the protection trees rooted at itself. EUFS has the following features. First, it achieves an ultra-fast recovery from any single failure in two-connected networks. Second, it supports backward compatibility, because switches implementing EUFS can inter-operate with the legacy Ethernet switches.

Network tomography has been widely used recently to obtain the network internal characteristics by end-to-end measurement. In this study, the authors consider the problem of estimating link loss rates using network tomography. The existing work based on maximum likelihood estimator (MLE) uses iterative approximation to make the inference, which requires a long execution time for large scale network. To overcome this limitation, the authors propose a fast path-based approach (FPA) by explicit estimation to infer the loss rate of links. Instead of estimating the link loss rates directly, the authors first estimate the path loss rates that are used to derive the link loss rates. In addition, the path loss rates are inferred by a new estimator which is an explicit function of loss observations. The authors evaluate the accuracy of this approach through the analysis of the loss rate estimator and simulation. The estimator is proved to be consistent and have the same asymptotic variance as that of the MLE. The simulation results show that the estimated loss rates using the FPA correctly converge to the real loss rates.

Proxy mobile IPv6 (PMIPv6), a network-based IP mobility solution, is a promising approach for mobility management in all-IP wireless networks. How to enhance its handoff-related performance, such as handoff delay and signaling cost, is an important issue. Current solutions rely on approaches such as fast handoff, routing optimization and paging extension. However, the case of many correlated mobile nodes (MNs) moving together and taking handoffs at the same time has not been considered. In this paper, we propose a group-based handoff scheme for correlated MNs to enhance the performance of PMIPv6. We first propose a correlated MNs detection algorithm to detect MNs as groups. Based on this algorithm, we propose a group-based handoff procedure, and discuss its benefits and limitations. Furthermore, we evaluate the performance of PMIPv6 and our proposal through the analysis and simulation. The results show that the proposed scheme is very efficient in reducing both the handoff delay and signaling cost.

Delay Tolerant Networks (DTNs) are able to provide communication services in challenged networks where the end-to-end path between the source and destination does not exist. In order to increase the probability of delivery, DTN routing mechanisms may require nodes in the network to store and carry messages in their local buffer and replicate many copies. When the limited buffer is consumed, choosing the appropriate messages to drop is critical to maximizing the system performance. Current methods for this are sub-optimal or assume unrealistic conditions. In this paper, we propose an adaptive optimal buffer management scheme for DTN in the situations where the bandwidth is limited and messages vary in size. In our proposal, the mobility model is adjusted according to the nodes' historical meeting information, and the message dropping policies are designed to optimize certain network performance goals, such as maximizing the average delivery rate or minimizing the average delivery delay. Furthermore, we theoretically prove that the designed message dropping policies are optimal to achieve the best system performance.

Network-on-Chip (NoC) design methodology is considered as an important trend for large System-on-Chip design because of the bandwidth and power constraints in traditional synchronous bus architecture. In the design of packet-based NoC, packetizing mechanism has great effect on communication performance, area, and energy consumption of NoC. In this paper, we carry out detailed simulation to evaluate several kinds of packetizing mechanisms of NoC based on topology of Ring and Spidergon. Simulation results show that Condition-Waiting adaptive packetizing mechanism (CW-APM) is the best trade-off packetizing mechanism in NoC design.

Proxy Mobile IPv6 (PMIPv6), a network-based local mobility management solution, is being actively discussed and standardized by IETF recently. Compared with the host-based mobility protocols such as mobile IPv6, PMIPv6 separates mobile node from the involvement of handover procedure and promises easier deployment and better handover performance. The system performance analysis of PMIPv6 is significant to its design and deployment. However, current related work is either restricted to a single performance metric or not considered in a realistic network environment. In this paper, we propose an analytical framework based on IP-based cellular networks. Based on the framework, we investigate the performance of PMIPv6 with respect to various metrics, including signaling cost, handover delay and packet loss, and compare it with host-based mobility management protocols, such as Mobile IPv6, FMIPv6 and HMIPv6. The simulation results demonstrate the salient performance of PMIPv6.

Proxy mobile IPv6 (PMIPv6) is being actively standardized by IETF, and its salient features, such as supporting unmodified mobile node (MN), expedite the real deployment of IP mobility management. However, current research and development mainly focus on its unicast mechanism. In this paper, we propose two multicast listener mobility mechanisms for PMIPv6, named LMA-MLM and MAG-MLM, by drawing a lesson from the designing of Mobile IP (MIP) based multicast solutions. Moreover, we present qualitative and quantitative comparison between MlP-based solutions and our proposals. Although the research of PMIPv6-based multicast mobility is at an early stage yet, it is strongly expected to be a promising candidate solution for multicast mobility in the wireless mobile IP networks.

The accuracy of interconnect delay estimations can be improved by the method presented in this paper, in which the first two moments are obtained with ABCD matrix and a stable model to incorporate effects of transport delay into the delay estimate is developed. Simulation results show that the method share the same accuracy with traditional methods when rise time delay is much longer than transport delay and more accurate when the two are of the same order.

In this paper, a hierarchical cluster-based irregular topology customization method is proposed for Networks-on-Chip (NoC). This method contains three steps: (1) partitioning IPs into many hierarchical clusters; (2) generating a core network; (3) deleting redundant edge routers. Results show that the irregular topologies generated by our hierarchical cluster-based method consume less power when satisfying the bandwidth and port number constraints. Compared with the previous method, our method can save about 15.41% of power averagely for all benchmark applications. Particularly, for MPEG 4 decoder, our method can save 31.62% of power.

Network tomography has been widely used recently as an method to infer the network internal link-level characteristics by end-to-end measurement. In this paper, we consider the problem of estimating link loss rates using network tomography. The existing methods make the inference based on the whole tree of network, which is very complex for large scale network. To overcome this limitation, we propose a low complexity inference approach named LCIA. In the LCIA, we deploy monitors at internal nodes to reduce the complexity of inferring the link loss rates. It mainly consists of two steps. The first step is to deploy monitors at specific internal nodes to divide the original tree into several sub-trees with minimum depth. The second step is to infer the link loss rates of sub-trees by a new estimator which is an explicit function of loss measurements. The LCIA has the following features. First, it greatly reduces the inference complexity as the inference on the sub-trees is much simpler. Second, it improves the accuracy of the estimated results since the variance of loss estimator on sub-trees with lower depth is smaller than that on the original tree. The analytical and simulation results demonstrate that the LCIA outperforms the existing methods both on computation complexity and inference accuracy.

Monitoring traffic pattern is always an important approach to improve the performance of computer networks. In recent years, peer-to-peer (P2P) service gradually dominates the Internet traffic against traditional client-server (C-S) service such as Web. The changed situation of networks is mainly in two aspects. One is that popular P2P file-sharing applications require both board downstream and upstream bandwidth, which conflicts to asymmetry structure of the C-S service oriented networks, and another is that the topology of P2P overlay networks is varying with peers joining and leaving. The dramatic shift of Internet traffic may cause different patterns from that observed in early years. This leads a new round of Internet measurement, which requires effective monitoring of network-wide traffic within the region of ISP or autonomous system. Unfortunately, few of technologies can capture well the dynamics of C-S and P2P traffic in a macroscopic level. In this paper, we propose a method based on random matrix theory (RMT) for the detection of networkwide traffic pattern. Using only a few observation points, our method can monitor the macroscopic effect of the Internet traffic. We show that such macroscopic-level monitoring can be used to capture shifts in spatial-temporal patterns caused by P2P and C-S traffic, and inform where and when P2P and C-S traffic possibly arise in transit networks.

Localization is one of the fundamental problems in many wireless sensor networks applications. They require sensor nodes to obtain their absolute or relative geographical position. Although many localization algorithms have been proposed recently, most of them require the node to equip special range-determining or angel-determining hardware in order to obtain the position related information. In this paper, we propose a concentric beacons localization algorithm which is a range-free approach. Four anchors are set in the four corners of the square target region, and emit localizing beacons at different power levels, with the information of their position and the estimated range of the beacon. The nodes in this region receive these beacons and compute their positions correspondingly. In region of different scale, we propose two alternative schemes. The One for small scale has lower calculation complexity, and the other has better stability on large scale applications. Simulation results show the estimation error is less than 0.4 times the beacon interval.

We propose a fair and simple high-performance scheduling algorithm for combined input-crosspoint-queued switches, which is called tracking fair quota allocation (TFQA). Our algorithm is based on low-cost round-Robin scheme, which prioritizes the ports lagging behind our fair quota allocation scheme. Simulation shows that our algorithm could maintain over 99% throughput and achieve relatively low mean delay under almost all typical test traffic patterns, outperforming all known algorithms with the same implementation complexity, especially under heavy load scenarios. Moreover, our algorithm could provide max-min fairness under inadmissible traffic, better than many other typical algorithms proposed before.

Emulating Output Queued (OQ) Switch with sustainable implementation cost and low fixed delay is always preferable in designing high performance routers. The Switch-Memory-Switch (SMS) router, also called Distributed Shared Memory (DSM) Switch, provides a possible way towards practically emulating OQ in backbone switches. However, the architectures and algorithms for SMS switches ever proposed are either unpractical or only supporting First-Come-First-Serve (FCFS) scheduling policy, which cannot support QoS and is unfair for light traffic flow. Our improved SMS architecture and algorithm aim at emulating Push-In-First-Out (PIFO) OQ. We employ a randomly-dispatching first stage and resolve memory access conflictions on the second stage of the switch through a probabilistic matching method, at the cost of fixed delay and sufficiently low cell loss probability (PCLP). The relative fixed delay of our algorithms for an NXN switch is composed of two parts: N and (-3/2log2PCLP), which result from the pipelined scheduling process and probabilistic method, respectively. Moreover, both the total memory and fabric bandwidth of our architecture implemented on crossbar could be lowered to only 2NR, where R is line rate, counting read and write separately.