Influence Maximization (IM) is a crucial problem in social network analysis and has been extensively studied. Traditional approaches rely on designing approximation algorithms using network sampling; however, these methods lack generalizability and depend on an explicit definition of the influence diffusion model as input. Recently, researchers have turned to deep learning methods to address the shortcomings of traditional IM algorithms, but current learning-based IM algorithms still suffer from severe deficiencies in scalability and generalizability. In this paper, we propose IMGNN, a simple, efficient, effective, and generalizable algorithm powered by graph neural networks. IMGNN is a learning-based IM algorithm with strong generalization capability that reduces the overhead of model retraining while also providing fast seed set inference speed. As a result, IMGNN achieves better performance in terms of both efficiency and effectiveness compared to existing IM algorithms. Its exceptional generalization capability also enables it to be trained on small-scale graphs and directly infer the seed node set for large-scale graphs. IMGNN achieves these advantages by adopting a novel design for feature construction and model training, utilizing features constructed from influence propagations over graphs with randomly skipped nodes. This approach enables IMGNN to avoid overfitting to specific network structures while employing a unique technique to improve time efficiency by training on smaller networks. We have conducted extensive experiments using real-world social networks with up to 40 million nodes, and the results strongly demonstrate the superiority of IMGNN in terms of influence spread, seed node set inference speed, and generalizability.

Incomplete node features are ubiquitous in real-world scenarios such as user profiling and cold-start recommendation, which severely hinders the practical deployment of graph learning systems (e.g., GNNs). Existing solutions typically rely on diffusion-based structural smoothing (e.g., feature propagation) to impute missing values. However, we find that these approaches suffer from structural overfitting, leading to three progressive challenges: 1) performance degradation on disjoint graphs, 2) loss of semantic diversity due to over-smoothing, and 3) feature distribution shift when generalizing to unseen graph structures (inductive tasks). To address these challenges, we introduce the DART framework. It begins by employing Global Structural Augmentation (GSA), which establishes global correlations to bridge disjoint components and extend diffusion coverage. Building upon this, we design a semantic rectifier based on masked autoencoding. This module learns the latent feature manifold to recover natural semantic details. Crucially, we introduce a test-time distribution rectification mechanism that projects structurally biased features back onto the learned manifold during inference, effectively bridging the inductive distribution gap. Furthermore, considering that synthetic masking fails to reflect realworld sparsity, we present a new dataset Sailing collected from voyage records with naturally missing attributes. Extensive experiments on six public datasets and Sailing demonstrate that DART significantly outperforms state-of-the-art methods in both transductive and inductive settings. Our code and dataset are available at https://github.com/yfsong00/DART.

Video diffusion models (VDMs) have demonstrated remarkable capabilities in text-to-video (T2V) generation. Despite their success, VDMs still suffer from degraded image quality and flickering artifacts. To address these issues, some approaches have introduced preference learning to exploit human feedback to enhance the video generation. However, these methods primarily adopt the routine in the image domain without an in-depth investigation into video-specific preference optimization. In this paper, we reexamine the design of the video preference learning from two key aspects: feedback source and feedback tuning methodology, and present OnlineVPO, a more efficient preference learning framework tailored specifically for VDMs. On the feedback source, we found that the image-level reward model commonly used in existing methods fails to provide a human-aligned video preference signal due to the modality gap. In contrast, video quality assessment (VQA) models show superior alignment with human perception of video quality. Building on this insight, we propose leveraging VQA models as a proxy of humans to provide more modality-aligned feedback for VDMs. Regarding the preference tuning methodology, we introduce an online DPO algorithm tailored for VDMs. It not only enjoys the benefits of superior scalability in optimizing videos with higher resolution and longer duration compared with the existing method, but also mitigates the insufficient optimization issue caused by off-policy learning via online preference generation and curriculum preference update designs. Extensive experiments on the open-source video-diffusion model demonstrate OnlineVPO as a simple yet effective and, more importantly, scalable preference learning algorithm for video diffusion models.

Representative subset selection from data streams is a critical problem with wide-ranging applications in web data mining and machine learning, such as social media marketing, big data summarization, and recommendation systems. This problem is often framed as maximizing a monotone submodular function subject to a knapsack constraint, where each data element in the stream has an associated cost, and the goal is to select elements within a budget B to maximize revenue. However, existing algorithms typically rely on restrictive assumptions about the costs of data elements, and their performance bounds heavily depend on the budget B. As a result, these algorithms are only effective in limited scenarios and have super-linear time complexity, making them unsuitable for large-scale data streams. In this paper, we introduce the first linear-time streaming algorithms for this problem, without any assumptions on the data stream, while also minimizing memory usage. Specifically, our single-pass streaming algorithm achieves an approximation ratio of 1/8-ε under O (n) time complexity and O(k log 1/ε) space complexity, where k is the largest cardinality of any feasible solution. Our multi-pass streaming algorithm improves this to a (1/2-ε)-approximation using only three passes over the stream, with O (n/ε log 1/ε) time complexity and O(k/ε log 1/ε) space complexity. Extensive experiments across various applications related to web data mining and social media marketing demonstrate the superiority of our algorithms in terms of both effectiveness and efficiency.

Submodular maximization has found extensive applications in various domains within the field of artificial intelligence, including but not limited to machine learning, computer vision, and natural language processing. With the increasing size of datasets in these domains, there is a pressing need to develop efficient and parallelizable algorithms for submodular maximization. One measure of the parallelizability of a submodular maximization algorithm is its adaptive complexity, which indicates the number of sequential rounds where a polynomial number of queries to the objective function can be executed in parallel. In this paper, we study the problem of non-monotone submodular maximization subject to a knapsack constraint, and propose a low-adaptivity algorithm achieving an (1/8 − ϵ)- approximation with practical Õ(n) query complexity. Moreover, we also propose the first algorithm with both provable approximation ratio and sublinear adaptive complexity for the problem of non-monotone submodular maximization subject to a k-system constraint. As a by-product, we show that our two algorithms can also be applied to the special case of submodular maximization subject to a cardinality constraint, and achieve performance bounds comparable with those of state-of-the-art algorithms. Finally, the effectiveness of our algorithms is demonstrated by extensive experiments on real-world applications.

