The rise of mixed reality (MR) as a key mobile application draws interest. Wireless headsets in femtocell networks complicate resource optimization. This study proposes a resource allocation for volumetric MR streaming in multi-BS settings. Neural networks predict viewing directions; based on predictions, confidence, and layers, the algorithm customizes vision scope and quality to boost utility. Simulations show superior performance.

The emergence of mixed reality (MR) as a significant application in mobile networks has garnered significant attention. Wireless headsets enable unrestricted user movement within femtocell networks comprising numerous small base stations, offering a promising solution for MR applications. However, the complexity of these systems poses challenges in optimizing resource allocation across base stations. This paper proposes a novel resource allocation method for volumetric MR streaming in multi-base-station environments. The method consists of two phases. Firstly, the method uses neural networks to model and forecast users’ viewing directions. Leveraging these predictions, their confidence levels, and layer characteristics, the algorithm adjusts video quality for each user and allocates transmission resources across base stations to optimize overall performance. Through comprehensive analysis, we prove that this novel problem is NP-hard and show that our approach achieves a performance within a bounded gap from the optimal solution. Simulation results reveal that our proposed algorithm outperforms existing techniques, enhancing aggregate performance across diverse scenarios.

Recently, Non-Fungible Tokens (NFTs) have attracted attention as valuable digital assets. However, NFT marketplaces face complex challenges in simultaneously recommending optimal pricing to sellers and desirable NFTs to buyers. Unlike conventional marketplaces that focus only on balancing demand and supply between sellers and buyers, these tasks are complicated by intricate value interdependencies arising from diverse buyer preferences, budgets, trait rarities, and the unprecedented breeding mechanisms. This paper formulates the NFT Project Pricing/Purchasing Recommendation (NP3R) problem, aiming to achieve a competitive equilibrium that concurrently optimizes seller revenue and buyer utility. We introduce BANTER, an iterative algorithm that jointly determines (1) optimal NFT purchases for buyers (via NFT-REC), considering breeding utility and current prices; and (2) optimal pricing for sellers (via PRICEREC), based on aggregated demand from NFT-REC. To efficiently manage the combinatorial complexity of breeding, we devise Optimal Parent Pair Selection (OPPS) and Heterogeneous Parent Set Selection (HPSS) schemes. Theoretical analysis guarantees BANTER to converge to a competitive equilibrium. Experiments on five real-world NFT datasets demonstrate its effectiveness in enhancing both seller revenue and average buyer utility. Source code: https://github.com/jimmy-academia/BANTER

Non-fungible tokens (NFTs) have emerged as a transformative innovation in art and technology, relying heavily on social networks for promotion and revenue generation. The value of NFTs is profoundly influenced by their scarcity, rarity, and unique breeding mechanisms, which present novel challenges for viral marketing strategies. In this paper, we introduce a new research problem of NFT Revenue Maximization (NRM), which focuses on maximizing revenue from the perspective of NFT marketplaces by optimally selecting users for viral marketing campaigns (NFT airdrops) and determining the ideal quantities of NFTs to release. We prove the hardness of NRM and propose an approximation algorithm named Quantity and Offspring-Oriented Airdrops (QOOA). Our algorithm leverages the concepts of Scarcity-Conscious Revenue and Valuation-based Quantity Inequality to prune suboptimal airdrops and quantities at an early stage. To further enhance revenue through NFT breeding, QOOA identifies and incentivizes Rare Trait Collectors to acquire multiple NFTs with rare traits, facilitating the breeding of high-value offspring. Experimental results demonstrate that QOOA significantly outperforms baselines, achieving up to 3.8 times higher revenue in large-scale social networks.

Community detection is a cornerstone problem in social network analysis (SNA), aimed at identifying cohesive communities with minimal external links. However, the rise of generative AI and Metaverse introduce complexities by creating hybrid human-AI social networks (denoted by HASNs), where traditional methods fall short, especially in human-centric settings. This paper introduces a novel community detection problem in HASNs (denoted by MetaCD), which seeks to enhance human connectivity within communities while reducing the presence of AI nodes. Effective processing of MetaCD poses challenges due to the delicate trade-off between excluding certain AI nodes and maintaining community structure. To address this, we propose CUSA, an innovative framework incorporating AI-aware clustering techniques that navigate this trade-off by selectively retaining AI nodes that contribute to community integrity. Furthermore, given the scarcity of real-world HASNs, we devise four strategies for synthesizing these networks under various hypothetical scenarios. Empirical evaluations on real social networks, reconfigured as HASNs, demonstrate the effectiveness and practicality of our approach compared to traditional non-deep learning and graph neural network (GNN)-based methods.

In this paper, we address the problem of revenue maximization (RM) for multi-grade products in social networks by considering pricing, seed selection, and coupon distribution. Previous works on RM often focus on a single product and neglect the use of coupons for promotion. We propose a new optimization problem,Revenue Maximization of Multi-Grade Product(RMMGP), to simultaneously determine pricing, seed selection, and coupon distribution for multi-grade products with both promotional and competitive relationships between grades in order to maximize revenue through viral marketing. We prove the hardness and inapproximability of RMMGP and show that the revenue function is not monotone or submodular. To solve RMMGP, we design an approximation algorithm, namelyData-Dependent Revenue Maximization (DDRM), and propose thePricing-Seeding-Coupon allocation (PriSCa)algorithm, which uses the concepts of Worth Receiving Probability, Pricing-Promotion Alternating Framework, and Independent/Holistic Customer-Grade Determinant sets. Our experiments on real social networks, using valuation distributions from Amazon.com, demonstrate that PriSCa and DDRM achieve on average 1.5 times higher revenue than state-of-the-art approaches. Additionally, PriSCa is efficient and scalable on large datasets.

The rapid development of multi-view videos (MVV) transmission is an irresistible trend. Concurrently, reconfigurable intelligent surface (RIS)-assisted wireless communication has drawn significant attention. We observe that the view selection based on the base station and the view synthesis based on depth-image-based rendering (DIBR) can effectively reduce power consumption. Therefore, this paper studies the view selection and synthesis for RIS-aided MVV in multigroup multicast beamforming. To deal with this complicated scenario, we investigate a problem, named the joint View selection, Multicast beamforming, and DIBR (JVMD), to minimize the total multicast beamforming power, the view transmission operation power, and view synthesis, subject to quality-of-service (QoS), RIS phase shifts, view selection, and DIBR constraints. Unfortunately, the mathematical model is a complicated mixed discrete-continuous optimization problem. To tackle this challenging problem, we designed an algorithm, named View selection, Beamforming, RIS phase, and DIBR (VBRD) algorithm. First, we deal with the discrete optimization problem of selecting the view. VBRD uses the dual-based approximation methodology to round back a primal's integer solution. Then, in the continuous optimization problem, we apply the alternating optimization (AO) method to determine beamforming, RIS phase, and DIBR. Finally, simulation results show the performance of exploiting view synthesis for RIS-assisted wireless communication.

Virtual reality (VR) imaging is 360°, which requires a large bandwidth for video transmission. To address this challenge, tile-based streaming has been proposed to deliver only the focused part of the video instead of the entire one. However, the impact of cybersickness, akin to motion sickness, on tile selection in VR has not been explored. In this paper, we investigate Multi-user Tile Streaming with Cybersickness Control (MTSCC) in an adaptive 360$^\circ$video streaming system with multicast and cybersickness alleviation. We propose a novel$m^{2}$-competitive online algorithm that utilizes Individual Sickness Indicator (ISI) and Bitrate Restriction Indicator (BRI) to evaluate user cybersickness tendency and network bandwidth efficiency. Moreover, we introduce the Video Loss Indicator (VLI) and Quality Variance Indicator (QVI) to assess video quality loss and quality difference between tiles. We also propose a multi-armed bandit (MAB) algorithm with confidence bound-based reward (video quality) and cost (cybersickness) estimation. The algorithm learns the weighting factor of each user's cost to slow down cybersickness accumulation for users with high cybersickness tendencies. We prove that the algorithm converges to an optimal solution over time. According to simulation with real network settings, our proposed algorithms outperform baselines in terms of video quality and cybersickness accumulation.

New radio (NR) and non-orthogonal multiple access (NOMA) offer scalable and efficient resource allocation in Beyond 5G (B5G) networks. NR implements mixed numerology with flexible frame structures for future compatibility, whereas NOMA allows users with different channel states to share an identical Physical Resource Block (PRB). Multi-connectivity enables a user to connect to multiple networks for reliability, and multicast conveys data to users simultaneously that request the same content. However, resource allocation in the NOMA-based mixed numerology system with multi-connectivity for multicast remains unexplored. The problem is challenging due to 1) the different shapes of PRBs in NR and 2) the shared locations of PRBs in a frame with NOMA. In this paper, we formulate a new optimization problem, named Multicast, Multi-connectivity, and Multi-Dimensional Resource Allocation Problem (M3DRAP), and prove its NP-hardness and inapproximability. We propose an approximation algorithm for general M3DRAP with the ideas ofMulticast Inter-Numerology Relation,Layer Dissimilarity,Subgrouping Nonuniformity, andSegmentation Preference. To find the intrinsic properties of PRB allocation for multicast in NOMA-based networks, we consider a single B5G usage scenario (e.g., eMBB, URLLC, or mMTC) and propose another approximation algorithm. Simulations demonstrate our algorithms improve the weighted sum rate by over 50% and increase the user satisfaction ratio by 1.5x.

Virtual Reality (VR) has emerged due to advancements in hardware and computer graphics. During the pandemic, conferences and exhibitions leveraging VR have gained attention. However, large-scale VR conferences, face a significant problem not yet studied in the literature -- displaying too many irrelevant users on the screen which may negatively impact the user experience. To address this issue, we formulate a new research problem, Social-Aware VR Conference Group Display Configuration (SVGD). Accordingly, we design the Social Utility-Aware VR Conference Group Formation (SVC) algorithm, which is a 2-approximation algorithm to SVGD. SVC iteratively selects either the P-Configuration or S-Configuration based on their effective ratios. This ensures that in each iteration, SVC identifies and chooses the solution with the highest current effectiveness. Experiments on real metaverse datasets show that the proposed SVC outperforms 11 baselines by 75% in terms of solution quality.

Virtual reality (VR) imaging, with its 360° perspective, poses bandwidth challenges for video transmission. To solve the challenge, tile-based streaming delivers only the viewed portion of the video rather than the whole video. However, the influence of VR sickness and social relations on tile quality assignment has not been fully investigated. In this paper, we formulate Tile and Handover Management regarding VR sickness and Social relation (THMVS) in an adaptive 360° video streaming system for mobile users, along with VR sickness alleviation. We propose a multi-armed bandit (MAB) algorithm with confidence bound-based reward and cost estimation to evaluate video quality and VR sickness. Our algorithm dynamically adjusts the tile quality and weighting factor of each user’s VR sickness increment according to user social relation, decelerating the VR sickness accumulation of susceptible individuals. Simulation results manifest that our algorithm outperforms existing video streaming algorithms regarding video quality and VR sickness accumulation.

With the emergence of new applications for holographic-type communication in healthcare, entertainment, and education, point cloud video transmission has become essen-tial. This paper aims to reduce the bandwidth cost by leveraging tile-based video transmission with point cloud registration in a wireless multicast network. A point cloud video is divided into multiple tiles, and each tile contains a portion of point cloud objects and can be registered by adjacent tiles with some similar objects under the registration rotation and registration overlap constraints. We formulate a new optimization problem and prove that it is NP-hard, and then we design an algorithm Multicast Multi-Tile Registration (MMTR) to select multicasting and registered tiles under consideration of socially related users' preferences with the idea of a tile registration graph. A more popular tile can be multicasted to more friends to minimize the bandwidth cost. Experimental results with real datasets show that MMTR can reduce bandwidth costs by more than 20% and achieve better video quality compared to state-of-the-art point cloud transmission algorithms.

Recent advancements in the field of extended reality (XR) have garnered significant interest in XR socialization. However, traditional social XR experiences often fall short of satisfying users' social expectations due to the negligence of the emerging opportunities in XR. In this paper, we propose a novel scenario of socializing in social XR, which has the potential to substantially enhance traditional social media through i) the recommendation of appropriate surrounding users that cater to users' individual preferences, ii) the adaptive avoidance of view occlusions to facilitate users in locating their friends, iii) the consideration of users' social presence, and iv) the development of cross-platform solutions to provide hybrid participation. To this end, we formulate Adaptive Friend Discovery for Temporal-spatial and Social-aware XR, a new NP-hard social recommendation problem aiming at satisfying social XR users. The proposed model, POSHGNN, is a deep temporal graph learning framework designed to provide efficient social recommendations for target users. Experimental results obtained from real-world social XR datasets and a user study that supports multiple XR interfaces demonstrate that the proposed method outperforms baseline approaches with an improvement of 18.5 % in solution quality.

Due to the growing need for bandwidth starving Multi-View Videos (MVV) in virtual reality, TV, and education, effectively allocating the resources of next-generation wireless technologies for MVV streams becomes increasingly crucial. To achieve high utility for MVV users, this article proposes a cross-layer resource allocation mechanism to leverage video synthesizing schemes (such as Depth-Image-Based Rendering (DIBR) for efficient MVV streaming with massive MIMO). First, we formulate a new problem,antenna allocation with video synthesis(AAVS), and prove its NP-hardness. Then, we design an approximation algorithm namedUtility-based Multi-View Synthesis(UMVS) with the analytical performance provided, and dynamic scenarios are addressed by augmenting UMVS with deep reinforcement learning. Data-driven simulation results show that UMVS outperforms existing antenna allocation schemes by at least 10%, and the DRL extension provides an additional 6% improvement in system utility under congested scenarios.

Wireless power transfer (WPT) has emerged to enhance the robustness of the energy harvesting Internet of Things (EH-IoT), whereas beamforming has been leveraged to significantly boost the efficiency of far-field WPT. Nevertheless, potential negative impacts due to high electromagnetic fields (EMF) exposure for radiation-susceptible users have not been thoroughly considered in the design of WPT for EH-IoT with IoT application-level requirements (e.g., coverage). In this article, we explore the health-aware beamforming and IoT selection problem under the EH and human safety constraints. First, we formulate a new optimization problem Health-Aware Beamforming and IoT Selection (HABIS) and prove the NP-hardness. Second, we design an approximation algorithm, named Minimum Radiation Exposure and Maximum IoT Coverage (MREMIC), to exploit the EH-health dependency (EHHD) graph for properly addressing the trade-off between EH efficiency and potential EMF radiation exposure to human bodies. We also discover the optimal health-aware beamforming to minimize the total radiation energy absorption of humans. Simulation results show that MREMIC can effectively charge IoT devices and significantly outperforms existing EH approaches by more than 200% regarding human safety.

Multi-view videos (MVV) have emerged to provide users with immersively interactive experiences with 3D multimedia content. Compared with traditional 2D videos, MVV offers multiple view angles to avoid generating occluded regions from a single viewpoint and allows users to receive different view angles, which consume much higher bandwidth. In this paper, we leverage multicast and view synthesis to effectively reduce the number of transmitted views and total bandwidth consumption in software-defined content delivery networks (SD-CDN). By exploiting the SDN architecture, SD-CDN can optimize traffic engineering and the selection of multi-view sources to serve users. We formulate a new optimization problem, (), prove the NP-hardness, and design an online algorithm with the ideas of View Popularity Cost Ratio, View Watching Possibility, and synthesis tree, to achieve the tightest competitive ratio. The experiment on real networks and implementation in an experimental SDN manifest that the proposed algorithm outperforms state-of-the-art algorithms regarding the total cost, bandwidth consumption, synthesis quality, and link and node utilization.

The virtual reality (VR) market is expected to reach 202.7 billion dollars by 2028, at a compound annual growth rate of 24.74% over the forecast period 2023–2028. It motivates innovative VR services in touring, E-commerce, and social activities, and effective VR video streaming becomes essential. However, VR services are envisaged to consume a large amount of bandwidth, but current research primarily focuses on multimedia streaming for each individual user without considering the opportunity of view synthesis for multicast to reduce wireless resource consumption further. In this article, we formulate a new optimization problem VR Content Sharing and Multicasting (VCSM) and prove the NP-hardness. Then, we propose an approximation algorithm, named Efficient View Synthesis and Multicasting (EVSM), to select multicast views and their Modulation and Coding Schemes (MCS) for wireless VR services. Afterward, we extend EVSM to support dynamic user behaviors and increase scalability with distributed mobile edge computing. We also explore the intrinsic properties of view selections to find the optimal solution for regular user deployment. Experiment results show that EVSM can effectively reduce bandwidth consumption for VR services by more than 50$\%$.

The emergence of AI has shifted the focus of wireless communications towards deep semantic-level fidelity (i.e., semantic communication networks), emphasizing the significance and effectiveness of transmitted data. However, semantic feature selection considering multicast users with social relations for feature sharing has not been explored. In this paper, we formulate a new optimization problem to minimize the total communication, forwarding, and computation costs, with the proof of NP-hardness and inapproximability. We propose a new algorithm, Multicast Semantic Feature Selection (MSFS), with the notions of Cross Task Semantic Indicator, Substituted Subgraph, and Socially Feature Selection Indicator, to select features on different mobile edge computing servers and cluster the users to receive features via multicast. Simulations with real datasets manifest that MSFS can reduce the total cost by more than 50% compared with state-of-the-art algorithms.