Multimodal recommendation enhances item representation in recommendation systems by integrating diverse modalities of item information beyond traditional ID-based features. This approach utilizes supplementary item details, including images, text, videos, and audio, to refine the accuracy of item representation and thereby boost the precision of recommendations. Multimodal recommendation has emerged as a vibrant field within the scope of systems that generate suggestions. It offers a powerful approach to address the challenges of data scarcity and the representation of long-tail content, thereby improving the overall quality of recommendations. However, the advancement in multimodal recommendation is currently hindered by two main obstacles. First, the process of extracting multimodal features from pre-trained models using either shallow or deep neural networks often results in insufficient data extraction or sparse recommendation data, leading to suboptimal model performance. Second, a significant portion of previous research has focused on integrating information across modalities, often overlooking the distinct characteristics inherent in different modalities. Addressing these challenges, we introduce a unique methodology titled “modality-disentangled featureextraction via knowledge distillation in multimodal recommendation systems” (MODEST). First, to tackle the aforementioned problems that arise when extracting multimodal features with either deep or shallow neural networks, our approach adopts a teacher–student network framework. In this framework, deep neural networks are utilized to extract representation vectors from text and image data. Feature fusion is then carried out via attention mechanisms, and semantic labels are employed as classification labels to derive three supervised learning loss functions. This process significantly enhances the teacher network’s capacity to extract multimodal features. Subsequently, the knowledge from the teacher network is transferred to the student network through knowledge distillation. The student network makes use of a shallow neural network, and during the inference stage, we rely on the student network. This strategy effectively resolves the issues of data sparsity in deep networks and insufficient information extraction in shallow networks. Second, to more effectively capture the similarities and distinct features among different modalities, we implement a disentangled modality decomposition technique. Through integrated mappings, it separately extracts text and image information from the teacher–student networks and decomposes them into cross-modality common information and cross-modality specific information. By applying the constraints of contrastive learning, we minimize the distance between cross-modality common information and maximize the separation of cross-modality specific information, promoting convergence with the aid of auxiliary loss. This effectively addresses the problem of cross-modality feature alignment. Lastly, we combine the recommendation loss function with the multiple loss constraints we have added to formulate a unified optimization objective function. To underscore the remarkable efficacy of our proposed model, we have executed comprehensive experiments and visualizations on several real-world datasets. The results distinctly show a significant enhancement in our model’s performance, allowing it to achieve a level of competitiveness against other methods.

Submodular maximization algorithms have found wide applications in various fields such as data summarization, recommendation systems, and active learning. In recent years, deletion-robust submodular maximization algorithms have garnered attention due to their significant implications in scenarios where some data points may be removed due to user preferences or privacy concerns, such as in recommendation systems and influence maximization. In this paper, we study the fundamental problem of submodular maximization with knapsack constraints and propose a robust streaming algorithm for it. To the best of our knowledge, our algorithm is the first to solve this problem for non-monotone submodular functions and can achieve an approximation ratio of 1/(6.82+2.63d)-ϵ under a near-optimal summary size of O(k+r), where k denotes the maximum cardinality of any feasible solution, d denotes the number of the knapsack constraints and r is the robustness parameter. For monotone submodular functions, our algorithm can achieve an approximation ratio of 1/(2+2d)-ϵ under a near-optimal summary size of O(k+r), significantly improving upon the best-known ratio of Ω((1/d-ϵ)^2). The empirical performance of our algorithm is extensively evaluated in several applications including influence maximization and recommendation systems, and the experimental results demonstrate the effectiveness of our algorithm.

Submodular optimization has been identified as a powerful tool for many data mining applications, where a representative subset of moderate size needs to be extracted from a large-scale dataset. In scenarios where data points possess sensitive attributes such as age, gender, or race, it becomes imperative to integrate fairness measures into submodular optimization to mitigate bias and discrimination. In this paper, we study the fundamental problem of fair submodular maximization subject to a knapsack constraint and propose the first streaming algorithm for it with provable performance guarantees for both monotone and non-monotone submodular functions. As a byproduct, we also propose a streaming algorithm for submodular maximization subject to a partition matroid and a knapsack constraint, significantly improving the performance bounds achieved by previous work. We conduct extensive experiments on real-world applications such as movie recommendation, image summarization, and maximum coverage in social networks. The experimental results strongly demonstrate the superiority of our proposed algorithms in terms of both fairness and utility.

In recent years, recommendation systems have become increasingly prevalent in various fields, facilitating quick access to the information users need. As a result, many models have been proposed to model user interests, leading to more accurate recommendation lists, superior user experience, and business value. However, characterizing the dynamically changing interests of users is a challenging task. User interests shift over time while maintaining some long-term interests, and at each time, users’ interests are diverse. To investigate the benefits of multidimensional interests for users, this article proposes to characterize user preferences based on their spatiotemporal interests. Utilizing temporal and spatial information is critical for improving recommendation accuracy. To achieve this, we present a novel approach called multilong short-term interest (MLSI) user representation for recommendation. This method extracts long-term and short-term interests of users from their behavioural sequences using decoupled self-supervised learning with different optimizers. Self-attention is then employed to capture the diverse interests of users through their behavioral sequences. Final, long-term and short-term interests, as well as diversified interests, are aggregated to represent user interests. Extensive experiments on real-world datasets show that MLSI not only outperforms state-of-the-art methods but also more effectively characterizes user interests, reflecting an improvement ranging from 5% to 20% across various metrics on multiple datasets.

Personalized Session-based recommendation (PSBR) is a general and challenging task in the real world, aiming to recommend a session’s next clicked item based on the session’s item transition information and the corresponding user’s historical sessions. A session is defined as a sequence of interacted items during a short period. The PSBR problem has a natural hierarchical architecture in which each session consists of a series of items, and each user owns a series of sessions. However, the existing PSBR methods can merely capture the pairwise relation information within items and users. To effectively capture the hierarchical information, we propose a novel hierarchical hypergraph neural network to model the hierarchical architecture. Moreover, considering that the items in sessions are sequentially ordered, while the hypergraph can only model the set relation, we propose a directed graph aggregator (DGA) to aggregate the sequential information from the directed global item graph. By attentively combining the embeddings of the above two modules, we propose a framework dubbed H3GNN (Hybrid Hierarchical HyperGraph Neural Network). Extensive experiments on three benchmark datasets demonstrate the superiority of our proposed model compared to the state-of-the-art methods, and ablation experiment results validate the effectiveness of all the proposed components.

Submodular maximization has wide applications in machine learning and data mining, where massive datasets have brought the great need for designing efficient and parallelizable algorithms. One measure of the parallelizability of a submodular maximization algorithm is its adaptivity complexity, which indicates the number of sequential rounds where a polynomial number of queries to the objective function can be executed in parallel. In this paper, we study the problem of non-monotone submodular maximization subject to a knapsack constraint, and propose the first combinatorial algorithm achieving an (8+epsilon)-approximation under O(log n) adaptive complexity, which is optimal up to a factor of O(loglog n). Moreover, under slightly larger adaptivity, we also propose approximation algorithms with nearly optimal query complexity of O(n), while achieving better approximation ratios. We show that our algorithms can also be applied to the special case of submodular maximization subject to a cardinality constraint, and achieve performance bounds comparable with those of state-of-the-art algorithms. Finally, the effectiveness of our approach is demonstrated by extensive experiments on real-world applications.

We revisit the classical problem of designing Budget-Feasible Mechanisms (BFMs) for submodular valuation functions, which has been extensively studied since the seminal paper of Singer [FOCS’10] due to its wide applications in crowdsourcing and social marketing. We propose TripleEagle, a novel algorithmic framework for designing BFMs, based on which we present several simple yet effective BFMs that achieve better approximation ratios than the state-of-the-art work for both monotone and non-monotone submodular valuation functions. Moreover, our BFMs are the first in the literature to achieve linear complexities while ensuring obvious strategyproofness, making them more practical than the previous BFMs. We conduct extensive experiments to evaluate the empirical performance of our BFMs, and the experimental results strongly demonstrate the efficiency and effectiveness of our approach.