Quantization is an effective approach for memory cost reduction by compressing networks to lower bits. However, existing quantization processes learned only from the current data tend to suffer from forgetting catastrophe on streaming data, i.e., significant performance decrement on old task data after being trained on new tasks. Therefore, we propose a lifelong quantization process, LifeQuant, to address the problem. We theoretically analyze the forgetting catastrophe from the shift of quantization search space with the change of data tasks. To overcome the forgetting catastrophe, we first minimize the space shift during quantization and propose Proximal Quantization Space Search (ProxQ), for regularizing the search space during quantization to be close to a pre-defined standard space. Afterward, we exploit replay data (a subset of old task data) for retraining in new tasks to alleviate the forgetting problem. However, the limited amount of replay data usually leads to biased quantization performance toward the new tasks. To address the imbalance issue, we design a Balanced Lifelong Learning (BaLL) Loss to reweight (to increase) the influence of replay data in new task learning, by leveraging the class distributions. Experimental results show that LifeQuant achieves outstanding accuracy performance with a low forgetting rate.

Data poisoning attacks against recommender systems (RecSys) often assume a single seller as the adversary. However, in reality, there are usually multiple sellers attempting to promote their items through RecSys manipulation. To obtain the best data poisoning plan, it is important for an attacker to anticipate and withstand the actions of his opponents. This work studies the problem of Multiplayer Comprehensive Attack (MCA) from the perspective of the attacker, considering the subsequent attacks by his opponents. In MCA, we target the Heterogeneous RecSys, where user-item interaction records, user social network, and item correlation graph are used for recommendations. To tackle MCA, we present the Multilevel Stackelberg Optimization over Progressive Differentiable Surrogate (MSOPDS). The Multilevel Stackelberg Optimization (MSO) method is used to form the optimum strategies by solving the Stackelberg game equilibrium between the attacker and his opponents, while the Progressive Differentiable Surrogate (PDS) addresses technical challenges in deriving gradients for candidate poisoning actions. Experiments on Heterogeneous RecSys trained with public datasets show that MSOPDS outperforms all examined prior works by up to 10.6% in average predicted ratings and up to 11.4% in HitRate@3 for an item targeted by an attacker facing one opponent. Source code provided in https://github.com/jimmy-academia/MSOPDS.

Recent pandemics, such as H1N1 and COVID-19, have had extensive negative effects on the social and economic well-being of communities. Despite efforts to prevent and control their spread, governments have turned to a strategy of Living With the Virus to manage, rather than eliminate, the impact of these pandemics. However, group activities such as collaborative spatial crowdsourcing can still lead to the significant spread of infection due to the correlation between individuals’ mobility, interactions, and infection spread. In this paper, we address the problem of spatial crowdsourcing-induced infection spread and propose Epidemic-aware Maximum Task Assignment (EMTA). EMTA aims to form and assign collaborative worker groups to spatial crowdsourcing tasks while taking into consideration the control of epidemic spread. We prove that EMTA is NP-hard and inapproximable. We then propose the Epidemic-aware Task Assignment Algorithm (ETAA) that leverages epidemic characteristics to fully address EMTA. The experimental results from real LBSN and real epidemic datasets demonstrate that the proposed algorithm outperforms the state-of-the-art baselines in terms of effectiveness and efficiency.

The localization of Road Users (RUs) is an important issue in adverse event prevention due to the unreliable nature of GPS and the high cost of high-precision location acquisition sensors. In addition, previous research on adverse event prevention on roads has not taken into account RUs in blind spots at the same time. To address these issues, we investigate a collaboration system for heterogeneous RUs and Mobile Edge Computing (MEC) servers, called Collaborative Adverse Event Prevention system (CAEP) to efficiently alert RUs to potential adverse events and perceive the blind spot of the RUs. CAEP includes two AI-based functional modules, a localization module and a blind spot detection module, and an adverse event prevention algorithm. The localization module localizes each RU and the blind spot detection module detects the other RUs in the blind spot. The adverse event prevention algorithm jointly considers general road collision events and the event of a difference in radius between the inner wheels of a vehicle to completely include adverse events on the road. We implement CAEP in a real-world traffic environment with Jetson AGX Xavier devices and cameras to evaluate the performance. Our evaluation shows that CAEP provides RUs with sufficient preparation time to prevent adverse events and correctly detects the RUs in blind spots.

The phenomena of influence diffusion on social networks have received tremendous research interests in the past decade. While most prior works mainly focus on predicting the total influence spread on a single network, a marketing campaign that exploits influence diffusion often involves multiple channels with various information disseminated on different media. In this paper, we introduce a new influence estimation problem, namely Content-aware Multi-channel Influence Diffusion (CMID), and accordingly propose CMINet to predict newly influenced users, given a set of seed users with different multimedia contents. In CMINet, we first introduce DiffGNN to encode the influencing power of users (nodes) and Influence-aware Optimal Transport (IOT) to align the embeddings to address the distribution shift across different diffusion channels. Then, we transform CMID into a node classification problem and propose Social-based Multimedia Feature Extractor (SMFE) and Content-aware Multi-channel Influence Propagation (CMIP) to jointly learn the user preferences on multimedia contents and predict the susceptibility of users. Furthermore, we prove that CMINet preserves monotonicity and submodularity, thus enabling (1 − 1/e)-approximate solutions for influence maximization. Experimental results manifest that CMINet outperforms eleven baselines on three public datasets.

Previous research on SDN multicast traffic engineering mainly focused on intra-domain optimization. However, the main traffic on the Internet is inter-domain, and the selection of border nodes and sharing of network information between domains are usually distributed but ignored in previous works. In this article, we explore multi-domain online distributed multicast traffic engineering (MODMTE). To effectively solve MODMTE, we first prove that MODMTE is inapproximable within$|D_{\max }|$, which indicates that it is impossible to find any algorithm with a ratio better than$|D_{\max }|$for MODMTE, and$|D_{\max }|$is the maximum number of destinations for a multicast tree. Then, we design a$|D_{\max }|$-competitive distributed algorithm with the ideas of Domain Tree, Dual Candidate Forest Construction, and Forest Rerouting to achieve the tightest performance bound for MODMTE. Experiments on a real SDN with YouTube traffic manifest that the proposed distributed algorithm can reduce more than 30% of the total cost of bandwidth consumption and rule updates for multicast tree rerouting compared with the state-of-the-art algorithms.

Real-timesocial interactions andmulti-streamingare two critical features oflive streaming services. In this paper, we formulate a new fundamental service query,Social-aware Diverse and Preferred Organization Query (SDSQ), that jointly selects a set of diverse and preferred live streaming channels and a group of socially tight viewers for organization of a live multi-streaming soiree. We prove that SDSQ is NP-hard and inapproximable within any factor, and designSDSSel, a 2-approximation algorithm with a guaranteed error bound. Moreover, we study SDSQ-T, a special case of SDSQ, where the social graph is a threshold graph, and proposeTDSSel, a 2-approximation algorithm without any error to SDSQ-T. We propose two pruning strategies,PCPandCDPto boost SDSSel and TDSSel. We further propose a more challenging but practical service query,Generalized Social-aware Maximum Preferred and Diverse Query (GSPQ), a generalization of SDSQ. We designGPDSel, a 4-approximation algorithm for GSPQ with a guaranteed error bound. We propose a strategy to improve the approximation ratios of the proposed algorithms. A user study on Twitch validates SDSQ, and the large-scale experiments on real datasets demonstrate the superiority of the proposed algorithms over several baselines for live-streaming services.

Social metaverse with VR has been viewed as a paradigm shift for social media. However, most traditional VR social platforms ignore emerging characteristics in a metaverse, thereby failing to boost user satisfaction. In this paper, we explore a scenario of socializing in metaverse with VR, which brings major advantages over conventional social media: 1) leverage flexible display of users' 360-degree viewports to satisfy individual user interests, 2) ensure the user feelings of co-existence, 3) prevent view obstruction to help users find friends in crowds, and 4) support socializing with digital twins. Therefore, we formulate the Co-presence, and Occlusion-aware Metaverse User Recommendation (COMUR) problem to recommend a set of rendered players for users in social metaverse with VR. We prove COMUR is an NP-hard optimization problem and design a dual-module deep graph learning framework (COMURNet) to recommend appropriate users for viewport display. Experimental results on real social metaverse datasets and a user study with Occulus Quest 2 manifest that the proposed model outperforms baseline approaches by at least 36.7% of solution quality.

When spreading information over social networks, seeding algorithms selecting users to start the dissemination play a crucial role. The majority of existing seeding algorithms focus solely on maximizing the total number of reached nodes, overlooking the issue of group fairness, in particular, gender imbalance. To tackle the challenge of maximizing information spread on certain target groups, e.g., females, we introduce the concept of the community and gender-aware potential of users. We first show that the network's community structure is closely related to the gender distribution. Then, we propose an algorithm that leverages the information about community structure and its gender potential to iteratively modify a seed set such that the information spread on the target group meets the target ratio. Finally, we validate the algorithm by performing experiments on synthetic and real-world datasets. Our results show that the proposed seeding algorithm achieves not only the target ratio but also the highest information spread, compared to the state-of-the-art gender-aware seeding algorithm.

Quantization is an efficient network compression approach to reduce the inference time. However, existing approaches ignored the distribution difference between training and testing data, thereby inducing a large quantization error in inference. To address this issue, we propose a new quantization scheme, Alignment Quantization with ADMM-based Correlation Preservation (AlignQ), which exploits the cumulative distribution function (CDF) to align the data to be i.i.d. (independently and identically distributed) for quantization error minimization. Afterward, our theoretical analysis indicates that the significant changes in data correlations after the quantization induce a large quantization error. Accordingly, we aim to preserve the relationship of data from the original space to the aligned quantization space for retaining the prediction information. We design an optimization process by leveraging the Alternating Direction Method of Multipliers (ADMM) optimization to minimize the differences in data correlations before and after the alignment and quantization. In experiments, we visualize non-i.i.d. in training and testing data in the benchmark. We further adopt domain shift data to compare AlignQ with the state-of-the-art. Experimental results show that AlignQ achieves significant performance improvements especially in low-bit models. Code is available at https://github.com/tinganchen/AlignQ.git.

3GPP has defined Dual Connectivity (DC) to allow a user to access a 4G and a 5G base station (BS) simultaneously. However, the resource allocation for DC is challenging because of not only the co-channel interference between 4G and 5G BSs but also different shapes of Resource Blocks (RBs) for New Radio (NR) and the reuse of RBs for Non-Orthogonal Multiple Access (NOMA). In this paper, we formulate Dual Connectivity Multidimensional Resource Allocation Problem and prove that it is NP-hard. We design an approximation algorithm with the ideas of 1) Zone Shaping, 2) Occupancy Indicator and Overlap Degree of RBs, 3) DC Slicing, and 4) DC Inter-Numerology Relation, to maximize the total throughput of heterogeneous user demands in the coexisting 4G and 5G network with NR, NOMA, and DC. Simulation results manifest that our algorithm outperforms the state-of-the-arts regarding throughput and resource efficiency.

With the advances in Social Internet of Things (SIoT) and Federated learning (FL), smart devices are now able to cooperatively and locally perform learning tasks to protect sensitive data by Differential Privacy (DP). On the other hand, Hierarchical FL (HFL) clusters SIoTs into multiple local training groups to reduce communication overheads by local aggregation. In this paper, we explore SIoT Training Group Construction (STGC) for HFL to minimize the total SIoT computation, communication and hiring costs, and the privacy cost for exploiting DP. We prove that STGC is NP-hard and inapproximable within any factor unless P = NP. Then, we design an algorithm with the ideas of Coverage Efficiency Indicator, Data Balance-aware Dual Adjustment, and Privacy-Aware Rerouting to choose and cluster SIoTs and to determine the aggregator for local training and SIoT routing in each cluster. Simulation results manifest that the proposed algorithm outperforms state-of-the-arts regarding the total cost, model accuracy, and convergence time.

While mobile edge computing (MEC) potentially supports the stringent latency requirements for Virtual Reality (VR), previous research only considers minimizing the latency of transmitting required data and ignores the latency consistency of a group of friends in social VR. In this paper, we leverage the human motion prediction to eliminate the inconsistency among users in a group while ensuring the low latency interaction between friends with the aid of MEC. Moreover, to capture the accurate users’ interaction behaviors, it is critical to jointly predict the motions of users with spatially close proximity in VR. Accordingly, we formulate a new problem, named Group Motion Prediction for Social VR problem (GMSV), with group consistency requirement and the objective of prediction costs minimization on the MEC server. Then, we prove that GMSV is NP-Hard and design a new algorithm, named Social-Aware Latency Synchronization for Remote Users (SLSR), to select an appropriate set of remote users in social VR for motion prediction, with the ideas of generating a partial order set of remote subgroups and extracting the remote subgroups with high social interaction utilities. Simulation results show that SLSR can effectively increase latency consistency by more than 50% compared with the baseline schemes.

Remote working and virtual socializing are becoming the norm. This trend evokes the growth of virtual reality (VR). Users can explore virtual environments (VEs) with the most intuitive approach: walking. In contrast to traditional static VR experience, redirected walking (RW) enables users to walk in VEs larger than the physical space. Recent RW works aim to deliver an obstacle-free VR experience. However, they ignore the user’s cybersickness and received signal strength, which degrades the VR experience. In this paper, we investigate Path Planning with Cybersickness and IRS Control (PPCIC) in an indoor RW system with cybersickness and IRS control. We proposed an algorithm with Cybersickness Indicator (CI) and SINR Indicator (SI) to evaluate the cybersickness and received signal strength of each path. Simulation results show that our algorithm outperforms the baselines regarding the total cost, cybersickness, and received signal strength.

The potential impact of epidemics, e.g., COVID-19, H1N1, and SARS, is severe on public health, the economy, education, and society. Before effective treatments are available and vaccines are fully deployed, combining Non-Pharmaceutical Interventions (NPIs) and vaccination strategies is the main approaches to contain the epidemic or live with the virus. Therefore, research for deciding the best containment operations to contain the epidemic based on various objectives and concerns is much needed. In this paper, we formulate the problem of Containment Operation Optimization Design (COOD) that optimizes the epidemic containment by carefully analyzing contacts between individuals. We prove the hardness of COOD and propose an approximation algorithm, named Multi-Type Action Scheduling (MTAS), with the ideas of Infected Ratio, Contact Risk, and Severity Score to select and schedule appropriate actions that implement NPIs and allocate vaccines for different groups of people. We evaluate MTAS on real epidemic data of a population with real contacts and compare it against existing approaches in epidemic and misinformation containment. Experimental results demonstrate that MTAS improves at least 200% over the baselines in the test case of sustaining public health and the economy. Moreover, the applicability of MTAS to various epidemics of different dynamics is demonstrated, i.e., MTAS can effectively slow down the peak and reduce the number of infected individuals at the peak.

In recent years, the social world of virtual reality has become more popular in education, metaverse, entertainment, design, and real-life applications with simultaneous localization and mapping. This is based on an augmented reality (AR) smartphone that supports simultaneous localization and mapping with its two cameras, RGB camera and depth camera, to sense 3D real world. In this study, the average depth data of point clouds on the real 3D objects captured by the depth camera are used to determine whether there are 3D dynamic objects for social world of virtual and real world. When the average depth data change exceeds the threshold of the average depth data, a 3D dynamic object can be detected. This threshold is also adopted to adjust 3D scanning speed and to update Virtual Reality (VR) representation. We conduct detailed experimental analysis as well as verification and completely analyze physical errors for integrating virtual and real worlds.

Epidemics such as COVID-19, SARS, H1N1 have highly transmissible viruses and spread wildly through the population with negative consequences. Multiple studies have shown the correlation between the contact networks between individuals and the transmission of infections due to contact between colocated individuals. To mitigate the transmission of the virus, intervention measures have been applied without decisive success. Therefore, reducing transmissions through suitable epidemicaware POI recommendations to users is necessary to cope with user mobility. Current POI recommendation approaches do not take into consideration the transmission of infections between co-located users. In this paper, we formulate a new query named Epidemic-aware POI Recommendation Query (EPQ), to timely recommend a set of POIs to users at different time steps, while considering the spread of infection between co-located users, their social friendships, and their preference. We prove that EPQ is NP-hard and propose an effective and efficient algorithm, Epidemic-aware POI Recommendation (EpRec) to tackle EPQ. We evaluate EpRec on existing location-based social networks and pandemic datasets against state-of-the-art algorithms. The experimental results show that EpRec outperforms the baselines in effectiveness and efficiency.

Quantization compresses models to low bits for efficient inferences which has received increasing attentions. However, existing approaches focused on balanced datasets, while imbalanced data is pervasive in the real world. Therefore, in this study, we investigate the realistic problem, quantization on class-imbalanced data. We observe from the analytical results that quantizing imbalanced data tends to obtain a large error due to the differences between separate class distributions, which leads to a significant accuracy loss. To address this issue, we propose a novel quantization framework, Class Imbalanced Quantization (ClimbQ) that focuses on diminishing the inter-class heterogeneity for quantization error reduction. ClimbQ first scales the variance of each class distribution and then projects data through the new distributions to the same space for quantization. To guarantee the homogeneity of class variances after the ClimbQ process, we examine the quantized features and derive that the homogeneity satisfies when data size for each class is restricted (bounded). Accordingly, we design a Homogeneous Variance Loss (HomoVar Loss) which reweights the data losses of each class based on the bounded data sizes to satisfy the homogeneity of class variances. Extensive experiments on class-imbalanced and benchmark balanced datasets reveal that ClimbQ outperforms the state-of-the-art quantization techniques, especially on highly imbalanced data.

Research on new queries for finding dense subgraphs and groups has been actively pursued due to their many applications, especially in social network analysis and graph mining. However, existing work faces two major weaknesses: i) incapability of supporting personalized neighborhood density, and ii) inability to find sparse groups. To tackle the above issues, we propose a new query, called Density-Customized Social Group Query (DCSGQ), that accommodates the need for personalized density by allowing individual users to flexibly configure their social tightness (and sparseness) for the target group. The proposed DCSGQ is general due to flexible in configuration of neighboring social density in queries. We prove the NP-hardness and inapproximability of DCSGQ, formulate an Integer Program (IP) as a baseline, and propose an efficient algorithm, FSGSel-RR, by relaxing the IP. We then propose a fixed-parameter tractable algorithm with a performance guarantee, named FSGSel-TD, and further combine it with FSGSel-RR into a hybrid approach, named FSGSel-Hybrid, in order to strike a good balance between solution quality and efficiency. Extensive experiments on multiple large real datasets demonstrate the superior solution quality and efficiency of our approaches over existing subgraph and group queries.

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group with No-Pair Constraint (MkTG), to find a socially tenuous group from the online social network. We prove that MkTG is NP-hard and inapproximable within any ratio. Two algorithms, namely TERA and TERA-ADV, are designed for solving MkTG effectively and efficiently. Further, we examine the MkTG problem on tree-based social networks, due to their structural resemblance with corporate social networks built upon the supervision relation. Accordingly, we devise an efficient algorithm, namely Tenuity Maximization for Trees (TMT), to obtain the optimal solution in polynomial time. In addition, we study a more general version of MkTG, named Generalized Minimum k-Triangle Disconnected Group without No-Pair Constraint (MkTG-G). We formulate MkTG-G, analyze its inapproximability, and propose a randomized approximation algorithm, named Randomized Ranking with Limited Neighborhood Participation (RLNP). Experimental results on real datasets manifest that the proposed algorithms outperform the baselines in terms of both efficiency and solution quality.

The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. Thus, it's important to organize social activities for online social network users to meet in person. In this paper, we consider the scenarios of organizing in person friend-making social activities via online social networks (OSNs) and formulate a new research problem, namely,Hop-bounded Maximum Group Friending (HMGF), that takes into consideration both existing friendships and the likelihood of new friend making in organization of the targeted in person friend-making social activities. To find a set of attendees for such social activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships, and the objective of maximizing the likelihood of friend making. We prove that HMGF is NP-Hard, and there exists no approximation algorithm for it unless$P=NP$. We also provide an Integer Linear Programming (ILP) formulation for the HMGF problem. The ILP formulation, which can be solved efficiently by a commercial solver to obtain the optimal solution for small HMGF instances, acts as a baseline approach for comparison in the evaluation of the proposed algorithm. We further propose an error-bounded approximation algorithm,MaxGF, to efficiently obtain the solutions very close to the optimal solutions. To boost the performance, we devise two graph-theoretical pruning strategies, namelyNeighbor PruningandCore Pruning, which can effectively avoid redundant graph explorations to improve the performance of HMGF. We also study HMGF on a class of special graphs,threshold graphs, which have properties very similar to many online social networks. We prove that MaxGF can obtain the optimal solution to HMGF on threshold graphs in polynomial time. We conduct a user study to validate our problem formulation and perform extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm. The experimental results manifest that our proposed algorithms outperform the baselines, including the ILP formulation.

Due to the emergence of mobile 3D devices, multi-view 3D videos are expected to play increasingly important roles in providing immersively interactive experiences to users. Compared with traditional single-view videos, it is envisaged that a multi-view 3D video requires a larger storage space and bandwidth consumption. Nevertheless, efficient caching for multi-view 3D videos in a mobile proxy has not been explored in the literature. In this paper, therefore, we first observe that the storage space can be effectively reduced by leveraging Depth Image Based Rendering (DIBR) in multi-view 3D videos. We then formulate a new cache management problem, named Adaptive View Selection and Cache Operation (AVSCO), and find the optimal policy based on Markov Decision Process (MDP). Afterward, we propose an online algorithm with a guaranteed competitive ratio to support human visual continuity in AVSCO. Then, we devise an approximate MDP to accelerate the computation of MDP by aggregating similar states to reduce the state space. Simulation and prototype implementation results manifest that the proposed algorithms can significantly improve the cache hit rate and reduce the bandwidth consumption for the remote access compared with the existing cache replacement algorithms.

Flow consolidation has been proposed for merging multiple flows from different services into an aggregate flow to remedy the state explosion problem in software-defined networks (SDN). However, we observe that the Quality of Service (QoS) requirements are no longer sustained in aggregate flows since the bandwidth decided by TCP is usually different from the desired rate of each service. Therefore, this article explores an idea to control the rates of only a few service flows so that the rates of all uncontrolled flows allocated by TCP will meet their QoS requirements. We design a new architecture, called Scalable Per-Flow Rate Allocation (SPFRA), and formulate a new optimization problem, termed Scalable Rate Allocation for Aggregate Flows (SRAF), to find a minimum number of controlled flows to increase the scalability of SDN with diverse service requirements. We prove the NP-hardness and inapproximability of SRAF. To solve the problem, we design an algorithm, named Aggregate Flow Selection and Flow Release (AFSFR), to achieve the tightest bound and extend it to support distributed computation and dynamic traffic for instant services. Simulations and implementation on an SDN testbed manifest that AFSFR performs nearly optimally in real networks, and the number of controlled flows can be effectively reduced by 50 percent.

Online social networks have become a crucial medium to disseminate the latest political, commercial, and social information. Users with high visibility are often selected as seeds to spread information and affect their adoption in target groups. We study how gender differences and similarities can impact the information spreading process. Using a large-scale Instagram dataset and a small-scale Facebook dataset, we first conduct a multi-faceted analysis taking the interaction type, directionality and frequency into account. To this end, we explore a variety of existing and new single and multihop centrality measures. Our analysis unveils that males and females interact differently depending on the interaction types, e.g., likes or comments, and they feature different support and promotion patterns. We complement prior work showing that females do not reach top visibility (often referred to as the glass ceiling effect) jointly factoring in the connectivity and interaction intensity, both of which were previously mainly discussed independently.

Device-to-device (D2D) communication is one of the promising solutions to improve spectrum efficiency and alleviate the mobile traffic explosion. However, interference mitigation and resource allocation in the underlying cellular network is a challenging task. In this paper, we propose a distributed deep reinforcement learning (DRL) based scheme to solve the interference mitigation and resource allocation problem. According to the channel status, each cellular user (CU) and D2D transmitter (D2D TX) will determine the appropriate reused channel and transmit power to maximize the system throughput. We propose a distributed DRL scheme and integrate two hotbooting algorithms into the scheme to improve the system throughput at the early stage of training. Simulation results show that the proposed distributed DRL with hotbooting outperforms the baselines regarding running time, message overhead, and throughput.

In contrast to traditional videos, the imaging in virtual reality (VR) is 360°, and it consumes larger bandwidth to transmit video contents. To reduce bandwidth consumption, tile-based streaming has been proposed to deliver the focused part of the video, instead of the whole one. On the other hand, the techniques to alleviate cybersickness, which is akin to motion sickness and happens when using digital displays, have not been jointly explored with the tile selection in VR. In this paper, we investigate Tile Selection with Cybersickness Control (TSCC) in an adaptive 360° video streaming system with cybersickness alleviation. We propose an$m$-competitive online algorithm with Cybersickness Indicator (CI) and Video Loss Indicator (VLI) to evaluate instant cybersickness and the total loss of video quality. Moreover, the algorithm exploits Sickness Migration Indicator (SMI) to evaluate the cybersickness accumulated over time and the increase of optical flow to improve the tile quality assignment. Simulations with a real network dataset show that our algorithm outperforms the baselines regarding video quality and cybersickness accumulation.

Social Internet of Things (SIoT) has become an emerging network paradigm, where IoT devices with Artificial Intelligence (AI) and social relations can automatically establish a collaborative group to identify events locally. On the other hand, mobile users can act as ubiquitous and versatile sensors to improve the accuracy of SIoT event detection. In this paper, we explore the SIoT Collaboration with Crowdsourcing (SCC) problem to jointly select SIoT devices and hire users to monitor events and locations with accuracy requirements, while minimizing the total SIoT communication and computation costs and the user hiring cost. We prove that SCC is NP-hard and cannot be approximated by any factor unless P = NP. Then, we propose a new algorithm, Accuracy- and Social-aware SIoT and User Selection (ASSUS), with the idea of Collaborative Tree (CT) and Accuracy Profit (AP), where CT exploits users’ social relations to properly choose intermediate SIoTs. Simulation results manifest that ASSUS can effectively reduce more than 50% of the total cost compared with state-of-the-art algorithms.

Due to the great success of image-to-image (Img2Img) translation GANs, many applications with ethics issues arise, e.g., DeepFake and DeepNude, presenting a challenging problem to prevent the misuse of these techniques. In this work, we tackle the problem by a new adversarial attack scheme, namely the Nullifying Attack, which cancels the image translation process and proposes a corresponding framework, the Limit-Aware Self-Guiding Gradient Sliding Attack (LaS-GSA) under a black-box setting. In other words, by processing the image with the proposed LaS-GSA before publishing, any image translation functions can be nullified, which prevents the images from malicious manipulations. First, we introduce the limit-aware RGF and the gradient sliding mechanism to estimate the gradient that adheres to the adversarial limit, i.e., the pixel value limitations of the adversarial example. We theoretically prove that our model is able to avoid the error caused by the projection in both the direction and the length. Then, an effective self-guiding prior is extracted solely from the threat model and the target image to efficiently leverage the prior information and guide the gradient estimation process. Extensive experiments demonstrate that LaS-GSA requires fewer queries to nullify the image translation process with higher success rates than 4 state-of-the-art methods.

Owing to a wide range of important applications, such as team formation, dense subgraph discovery, and activity attendee suggestions on online social networks, Group Query attracts a lot of attention from the research community. However, most existing works are constrained by a unified social tightness k (e.g., for k-core, or k-plex), without considering the diverse preferences of social cohesiveness in individuals. In this paper, we introduce a new group query, namely Parameter-free Group Query (PGQ), and propose a learning-based model, called PGQN, to find a group that accommodates personalized requirements on social contexts and activity topics. First, PGQN extracts node features by a GNN-based method on Heterogeneous Activity Information Network (HAIN). Then, we transform the PGQ into a graph-to-set (Graph2Set) problem to learn the diverse user preference on topics and members, and find new attendees to the group. Experimental results manifest that our proposed model outperforms nine state-of-the-art methods by at least 51% in terms of F1-score on three public datasets.

Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization based on Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves at least 6 times of influence spread in large datasets over the state-of-the-art approaches.

Since early 2020, the COVID-19 global pandemic has significantly impacted almost every aspect of the human society throughout the world. Until now, middle of 2021, although with all the efforts on pandemic intervention and vaccination, COVID-19 is still hovering around the world, resulting in more than 177 million confirmed cases and 3.8 million deaths.

In contrast to traditional online videos, live multi-streaming supports real-time social interactions between multiple streamers and viewers, such as donations. However, donation and multi-streaming channel recommendations are challenging due to complicated streamer and viewer relations, asymmetric communications, and the tradeoff between personal interests and group interactions. In this paper, we introduce Multi-Stream Party (MSP) and formulate a new multi-streaming recommendation problem, called Donation and MSP Recommendation (DAMRec). We propose Multi-stream Party Recommender System (MARS) to extract latent features via socio-temporal coupled donation-response tensor factorization for donation and MSP recommendations. Experimental results on Twitch and Douyu manifest that MARS significantly outperforms existing recommenders by at least 38.8% in terms of hit ratio and mean average precision.

New radio (NR) and non-orthogonal multiple access (NOMA) have emerged for more scalable and efficient resource utilization in 5G. NR implements mixed numerology with a flexible radio frame structure to ensure forward compatibility for future services, whereas NOMA allows multiple users with different channel states to share identical radio resources. However, the resource allocation in the NOMA-based mixed numerology system is challenging due to the naturally different shapes of Physical Resource Block (PRB) for NR and the reused locations of PRBs in a radio frame for NOMA. In this paper, we formulate a new optimization problem Multi-Dimensional Resource Allocation Problem (MDRAP) and prove that MDRAP is NP-hard. To solve the problem, we propose an approximation algorithm to maximize the weighted sum rate under the heterogeneity of users. The algorithm includes Zone Displacement to displace the locations of allocated PRBs in different layers of the radio frame, and Zone Allocation to change the location of the bounded rectangles (i.e., zones) for the allocation in each layer. We design Layer Dissimilarity to examine the location and shape of PRBs for avoiding inter-numerology interference between different layers. Simulation results show that the proposed algorithm outperforms state-of-the-art algorithms regarding throughput and fairness.

With the emergence of innovative applications for Virtual Reality (VR) in touring, E-commerce, and social activities, high-quality VR video streaming becomes essential. To support numerous wireless VR users, this paper aims to leverage video synthesis techniques to effectively reduce the multicast bandwidth consumption. It synthesizes the view in the video for a user from the one of a nearby user with similar Field of View (FoV), under the virtual distance and view angle constraints. We first formulate a new optimization problem, named VR Content Sharing and Multicasting (VCSM), and prove the NP-hardness. Then, we propose View Sharing Relation Graph (VSRG) to model the synthesis relation between each pair of views. We then design a new algorithm, named Bandwidth-Efficient Multicast with Synthesis (BEMS) to select multicast views and the corresponding MCS in wireless networks. Simulation results show that BEMS can effectively reduce bandwidth consumption by more than 50% compared with state-of-the-art wireless transmission schemes.

Due to the growing need for Multi-View Videos (MVV) in advertisement, TV, and education, effectively allocating the resources of next-generation wireless technologies to provide MVV streams is challenging. To achieve the high utility for MVV users, this paper proposes a cross-layer resource allocation mechanism to leverage video synthesizing schemes (such as Depth-Image-Based Rendering (DIBR)) for efficient MVV streaming with massive MIMO. We formulate a new problem Antenna Allocation with Video Synthesizing (AAVS) and prove its NP-hardness. Then, we design an algorithm, named Marginal Utility-Based Iteration (MUBI). The performance is evaluated by the data-driven simulations, and the results manifest that MUBI outperforms the baselines regarding the total utility of users.

Previous research on Segment Routing (SR) mostly focused on unicast, whereas online SDN multicast with segment trees supporting IETF dynamic group membership has not been explored. Compared with unicast SR, online SDN multicast with segment trees is more challenging since finding an appropriate size, shape, and location for each segment tree is crucial to deploy it in more multicast trees. In this paper, we explore Multi-tree Multicast Segment Routing (MMSR) to jointly minimize the bandwidth consumption and forwarding rule updates over time by leveraging segment trees. We prove MMSR is NP-hard and design an online competitive algorithm, named Segment Tree Routing and Update Scheduling (STRUS) to achieve the tightest bound. STRUS includes Segment Tree Merging and Segment Tree Pruning to merge smaller overlapping subtrees into segment trees, and then tailor them to serve more multicast trees. We design Stability Indicator and Reusage Indicator to carefully construct segment trees at the backbone of multicast trees and reroute multicast trees to span more segment trees. Simulation and implementation on real SDNs with YouTube traffic manifest that STRUS outperforms state-of-the-art algorithms regarding the total cost and TCAM usage. Moreover, STRUS is practical for SDN since its running time is about 1 second, even for massive networks with thousands of nodes.

Research suggests that social relationships have substantial impacts on individuals’ health outcomes. Network intervention, through careful planning, can assist a network of users to build healthy relationships. However, most previous work is not designed to assist such planning by carefully examining and improving multiple network characteristics. In this paper, we propose and evaluate algorithms that facilitate network intervention planning through simultaneous optimization of network degree, closeness, betweenness, and local clustering coefficient, under scenarios involving Network Intervention with Limited Degradation - for Single target (NILD-S) and Network Intervention with Limited Degradation - for Multiple targets (NILD-M). We prove that NILD-S and NILD-M are NP-hard and cannot be approximated within any ratio in polynomial time unless P=NP. We propose the Candidate Re-selection with Preserved Dependency (CRPD) algorithm for NILD-S, and the Objective-aware Intervention edge Selection and Adjustment (OISA) algorithm for NILD-M. Various pruning strategies are designed to boost the efficiency of the proposed algorithms. Extensive experiments on various real social networks collected from public schools and Web and an empirical study are conducted to show that CRPD and OISA outperform the baselines in both efficiency and effectiveness.