The problem of constrained subset selection from a large data stream for profit maximization has many applications in web data mining and machine learning, such as social advertising, team formation and recommendation systems. Such a problem can be formulated as maximizing a regularized submodular function under certain constraints. In this paper, we consider a generalized k-system constraint, which captures various requirements in real-world applications. For this problem, we propose the first streaming algorithm with provable performance bounds, leveraging a novel multitudinous distorted filter framework. The empirical performance of our algorithm is extensively evaluated in several applications including web data mining and recommendation systems, and the experimental results demonstrate the superiorities of our algorithm in terms of both effectiveness and efficiency.

A lot of applications in web economics need to maximize the revenue under a budget for payments and also guarantee the truthfulness of users, so Budget-Feasible Mechanism (BFM) Design has aroused great interests during last decade. Most of the existing BFMs concentrate on maximizing a monotone submodular function subject to a knapsack constraint, which is insufficient for many applications with complex objectives or constraints. Observing this, the recent studies (e.g., [4, 5, 11]) have considered non-monotone submodular objectives or more complex constraints such as a k-system constraint. In this study, we follow this line of research and propose truthful BFMs with improved performance bounds for non-monotone submodular objectives with or without a k-system constraint. Our BFMs leverage the idea of providing random prices to users while deferring the decision on the final winning set, and are also based on a novel randomized algorithm for the canonical constrained submodular maximization problem achieving better performance bounds compared to the state-of-the-art. Finally, the effectiveness and efficiency of our approach are demonstrated by extensive experiments on several applications about social network marketing, crowdsourcing and personalized recommendation.

Streaming Session-Based Recommendation (SSBR) is a challenging problem as user preferences in sessions are continually drifting with sessions generated chronologically. In recent years, some SSBR models have been proposed to address this problem by reservoir technique and Graph Neural Networks (GNN) which help to preserve a representative sketch of the historical data and extract item transition information in sessions. However, there are two critical problems in existing methods: (1) most existing methods only focus on the local session information without exploiting the information of other sessions and users; (2) GNN models in existing SSBR methods are unable to capture the importance of different user features. To address the problems mentioned above, we propose a novel architecture namedGlobalItem andUser embeddingAssistedGraphNeuralNetwork (GIUA-GNN) for combining the global user and item information in an attentional manner with local session information for the recommendation. We also propose a novel architecture of graph neural network which utilizes the attention mechanism for better extracting the importance of different features of user embeddings namedBi-directedAttentionalGraphConvolutionalNetwork (BA-GCN). Extensive experiments on three different sizes of real-world datasets have been conducted to demonstrate the superiority of our model on metrics MRR and Recall.

Thanks to billions of users in online social networks (OSNs), viral marketing becomes one of the most effective promotion channels for various new products or campaigns. Influence maximization is a classic problem in viral marketing, which has been extensively studied in the past two decades. Existing algorithms for influence maximization, however, mostly focus on single machine processing. To address the influence maximization problem on a massive scale, we design distributed algorithms via a cluster of machines, which can effectively speed up the computation while maintaining the state-of-the-art (1 -1/e-c)-approximation guarantee. Our distributed algorithms consist of two building blocks: (i) distributed reverse influence sampling, and (ii) element-distributed maximum coverage. We carry out extensive experiments on real datasets with millions of nodes and billions of edges to demonstrate the scalability of our distributed algorithms for both influence maximization and maximum coverage. In particular, our distributed algorithms accelerate the state-of-the-art IMM algorithm by 31x-56x times using a machine with 64 cores.

As an effective tool to extract representative summary from big data, data summarization is often cast into a submodular maximization problem. Although submodular maximization problem has a long research history, and many related algorithms have been born, these algorithms often have high computational complexity and are difficult to apply to the field of big data. Therefore, in recent years, research on low-time complexity algorithms has attracted extensive attention. In this paper, we mainly focus on the non-monotone submodular maximization problem under the setting of a knapsack and a partition matroid constraints. To solve it, we design a practical, effective and efficient algorithm called FASKP, that can achieve an approximation ratio of near 7.2 + ϵ using near linear runing time. As far as we know, the FASKP algorithm achieves the best approximate guarantee compared to existing algorithms with low-time complexity. Furthermore, we demonstrate how to apply FASKP in three real data summarization applications: image summarization (10K images), movie recommendation (11K movies), and revenue maximization on social networks (Youtube). Experimental results in real scenarios show that, compared with existing algorithms, the FASKP algorithm can consistently obtain the highest utility, which validates its superiority.

The interactive graph search (IGS) problem aims to locate an initially unknown target node leveraging human intelligence. In IGS, we can gradually find the target node by sequentially asking humans some reachability queries like "is the target node reachable from a given node x?". However, human workers may make mistakes when answering these queries. Motivated by this concern, in this paper, we study a noisy version of the IGS problem. Our objective in this problem is to minimize the query complexity while ensuring accuracy. We propose a method to select the query node such that we can push the search process as much as possible and an online method to infer which node is the target after collecting a new answer. By rigorous theoretical analysis, we show that the query complexity of our approach is near-optimal up to a constant factor. The extensive experiments on two real datasets also demonstrate the superiorities of our approach.

Chromatic Correlation Clustering (CCC) (introduced by Bonchi et al. [6]) is a natural generalization of the celebrated Correlation Clustering (CC) problem, introduced by Bonchi et al. [6]. It models objects with categorical pairwise relationships by an edge-colored graph, and has many applications in data mining, social networks and bioinformatics. We show that there exists a $2.5$-approximation to the CCC problem based on a Linear Programming (LP) approach, thus improving the best-known approximation ratio of 3 achieved by Klodt et al. [21] . We also present an efficient heuristic algorithm for CCC leveraging a greedy clustering strategy, and conduct extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithm.

Information diffusion prediction studies how information items spread in the social network. Previous works either concentrate on leveraging a single diffusion sequence once a time or using the social relationships among users. However, diffusion sequence as a simple chain structure cannot fully capture complex interactions between users. And the diffusion paths of all messages can construct a dynamic diffusion graph. In this paper, we propose a new dynamic structural-temporal graph neural network(DySTGNN) to jointly utilize the structural pattern of the social network and the temporal feature underlying the diffusion graph. What's more, the experimental results have shown that DySTGNN significantly outperforms many recent competitive works on three real-world datasets, which validate the effectiveness of our methods.

Submodular optimization has numerous applications such as crowdsourcing and viral marketing. In this paper, we study the problem of non-negative submodular function maximization subject to a $k$-system constraint, which generalizes many other important constraints in submodular optimization such as cardinality constraint, matroid constraint, and $k$-extendible system constraint. The existing approaches for this problem are all based on deterministic algorithmic frameworks, and the best approximation ratio achieved by these algorithms (for a general submodular function) is $k+2\sqrt{k+2}+3$. We propose a randomized algorithm with an improved approximation ratio of $(1+\sqrt{k})^2$, while achieving nearly-linear time complexity significantly lower than that of the state-of-the-art algorithm. We also show that our algorithm can be further generalized to address a stochastic case where the elements can be adaptively selected, and propose an approximation ratio of $(1+\sqrt{k+1})^2$ for the adaptive optimization case. The empirical performance of our algorithms is extensively evaluated in several applications related to data mining and social computing, and the experimental results demonstrate the superiorities of our algorithms in terms of both utility and efficiency.