Artificial intelligence (AI) on chips has recently driven the expansion of the Social Internet of Things (SIoT), where a group of SIoT devices with social relations can collaboratively identify and handle local events without the help of remote servers. On the other hand, mobile-edge computing (MEC) is a favorable way to locally process SIoT data for reducing data transmission and computation among SIoT devices and backhaul networks. Nevertheless, the load sharing among SIoT devices, MEC, and remote servers brings about new challenges for the communication and computation tradeoff, cross-layer design in SIoT, and forwarding and aggregation tradeoff. To tackle these issues, we formulate a new optimization problem, namely, SIoT collaborative group and device selection problem (SCGDSP), and prove the NP-hardness. We first explore the intrinsic properties of a fundamental SCGDSP case by finding the optimal collaborative group for each user request. Then, we design an approximation algorithm for the general SCGDSP that first evaluates candidate collaborative groups under different social relations, and then selects the collaborative groups and SIoT devices properly. For scalability, the proposed algorithm also supports dynamic user requests and can be distributionally deployed in massive networks enabling collaborative MEC. Moreover, it also sustains local SIoT services, where the computation only involves SIoT devices and MEC servers. Simulation results demonstrate that effective SIoT and collaborative group selection (ESCGS) can reduce by more than 50% of the total communication and computation costs compared with baseline schemes in the real networks from topology zoo. Moreover, the distributed ESCGS reduces by 87% of the running time with total 16.5-MB message overhead, requiring no more than 0.05-ms transmission delay in a 100-Gb/s backbone network with eight MEC servers, 1000 SIoTs, and 800 monitored locations.

Shopping in VR malls has been regarded as a paradigm shift for E-commerce, but most of the conventional VR shopping platforms are designed for a single user. In this paper, we envisage a scenario of VR group shopping, which brings major advantages over conventional group shopping in brick-and-mortar stores and Web shopping: 1) configure flexible display of items and partitioning of subgroups to address individual interests in the group, and 2) support social interactions in the subgroups to boost sales. Accordingly, we formulate the Social-aware VR Group-Item Configuration (SVGIC) problem to configure a set of displayed items for flexibly partitioned subgroups of users in VR group shopping. We prove SVGIC is APX-hard and also NP-hard to approximate within [EQUATION]. We design a 4-approximation algorithm based on the idea of Co-display Subgroup Formation (CSF) to configure proper items for display to different subgroups of friends. Experimental results on real VR datasets and a user study with hTC VIVE manifest that our algorithms outperform baseline approaches by at least 30.1% of solution quality.

With the rapid advent of Virtual Reality (VR) technology and virtual tour applications, there is a research need on spatial queries tailored for simultaneous movements in both the physical and virtual worlds. Traditional spatial queries, designed mainly for one world, do not consider the entangled dual worlds in VR. In this paper, we first investigate the fundamental shortest-path query in VR as the building block for spatial queries, aiming to avoid hitting boundaries and obstacles in the physical environment by leveraging Redirected Walking (RW) in Computer Graphics. Specifically, we first formulate Dual-world Redirected-walking Obstacle-free Path (DROP) to find the minimum-distance path in the virtual world, which is constrained by the RW cost in the physical world to ensure immersive experience in VR. We prove DROP is NP-hard and design a fully polynomial-time approximation scheme, Dual Entangled World Navigation (DEWN), by finding Minimum Immersion Loss Range (MIL Range). Afterward, we show that the existing spatial query algorithms and index structures can leverage DEWN as a building block to support kNN and range queries in the dual worlds of VR. Experimental results and a user study with implementation in HTC VIVE manifest that DEWN outperforms the baselines with smoother RW operations in various VR scenarios.

Recent technological advent in virtual reality (VR) has attracted a lot of attention to the VR shopping, which thus far is designed for a single user. In this paper, we envision the scenario of VR group shopping, where VR supports: 1) flexible display of items to address diverse personal preferences, and 2) convenient view switching between personal and group views to foster social interactions. We formulate the Multiview-Enabled Configuration Recommendation (MECR) problem to rank a set of displayed items for a VR shopping user. We design the Multiview-Enabled Configuration Ranking System (MEIRS) that first extracts discriminative features based on Marketing theories and then introduces a new coupled tensor factorization model to learn the representation of users, Multi-View Display (MVD) configurations, and multiple feedback with content features. Experimental results manifest that the proposed approach outperforms personalized recommendations and group recommendations by at least 30.8% in large-scale datasets and 63.3% in the user study in terms of hit ratio and mean average precision.

With the emergence of virtual reality (VR) like holographic telepresence, it is envisaged that the current networks may be overwhelmed due to the higher bandwidth demand to support high-resolution videos. On the other hand, Camera Blending Field (CBF) has been proposed to restore the occluded regions of cameras to enhance the user’s Quality of Experience (QoE) in VR. In this paper, we explore the source selection to maximize the user’s QoE under the network capacity and 3D reconstruction constraints. We first formulate a new optimization problem, named Source Selection for Real-time Telepresence with Occlusion (SSRTO), with the objective of QoE maximization. Then, we prove the NP-hardness and propose a new algorithm, Maximum Quality of Complete Model (MQCM), to maximize the user’s QoE by examining the proximity of cameras on the built Angle Directed Graph (ADG) and Neighbor Directed Graph (NDG) for reconstructing the complete 3D model. Simulation results show that MQCM can effectively improve the user’s QoE by more than 100% compared with the baseline schemes.

Existing research on social networks manifests two crucial criteria to improve activity engagement of users: (1) user interests in the activity topics and (2) opportunities of making new friends with some acquaintances. However, current online platforms still involve massive manual selection for activity attendees and contents without proper recommendations. In this paper, therefore, we formulate a new activity organization problem, named Social Knowledge Group Query (SKGQ), to recommend attendees and topic-related contents simultaneously. We prove that SKGQ is NP-hard and design an approximation algorithm, named Social cOntent Knowledge Exploration (SOKE), to jointly choose the activity attendees and topic-related contents according to social-oriented and topic- oriented strategies. Simulation results manifest that the solution acquired by SOKE is close to the optimal solution and outperforms various baselines.

Online social networks have become the medium for efficient viral marketing exploiting social influence in information diffusion. However, the emerging application Social Coupon (SC) incorporating social referral into coupons cannot be efficiently solved by previous researches which do not take into account the effect of SC allocation. The number of allocated SCs restricts the number of influenced friends for each user. In the paper, we investigate not only the seed selection problem but also the effect of SC allocation for optimizing the redemption rate which represents the efficiency of SC allocation. Accordingly, we formulate a problem named Seed Selection and SC allocation for Redemption Maximization (S3CRM) and prove the hardness of S3CRM. We design an effective algorithm with a performance guarantee, called Seed Selection and Social Coupon allocation algorithm. For S3CRM, we introduce the notion of marginal redemption to evaluate the efficiency of investment in seeds and SCs. Moreover, for a balanced investment, we develop a new graph structure called guaranteed path, to explore the opportunity to optimize the redemption rate. Finally, we perform a comprehensive evaluation on our proposed algorithm with various baselines. The results validate our ideas and show the effectiveness of the proposed algorithm over baselines.

Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.

Internet of Things (IoT) has been regarded as one of the most significant network paradigms in the future. For IoT, it is crucial to ensure the correctness of detection which includes the factors of accuracy and precision. On the other hand, Mobile Edge Computing (MEC) has emerged as a promising way to process big IoT data at the network edge so as to reduce the computation and transmission energy in the networks. In this paper, we explore the energy minimization problem in MEC networks by considering both the accuracy and precision requirements of IoT. Specifically, given 1) a set of IoT devices, 2) a set of observed targets, 3) an MEC network, 4) the energy consumption model, and 5) the accuracy and precision requirements, we formulate a new optimization problem, named Accuracy and Precision-Aware IoT Device Selection (APAIDS), to minimize the overall energy consumption in MEC networks. We prove the NP-hardness of APAIDS and then propose a new algorithm, named Energy Efficient Device and MEC Server Selection (EDMS), to minimize energy consumption by jointly selecting IoT devices, configuring MEC association, and selecting processing servers for dealing with the data of each target. Finally, we evaluate EDMS on two real networks. In comparison with the baseline schemes, the results manifest that the overall energy consumption can be reduced by more than 60%.

Three essential criteria are important for social activity planning: (1) finding attendees familiar with the initiator, (2) ensuring most attendees have tight social relations with each other, and (3) selecting an activity period available to all. In this paper, we propose the Social-Temporal Group Query (STGQ) to find suitable time and attendees with minimum total social distance. We first prove that the problem is NP-hard and inapproximable within any ratio. Next, we design two algorithms, SGSelect and STGSelect, which include effective pruning techniques to substantially reduce running time. Moreover, as users may iteratively adjust query parameters to fine tune the results, we study the problem of Subsequent Social Group Query (SSGQ). We propose the Accumulative Search Tree and Social Boundary, to cache and index intermediate results of previous queries in order to accelerate subsequent query processing. Experimental results indicate that SGSelect and STGSelect are significantly more efficient than baseline approaches. With the caching mechanisms, processing time of subsequent queries can be further reduced by 50-75 percent. We conduct a user study to compare the proposed approach with manual activity coordination. The results show that our approach obtains higher quality solutions with lower coordination effort, thereby increasing the users' willingness to organize activities.

The popularity of live streaming has led to the explosive growth in new video contents and social communities on emerging platforms such as Facebook Live and Twitch. Viewers on these platforms are able to follow multiple streams of live events simultaneously, while engaging discussions with friends. However, existing approaches for selecting live streaming channels still focus on satisfying individual preferences of users, without considering the need to accommodate real-time social interactions among viewers and to diversify the content of streams. In this paper, therefore, we formulate a new Social-aware Diverse and Preferred Live Streaming Channel Query (SDSQ) that jointly selects a set of diverse and preferred live streaming channels and a group of socially tight viewers. We prove that SDSQ is NP-hard and inapproximable within any factor, and design SDSSel, a 2-approximation algorithm with a guaranteed error bound. We perform a user study on Twitch with 432 participants to validate the need of SDSQ and the usefulness of SDSSel. We also conduct large-scale experiments on real datasets to demonstrate the superiority of the proposed algorithm over several baselines in terms of solution quality and efficiency.

While the popularity of online social network (OSN) apps continues to grow, little attention has been drawn to the increasing cases of Social Network Addictions (SNAs). In this paper, we argue that by mining OSN data in support of online intervention treatment, data scientists may assist mental healthcare professionals to alleviate the symptoms of users with SNA in early stages. Our idea, based on behavioral therapy, is to incrementally substitute highly addictive newsfeeds with safer, less addictive, and more supportive newsfeeds. To realize this idea, we propose a novel framework, called Newsfeed Substituting and Supporting System (N3S), for newsfeed filtering and dissemination in support of SNA interventions. New research challenges arise in 1) measuring the addictive degree of a newsfeed to an SNA patient, and 2) properly substituting addictive newsfeeds with safe ones based on psychological theories. To address these issues, we first propose the Additive Degree Model (ADM) to measure the addictive degrees of newsfeeds to different users. We then formulate a new optimization problem aiming to maximize the efficacy of behavioral therapy without sacrificing user preferences. Accordingly, we design a randomized algorithm with a theoretical bound. A user study with 716 Facebook users and 11 mental healthcare professionals around the world manifests that the addictive scores can be reduced by more than 30%. Moreover, experiments show that the correlation between the SNA scores and the addictive degrees quantified by the proposed model is much greater than that of state-of-the-art preference based models.

With the emergence of multi-view 3D videos, network operators now face a new challenge to resolve the dramatic increase of the network bandwidth required to support all subscribed views (typically 16 or 32) of a video. Recently, Depth-Image-Based Rendering (DIBR) in Computer Vision has been demonstrated as a promising way for efficient multi-view 3D video multicast, because many views can be synthesized in mobile devices and no longer need to be transmitted. Nevertheless, DIBR is computationally intensive and incurs additional power consumption in mobile devices, and unsubscribed views need to be transmitted to mobile users for DIBR. In this paper, therefore, we aim to leverage Mobile Edge Computing (MEC) for DIBR to foster effective and efficient multi-view video multicast. We formulate a new problem, named Multi-view Multicast Synthesis and Delivery (MMSD) and prove the NP-Hardness. We design an approximation algorithm, named Merge Search Forest Algorithm (MSFA), to choose the view to be synthesized and build a multicast topology including a low-cost forest for supporting each subscribed view. Simulation results manifest that MSFA outperforms the existing approaches by 30% to 50% of the total communication and computation cost.

Mobile Edge Computing (MEC) has recently emerged as a primary candidate for big data processing to reduce the latency and jitter. On the other hand, Software-Defined Internet of Things (SD-IoT) has been proposed to effectively and flexibly collect and process big IoT data. Nevertheless, minimizing the energy consumption in SD-IoT with big data processing (e.g., data aggregation and reconstruction) has not been explored before. In this paper, therefore, we explore the sensor data selection and routing problem in SD-IoT with big data processing. Specifically, given 1) a set of sensors, 2) a set of observed locations, 3) the network topology, and 4) the energy consumption model of big data processing and forwarding, we formulate a new optimization problem, named Sensor Data Selection, Processing, and Routing Problem (SDSPRP), to minimize the total energy consumption in SD-IoT. We prove that the emphasized problem is NP-hard and inapproximable within O(log|K|). To solve the problem, we propose an αlog|K|- approximation algorithm, called Energy Efficient Sensor Selection and Routing (ESR), to minimize the energy consumption by jointly considering the sensor selection and the energy consumption in traffic engineering and data processing. The proposed algorithm is evaluated on two real networks, and the results manifest that the energy consumption in SD- IoT can be reduced by more than 56%.

Previous research on SDN traffic engineering mostly focuses on static traffic, whereas dynamic traffic, though more practical, has drawn much less attention. Especially, online SDN multicast that supports IETF dynamic group membership (i.e., any user can join or leave at any time) has not been explored. Different from traditional shortest-path trees (SPT) and graph theoretical Steiner trees (ST), which concentrate on routing one tree at any instant, online SDN multicast traffic engineering is more challenging because it needs to support dynamic group membership and optimize a sequence of correlated trees without the knowledge of future join and leave, whereas the scalability of SDN due to limited TCAM is also crucial. In this paper, therefore, we formulate a new optimization problem, named Online Branch-aware Steiner Tree (OBST), to jointly consider the bandwidth consumption, SDN multicast scalability, and rerouting overhead. We prove that OBST is NP-hard and does not have a |Dmax|1-ε-competitive algorithm for any , where |Dmax| is the largest group size at any time. We design a |Dmax|-competitive algorithm equipped with the notion of the budget, the deposit, and Reference Tree to achieve the tightest bound. The simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 25% compared with SPT and ST, and the computation time is small for massive SDN.

Because Online Social Networks (OSNs) have become increasingly important in the last decade, they have motivated a great deal of research on Social Network Analysis (SNA). Currently, SNA algorithms are evaluated on real datasets obtained from large-scale OSNs, which are usually sampled by Breadth-First-Search (BFS), Random Walk (RW), or some variations of the latter. However, none of the released datasets provides any statistical guarantees on the difference between the sampled datasets and the ground truth. Moreover, all existing sampling algorithms only focus on sampling a single OSN, but each OSN is actually a sampling of a complete social network. Hence, even if the whole dataset from a single OSN is sampled, the results may still be skewed and may not fully reflect the properties of the complete social network. To address the above issues, we have made the first attempt to explore the joint sampling of multiple OSNs and propose an approach called Quality-guaranteed Multi-network Sampler (QMSampler) that can jointly sample multiple OSNs. QMSampler provides a statistical guarantee on the difference between the sampled real dataset and the ground truth (the perfect integration of all OSNs). Our experimental results demonstrate that the proposed approach generates a much smaller bias than any existing method. QMSampler has also been released as a free download.

The explosive growth in popularity of social networking leads to the problematic usage. An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental status cannot be directly observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires in Psychology. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD), that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMD-based Tensor Model (STM) to improve the accuracy. To increase the scalability of STM, we further improve the efficiency with performance guarantee. Our framework is evaluated via a user study with 3,126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results manifest that SNMDD is promising for identifying online social network users with potential SNMDs.

With the advance of the photovoltaic panel technology, the infrastructure equipment of cellular networks with solar energy sources has attracted extensive interests. It is expected that base stations (BSs) and relay stations (RSs) with renewable energy will play important roles in reducing the power consumption from electrical grids in future green cellular networks. Inspired by this technology trend, this paper considers a heterogeneous green cellular network, in which a part of RSs is powered by solar energy sources to represent the incremental deployment for the infrastructure with renewable energy in the near future. We formulate a new relay selection and power allocation problem with Mixed Integer Linear Programming to select solar-powered RSs and grid-powered RSs, such that the total grid power consumption is effectively minimized in decode-and-forward cooperative communication networks. We design an algorithm to derive the optimal solution, and also devise an efficient distributed algorithm to reduce the computational cost. The simulation results demonstrate that the algorithms can effectively reduce the total grid power consumption with different channel conditions, different deployments of RSs in a network, and different available power levels in solar-powered RSs. In addition, the problem model and the proposed algorithms can be extended to support hybrid energy sources.

With the recent emergence of naked-eye 3D mobile devices and various 3D-enabled laptops, service providers now afford the opportunity to provide mobile 3D video streaming in LTE-Advanced networks. Differing from traditional single-view 3D videos, multi-view 3D videos allow users to choose preferred view angles and thus are promising for new applications, such as free-viewpoint television (FTV). Nevertheless, enabling multi-view 3D video services may overwhelm the network resource when transmitting all views of every video. Fortunately, Depth-Image-Based Rendering (DIBR) allows each mobile client to synthesize the desired view from a nearby left view and right view, so that not all views of a video are necessarily transmitted. A new challenge with DIBR, however, is to carefully choose the transmitted views to limit the video distortion and minimize the bandwidth consumption. In this paper, therefore, we first formulate a new optimization problem, called View and MCS Selection (VMS) Problem, to minimize the bandwidth consumption for multi-view 3D video multicast in LTE networks. An algorithm, called View and MCS Aggregation (VMAG) is proposed to find the optimal solution to VMS. For Carrier Aggregation (CA) in LTE-Advanced networks, we formulate a new View, MCS and Carrier Selection (VMCS) Problem and prove that the problem is NP-Hard. We first design a dynamic programming algorithm, called the View Assignment with MCS and Carrier (VAMC) algorithm, to find the optimal solution for small instances. We then propose the View and MCS Aggregation with Carrier (VMAGC) algorithm based on VMAG to effectively find the near-optimal solution to VMCS. The simulation results show that bandwidth consumption can be effectively reduced by over 30 percent in VMS and VMCS.

Most scheduling algorithms in the literature for cellular networks are concerned with throughput, fairness, or cost optimization. Recently, however, wireless surveillance in cellular networks has become increasingly important, and more and more institutions and companies have adopted commercial cellular surveillance cameras due to their low installation cost and the wide network coverage. In this paper, therefore, we first explore the resource allocation problem for a multi-camera surveillance system in cellular networks. We minimize the number of allocated resource blocks (RBs) while simultaneously ensuring the coverage requirement for the surveillance system in cellular networks. Specifically, we first describe our system model and then formulate the Camera Set Resource Allocation Problem (CSRAP). Next, we prove that the problem is NP-hard and inapproximable within ln n, where n is the number of surveillance targets. To solve the problem, we propose an approximation algorithm for the general case of CSRAP and then we find the optimal solutions of three deployments of cameras in the Manhattan Street Network to find the intrinsic characteristics of camera selections. The simulation results, based on two real surveillance maps and synthetic datasets, show that the number of allocated RBs can be effectively reduced compared to the existing approach for cellular networks.

Software-Defined Networking and Network Function Virtualisation (SDN/NFV) can provide flexible resource allocation to support innovative security solutions in a central manner. To mitigate HTTP DDoS attacks, shuffling-based moving target defense has been regarded as one of the most effective ways by redirecting user traffic among a group of virtualized service functions. However, previous work did not notice that frequent changes of user traffic will significantly intensify the control overhead of SDN. In this paper, therefore, we first model the effectiveness and cost for shuffling in SDN/NFV networking with Multi-Objective Markov Decision Processes to find the optimal tradeoff between the effectiveness and cost. We then propose a cost-effective approximation algorithm with a guarantee performance bound to solve the problem. Simulation and implementation on an experimental SDN/NFV network manifest that, given 100 attackers among 1000 users and 50 virtualized functions of a web service, our algorithm achieves the approximation ratio of 0.68 and imposes only 2.4s rule modification latency for each shuffle.

Network Function Virtualization (NFV) on Software-Defined Networks (SDN) can effectively optimize the allocation of Virtual Network Functions (VNFs) and the routing of network flows simultaneously. Nevertheless, most previous studies on NFV focus on unicast service chains and thereby are not scalable to support a large number of destinations in multicast. On the other hand, the allocation of VNFs has not been supported in the current SDN multicast routing algorithms. In this paper, therefore, we make the first attempt to tackle a new challenging problem for finding a service forest with multiple service trees, where each tree contains multiple VNFs required by each destination. Specifically, we formulate a new optimization, named Service Overlay Forest (SOF), to minimize the total cost of all allocated VNFs and all multicast trees in the forest. We design a new 3ρST-approximation algorithm to solve the problem, where ρSTdenotes the best approximation ratio of the Steiner Tree problem, and the distributed implementation of the algorithm is also presented. Simulation results on real networks for data centers manifest that the proposed algorithm outperforms the existing ones by over 25%. Moreover, the implementation of an experimental SDN with HP OpenFlow switches indicates that SOF can significantly improve the QoE of the Youtube service.

With software-defined network (SDN) and network function virtualization (NFV) techniques, we can embed the service chain consisting of a sequence of virtualized network functions (VNFs), i.e., we can determine the flow path and deploy the VNFs contained in the service chain at any place on the path. In the literature, the methods of service chain embedding bound the number of VNFs at a node, whereas the link capacities are disregarded and the amount of flows is not considered, which could cause serious congestion. In addition, according to our experiment, the process overhead on a computation node is linear to the total amount of flows processed. In this paper, we propose a method of service chain embedding to maximize the total amount of flows while bounding the process overhead of the flows on a node by its computation capability and the total amount of flows on an link by its bandwidth capacity. To our knowledge, our method is the first approximation algorithm of service chain embedding with considering flow in the literature. Simulations show our algorithm has good performance in terms of the total amount of flows.

Existing research on finding social groups mostly focuses on dense subgraphs in social networks. However, finding socially tenuous groups also has many important applications. In this paper, we introduce the notion of k-triangles to measure the tenuity of a group. We then formulate a new research problem, Minimum k-Triangle Disconnected Group (MkTG), to find a socially tenuous group from online social networks. We prove that MkTG is NP-Hard and inapproximable within any ratio in arbitrary graphs but polynomial-time tractable in threshold graphs. Two algorithms, namely TERA and TERA-ADV, are designed to exploit graph-theoretical approaches for solving MkTG on general graphs effectively and efficiently. Experimental results on seven real datasets manifest that the proposed algorithms outperform existing approaches in both efficiency and solution quality.

The small screen size of a smartwatch limits user experience when watching or interacting with media. We propose a supplementary tactile feedback system to enhance the user experience with a method unique to the smartwatch form factor. Our system has a deformable surface on the back of the watch face, allowing the visual scene on screen to extend into 2.5D physical space. This allows the user to watch and feel virtual objects, such as experiencing a ball bouncing against the wrist. We devised two controlled experiments to analyze the influence of tactile display resolution on the illusion of virtual object presence. Our first study revealed that on average, a taxel can render virtual objects between 70% and 138% of its own size without shattering the illusion. From the second study, we found visual and haptic feedback can be separated by 4.5mm to 16.2mm for the tested taxels. Based on the results, we developed a prototype (called RetroShape) with 4×4 10mm taxels using micro servo motors, and demonstrated its unique capability through a set of tactile-enhanced games and videos. A preliminary user evaluation showed that participants welcome RetroShape as a useful addition to existing smartwatch output.

Thumb-to-fingers interfaces augment touch widgets on fingers, which are manipulated by the thumb. Such interfaces are ideal for one-handed eyes-free input since touch widgets on the fingers enable easy access by the stylus thumb. This study presents DigitSpace, a thumb-to-fingers interface that addresses two ergonomic factors: hand anatomy and touch precision. Hand anatomy restricts possible movements of a thumb, which further influences the physical comfort during the interactions. Touch precision is a human factor that determines how precisely users can manipulate touch widgets set on fingers, which determines effective layouts of the widgets. Buttons and touchpads were considered in our studies to enable discrete and continuous input in an eyes-free manner. The first study explores the regions of fingers where the interactions can be comfortably performed. According to the comfort regions, the second and third studies explore effective layouts for button and touchpad widgets. The experimental results indicate that participants could discriminate at least 16 buttons on their fingers. For touchpad, participants were asked to perform unistrokes. Our results revealed that since individual participant performed a coherent writing behavior, personalized $1 recognizers could offer 92% accuracy on a cross-finger touchpad. A series of design guidelines are proposed for designers, and a DigitSpace prototype that uses magnetic-tracking methods is demonstrated.

Due to the emergence of mobile 3D and VR devices, multi-view 3D videos are expected to play increasingly important roles shortly. Compared with traditional single-view videos, it is envisaged that a multi-view 3D video requires a larger storage space. Nevertheless, efficient caching of multi-view 3D videos in a proxy has not been explored in the literature. In this paper, therefore, we first observe that the storage space can be effectively reduced by leveraging Depth Image Based Rendering (DIBR) in multi-view 3D. We then formulate a new cache replacement problem, named View Selection and Cache Operation (VSCO), and find the optimal policy based on Markov Decision Process. Also, we devise an efficient and effective algorithm to solve the problem. Simulation results manifest that the proposed algorithm can significantly improve the cache hit rate and reduce the total cost compared with the previous renowned cache replacement algorithms.

With the emergence of 3D mobile and VR devices, mobile 3D video services are becoming increasingly important for video service providers, such as Youtube and Netflix, while multi-view 3D videos have the potential to inspire a variety of innovative applications. However, enabling multi- view 3D video services may overwhelm WiFi networks when every view of a video are multicasted. In this paper, therefore, we propose to leverage depth-image-based rendering (DIBR) in multi-view 3D, which allows each mobile client to synthesize the desired view from nearby left and right views, in order to effectively reduce the bandwidth consumption. Moreover, when each client suffers from packet losses, retransmissions incur additional bandwidth consumption and excess delay, which in turn undermines the quality of experience in video applications. To address the above issue, we first discover the merit of view protection via DIBR for multi-view video multicast using a mathematical analysis and then design a new protocol, named Multi-View Group Management Protocol (MVGMP), to support the dynamic join and leave of users and the change of desired views. The simulation results demonstrate that our protocol effectively reduces bandwidth consumption and increases the probability for each client to successfully playback the desired views in a multi-view 3D video.

Most prior algorithms for influence maximization focused are designed for Online Social Networks (OSNs) and require centralized computation. Directly deploying the above algorithms in distributed Mobile Social Networks (MSNs) will overwhelm the networks due to an enormous number of messages required for seed selection. In this paper, therefore, we design a new cross-layer strategy to jointly examine MSN and mobile ad hoc networks (MANETs) to facilitate efficient seed selection, by extracting a subset of nodes as agents to represent nearby friends during the distributed computation. Specifically, we formulate a new optimization problem, named Agent Selection Problem (ASP), to minimize the message overhead transmitted in MANET. We prove that ASP is NP-Hard and design an effectively distributed algorithm. Simulation results in real and synthetic datasets manifest that the message overhead can be significantly reduced compared with the existing approaches.

Deep packet filtering (DPF) has been demonstrated as an essential technique for effective fine-grained access controls, but it is commonly recognized that the technique may invade the individual privacy of the users. Secure computation can address the tradeoff between privacy and DPF functionality, but the current solutions limit the scalability of the network due to the intensive computation overheads and large connection setup delay, especially for the latest network paradigm, network function virtualisation (NFV) and software-defined network (SDN). In this paper, therefore, we propose a privacy-preserving deep packet filtering protocol, named DPF-ET, that can efficiently perform filtering function over encrypted traffic while diminishing the communication overhead and setup delay for the controller in SDN. DPF-ET guarantees the data privacy for users and remains rule privacy for the network owner. The implementation results on an experimental HP SDN/NFV platform demonstrate that the proposed DPF-ET outperforms the current approaches by reducing 250 times in the communications overhead and 32 times in the setup delay.

Owing to the rising popularity of online social networking services (OSNs), studies on social influence and its diffusion have received significant attention from the research community. Prior research has mostly studied the impact of single-hop influence diffusion and multi-hop influence broadcast in online social networks. Very little research explores the idea of guiding (routing) multi-hop social influence towards a specific target. In this paper, we motivate the needs of timely routing social influence to formulate a new optimization problem, namely, Routing And Scheduling of Target-Oriented Social Influence Diffusion (RAS-TOSID). Accordingly, we propose the Efficient Routing And Scheduling with Social and Temporal decOmposition (ERASSTO) algorithm, which finds the optimal solution to RAS-TOSID in polynomial time. We carry out a user study by implementing ERASSTO in Facebook and conduct a comprehensive evaluation on ERASSTO and alternative approaches by simulation. The result shows that ERASSTO significantly outperforms other algorithms regarding solution quality and computational efficiency.

Although Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, current literature mostly focuses on unicast communications. Compared to traffic engineering for multiple unicast flows, multicast traffic engineering for multiple trees is very challenging not only because minimizing the bandwidth consumption of a single multicast tree by solving the Steiner tree problem is already NP-Hard, but the Steiner tree problem does not consider the link capacity constraint for multicast flows and node capacity constraint to store the forwarding entries in Group Table of OpenFlow. In this paper, therefore, we first study the hardness results of scalable multicast traffic engineering in SDN. We prove that scalable multicast traffic engineering with only the node capacity constraint is NP-Hard and not approximable within δ, which is the number of destinations in the largest multicast group. We then prove that scalable multicast traffic engineering with both the node and link capacity constraints is NP-Hard and not approximable within any ratio. To solve the problem, we design a δ-approximation algorithm, named Multi-Tree Routing and State Assignment Algorithm (MTRSA), for the first case and extend it to the general multicast traffic engineering problem. The simulation and implementation results demonstrate that the solutions obtained by the proposed algorithm outperform the shortest-path trees and Steiner trees. Most importantly, MTRSA is computation-efficient and can be deployed in SDN since it can generate the solution with numerous trees in a short time.

Research issues and data mining techniques for product recommendation and viral marketing have been widely studied. Existing works on seed selection in social networks do not take into account the effect of product recommendations in e-commerce stores. In this paper, we investigate the seed selection problem for viral marketing that considers both effects of social influence and item inference (for product recommendation). We develop a new model, Social Item Graph (SIG), that captures both effects in the form of hyperedges. Accordingly, we formulate a seed selection problem, called Social Item Maximization Problem (SIMP), and prove the hardness of SIMP. We design an efficient algorithm with performance guarantee, called Hyperedge-Aware Greedy (HAG), for SIMP and develop a new index structure, called SIG-index, to accelerate the computation of diffusion process in HAG. Moreover, to construct realistic SIG models for SIMP, we develop a statistical inference based framework to learn the weights of hyperedges from data. Finally, we perform a comprehensive evaluation on our proposals with various baselines. Experimental result validates our ideas and demonstrates the effectiveness and efficiency of the proposed model and algorithms over baselines.

Force sensing has been widely used for bringing the touch from binary to multiple states, creating new abilities on surface interactions. However, prior proposed force sensing techniques mainly focus on enabling force-applied gestures on certain devices. This paper presents Nail+, a technique using fingernail deformation to enable force touch sensing interactions on everyday rigid surfaces. Our prototype, 3x3 0.2mm strain sensor array mounted on a fingernail, was implemented and conducted with a 12-participant study for evaluating the feasibility of this sensing approach. Result showed that the accuracy for sensing normal and force-applied tapping and swiping can achieve 84.67% on average. We finally proposed two example applications using Nail+ prototype for controlling the interfaces of head-mounted display (HMD) devices and remote screens.

An increasing number of social network mental disorders (SNMDs), such as Cyber-Relationship Addiction, Information Overload, and Net Compulsion, have been recently noted. Symptoms of these mental disorders are usually observed passively today, resulting in delayed clinical intervention. In this paper, we argue that mining online social behavior provides an opportunity to actively identify SNMDs at an early stage. It is challenging to detect SNMDs because the mental factors considered in standard diagnostic criteria (questionnaire) cannot be observed from online social activity logs. Our approach, new and innovative to the practice of SNMD detection, does not rely on self-revealing of those mental factors via questionnaires. Instead, we propose a machine learning framework, namely, Social Network Mental Disorder Detection (SNMDD), that exploits features extracted from social network data to accurately identify potential cases of SNMDs. We also exploit multi-source learning in SNMDD and propose a new SNMDbased Tensor Model (STM) to improve the performance. Our framework is evaluated via a user study with 3126 online social network users. We conduct a feature analysis, and also apply SNMDD on large-scale datasets and analyze the characteristics of the three SNMD types. The results show that SNMDD is promising for identifying online social network users with potential SNMDs.

Spatial proximity is one of the most important factors for the quick deployment of the task groups in various time-sensitive missions. This article proposes a new spatial query, Spatio-Social Team Query (SSTQ) , that forms a strong task group by considering (1) the group’s spatial distance (i.e., transportation time), (2) skills of the candidate group members, and (3) social rapport among the candidates. Efficient processing of SSTQ is very challenging, because the aforementioned spatial, skill, and social factors need to be carefully examined. In this article, therefore, we first formulate two subproblems of SSTQ, namely Hop-Constrained Team Problem (HCTP) and Connection-Oriented Team Query (COTQ) . HCTP is a decision problem that considers only social and skill dimensions. We prove that HCTP is NP-Complete. Moreover, based on the hardness of HCTP, we prove that SSTQ is NP-Hard and inapproximable within any factor . On the other hand, COTQ is a special case of SSTQ that relaxes the social constraint. We prove that COTQ is NP-Hard and propose an approximation algorithm for COTQ, namely COTprox . Furthermore, based on the observations on COTprox, we devise an approximation algorithm, SSTprox , with a guaranteed error bound for SSTQ. Finally, to efficiently obtain the optimal solution to SSTQ for small instances, we design two efficient algorithms, SpatialFirst and SkillFirst , with different scenarios in mind. These two algorithms incorporate various effective ordering and pruning techniques to reduce the search space for answering SSTQ. Experimental results on real datasets indicate that the proposed algorithms can efficiently answer SSTQ under various parameter settings.