Traffic flow prediction is of great importance for city risk assessment and traffic management, which profoundly impacts people’s lives and property. However, the traffic forecasting task is difficult due to the complex interactions and spatial-temporal characteristics. Previous studies usually focus on capturing the spatial correlations and temporal dependencies separately, meanwhile, off-the-shelf studies neglect the effect of explicit differential information. What’s more, there is a lack of effective methods for capturing potential interactions. In this paper, we propose a novel model for traffic flow prediction, named as Attention-based Bicomponent Synchronous Graph Convolutional Network (ABSGCN). This model is able to capture the synchronous spatial-temporal information with a fused signal matrix and potential interactions by constructing a novel edgewise graph, which can remedy the shortcomings in traditional approaches. Extensive experiments are implemented on two real-world datasets and the results demonstrate that our model outperforms other baselines by a margin.

We consider the revenue maximization problem in social advertising, where a social network platform owner needs to select seed users for a group of advertisers, each with a payment budget, such that the total expected revenue that the owner gains from the advertisers by propagating their ads in the network is maximized. Previous studies on this problem show that it is intractable and present approximation algorithms. We revisit this problem from a fresh perspective and develop novel efficient approximation algorithms, both under the setting where an exact influence oracle is assumed and under one where this assumption is relaxed. Our approximation ratios significantly improve upon the previous ones. Furthermore, we empirically show, using extensive experiments on four datasets, that our algorithms considerably outperform the existing methods on both the solution quality and computation efficiency.

We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. The prior best-known deterministic approximation ratio for this problem is $\frac{1}{4}-\epsilon$ under $\mathcal{O}(({n^4}/{\epsilon})\log n)$ time complexity. We show that this deterministic ratio can be improved to $\frac{1}{4}$ under $\mathcal{O}(nr)$ time complexity, and then present a more practical algorithm dubbed TwinGreedyFast which achieves $\frac{1}{4}-\epsilon$ deterministic ratio in nearly-linear running time of $\mathcal{O}(\frac{n}{\epsilon}\log\frac{r}{\epsilon})$. Our approach is based on a novel algorithmic framework of simultaneously constructing two candidate solution sets through greedy search, which enables us to get improved performance bounds by fully exploiting the properties of independence systems. As a byproduct of this framework, we also show that TwinGreedyFast achieves $\frac{1}{2p+2}-\epsilon$ deterministic ratio under a $p$-set system constraint with the same time complexity. To showcase the practicality of our approach, we empirically evaluated the performance of TwinGreedyFast on two network applications, and observed that it outperforms the state-of-the-art deterministic and randomized algorithms with efficient implementations for our problem.

We propose the first budget-limited multi-armed bandit (BMAB) algorithm subject to a union of matroid constraints in arm pulling, while at the same time achieving differential privacy. Our model generalizes the arm-pulling models studied in prior BMAB schemes, and it can be used to address many practical problems such as network backbone construction and dynamic pricing in crowdsourcing. We handle the exploitation versus exploration tradeoff in our BMAB problem by exploiting the combinatorial structures of matroids, and reduce the searching complexity of arm selection based on a divide-and-conquer approach. Our algorithm achieves a uniform logarithmic regret bound with respect to B and ɛ-differential privacy, where B is the budget for pulling the arms with random costs. Without differential privacy, our algorithm achieves a uniform logarithmic regret bound with respect to B, which advances the asymptotic regret bounds achieved by prior BMAB algorithms. We performed side-by-side comparisons with prior schemes in our experiments. Experimental results show that our purely-combinatorial algorithm not only achieves significantly better regret performance, but also is more than 20 times faster than prior BMAB schemes, which use time-consuming LP-solving techniques.

We study the min-cost seed selection problem in online social networks for viral marketing, where the goal is to select a set of seed nodes with the minimum total cost such that the expected number of influenced nodes in the network exceeds a predefined threshold. We propose several algorithms that outperform the previous studies both on the theoretical approximation ratio and on the experimental performance. In the case where the nodes have heterogeneous costs, our algorithms are the first bi-criteria approximation algorithms with polynomial running time and provable approximation ratio. In the case where the users have uniform costs, our algorithms achieve logarithmic approximation ratio and provable time complexity which is smaller than that of the existing algorithms in orders of magnitude. We conduct extensive experiments using real social networks. The experimental results show that, our algorithms significantly outperform the existing algorithms both on the total cost and on the running time, and also scale well to billion-scale networks.

Recently, the advances on programmable data plane (PDP) promote the studies on the network virtualization in a PDP-based substrate network (SNT). In this paper, we address the table resource virtualization and network slicing in PDP-based SNTs. We first leverage the idea of “Big-Switch” to design an effective table resource virtualization scheme in which the flow tables of a virtual switch (V-SW) can be installed in multiple adjacent substrate switches (S-SWs) according to their table sizes, while the feasible table size(s) on each S-SW are determined based on the global information of the SNT. By doing so, we can regulate the flow tables in the S-SWs in a more organized way to minimize memory fragmentation. Next, we address the network slicing based on the virtualization scheme, and come up with a three-layer VNE problem. To the best of our knowledge, such a VNE problem has not been studied before and the existing algorithms designed for traditional two-layer VNE problems can hardly solve it. We formulate an integer linear programming (ILP) model to solve the VNE problem exactly, and also design a time-efficient heuristic that can provide near-optimal solutions. Finally, we implement the heuristic in TPVX, which is a network hypervisor based on protocol-oblivious forwarding (POF), and also improve its performance by introducing source routing. The new TPVX is experimentally demonstrated in a real network testbed, and the results verify that our proposal maintains the additional latency caused by the three-layer VNE well and would not degrade the network services in virtual networks (VNTs).

In this work, we try to further enhance the flexibility and cost-effectiveness of network function virtualization (NFV) by considering virtual network function service chaining (vNF-SC) in a heterogeneous NFV environment that can instantiate vNFs on virtual machines (VMs), docker containers, and SmartNICs. Specifically, we first lay out the network model, build a real network testbed that supports vNF deployment on kernel-based VMs, docker containers, and commercial SmartNICs, and then conduct experiments to measure the throughput and latency of traffic processing and memory usage of four types of vNFs implemented on them. Next, based on the measurement results, we formulate an integer linear programming (ILP) model to optimize the application-aware vNF-SC provisioning in the heterogenous NFV environment. Finally, we design and perform two experiments to demonstrate that our heterogeneous NFV environment can combine the advantages of VM/docker container/SmartNIC to provide enhanced flexibility for realizing on-demand and application-aware vNF-SC composition.

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform cost. We propose an O(log K)-competitive randomized algorithm Camul and an O(K)-competitive deterministic algorithm Camul-Det, where K is the total number of slots in all caches. Both online algorithms achieve asymptotically optimal competitive ratios, and can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform existing schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and can perform consistently well on various settings of experiment parameters.