The development and integration of social networking services and smartphones have made it easy for individuals to organize impromptu social activities anywhere and anytime. Main challenges arising in organizing impromptu activities are mostly due to the requirements of making timely invitations in accordance with the potential activity locations, corresponding to the locations of, and the relationships among the candidate attendees. Various combinations of candidate attendees and activity locations create a large solution space. Thus, in this paper, we propose Multiple Rally-Point Social Spatial Group Query (MRGQ), to select an appropriate activity location for a group of nearby attendees with tight social relationships. We first consider a special case of MRGQ, namely the Socio-Spatial Group Query (SSGQ), to determine a set of socially acquainted attendees while minimizing the total spatial distance to a specific activity location. We prove that SSGQ is NP-hard and formulate an Integer Linear Programming optimization model for SSGQ. We then develop an efficient algorithm, called SSGS, which employs effective pruning techniques to reduce the running time to determine the optimal solution. Moreover, we propose a heuristic algorithm for SSGQ to efficiently produce good solutions. We next consider the more general MRGQ. Although MRGQ is NP-hard, the number of attendees in practice is usually small enough such that an optimal solution can be found efficiently. Therefore, we first propose an Integer Linear Programming optimization model for MRGQ. We then design an efficient algorithm, called MAGS, which employs effective search space exploration and pruning strategies to reduce the running time for finding the optimal solution. We also propose to further optimize efficiency by indexing the potential activity locations. A user study demonstrates the strength of using SSGS and MAGS over manual coordination in terms of both solution quality and efficiency. Experimental results on real datasets show that our algorithms can process SSGQ and MRGQ efficiently and significantly outperform other baseline algorithms, including one based on the commercial parallel optimizer IBM CPLEX.

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.

Power and on-off control problems are examined for renewable energy enabled base-stations (BSs) and relay nodes (RNs) in cooperative multicast networks. Renewable energy is utilized at BSs and RNs to reduce the overall grid energy cost. By considering a practical energy consumption model and the statistics of the renewable energy arrival, the optimal transmit powers are first determined by minimizing the expected grid energy consumption subject to an average outage probability constraint at MUs. The optimal solution is found via line search in the general case and is obtained in closed-form at high SNR. In addition, an on-off control policy is also proposed to further reduce the basic operational energy costs. The joint on-off and power control problems are solved approximately using two sequential deflation techniques, namely, the subset-search and the convex-relaxation-based approaches. The power control problem is also extended to the multicarrier scenario with unequal transmit powers and is solved using successive convex approximation. Simulations using the photovoltaic energy arrival model are provided to demonstrate the effectiveness of the proposed schemes. The results show that expending more power at RNs allows for more efficient use of renewable energy and, thus, increases energy-savings.

Viral marketing, a marketing strategy that leverages the influence power in intimate relationship, has become more prevalent due to the popularity of online social networking services in recent years. Consumers are more likely to make a purchase based on social media referrals. Since marketing through social media and traditional channels may target on different audiences, how to maximize the revenue of a telecommunications company by employing different advertising ways and selecting initial users for advertisements is a critical problem. Therefore, in this paper, we formulate a new research problem, namely Cost-Aware Multi-wAy Influence maXimization (CAMAIX) to address the need mentioned above. We design a 1/2-approximation algorithm with various pruning and budget allocation strategies to solve CAMAIX efficiently. We conduct extensive experiments on a large-scale real dataset from a telecommunications company. The results show that our proposed algorithm outperforms the baseline algorithms in both solution quality and efficiency.

This work presents WonderLens, a system of optical lenses and mirrors for enabling tangible interactions on printed paper. When users perform spatial operations on the optical components, they deform the visual content that is printed on paper, and thereby provide dynamic visual feedback on user interactions without any display devices. The magnetic unit that is embedded in each lens and mirror allows the unit to be identified and tracked using an analog Hall-sensor grid that is placed behind the paper, so the system provides additional auditory and visual feedback through different levels of embodiment, further enhancing the interactivity with the printed content on the physical paper.

While online social networks have become a part of many people's daily lives, Internet and social network addictions (ISNAs) have been noted recently. With increased patients in addictive Internet use, clinicians often form support groups to help patients. This has become a trend because groups organized around therapeutic goals can effectively enrich members with insight and guidance while holding everyone accountable along the way. With the emergence of online social network services, there is a trend to form support groups online with the aid of mental health professionals. Nevertheless, it becomes impractical for a psychiatrist to manually select the group members because she faces an enormous number of candidates, while the selection criteria are also complicated since they span both the social and symptom dimensions. To effectively address the need of mental healthcare professionals, this paper makes the first attempt to study a new problem, namely Member Selection for Online Support Group (MSSG). The problem aims to maximize the similarity of the symptoms of all selected members, while ensuring that any two members are unacquainted to each other. We prove that MSSG is NP-Hard and inapproximable within any ratio, and design a 3-approximation algorithm with a guaranteed error bound. We evaluate MSSG via a user study with 11 mental health professionals, and the results manifest that MSSG can effectively find support group members satisfying the member selection criteria. Experimental results on large-scale real datasets also demonstrate that our proposed algorithm outperforms other baselines in terms of solution quality and efficiency.

With the ubiquity of social networks and mobile devices, various new mobile applications for impromptu group formation and communications have emerged recently, such as Meetup, Plancast, Yahoo! Upcoming, Eventbrite and Epinions. Among those important applications, finding a dense subgraph in a social network plays a crucial role, but the current algorithms are only designed for online social networks. Different from online social networks, no central repository is available in mobile social networks (MSNs). Finding a dense subgraph in a distributed manner without compromising the individual privacy is very challenging, because a dense subgraph usually includes abundant friendship information. To address this important need for MSNs, we propose a privacy-preserving k-core discovery protocol, named PKcore. We show that the solution group returned by our protocol is optimal. In addition, we guarantee that the MSN users in our protocol do not reveal any social links to both the initiator and the other contacts. We also prove that the privacy properties based on Canetti's model always hold. Finally, we analyze the computation and communication overheads and show that our protocol is feasible for current mobile devices.

Wireless surveillance in cellular networks has become increasingly important, while commercial LTE surveillance cameras are also available nowadays. Nevertheless, most scheduling algorithms in the literature are throughput, fairness, or profit-based approaches, which are not suitable for wireless surveillance. In this paper, therefore, we explore the resource allocation problem for a multi-camera surveillance system in 3GPP Long Term Evolution (LTE) uplink (UL) networks. We minimize the number of allocated resource blocks (RBs) while ensuring the coverage requirement for surveillance systems in LTE UL networks. Specifically, we formulate the Camera Set Resource Allocation Problem (CSRAP) and prove that the problem is NP-Hard. We then propose an Integer Linear Programming formulation for general cases to find the optimal solution. Moreover, we present a baseline algorithm and devise an approximation algorithm to solve the problem. Simulation results based on a real surveillance map and synthetic datasets manifest that the number of allocated RBs can be effectively reduced compared to the existing approach for LTE networks.

With the recent emergence of 3D TVs, video service providers now face an opportunity to provide high resolution multi-view 3D videos over IP networks. One simple way is to deliver each desired view in a multicast stream. Nevertheless, it is expected that significantly increased bandwidth will be required to support the transmission of all views in multi-view 3D videos. However, the recent emergence of a new video synthesis technique called Depth-Image-Based Rendering (DIBR) suggests that a multi-view 3D video does not necessarily require the transmission of all views. Therefore, we formulate a new problem, named Multi-view and Multicast Delivery Selection Problem (MMDS), and design an algorithm, called MMDEA, to find the optimal solution. Simulation results manifest that using DIBR can effectively reduce bandwidth consumption by 35% compared to the original multicast delivery scheme.

Current traffic engineering in SDN mostly focuses on unicast. By contrast, compared with individual unicast, multicast can effectively reduce network resources consumption to serve multiple clients jointly. Since many important applications require reliable transmissions, it is envisaged that reliable multicast plays a crucial role when an SDN operator plans to provide multicast services. However, the shortest-path tree (SPT) adopted in current Internet is not bandwidth-efficient, while the Steiner tree (ST) in Graph Theory is not designed to support reliable transmissions since the selection of recovery nodes is not examined. In this paper, therefore, we propose a new reliable multicast tree for SDN, named Recover-aware Steiner Tree (RST). The goal of RST is to minimize both tree and recovery costs, while finding an RST is very challenging. We prove that the RST problem is NP-Hard and inapproximable within k, which is the number of destination nodes. Thus, we design an approximate algorithm, called Recover Aware Edge Reduction Algorithm (RAERA), to solve the problem. The simulation results on real networks and large synthetic networks, together with the experiment on our SDN testbed with real YouTube traffic, all manifest that RST outperforms both SPT and ST. Also, the implementation of RAERA in SDN controllers shows that an RST can be returned within a few seconds and thereby is practical for SDN networks.

Due to the proliferation of applications for the Internet of Things, an increasing number of machine to machine (M2M) devices are being deployed. In particular, one of the M2M applications, video surveillance, has been widely discussed. Long Term Evolution (LTE), which can provide a high rate of data transmission and wide range of coverage, is a promising standard to serve as an M2M video surveillance system. In this paper, we study a performance maximization problem in an LTE video surveillance system. Given a set of objects and a set of cameras, each camera has its own performance grade and its own coverage. The goal is to maximize the performance of the system by allocating limited resources to cameras while all objects should be monitored by the selected cameras. We propose a heuristic method to select the cameras and allocate resources to them to solve the problem. Moreover, to reduce the load of the LTE system, a dynamic adjustment method is also proposed.

Depth-Image-Based Rendering (DIBR) is a popular technology and enables the viewers to watch multi-view 3D videos via TV or smart phone. In this paper, we propose a game-theoretical framework over a multi-view and multi-video network where one server delivers multiple multi-view 3D videos to multiple viewers. In a mobile network, any individual viewers can subscribe to a video with any viewing angle within a specified viewing range in 3D-enabled mobile handsets. To facilitate efficient resource allocation for multi-view 3D videos, we formulate a new resource allocation problem, named Price-based 3D Viewing Range Control problem (PVRC), as a Stackelberg game in Game Theory, in which the server and the viewers are modeled as the leader and the followers, respectively, to jointly consider the revenue of the server and the utilities of the viewers. We analyze the price setting problem by investigating the Stackelberg equilibrium between the server and viewers. Simulation results demonstrate that compared to popular uniform-price setting, non-uniform pricing is an effective approach for reducing the difference of utilities among the viewers, effectively controlling the viewing ranges and avoiding starvation of the network resources to only few viewers. Moreover, we also derive the social optimum in the problem, and the simulation results show that the derived Stackelberg equilibrium is close to the social optimum.

This work describes a novel building block system for tangible interaction design, GaussBricks, which enables real-time constructive tangible interactions on portable displays. Given its simplicity, the mechanical design of the magnetic building blocks facilitates the construction of configurable forms. The form constructed by the magnetic building blocks, which are connected by the magnetic joints, allows users to stably manipulate with various elastic force feedback mechanisms. With an analog Hall-sensor grid mounted to its back, a portable display determines the geometrical configuration and detects various user interactions in real time. This work also introduce several methods to enable shape changing, multi-touch input, and display capabilities in the construction. The proposed building block system enriches how individuals interact with the portable displays physically.

Business location planning, critical to success of many businesses, can be addressed by reverse nearest neighbors (RNN) query using geographical proximity to the customers as the main metric to find a store location which is the closest to many customers. Nevertheless, we argue that other marketing factors such as social influence could be considered in the process of business location planning. In this paper, we propose a framework for business location planning that takes into account both factors of geographical proximity and social influence. An essential task in this framework is to compute the “influence spread” of RNNs for candidate locations. However, excessive computational overhead and long latency hinder its feasibility for our framework. Thus, we trade storage overhead for the processing speed by precomputing and storing the social influences between pairs of customers and design a suite of algorithms based on Targeted Region-oriented strategy. Various ordering and pruning techniques have been incorporated in these algorithms to enhance the processing efficiency of our framework. Experiments also show that the proposed algorithms efficiently support the task of location planning under various parameter settings.

Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, but at the same time the scalability problem becomes more serious since traffic is more difficult to be aggregated. Those crucial issues in SDN have been studied for unicast but have not been explored for multicast traffic, and addressing those issues for multicast is more challenging since the identities and the number of members in a multicast group can be arbitrary. In this paper, therefore, we propose a new multicast tree for SDN, named Branch-aware Steiner Tree (BST). The BST problem is difficult since it needs to jointly minimize the numbers of the edges and the branch nodes in a tree, and we prove that it is NP-Hard and inapproximable within k, which denotes the number of group members. We further design an approximation algorithm, called Branch Aware Edge Reduction Algorithm (BAERA), to solve the problem. Simulation results demonstrate that the trees obtained by BAERA are more bandwidth-efficient and scalable than the shortest-path trees and traditional Steiner trees. Most importantly, BAERA is computation-efficient to be deployed in SDN since it can generate a tree on massive networks in small time.

The effectiveness of epidemic routing for information dissemination in energy harvesting wireless sensor networks is examined in this work. Here, information is to be disseminated from a few nodes to a considerable fraction of all other nodes in the network. The use of epidemic routing is motivated by the fact that, when sensors are supported solely by harvested energy, the sensors' availability and the network topology may change dynamically due to the uncertainty of the energy arrival at the sensors. With epidemic routing, a node will receive and forward a packet to all other nodes in its neighborhood whenever it is able to do so. Each node will keep the packet only for a certain time duration depending on its recovery rate. By utilizing only energy harvested from the environment, the transmission radius of each sensor (and, thus, the network connectivity) is affected by its local energy arrival and the time in between transmissions. The less frequently it transmits, the further the distance it is able to reach. Two cases are examined in this work: 1) the case with identical transmission radius and 2) the case with identical inter-transmission time. The first case occurs when sensors transmit with fixed power and the second case occurs when the sensors operate under a fixed sleep-wake cycle or TDMA scheduling. The transmission radius and intertransmission time required to guarantee that a considerable fraction of nodes receive the information is derived for a given sensor density and recovery rate. Computer simulations are provided to validate our theoretical claims.

This work presents GaussStones, a system of shielded magnetic tangibles design for supporting multi-token interactions on portable displays. Unlike prior works in sensing magnetic tangibles on portable displays, the proposed tangible design applies magnetic shielding by using an inexpensive galvanized steel case, which eliminates interference between magnetic tangibles. An analog Hall-sensor grid can recognize the identity of each shielded magnetic unit since each unit generates a magnetic field with a specific intensity distribution and/or polarization. Combining multiple units as a knob further allows for resolving additional identities and their orientations. Enabling these features improves support for applications involving multiple tokens. Thus, using prevalent portable displays provides generic platforms for tangible interaction design.

As an increasing number of social networking data is published and shared for commercial and research purposes, privacy issues about the individuals in social networks have become serious concerns. Vertex identification, which identifies a particular user from a network based on background knowledge such as vertex degree, is one of the most important problems that have been addressed. In reality, however, each individual in a social network is inclined to be associated with not only a vertex identity but also a community identity, which can represent the personal privacy information sensitive to the public, such as political party affiliation. This paper first addresses the new privacy issue, referred to as community identification, by showing that the community identity of a victim can still be inferred even though the social network is protected by existing anonymity schemes. For this problem, we then propose the concept of structural diversity to provide the anonymity of the community identities. The k-Structural Diversity Anonymization (k-SDA) is to ensure sufficient vertices with the same vertex degree in at least k communities in a social network. We propose an Integer Programming formulation to find optimal solutions to k-SDA and also devise scalable heuristics to solve large-scale instances of k-SDA from different perspectives. The performance studies on real data sets from various perspectives demonstrate the practical utility of the proposed privacy scheme and our anonymization approaches.

Mining big graph data is an important problem in the graph mining research area. Although cloud computing is effective at solving traditional algorithm problems, mining frequent patterns of a massive graph with cloud computing still faces the three challenges: 1) the graph partition problem, 2) asymmetry of information, and 3) pattern-preservation merging. Therefore, this paper presents a new approach, the cloud-based SpiderMine (c-SpiderMine), which exploits cloud computing to process the mining of large patterns on big graph data. The proposed method addresses the above issues for implementing a big graph data mining algorithm in the cloud. We conduct the experiments with three real data sets, and the experimental results demonstrate that c-SpiderMine can significantly reduce execution time with high scalability in dealing with big data in the cloud.

We present GaussBits, which is a system of the passive magnetic tangible designs that enables 3D tangible interactions in the near-surface space of portable displays. When a thin magnetic sensor grid is attached to the back of the display, the 3D position and partial 3D orientation of the GaussBits can be resolved by the proposed bi-polar magnetic field tracking technique. This portable platform can therefore enrich tangible interactions by extending the design space to the near-surface space. Since non-ferrous materials, such as the user's hand, do not occlude the magnetic field, interaction designers can freely incorporate a magnetic unit into an appropriately shaped non-ferrous object to exploit the metaphors of the real-world tasks, and users can freely manipulate the GaussBits by hands or using other non-ferrous tools without causing interference. The presented example applications and the collected feedback from an explorative workshop revealed that this new approach is widely applicable.