Traffic volume estimation is critical to the intelligent transportation engineering. Previous state-of-the-art studies mainly focus on measuring two types of traffic volume: “point” traffic (i.e., the number of vehicles passing a given location) and “point-to-point” traffic (i.e., the number of vehicles traversing between two given locations) during each measurement period. In this paper, we extend this line of research from single-period to multiple periods and study new problems of estimating the number of k-persistent vehicles that pass a location or two different locations in at least k-out-of-t predefined measurement periods. We propose two novel k-persistent traffic estimators with privacy-preserving for the point and point-to-point traffic models, respectively. Through theoretical analysis, we prove that our solution can solve more general traffic measurement problems and employ stronger privacy preserving, i.e., E-differential privacy, than the existing studies. We also demonstrate the effectiveness and the accuracy of the proposed estimators through extensive experiments based on real transportation traffic flows in Shenzhen, China for five consecutive working days. The numerical results show that the estimators can achieve a tradeoff between the estimation accuracy and privacy preservation through proper parameter setting.

We consider the edge uncertainty in an undirected graph and study the k -median (resp. k -center) problems, where the goal is to partition the graph nodes into k clusters such that the average (resp. minimum) connection probability between each node and its cluster's center is maximized. We analyze the hardness of these problems, and propose algorithms that provide considerably improved approximation guarantees than the existing studies do. Specifically, our algorithms offer (1 -- 1/e)-approximations for the k -median problem and (OPTck)-approximations for the k -center problem, where OPTck is the optimal objective function value for k -center. In addition, our algorithms incorporate several non-trivial optimizations that significantly enhance their practical efficiency. Extensive experimental results demonstrate that our algorithms considerably outperform the existing methods on both computation efficiency and the quality of clustering results.

Recently, the proliferation of event-based social services has made it possible for organizing personalized offline events through the users' information shared online. In this paper, we study the budget-constrained influential social event organization problem, where the goal is to select a group of influential users with required features to organize a social event under a budget B. We show that our problem is NP-hard and can be formulated as a submodular maximization problem with mixed packing and covering constraints. We then propose several polynomial time algorithms for our problem with provable approximation ratios, which adopt a novel “surrogate optimization” approach and the method of reverse-reachable set sampling. Moreover, we also consider the case where the influence spread function is unknown and can be arbitrarily selected from a set of candidate submodular functions, and extend our algorithms to address a “robust influential event organization” problem under this case. Finally, we conduct extensive experiments using real social networks to test the performance of our algorithms, and the experimental results demonstrate that our algorithms significantly outperform the prior studies both on the running time and on the influence spread.

Recently, Mobile Crowdsourcing (MC) has aroused great interest on the part of both academic and industrial circles. One of the key problems in MC is designing the proper mechanisms to incentivize user participation, as users are typically self-interested and must consume a substantial amount of MC resources/costs. Although considerable research has been devoted to this problem, the majority of studies have neglected the privacy issue in mechanism design. In this study, we consider the scenario where a mobile crowdsourcing platform aims to maximize the crowdsourcing revenue under a budget constraint, and users are interested in maximizing their utility while keeping their cost private. We design differentially-private mechanisms for such a scenario under an offline setting where users bid their costs simultaneously and under an online setting where user bids are revealed one by one. We show that our mechanisms simultaneously achieve provable performance bounds with respect to several measures, including revenue, differential privacy, truthfulness, and individual rationality. Finally, we also conduct extensive numerical experiments to demonstrate the effectiveness of our approach.

Measuring traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problem of persistent traffic measurement, which was not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose three estimators for privacy-preserving persistent traffic measurement: one for point traffic, one for point-to-point traffic, and another for three-point traffic. After that, we present a general framework to measure persistent traffic that go through more than three locations. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

The combination of network virtualization and software-defined networking enables an infrastructure provider to create software-defined virtual networks (vSDNs) over a shared substrate network (SNT), for supporting new network services more timely and cost-effectively. Meanwhile, as both the services and traffic in the Internet are becoming more and more dynamic, how to properly maintain vSDNs in a dynamic network environment exhibits increasing importance but still has not been fully explored. In this paper, we conduct a study on how to realize proactive and hitless vSDN reconfiguration to balance the utilization of ternary content-addressable memory (TCAM) in a dynamic SNT. Specifically, we consider both algorithm design and system prototyping. From the algorithmic perspective, we try to solve the problems of “what to reconfigure” and “how to reconfigure”. A selection algorithm is designed to proactively choose the virtual switches (vSWs) that should be migrated to other substrate switches for balancing TCAM utilization, i.e., solving what to reconfigure. Then, for the problem of how to reconfigure, i.e., where to re-map the selected vSWs and the virtual links connecting to them, we formulate a mixed integer linear programming model to solve it exactly, and design two heuristics to improve time efficiency. Next, we move to the system part, implement the proposed algorithms in our protocol-oblivious forwarding enabled network virtualization hypervisor system, and conduct experiments to demonstrate proactive and hitless vSDN reconfiguration. The experimental results indicate that our proposal does make vSDN reconfiguration transparent to the vSDNs' virtual controllers and proactive, and when reconfiguring a vSDN with live traffic, it achieves hitless operations without traffic disruption.

Many people use mobile devices as the basic sensing units since they are cheap and convenient. Several incentive mechanisms have been proposed in past literature to incentivize worker participation in such sensing units. However, existing auction-based privacy-preserving incentive mechanisms only consider asymptotically truthful property apart from exactly dominant strategy truthful property while maximizing crowdsourcers' revenue. Past research has shown that a single mechanism model is difficult to solve this problem, so we designed a novel hybrid mechanism with differential privacy to strike the balance between utility property and truthful bidding property. The hybrid mechanism, denoted as PQHM, consists of price-privacy auction-based mechanism (denoted as PPAM) and quality-privacy auction-based mechanism (denoted as QPAM). PPAM can get great social utility and QPAM can get truthful bidding property. We could randomize between running the two mechanisms according to a probability distribution (defined as λ) to guarantee the reasonable utility for the crowdsourcers, and give each bidder a strict positive incentive to report truthfully. This paper found that the hybrid incentive mechanism has the characteristics of differential private, exactly truthful, individual rationality, reasonable platform profitability, and calculation efficiency. Furthermore, the selection probability λ of PQHM is linearly controllable.

In this work, we try to address the problem of memory fragmentation in ternary content addressable memory (TCAM) in programmable data plane (PDP), by designing and implementing a novel network hypervisor for PDP, namely, TPVX. TPVX realizes the virtualization of table resources in PDP with global consideration, i.e., when mapping tenant flow tables to physical switches, TPVX considers their table sizes and the pre-formatted sub-tables in the physical network to improve TCAM utilization and avoid memory fragmentation. Our experimental results verify that with TPVX, the utilization of the table resources in PDP can be improved dramatically and the extra processing latency due to the newly-introduced overheads can be maintained well simultaneously.

With network virtualization, an infrastructure provider can create virtual software-defined networks (vSDNs) over a shared substrate network and lease them to service providers (SPs). This enables the SPs to run their Big Data applications in a short time-to-market, flexible and cost-effective way. However, in a dynamic network, both the instances of vSDNs and the traffic in each vSDN can change over time, which would degrade the optimality of the embedding schemes of vSDNs and even cause serious reliability issues. Therefore, in this work, we extend our protocol-oblivious forwarding (POF) based network virtualization hypervisor (NVH) system (i.e., PVX) to realize hitless vSDN migration to avoid ternary content addressable memory (TCAM) depletion. Specifically, we design the PVX system to realize the vSDN migration that is transparent to the controllers of vSDNs and would cause zero or very few packet losses. The proposed PVX is then implemented in a real network testbed, and we conduct experiments to verify its effectiveness.

Recently, the proliferation of event-based social services has made it possible for organizing personalized offline events through the users' information shared online. In this paper, we study the budget-constrained influential social event organization problem, where the goal is to select a group of influential users with required features to organize a social event under a budget B. We show that our problem is NP-hard and can be formulated as a submodular maximization problem with mixed packing and covering constraints. We then propose several polynomial time algorithms for our problem with provable approximation ratios, which adopt a novel "surrogate optimization approach and the method of reverse-reachable set sampling. Compared with some related work that can only handle special cases of our problem but with exponential time complexity, our algorithms are much more efficient, and their superiorities on both the running time and the influence spread are demonstrated through extensive experiments using real social networks."

Traffic measurement in high-speed networks has many applications in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a new problem called k-persistent spread estimation, which measures persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t can be arbitrarily defined in user queries. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. Yet, it is under-investigated as the prior work only addresses a special case with a questionable assumption. Designing an efficient and accurate k -persistent estimator requires us to use bitwise SUM (instead of bitwise AND typical in the prior art) to join the information collected from different periods. This seemly simple change has fundamental impact on the mathematical process in deriving an estimator, particular over space-saving virtual bitmaps. Based on real network traces, we show that our new estimator can accurately estimate the k -persistent spreads of the flows. It also performs much better than the existing work on the special case of measuring elements that appear in all periods.

Viral marketing through online social networks (OSNs) has aroused great interests in the literature. However, the fundamental problem of how to optimize the "pure gravy" of a marketing strategy through influence propagation in OSNs still remains largely open. In this paper, we consider a practical setting where the "seed nodes" in an OSN can only be probabilistically activated by the product discounts allocated to them, and make the first attempt to seek a discount allocation strategy to maximize the expected difference of profit and cost (i.e., revenue) of the strategy. We show that our problem is much harder than the conventional influence maximization issues investigated by previous work, as it can be formulated as a non-monotone and non-submodular optimization problem. To address our problem, we propose a novel "surrogate optimization" approach as well as two randomized algorithms which can find approximation solutions with constant performance ratios with high probability. We evaluate the performance of our approach using real social networks. The extensive experimental results demonstrate that our proposed approach significantly outperforms previous work both on the revenue and on the running time.

Given a social network G , the influence maximization (IM) problem seeks a set S of k seed nodes in G to maximize the expected number of nodes activated via an influence cascade starting from S. Although a lot of algorithms have been proposed for IM, most of them only work under the non-adaptive setting, i.e., when all k seed nodes are selected before we observe how they influence other users. In this paper, we study the adaptive IM problem, where we select the k seed nodes in batches of equal size b , such that the choice of the i -th batch can be made after the influence results of the first i - 1 batches are observed. We propose the first practical algorithms for adaptive IM with an approximation guarantee of 1 − exp(ξ − 1) for b = 1 and 1 − exp(ξ − 1 + 1/ e ) for b > 1, where ξ is any number in (0, 1). Our approach is based on a novel AdaptGreedy framework instantiated by non-adaptive IM algorithms, and its performance can be substantially improved if the non-adaptive IM algorithm has a small expected approximation error. However, no current non-adaptive IM algorithms provide such a desired property. Therefore, we further propose a non-adaptive IM algorithm called EPIC, which not only has the same worst-case performance bounds with that of the state-of-the-art non-adaptive IM algorithms, but also has a reduced expected approximation error. We also provide a theoretical analysis to quantify the performance gain brought by instantiating AdaptGreedy using EPIC, compared with a naive approach using the existing IM algorithms. Finally, we use real social networks to evaluate the performance of our approach through extensive experiments, and the experimental experiments strongly corroborate the superiorities of our approach.

Software-defined networking (SDN) has been considered as a break-through technology for the next-generation Internet. It enables fine-grained flow control that can make networks more flexible and programmable. However, this might lead to scalability issues due to the possible flow state explosion in SDN switches. SDN-based source routing can reduce the volume of flow-tables significantly by encoding the path information into packet headers. In this paper, we leverage the protocol-oblivious forwarding instruction set to design protocol-oblivious source routing (POSR), which is a protocol-independent, bandwidth-efficient, and flow-table-saving packet forwarding technique. We lay out the packet format for POSR, come up with the packet processing pipelines for realizing unicast, multicast, and link failure recovery, and implement POSR in a protocol-oblivious forwarding-enabled SDN network system. Experiments are then performed in a network testbed, which consists of 14 stand-alone SDN switches, to validate the advantages of POSR. Specifically, we compare POSR with several OpenFlow-based benchmarks for unicast, multicast, and link failure recovery, and confirm that POSR can reduce flow-table utilization effectively, shorten path setup latency and expedite link failure recovery.

In the Internet, to enable emerging network services such as e-Health to be delivered to numerous people anytime and anywhere, mobility management plays an important role. In this work, we leverage the protocol-oblivious forwarding (POF) to design a novel network system that can realize highly-efficient mobility management and overcome the drawbacks of existing approaches. Moreover, we explore the forwarding plane programmability provided by POF to realize dynamic virtual network function (vNF) deployment for traffic adaption. We implement our system and conduct experiments to verify that it functions well for NFV-assisted mobility management and achieves reduced handover latency and enhanced QoE.

We study how to embed virtual software-defined networks (vSDNs) cost-effectively over a substrate network with distributed network virtualization hypervisors (NVHs) for virtual datacenter (vDC) formulation to support Big Data applications. Specifically, we try to jointly optimize the embedding schemes of the control and data planes of each vSDN, i.e., to minimize the data plane's resource consumption and limit the number of NVHs used in the control plane simultaneously. We first formulate an integer linear programming (ILP) model to solve the problem exactly, and then design a heuristic to reduce the time complexity. Simulation results suggest that our proposed algorithms can embed vSDNs cost-effectively and significantly outperform the existing scheme based on global resource capacity (GRC).

In this paper, we investigate a largely extended version of classical MAB problem, called networked combinatorial bandit problems. In particular, we consider the setting of a decision maker over a networked bandits as follows: each time a combinatorial strategy, e.g., a group of arms, ischosen, and the decision maker receives a rewardresulting from her strategy and also receives a side bonusresulting from that strategy for each arm's neighbor. This is motivated by many real applications such as on-line social networks where friends can provide their feedback on shared content, therefore if we promote a product to a user, we can also collect feedback from her friends on that product. To this end, we consider two types of side bonus in this study: side observation and side reward. Upon the number of arms pulled at each time slot, we study two cases: single-play and combinatorial-play. Consequently, this leaves us four scenarios to investigate in the presence of side bonus: Single-play with Side Observation, Combinatorial-play with Side Observation, Single-play with Side Reward, and Combinatorial-play with Side Reward. For each case, we present and analyze a series of zero regret polices where the expect of regret over time approaches zero as time goes to infinity. Extensive simulations validate the effectiveness of our results.