To many location-based service applications that prefer diverse results, finding locations that are spatially diverse and close in proximity to a query point (e.g., the current location of a user) can be more useful than finding the k nearest neighbors/locations. In this paper, we investigate the problem of searching for the k Diverse-Near Neighbors (kDNNs)} in spatial space that is based upon the spatial diversity and proximity of candidate locations to the query point. While employing a conventional distance measure for proximity, we develop a new and intuitive diversity metric based upon the variance of the angles among the candidate locations with respect to the query point. Accordingly, we create a dynamic programming algorithm that finds the optimal kDNNs. Unfortunately, the dynamic programming algorithm, with a time complexity of O(kn3), incurs excessive computational cost. Therefore, we further propose two heuristic algorithms, namely, Distance-based Browsing (DistBrow) and Diversity-based Browsing (DivBrow) that provide high effectiveness while being efficient by exploring the search space prioritized upon the proximity to the query point and spatial diversity, respectively. Using real and synthetic datasets, we conduct a comprehensive performance evaluation. The results show that DistBrow and DivBrow have superior effectiveness compared to state-of-the-art algorithms while maintaining high efficiency.

Real datasets always play an essential role in graph mining and analysis. However, nowadays most available real datasets only support millions of nodes. Therefore, the literature on Big Data analysis utilizes statistical graph generators to generate a massive graph (e.g., billions of nodes) for evaluating the scalability of an algorithm. Nevertheless, current popular statistical graph generators are properly designed to preserve only the statistical metrics, such as the degree distribution, diameter, and clustering coefficient of the original social graphs. Recently, the importance of frequent graph patterns has been recognized in the various works on graph mining, but unfortunately this crucial criterion has not been noticed in the existing graph generators. To address this important need, we make the first attempt to design a Pattern Preserving Graph Generation (PPGG) algorithm to generate a graph including all frequent patterns and three most popular statistical parameters: degree distribution, clustering coefficient, and average vertex degree. The experimental results show that PPGG, which we have released as a free download, is efficient and able to generate a billion-node graph in approximately 10 minutes, much faster than the existing graph generators.

Friending recommendation has successfully contributed to the explosive growth of online social networks. Most friending recommendation services today aim to support passive friending, where a user passively selects friending targets from the recommended candidates. In this paper, we advocate a recommendation support for active friending, where a user actively specifies a friending target. To the best of our knowledge, a recommendation designed to provide guidance for a user to systematically approach his friending target has not been explored for existing online social networking services. To maximize the probability that the friending target would accept an invitation from the user, we formulate a new optimization problem, namely, Acceptance Probability Maximization (APM), and develop a polynomial time algorithm, called Selective Invitation with Tree and In-Node Aggregation (SITINA), to find the optimal solution. We implement an active friending service with SITINA on Facebook to validate our idea. Our user study and experimental results reveal that SITINA outperforms manual selection and the baseline approach in solution quality efficiently.

The grid-connected photovoltaic (PV) power generator has been demonstrated as a promising solution of hybrid energy to leverage instantaneous renewable energy generation for reducing the energy acquired from electrical grid. In light of this technology trend and opportunity, this paper takes an initial attempt to explore the relay selection and power allocation for green cooperative cellular networks with grid-connected PV power generators. By properly considering the distributions of PV power, we propose an opportunistic relay selection scheme to minimize the grid power consumption. We also analyze the performance on the expected total grid power consumption in the whole network and derive a corresponding upper bound. The simulation results demonstrate that more than 53% of grid power can be saved by the exploitation of PV power with the proposed scheme.

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users.

The skyline query, aiming at identifying a set of skyline tuples that are not dominated by any other tuple, is particularly useful for multicriteria data analysis and decision making. For uncertain databases, a probabilistic skyline query, called P-Skyline, has been developed to return skyline tuples by specifying a probability threshold. However, the answer obtained via a P-Skyline query usually includes skyline tuples undesirably dominating each other when a small threshold is specified; or it may contain much fewer skyline tuples if a larger threshold is employed. To address this concern, we propose a new uncertain skyline query, called U-Skyline query, in this paper. Instead of setting a probabilistic threshold to qualify each skyline tuple independently, the U-Skyline query searches for a set of tuples that has the highest probability (aggregated from all possible scenarios) as the skyline answer. In order to answer U-Skyline queries efficiently, we propose a number of optimization techniques for query processing, including 1) computational simplification of U-Skyline probability, 2) pruning of unqualified candidate skylines and early termination of query processing, 3) reduction of the input data set, and 4) partition and conquest of the reduced data set. We perform a comprehensive performance evaluation on our algorithm and an alternative approach that formulates the U-Skyline processing problem by integer programming. Experimental results demonstrate that our algorithm is 10-100 times faster than using CPLEX, a parallel integer programming solver, to answer the U-Skyline query.

Prior research on viral marketing mostly focuses on promoting one single product item. In this work, we explore the idea of bundling multiple items for viral marketing and formulate a new research problem, called Bundle Configuration for SpreAd Maximization (BCSAM). Efficiently obtaining an optimal product bundle under the setting of BCSAM is very challenging. Aiming to strike a balance between the quality of solution and the computational overhead, we systematically explore various heuristics to develop a suite of algorithms, including κ-Bundle Configuration and Aggregated Bundle Configuration. Moreover, we integrate all the proposed ideas into one efficient algorithm, called Aggregated Bundle Configuration (ABC). Finally, we conduct an extensive performance evaluation on our proposals. Experimental results show that ABC significantly outperforms its counterpart and two baseline approaches in terms of both computational overhead and bundle quality.

Challenges faced in organizing impromptu activities are the requirements of making timely invitations in accordance with the locations of candidate attendees and the social relationship among them. It is desirable to find a group of attendees close to a rally point and ensure that the selected attendees have a good social relationship to create a good atmosphere in the activity. Therefore, this paper proposes Socio-Spatial Group Query (SSGQ) to select a group of nearby attendees with tight social relation. Efficient processing of SSGQ is very challenging due to the tradeoff in the spatial and social domains. We show that the problem is NP-hard via a proof and design an efficient algorithm SSGSelect, which includes effective pruning techniques to reduce the running time for finding the optimal solution. We also propose a new index structure, Social R-Tree to further improve the efficiency. User study and experimental results demonstrate that SSGSelect significantly outperforms manual coordination in both solution quality and efficiency.

This work presents GaussSense, which is a back-of-device sensing technique for enabling input on an arbitrary surface using stylus by exploiting magnetism. A 2mm-thick Hall sensor grid is developed to sense magnets that are embedded in the stylus. Our system can sense the magnetic field that is emitted from the stylus when it is within 2cm of any non-ferromagnetic surface. Attaching the sensor behind an arbitrary thin surface enables the stylus input to be recognized by analyzing the distribution of the applied magnetic field. Attaching the sensor grid to the back of a touchscreen device and incorporating magnets into the corresponding stylus enable the system 1) to distinguish touch events that are caused by a finger from those caused by the stylus, 2) to sense the tilt angle of the stylus and the pressure with which it is applied, and 3) to detect where the stylus hovers over the screen. A pilot study reveals that people were satisfied with the novel sketching experiences based on this system.

Increasing concerns about climate change are generating significant interest among researchers in reducing the energy consumption of existing communication infrastructure. However, previous research into the efficiency of cooperative communication networks only considers throughput or energy consumption separately. In response, this paper explores the trade-off between these two important factors and proposes maximizing energy efficiency, defined as the ratio of throughput over energy consumption. Because recent research demonstrates that machine operations require more energy, we propose opti- mally switching off unnecessary relays, while efficiently exploiting adaptive modulation (AM) to ensure that all multicast users can be served simultaneously under a required bit error rate. However, finding the optimal on/off relay mode and AM mode is challenging due to numerous possibilities required to be carefully considered and examined. To address this issue, we design an energy efficiency-aware search algorithm (EESA) to find the optimal solution. Our simulation results demonstrate that EESA is able to effectively improve the energy efficiency in cooperative multicast networks.

With the advances of communications, computing, and positioning technologies, mobile devices have been regarded as mobile computing platforms for various kinds of location-based and human-computation services. However, most existing applications regard each device as a sensor or focus on services with the computation on a single device. In contrast, this paper leverages a group of mobile devices as a collaborative and distributed search platform. Specifically, we propose a search system with mobile devices for rescue and patrol operations. The system utilizes mobile devices to find and assign the search route to each searcher in a collaborative and distributed manner. Given the roads to be searched in an area and the candidate start locations, our system minimizes the time required to search the whole area and guarantees that each road will be searched at least once. We first formulate the k-Person Search Problem for k mobile devices and prove that the problem is NP-Hard. To find the optimal solutions, we propose a centralized algorithm for a special case and an Integer Linear Programming formulation for general cases. We also devise an approximation algorithm. The algorithms can be used to dispatch the searchers before the operation starts. Moreover, to support online adaptation, we formulate the Path Refinement Problem for path exchange among searchers and propose a distributed algorithm to adaptively adjust the paths after the search starts. We also implement the proposed algorithms in mobile devices as a collaborative and distributed search system and demonstrate the efficiency of our algorithms with computation simulations and field trials.

The issues of frequency offset and channel estimation are considered for the downlink of coordinated multiple-input multiple-output orthogonal frequency-division multiplexing systems. Multiple carrier frequency offsets exist in this coordinated system. Without implementing an appropriate compensation for these offsets, both inter-carrier and inter-cell interference will degrade the system performance. Here, we adopt a parallel interference cancelation strategy to iteratively mitigate inter-cell interference, and propose a frequency offset estimator, approximated by a Hadamard product and a Taylor series expansion, to eliminate the inter-carrier interference. Our scheme is significantly less complex than existing methods. Furthermore, the proposed channel estimator is robust to frequency offsets and performs comparably well to these conventional approaches.

Due to the rich information in graph data, the technique for privacy protection in published social networks is still in its infancy, as compared to the protection in relational databases. In this paper we identify a new type of attack called a friendship attack. In a friendship attack, an adversary utilizes the degrees of two vertices connected by an edge to re-identify related victims in a published social network data set. To protect against such attacks, we introduce the concept of k2-degree anonymity, which limits the probability of a vertex being re-identified to 1/k. For the k2-degree anonymization problem, we propose an Integer Programming formulation to find optimal solutions in small-scale networks. We also present an efficient heuristic approach for anonymizing large-scale social networks against friendship attacks. The experimental results demonstrate that the proposed approaches can preserve much of the characteristics of social networks.

How to protect individual privacy in public data is always a concern. For social networks, the challenge is that, the structure of the social network graph can be utilized to infer the private and sensitive information of users. The existing anonymity schemes mostly focus on the anonymity of vertex identities, such that a malicious attacker cannot associate an user with a specific vertex. In real social networks, however, each vertex is usually associated with not only a vertex identity but also a community identity, which could represent the private information for the corresponding user, such as the political party affiliation or disease information sensitive to the public. In this paper, we first show that the attacker can still infer the community identity of an user even though the graph is protected by previous anonymity schemes. Afterward, we propose the structural diversity, which ensures the existences of at least k communities containing vertices with the same degree for every vertex in the graph, to provide the anonymity of the community identities. Specifically, we formulate a new problem, k-Structural Diversity Anonymization (k-SDA), which protects the community identity of each individual in publishing social networks. We propose an Integer Programming formulation to find the optimal solutions to k-SDA. Moreover, we devise three scalable heuristics to solve the large instances of k-SDA with different perspectives. The experiments on real data sets demonstrate the practical utility of our privacy model and our approaches.

We consider the issues of frequency offset and channel estimation in downlink coordinated multiple-input multiple-output orthogonal frequency-division multiplexing systems. Multiple carrier frequency offsets exist in this coordinated system. Without implementing an appropriate compensation for these offsets, both inter-carrier and inter-cell interference will degrade system performance. In response, we adopt parallel interference cancelation to iteratively mitigate inter-cell interference, and propose a frequency offset estimator, approximated by Hadamard product and Taylor expansion, to eliminate the inter-carrier interference. Our scheme is significantly less computational complex than the existing methods. Furthermore, the proposed channel estimator is robust to frequency offsets and performs comparably to conventional approaches.

Three essential criteria are important for activity planning, including: (1) finding a group of attendees familiar with the initiator, (2) ensuring each attendee in the group to have tight social relations with most of the members in the group, and (3) selecting an activity period available for all attendees. Therefore, this paper proposes Social-Temporal Group Query to find the activity time and attendees with the minimum total social distance to the initiator. Moreover, this query incorporates an acquaintance constraint to avoid finding a group with mutually unfamiliar attendees. Efficient processing of the social-temporal group query is very challenging. We show that the problem is NP-hard via a proof and formulate the problem with Integer Programming. We then propose two efficient algorithms, SGSelect and STGSelect , which include effective pruning techniques and employ the idea of pivot time slots to substantially reduce the running time, for finding the optimal solutions. Experimental results indicate that the proposed algorithms are much more efficient and scalable. In the comparison of solution quality, we show that STGSelect outperforms the algorithm that represents manual coordination by the initiator.

Natural phenomena show that many creatures form large social groups and move in regular patterns. However, previous works focus on finding the movement patterns of each single object or all objects. In this paper, we first propose an efficient distributed mining algorithm to jointly identify a group of moving objects and discover their movement patterns in wireless sensor networks. Afterward, we propose a compression algorithm, called 2P2D, which exploits the obtained group movement patterns to reduce the amount of delivered data. The compression algorithm includes a sequence merge and an entropy reduction phases. In the sequence merge phase, we propose a Merge algorithm to merge and compress the location data of a group of moving objects. In the entropy reduction phase, we formulate a Hit Item Replacement (HIR) problem and propose a Replace algorithm that obtains the optimal solution. Moreover, we devise three replacement rules and derive the maximum compression ratio. The experimental results show that the proposed compression algorithm leverages the group movement patterns to reduce the amount of delivered data effectively and efficiently.

Existing object tracking applications focus on finding the moving patterns of a single object or all objects. In contrast, we propose a distributed mining algorithm that identifies a group of objects with similar movement patterns. This information is important in some biological research domains, such as the study of animals' social behavior and wildlife migration. The proposed algorithm comprises a local mining phase and a cluster ensembling phase. In the local mining phase, the algorithm finds movement patterns based on local trajectories. Then, based on the derived patterns, we propose a new similarity measure to compute the similarity of moving objects and identify the local group relationships. To address the energy conservation issue in resource-constrained environments, the algorithm only transmits the local grouping results to the sink node for further ensembling. In the cluster ensembling phase, our algorithm combines the local grouping results to derive the group relationships from a global view. We further leverage the mining results to track moving objects efficiently. The results of experiments show that the proposed mining algorithm achieves good grouping quality, and the mining technique helps reduce the energy consumption by reducing the amount of data to be transmitted.

Nowadays, mobile video streaming enables people to access digital content, such as online TV shows, music videos, sports reports, and news programs, anytime, anywhere. However, current streaming services in mobile networks are subject to the available wireless bandwidth shared among many users and can only provide videos with limited resolutions. Moreover, on recently developed high-resolution mobile devices, such as iPhone, Google Nexus One, Nokia N97, and SonyEricsson X10, the resolution of video streaming is much lower than the devices can actually support. As a result, existing video upsampling schemes usually introduce visual artifacts. In response to the above problem, we bridge the resolution gap between streaming videos and client screens, and propose a novel upsampling-based system architecture, called MobiUP, to enable high-quality video streaming onto mobile devices. To avoid modifying existing codecs for video streaming, MobiUP upsamples videos with decoded frames and appends a limited amount of metadata to the streaming videos for facilitating high-quality and real-time conversion from low resolution to high fullscreen resolution on the client side. In other words, the proposed upsampling architecture complements current systems. Therefore, MobiUP is generic and flexible, and it can be implemented easily on mobile devices for practical use. The implementation results demonstrate that, although the appended metadata is less than 8% of the total transmitted data, it improves the quality of the upsampled video significantly. Meanwhile, the computation time of MobiUP Client is close to that of bilinear upsampling algorithms implemented on mobile devices.

Recently, management of uncertain data draws lots of attention to consider the granularity of devices and noises in collection and delivery of data. Previous works directly model and handle uncertain data to find the required results. However, when data uncertainty is not small or limited, users are not able to obtain useful insights and thereby tend to provide more resources to improve the solution, by reducing the uncertainty of data. In light of this issue, this paper formulates a new problem of choosing a given number of uncertain data objects for acquiring their attribute values to improve the solutions of Probabilistic k-Nearest-Neighbor (k-PNN) query. We prove that solutions must be better after data acquisition, and we devise algorithms to maximize expected improvement. Our experiment results demonstrate that the probability can be significantly improved with only a small number of data acquisitions.