Mobile crowdsourcing has been proposed as a promising approach for urban data collection, but it has also brought the critical problem of designing proper mechanisms to incentivize user participation. Most previous work on crowdsourcing incentivization has assumed that each user holds a single private cost for participation or behaves in a "win all or nothing" (a.k.a. "single-minded") manner. However, in some crowdsourcing applications such as Amazon's Mechanical Turk, the users are usually "multi-minded" in the sense that each of them holds heterogeneous private costs for different tasks and only performs a portion of her/his interested tasks according to the announced payments. To address this problem, we propose LIME, an onLine prIcing mechanism to incentivize Multi-minded usErs under the scenario where the users arrive sequentially in an arbitrary order. We show that the design of LIME involves solving a "dummy semi-bandits with multiple knapsacks and random costs" problem, which has not been investigated before, and we also prove that LIME achieves several desirable properties including computational efficiency, budget feasibility, truthfulness, individual rationality and low regret on the utility. Finally, the effectiveness of LIME as well as its superiorities over prior related work are demonstrated through extensive simulations.

Due to the explosive proliferation of mobile cloud computing applications, much data needs to be transmitted between mobile users and clouds, incurring a huge traffic demand on cellular networks. Mobile offloading is a promising approach to address this challenge. In this paper, we focus on the problem of offloading many deadline-sensitive data items to some WiFi networks with capacity constraints; that is, how to schedule each data item to the WiFi networks, so that we can offload as many data items before their deadlines as possible, while taking the constraints of transmission capacity into consideration. This problem involves a probabilistic combination of multiple 0-1 knapsack constraints, which differs from existing problems. To solve this problem, we propose a greedy oFfline Data Offloading (FDO) algorithm, achieving an approximation ratio of 2. Also, we propose an oNline Data Offloading (NDO) algorithm, which has a competitive ratio of 2. Additionally, we extend our problem to a more general scenario where WiFi transmission costs are heterogeneous. We design a Heterogeneous Data Offloading (HDO) algorithm to solve the extended problem, and give its performance analysis. Finally, we demonstrate the significant performances of our algorithms through extensive simulations based on some real-world and synthetic WiFi datasets.

Mobile crowdsensing has been considered as a promising approach for large scale urban data collection, but has also posed new challenging problems such as incentivization and quality control. Among the other incentivization approaches, posted pricing has been widely adopted by commercial systems due to the reason that it naturally achieves truthfulness and fairness and is easy to be implemented. However, the fundamental problem of how to set a right posted price in crowdsensing systems remains largely open. In this paper, we study a quality-aware Bayesian pricing problem for mobile crowdsensing where the users' sensing costs and qualities for participating in crowdsensing are drawn from known distributions learned from historical information, and our goal is to choose an appropriate posted price to recruit a group of participants with reasonable sensing qualities for robust crowdsensing, while the total expected payment is minimized. We show that our problem is NP-hard and has close ties with the well known Poisson Binomial Distributions (PBD). To solve our problem, we first discover some non-trivial submodular properties of PBD, which have not been reported before, then we propose a novel "ironing method" that transforms our problem from a non-submodular optimization problem into a submodular one by leveraging the newly discovered properties of PBD. Finally, with the ironing method, an approximate algorithm with provable performance ratio is provided, and we also conduct extensive numerical simulations to demonstrate the effectiveness of our approach.

With the explosive proliferation of smartphones, many mobile cloud computing applications have emerged in recent years. These applications generally involve many data transmissions between mobile users and the cloud side. In order to reduce the monetary cost of these data transmissions, an effective approach is to offload partial data traffic from cellular networks to WiFi networks, when mobile users pass by some WiFi Access Points (APs). In this paper, we focus on the problem of offloading many deadline-sensitive data items to some WiFi APs with capacity constraints; that is, how to schedule each data item to the WiFi APs, so that we can offload as many data items before their deadlines as possible, while taking the constraints of transmission capacity into consideration. This problem involves a probabilistic combination of multiple 0-1 knapsack constraints, which differs from existing problems. To solve this problem, we propose a greedy oFfline Data Offloading (FDO) algorithm, and prove that this algorithm can achieve an approximation ratio of 2. Moreover, we extend our data offloading strategy to the online decision case, and propose an oNline Data Offloading (NDO) algorithm, which has a competitive ratio of 2. Finally, we demonstrate the significant performances of our algorithms through extensive simulations.

Mobile crowdsensing leverages mobile devices (e.g., smart phones) and human mobility for pervasive information exploration and collection; it has been deemed as a promising paradigm that will revolutionize various research and application domains. Unfortunately, the practicality of mobile crowdsensing can be crippled due to the lack of incentive mechanisms that stimulate human participation. In this paper, we study incentive mechanisms for a novel Mobile Crowdsensing Scheduling (MCS) problem, where a mobile crowdsensing application owner announces a set of sensing tasks, then human users (carrying mobile devices) compete for the tasks based on their respective sensing costs and available time periods, and finally the owner schedules as well as pays the users to maximize its own sensing revenue under a certain budget. We prove that the MCS problem is NP-hard and propose polynomial-time approximation mechanisms for it. We also show that our approximation mechanisms (including both offline and online versions) achieve desirable game-theoretic properties, namely truthfulness and individual rationality, as well as O(1) performance ratios. Finally, we conduct extensive simulations to demonstrate the correctness and effectiveness of our approach.

Mobile crowdsensing has been intensively explored recently due to its flexible and pervasive sensing ability. Although many crowdsensing platforms have been built for various applications, the general issue of how to manage such systems intelligently remains largely open. While recent investigations mostly focus on incentivizing crowdsensing, the robustness of crowdsensing toward uncontrollable sensing quality, another important issue, has been widely neglected. Due to the non-professional personnel and devices, the quality of crowdsensing data cannot be fully guaranteed, hence the revenue gained from mobile crowdsensing is generally uncertain. Moreover, the need for compensating the sensing costs under a limited budget has exacerbated the situation: one does not enjoy an infinite horizon to learn the sensing ability of the crowd and hence to make decisions based on sufficient statistics. In this paper, we present a novel framework, Budget LImited robuSt crowdSensing (BLISS), to handle this problem through an online learning approach. Our approach aims to minimize the difference on average sense (a.k.a. regret) between the achieved total sensing revenue and the (unknown) optimal one, and we show that our BLISS sensing policies achieve logarithmic regret bounds and Hannan-consistency. Finally, we use extensive simulations to demonstrate the effectiveness of BLISS.