In this paper, we propose an interference detectable adaptive notch filter (ANF) for GPS receivers. The proposed ANF can estimate the existence of continuous wave interference (CWI) and its power, by exploiting the statistic value within an adaptive second-order infinite impulse response (IIR) filter. Moreover, our ANF is modulized, which allows more modules can be included to deal with multiple CWIs. We also design an adaptation algorithm for each ANF module and prove that the ANF module can adaptively notch the strongest CWI at its input, and this merit enables us to notch the primary CWIs with a limited number of ANF modules. Simulation results show that the adaption of the ANF modules converges in four iterations, and the signal to interference plus noise ratio (SINR) improvements can reach 21 dB.

Instead of finding clusters in the full feature space, subspace clustering is an emergent task which aims at detecting clusters embedded in subspaces. Most of previous works in the literature are density-based approaches, where a cluster is regarded as a high-density region in a subspace. However, the identification of dense regions in previous works lacks of considering a critical problem, called "the density divergence problemrdquo in this paper, which refers to the phenomenon that the region densities vary in different subspace cardinalities. Without considering this problem, previous works utilize a density threshold to discover the dense regions in all subspaces, which incurs the serious loss of clustering accuracy (either recall or precision of the resulting clusters) in different subspace cardinalities. To tackle the density divergence problem, in this paper, we devise a novel subspace clustering model to discover the clusters based on the relative region densities in the subspaces, where the clusters are regarded as regions whose densities are relatively high as compared to the region densities in a subspace. Based on this idea, different density thresholds are adaptively determined to discover the clusters in different subspace cardinalities. Due to the infeasibility of applying previous techniques in this novel clustering model, we also devise an innovative algorithm, referred to as DENCOS (density conscious subspace clustering), to adopt a divide-and-conquer scheme to efficiently discover clusters satisfying different density thresholds in different subspace cardinalities. As validated by our extensive experiments on various data sets, DENCOS can discover the clusters in all subspaces with high quality, and the efficiency of DENCOS outperformes previous works.

In this paper, we first study an important but unsolved dilemma in the literature of subspace clustering, which is referred to as “information overlapping-data coverage” challenge. Current solutions of subspace clustering usually invoke a grid-based Apriori-like procedure to identify dense regions and construct subspace clusters afterward. Due to the nature of monotonicity property in Apriori-like procedures, it is inherent that if a region is identified as dense, all its projected regions are also identified as dense, causing overlapping/redundant clustering information to be inevitably reported to users when generating clusters from such highly correlated regions. However, naive methods to filter redundant clusters will incur a challenging problem in the other side of the dilemma, called the “data coverage” issue. Note that two clusters may have highly correlated dense regions but their data members could be highly different to each other. Arbitrarily removing one of them may lose the coverage of data with clustering information, thus likely reporting an incomplete and biased clustering result. In this paper, therefore, we further propose an innovative algorithm, called "NOnRedundant Subspace Cluster mining” (NORSC), to efficiently discover a succinct collection of subspace clusters while also maintaining the required degree of data coverage. NORSC not only avoids generating the redundant clusters with most of the contained data covered by higher dimensional clusters to resolve the information overlapping problem but also limits the information loss to cope with the data coverage problem. As shown by our experimental results, NORSC is very effective in identifying a concise and small set of subspace clusters, while incurring time complexity in orders of magnitude better than that of previous works.

In this paper, we propose a new data broadcast mechanism with network coding in heterogeneous wireless networks. Our mechanism adaptively clusters the mobile hosts in fewer cells to minimize the bandwidth consumption. In addition, we adaptively code the data according to the data temporarily stored in each mobile host with a distributed manner. Our mechanism allows each delivered message to be coded from only a subset of data to further reduce the number of required messages. We formulate the cell selection and broadcast coding problem with integer programming and prove that the problem is NP-hard. We design a distributed algorithm based on Lagrangean relaxation. Our algorithm needs no server to record the location, queried, and stored information of receivers. Moreover, our algorithm is adaptive to the dynamic group membership, mobility, queried, and stored data of receivers.

Applications with geo-tagged photos have drawn lots of attentions in recent years. However, most previous works consider the GPS information of each photo individually to improve the metadata of the corresponding photo. In this paper, we leverage GPS data in a series of scenic photos and propose the personalized scenic itinerary recommendation system. Our system provides personalized suggestion of a sequence of following visiting spots when each user takes the photo of the current scenic spot. The recommendation is based on the data mining techniques to extract and differentiate the preferences of various users. Our system is designed to provide a new location service for geo-tagged photo management.

Currently, IP multicast and Explicit Multi-Unicast (Xcast) are two approaches for multicast communications. IP multicast is designed for large groups but is not scalable in terms of the group number because every router in a multicast tree needs to store the forwarding state for each group. In contrast, Xcast is designed for small groups and is not scalable in terms of the group size because each packet’s header can include only the addresses of a few receivers. Therefore, the two approaches are designed for different scenarios and address different problems. However, the selection of IP multicast or Xcast is left to end users who will choose the corresponding API in the applications. In other words, the scalability of the network relies on the end users, and is not guaranteed by the protocol itself. In this paper, we address the above issues and propose a multicasting protocol that is scalable and adaptive in terms of both group number and group size. We avoid the disadvantages of IP multicast and Xcast by choosing only a few routers to store the forwarding states, and multicast packets are delivered via Xcast among these routers. The main advantage of our protocol is that the assignment of forwarding states is optimal and performed in a fully distributed manner. We show that IP multicast and Xcast are two extreme and special cases of our approach. We prove that the overhead of our protocol is limited. In addition, the assignment of forwarding states in our protocol is adaptive to the dynamic group membership and the change in network topology. Moreover, our protocol is simple and can be extended from existing multicast routing protocols.

On-demand data broadcast is widely deployed to achieve high scalability in a mobile computing environment. However, traditional on-demand data broadcasting assumes that each time slot includes only one data item. Therefore, the above constraint requires the mobile users to wait until the next broadcast cycle to retrieve a data item if they miss the item in this cycle. The above constraint also limits the number of users that can be served in each time slot. In this paper, we propose a new on-demand data broadcast model with modified network coding. Our approach enables a server to encode multiple data items in each time slot, while each mobile user retrieves the data items by decoding the encoded data items with the locally stored data items. Our approach is different from the traditional network coding because each time slot encodes only a subset of data items, which are decided according to identities of the requested and stored data items of users. The simulation results show that our algorithm can reduce the access time by 66% as compared to the traditional schemes.

In this paper, we leverage network coding to reduce the bandwidth consumption for data broadcast. We use the concept of mixing in a different way from the traditional network coding. Traditional network coding mixes all data items together. However, we mix each data item from only some data items according to the queried and stored data of receivers. Therefore, each receiver in our approach is required to receive fewer coded data to decode the required information, and the sender thereby is able to broadcast fewer data items. We formulate an optimization problem with integer-linear programming to minimize the bandwidth consumption in data broadcast. We prove that the problem is NP-hard and design an approximation algorithm that can be implemented in the data server. In addition, we show that different mixings of data items lead to different decoding costs for receivers. We design an algorithm to optimally code the data items with the minimum decoding cost.

In this paper, we propose a new mechanism to select the cells and the wireless technologies for layer-encoded video multicasting in the heterogeneous wireless networks. Different from the previous mechanisms, each mobile host in our mechanism can select a different cell with a different wireless technology to subscribe each layer of a video stream, and each cell can deliver only a subset of layers of the video stream to reduce the bandwidth consumption. We formulate the Cell and Technology Selection Problem (CTSP) to multicast each layer of a video stream as an optimization problem. We use Integer Linear Programming to model the problem and show that the problem is NP-hard. To solve the problem, we propose a distributed algorithm based on Lagrangean relaxation and a protocol based on the proposed algorithm. Our mechanism requires no change of the current video multicasting mechanisms and the current wireless network infrastructures. Our algorithm is adaptive not only to the change of the subscribers at each layer, but also the change of the locations of each mobile host.

In this paper, we propose a bandwidth-efficient multicast mechanism for heterogeneous wireless networks. We reduce the bandwidth cost of an Internet protocol (IP) multicast tree by adaptively selecting the cell and the wireless technology for each mobile host to join the multicast group. Our mechanism enables more mobile hosts to cluster together and leads to the use of fewer cells to save the scarce wireless bandwidth. Besides, the paths in the multicast tree connecting to the selected cells share more common links to save the wireline bandwidth. Our mechanism supports the dynamic group membership and offers mobility of group members. Moreover, our mechanism requires no modification to the current IP multicast routing protocols. We formulate the selection of the cell and the wireless technology for each mobile host in the heterogeneous wireless networks as an optimization problem. We use integer linear programming to model the problem and show that the problem is NP-hard. To solve the problem, we propose a distributed algorithm based on Lagrangean relaxation and a network protocol based on the algorithm. The simulation results show that our mechanism can effectively save the wireless and wireline bandwidth as compared to the traditional IP multicast.

In this paper, we propose a scalable and adaptive multicast forwarding mechanism based on explicit multicast (Xcast). This mechanism optimizes the allocation of forwarding states in routers and can be used to improve the scalability of traditional IP multicast and source-specific multicast. Compared with previous work, our mechanism needs fewer routers in a multicast tree to store forwarding states and therefore leads to a more balanced distribution of forwarding states among routers. We focus on two problems and formulate each of them as an optimization problem. The first problem, referred to as minstate, minimizes the total number of routers that store forwarding states in a multicast tree. The second problem, referred to as balancestate, minimizes the maximum number of forwarding states stored in a router for all multicast groups, which is proved to be an NP-hard problem. We design a distributed algorithm that obtains the optimal solution to the first problem and propose an approximation algorithm for the second problem. We also prove that the approach adopted by most existing works to allocate forwarding states in the branching routers of a multicast tree is a special case of our mechanism. The simulation results show that the forwarding state allocation provided by previous work is concentrated on the backbone routers in the Internet, which may cause the scalability problem. In contrast, our mechanism can balance forwarding states stored among routers and reduce the number of routers that store the forwarding states for a multicast tree.

Data broadcast is widely deployed to realize bandwidth efficiency in a mobile computing environment. However, traditional data broadcasting assumes that mobile users can only retrieve one data item in each time slot. Therefore, the above constraint leads to access conflicts and requires the mobile users to wait until the next broadcast cycle to retrieve the requested information. In this paper, we propose a novel data broadcasting framework that adopts network coding with the stored data items in users. In our approach, a server encodes multiple data items in each time slot, while each mobile user is able to retrieve the data item by decoding the encoded data items with the locally stored data items. We propose an algorithm to generate the broadcast program to minimize the average access time. In addition, our algorithm can avoid coding redundant data in each time slot to reduce access delay. Our simulation results show that our algorithm can reduce the access time by 56% as compared to no coding scheme.

With the ubiquitous of cellular phones, mobile applications with 2D barcodes have drawn a lot of attentions in recent years. However, the previous works for extracting 2D barcodes from an image do not consider the distortion resulted from camera shake. In this paper, therefore, we propose an efficient algorithm to extract 2D barcode from a camera-shaken image. Compared with previous approaches, our algorithm outperforms in not only smaller running time but also higher accuracy of the barcode recognition.

With the ubiquitous of cellular phones, mobile applications with 2D barcodes have drawn a lot of attentions in recent years. However, the previous works for extracting 2D barcodes from an image do not consider the distortion resulted from camera shake. Moreover, the previous works for extracting 2D barcodes from an image do not take a complex background into account. In this paper, therefore, we propose an efficient and effective algorithm to extract 2D barcode from a complex background in a camera-shaken image. Compared with previous approaches, our algorithm outperforms in not only smaller running time but also higher accuracy of the barcode recognition.

In this paper, we propose a new multicast delivery mechanism for bandwidth-demanding applications in IP networks. Our mechanism, referred to as multiple-destination overlay multicast (MOM), combines the advantages of IP multicast and overlay multicast. We formulate the MOM routing problem as an optimization problem. We then design an algorithm based on Lagrangian relaxation on our formulation and propose a distributed protocol based on the algorithm. For network operators, MOM consumes less network bandwidth than both IP multicast and overlay multicast. For users, MOM uses less interface bandwidth than overlay multicast.

In this paper, we propose a bandwidth-efficient multicast routing mechanism using rectilinear Steiner trees for IP-based LEO satellite networks. Different from the previous approach which minimizes the end-to-end delay, our mechanism minimizes the total bandwidth, i.e, the number of hops, used by a multicast tree since the wireless bandwidth in satellite networks is a limited and scarce resource. We propose a new integer linear programming formulation for network planning and a distributed algorithm for protocol design. Our simulation results show that the trees created by our approach use less bandwidth than shortest-path trees. Moreover, the difference of the optimal solutions and the solutions obtained by our distributed algorithm is within 5% on average.

We propose a new forwarding mechanism for IP multicast based on explicit multicast (Xcast). Compared with traditional IP multicast, our mechanism achieves a more flexible allocation of multicast forwarding states among routers. Previous works only focus on reducing the number of routers which store the forwarding states, ignoring the distribution of forwarding states among routers. The number of forwarding states stored in each router may be unbalanced. We formulate the assignment of the routers with forwarding states as two optimization problems. The first one is to minimize the number of routers with the forwarding states in each multicast tree. The second one is to minimize the maximum number of forwarding states stored in a router. We design several algorithms for both problems. We prove that our algorithms can find the optimal solution to the first problem. By simulation, we also show that our algorithms perform well in the second problem. Moreover, we prove that assigning all branching routers as the only routers with the forwarding states is a special case in our mechanism. Due to higher flexibility, we show that our mechanism use fewer forwarding states, and the distribution of forwarding states is more balanced.

This paper proposes a preemptive multiclass wavelength reservation protocol to provide differentiated service for Optical Burst Switched (OBS) networks. Unlike existing approaches, which may degrade to classless schemes or which may suffer from low wavelength utilization, our mechanism is robust, efficient, and supports an incremental deployment of QoS support. We maintain a usage profile for each class at the router, and implement a preemptive wavelength reservation mechanism to ensure QoS. We derive an analytical model and conduct simulations to evaluate the performance. The result shows that our approach performs the best in terms of lower blocking probability and higher resource utilization, making it an excellent QoS mechanism for OBS networks.

IP multicasting is an efficient group communication mechanism. It avoids transmitting packets from a sender to each of the receivers separately. With the current IP multicast mechanism, once having joined a group, a host will receive all data destined to the group from any source, irrespective of whether it wishes to receive them. This paper studies source filtering in IP multicasting. Source filtering is the ability for an individual host to specify the reception of packets sent to a multicast group only from a list of source addresses or to explicitly identify a list of the sources whose data the host does not want to receive. We investigate the issue of source filtering in the context of multicast routing protocols, and propose a solution to support source filtering in IP multicast routing. We have also conducted simulations to evaluate the performance of the proposed mechanism. The results show that, compared to multicasting without the capability of source filtering, our mechanism allows better bandwidth utilization and scalability, thus achieving a truly efficient use of resources for IP multicasting.

This paper studies the integration of multimedia multicasting, with the consideration of multicast with end-to-end QoS guarantees by resource reservation, dynamic join and departure of participants, user heterogeneity, scalability, robustness, and loop-free control. A protocol called MQ, Multicast with QoS, is proposed to support multimedia group communications with QoS guarantees for heterogeneous recipients. With MQ, while resource reservation is de-coupled from QoS multicast routing, they are integrated in a way to avoid the problem of "sender-oriented" path determination, a problem that occurs when RSVP is used in conjunction with QoS routing for heterogeneous reservations. Being a truly receiver-oriented and integrated scheme for multimedia multicasting, MQ supports such integration in a robust, scalable and loop-free way. It also accommodates heterogeneous users with varied QoS, dynamically adjusts QoS trees to improve resource utilization, and guarantees end-to-end QoS requirements. We have conducted simulations to evaluate the performance of the proposed mechanism. MQ demonstrates its advantages over the conventional loosely coupled integration of TP multicasting, resource reservation and QoS routing, in terms of better accommodation of heterogeneous users, higher scalability, lower blocking probability for users to join groups with service guarantees, and more efficient resource utilization to enhance system performance.

Internet multicast is an important networked service for many existing and emerging applications. The dominant mechanism for group management of IP multicasting is the Internet group management protocol (IGMP). IGMP is based on a query/reply model and refreshes group membership periodically. IGMP has been evolving through three versions. IGMP v1 develops the basis of the query/reply group management model and suppression mechanism, IGMP v2 reduces leave latency that IGMP v1 suffers from, and IGMP v3 adds the capability of source filtering but removes the suppression mechanism of IGMP v1/v2. In this paper, a new group management protocol called receiver-initiated group membership protocol (RGMP) is proposed. Both source filtering and membership report suppression are supported. An RGMP host actively refreshes group membership in the neighboring multicast routers. No querier, and hence no query messages and timers, is required for periodically probing the presence of known groups. An individual host maintains a refresh timer per group. The refresh timer is reset once the suppression rule holds for a received report message, where the report may be a join, leave, state change, or a periodical refresh message. The receiver-initiated, self-synchronized refresh timer makes the RGMP suppression mechanism superior to that of IGMP v1/v2, which applies only for periodical refresh report message. As a result, the protocol overhead compared to IGMP v3 is significantly reduced, over a wide variety of service scenarios. In addition to reduced protocol overhead, RGMP is robust, scalable and adaptive to serve as a group management protocol.