The recent development of 60GHz technology has made hybrid Data Center Networks (hybrid DCNs) possible, i.e., augmenting wired DCNs with highly directional 60GHz wireless links to provide flexible network connectivity. Although a few recent proposals have demonstrated the feasibility of this hybrid design, it still remains an open problem how to route DCN traffics with guaranteed performance under a hybrid DCN environment. In this paper, we make the first attempt to tackle this challenge, and propose the RUSH framework to minimize the network congestion in hybrid DCNs, by jointly routing flows and scheduling wireless (directional) antennas. Though the problem is shown to be NP-hard, the RUSH algorithms offer guaranteed performance bounds. Our algorithms are able to handle both batched arrivals and sequential arrivals of flow demands, and the theoretical analysis shows that they achieve competitive ratios of O(log n), where n is the number of switches in the network. We also conduct extensive simulations using ns-3 to verify the effectiveness of RUSH. The results demonstrate that RUSH produces nearly optimal performance and significantly outperforms the current practice and a simple greedy heuristics.

Because data dissemination is crucial to wireless sensor networks (WSNs), its energy efficiency and reliability are of paramount importance. While achieving these two goals together is highly nontrivial, the situation is exacerbated if WSN nodes are duty-cycled (DC) and their transmission power is adjustable. In this paper, we study the problem of minimizing the expected total transmission power for reliable data dissemination (multicast/broadcast) in DC-WSNs. Due to the NP-hardness of the problem, we design efficient approximation algorithms with provable performance bounds for it. To facilitate our algorithm design, we propose the novel concept of Time-Reliability-Power (TRP) space as a general data structure for designing data dissemination algorithms in WSNs, and the performance ratios of our algorithms based on the TRP space are proven to be$ {\cal O}(\log \Delta \log k)$for both multicast and broadcast, where$\Delta $is the maximum node degree in the network and$k$is the number of source/destination nodes involved in a data dissemination session. We also conduct extensive simulations to firmly demonstrate the efficiency of our algorithms.

Mobile crowdsensing has been intensively explored recently due to its flexible and pervasive sensing ability. Although many crowdsensing platforms have been built for various applications, the general issue of how to manage such systems intelligently remains largely open. While recent investigations mostly focus on incentivizing crowdsensing, the robustness of crowdsensing toward uncontrollable sensing quality, another important issue, has been widely neglected. Due to the nonprofessional personnel and devices, the quality of crowdsensing data cannot be fully guaranteed, hence the revenue gained from mobile crowdsensing is generally uncertain. Moreover, the need for compensating the sensing costs under a limited budget has exacerbated the situation: one does not enjoy an infinite horizon to learn the sensing ability of the crowd and hence to make decisions based on sufficient statistics. In this paper, we present a novel framework, Budget LImited robuSt crowdSensing (BLISS), to handle this problem through an online learning approach. Our approach aims to minimize the difference on average sense (a.k.a. regret) between the achieved total sensing revenue and the (unknown) optimal one, and our BLISS sensing policy is shown to be asymptotically optimal. Finally, we use extensive simulations to demonstrate the effectiveness of BLISS.

Because data dissemination is crucial to Wireless Sensor Networks (WSNs), its energy-efficiency and reliability are of paramount importance. While achieving these two goals together is highly non-trivial, the situation is exacerbated if WSN nodes are duty-cycled (DC) and their transmission power is adjustable. In this paper, we study the problem of minimizing the expected total transmission power for reliable data dissemination (multicast/broadcast) in DC-WSNs. Due to the NP-hardness of the problem, we design efficient approximation algorithms with provable performance bounds for it.

Inspired by the recent invention of a high efficiency Wireless Power Transfer (WPT) technique, we propose in this paper the Perpetual Wireless Networks (PWNs) as a novel wireless networking paradigm. Similar to the conventional wireless (data) access point, a PWN has a power access point, from which electrical power is injected and distributed into the network in a form of multi-hop transfer. Consequently, we lay our focus on this new type of multi-hop flow problems concerning not data but power. We formulate and analyze a set of such power flow problems (some are joint with data flow), and we devise algorithms to solve them. The intriguing insights obtained from solving these optimization problems offer instructive guidance for future studies on real PWN constructions.

In duty-cycled wireless sensor networks, the nodes switch between active and dormant states, and each node may determine its active/dormant schedule independently. This complicates the Minimum-Energy Multicasting (MEM) problem, which was primarily studied in always-active wireless ad hoc networks. In this paper, we study the duty-cycle-aware MEM problem in wireless sensor networks both for one-to-many multicasting and for all-to-all multicasting. In the case of one-to-many multicasting, we present a formalization of the Minimum-Energy Multicast Tree Construction and Scheduling (MEMTCS) problem. We prove that the MEMTCS problem is NP-hard, and it is unlikely to have an approximation algorithm with a performance ratio of (1 - 0(1)) ln Δ, where Δ is the maximum node degree in a network. We propose a polynomial-time approximation algorithm for the MEMTCS problem with a performance ratio of O (H(Δ + 1)), where H(·) is the harmonic number. In the case of all-to-all multicasting, we prove that the Minimum-Energy Multicast Backbone Construction and Scheduling (MEMBCS) problem is also NP-hard and present an approximation algorithm for it, which has the same approximation ratio as that of the proposed algorithm for the MEMTCS problem. We also provide a distributed implementation of our algorithms, as well as a simple but efficient collision-free scheduling scheme to avoid packet loss. Finally, we perform extensive simulations, and the results demonstrate that our algorithms significantly outperform other known algorithms in terms of the total transmission energy cost, without sacrificing much of the delay performance.

Wireless Sensor Networks (WSNs) have acquired new features recently, i.e., both the sensor and the antenna of a node can be directional. This brings new challenges to the Connected Coverage (CoCo) problem, where a finite set of targets needs to be monitored by some active sensor nodes, and the connectivity of these active nodes with the sink must be retained at the same time. In this paper, we study the Minimum-Energy Connected Coverage (MeCoCo) problem in WSNs with Omni-directional (O) and Directional (D) features, aiming at minimizing the total energy cost of both sensing and connectivity. Considering different combinations of O and D features, we study the MeCoCo problem under four cases, namely: O-Antenna and O-Sensor (OAOS), O-Antenna and D-Sensor (OADS), D-Antenna and D-Sensor (DADS), as well as D-Antenna and O-Sensor (DAOS). We prove that the MeCoCo problem is NP-hard under all these cases, and present approximation algorithms with provable approximation ratios. In particular, we propose a constant-approximation for OAOS, and polylogarithmic approximations for all other cases. Finally, we conduct extensive simulations and the results strongly confirm the effectiveness of our approach.

In multi-radio wireless mesh networks, each node can be equipped with multiple network interface cards tuned to different channels. In this paper, we present a routing and channel selection algorithm for reducing the broadcast redundancy in multi-radio wireless mesh networks. In our approach, the concept of Relaying Channel Redundancy is proposed, which is the sum of the number of different channels selected by each forward node in a broadcast tree. Our aim is to build a broadcast tree with minimum Relaying Channel Redundancy. We prove that building such a broadcast tree is a NP-hard problem, and propose an approximate algorithm for it. Our algorithm has an approximation ratio of at most 20delta5+2, wheredeltais the number of available non-overlapping channels. Finally, the distributed implementation of our algorithm is also presented.