Federated learning (FL) is a privacy-preserving distributed machine learning framework where multiple devices collaborate with the assistance of an aggregator. However, the limitations of aggregator communication result in only a portion of clients with high data quality being selected to participate in FL, but the quality of clients' data cannot be evaluated without access to the original data. Most existing methods for selecting clients employ a data quality metric with empirically defined scores, which may select clients with high non-ID degrees, thereby reducing the accuracy and freshness of the model. Furthermore, due to the unknown quality of clients' data, current incentive mechanisms lack FL convergence guarantees, which prevent the client behavior from improving the global model accuracy. To address these issues, in this paper, we propose using the gradient difference as a metric for the quality of clients' data, which can quantify the non-IID degree and contribution potential of each client. We formulate a client selection problem using the Combinatorial Multi-Armed Bandit (CMAB) model and design an effective selection strategy, improving the worst-case regret proof to provide a theoretical guarantee for it. Based on these results, we develop an incentive mechanism by the FL convergence analysis, quantifying the utility functions of the aggregator and clients, and modeling their interaction as a two-stage Stackelberg game. For the non-convex utility function, our method establishes the existence and uniqueness of the Stackelberg equilibrium, thereby enabling the determination of the optimal strategy for maximizing the utility of all participants. Finally, extensive simulation experiments on real-world datasets demonstrate the effectiveness of our proposed method compared to state-of-the-art approaches.

Seeding conflict in online society is a public issue obtaining increasing attention. In this paper, we take a step to study the problem of maximizing conflict in online social networks from the adversarial perspective. More specifically, we combine the widely used stochastic information propagation model and opinion dynamics model to jointly model the processes of adversarial content propagation and opinion evolution through peer pressure on social networks, based on which we define the adversarial perturbations maximization (APM) problem. The APM problem focuses on two popular network conflict measures, disagreement and polarization. Our analysis begins by showing the complex nature of the APM problem. We show that by decomposing the objective into a subtraction of two set functions, an upper bound of the objective which is essentially a difference of two submodular (DS) functions can be devised. Then inspired by the success of modular-modular procedure and reverse influence sampling technique in related optimization tasks, we build a two-level approximation framework to maximize the upper bound heuristically with a data-dependent guarantee and further strengthen the approximation result using the sandwich approximation framework. Also, we apply dimension reduction technique to design a faster naïve greedy algorithm for the objective. Experiments show both the seriousness of this problem and the performance of our proposed algorithms.

The dynamic topology, resource constraints, and data heterogeneity inherent in the Internet of Vehicles (IoV) present fundamental challenges to the effective deployment of federated learning (FL) applications. Traditional FL strategies often suffer from suboptimal model performance and excessive communication overhead under such conditions. Existing solutions primarily focus on static resource allocation and overlook the compounded effects of high mobility, diverse device capabilities, and time-varying data quality. Moreover, current incentive mechanisms lack adaptability to dynamic resource-benefit trade-offs, making it challenging to sustain efficient participation from vehicle clients. To address these issues, we propose NBCI-FL, an incentive framework that redefines vehicular collaboration as a multi-objective coalition game. It introduces a mobility-aware coalition-formation mechanism based on heterogeneous coalition games, along with a three-dimensional evaluation-based client-selection mechanism to construct efficient and stable learning clusters. Furthermore, we propose a two-stage Nash bargaining game that dynamically balances the fairness of data contributions with the optimization of resource utilization efficiency. Theoretical analysis proves the existence and effectiveness of the Nash bargaining equilibrium under vehicular dynamic conditions. Extensive simulations on real-world datasets demonstrate that our proposed NBCI-FL substantially outperforms state-of-the-art traditional FL baselines by maintaining high global model accuracy, improving communication efficiency, enhancing network stability, and ensuring fair and rational utility allocation among all participants.

Federated Learning (FL) enables collaborative model training across distributed clients without requiring the exchange of raw data. However, existing One-Shot FL (OSFL) methods, designed for communication efficiency by reducing fed-erated rounds to one, suffer substantial performance degradation when faced with highly non-IID data across clients, primarily due to critical distribution shifts: label shift, feature shift, and concept shift. In this paper, we introduce POSFed, a new personalized three-stage approach, to systematically address these fundamen-tal limitations: (1) Each client locally generates robust and label-agnostic synthetic datasets via self-supervising learning, ensuring essential knowledge is captured despite local distribution shifts; (2) The server aggregates all synthetic datasets to train a global feature extractor, capturing generalizable and transferable rep-resentations across heterogeneous client data; and (3) Each client efficiently adapts the feature extractor by learning a personalized classification head on its own data, enabling effective local customization and mitigating both feature and concept shifts. Extensive experiments across multiple benchmarks demonstrate that POSFed significantly outperforms state-of-the-art methods, achieving performance comparable to multi-round personalized approaches while using only one communication round. By ensuring both superior personalization and practical communication efficiency, POSFed establishes a feasible paradigm for FL under more realistic and heterogeneous conditions. Code is available at https://github.com/I643204431IPOSFed.

In contemporary society, groups are pivotal in shaping decisions and actions. The consensus of a majority of members on specific topics often guides the collective decision-making in groups. Group influence maximization (GIM) aims to select$k$seed users in a network to maximize the number of eventually activated groups. A group is said to be activated if$\beta$percent of users in this group are activated. This study delves into the strategic selection of seed users in social networks to maximize the spread of a topic, thereby activating the highest number of groups. The GIM problem, inherently NP-hard when computing the influence spread from a selected set of nodes, has traditionally faced obstacles in ensuring theoretical robustness, time efficiency, and adaptability in large and complex network environments. To overcome these challenges, we introduce a robust framework called GIMDRL that addresses the GIM problem in social networks using deep reinforcement learning (DRL). Our approach integrates node embeddings from multiple graph neural networks, thereby utilizing diverse information for effective network analysis. This integration plays a crucial role in optimizing the parameter learning process. Extensive experiments are conducted on real-world and synthetic datasets to assess the performance of our proposed framework. The results of these experiments indicate that our approach significantly outperforms existing methods in GIM, even when trained on sampled graphs. This highlights our model's strong capacity for generalization in varying network scenarios.

Federated learning (FL) is emerging as a sought-after distributed machine learning architecture, offering the advantage of model training without direct exposure to raw data. With advancements in network infrastructure, FL has been seamlessly integrated into edge computing. However, the limited resources on edge devices introduce security vulnerabilities to FL in the context. While blockchain technology promises to bolster security, practical deployment on resource-constrained edge devices remains a challenge. Moreover, the exploration of FL with multiple aggregators in edge computing is still new in the literature. Addressing these gaps, we introduce the blockchain-empowered heterogeneous multiaggregator federated learning architecture (BMA-FL). We design a novel lightweight Byzantine consensus mechanism, namely PBCM, to enable secure and fast model aggregation and synchronization in BMA-FL. We study the heterogeneity problem in BMA-FL that the aggregators are associated with varied number of connected trainers with non-IID data distributions and diverse training speed. We propose a multiagent deep reinforcement learning algorithm (MASB-DRL) to help aggregators decide the best training strategies. Experiments on real-word datasets demonstrate the efficiency of BMA-FL to achieve better models faster than baselines, showing the efficacy of PBCM and MASB-DRL.

Spatiotemporal Mobile CrowdSourcing (MCS) is a new intelligent sensing paradigm for large-scale data acquisition where requesters can recruit a crowd of workers to perform data collection tasks. How to recruit suitable workers in a dynamic environment to maximize platform utility is a key issue and has become a research hotspot. Many past studies have made great efforts in this regard, but most of them either assume that the worker quality is known in advance or ignore the limitations of workers’ short-term ability to provide resources. In this article, we consider a platform-centered online spatiotemporal MCS system where mobile workers have both long-term and short-term constraints for providing resources, and their quality is unknown to the platform, while the platform has a long-term budget constraint for recruiting workers. We aim to find an online worker scheduling scheme to maximize the platform’s long-term utility without violating the constraints of both workers and the platform. To address this problem, we first transform the long-term utility maximization problem into a real-time utility maximization problem by leveraging the Lyapunov optimization, then design algorithms based on the Upper Confidence Bound (UCB) and Markov approximation to solve each real-time utility maximization problem with unknown worker quality. We demonstrate that our UCB-based algorithm has a sublinear regret and prove that our proposed framework has a performance guarantee for the addressed problem. Finally, we evaluate our design through numerical simulation experiments, and the results demonstrate the effectiveness of our algorithm.

Multi-modal Federated Learning (FL) is a type of FL that considers utilizing multiple modalities of data to improve overall performance. While multi-modal data brings richer information, it also introduces more significant communication overhead. Reducing this overhead hinges on two key strategies: increasing the convergence speed of the training or reducing the communication overhead in each communication round. However, few studies have considered these two strategies simultaneously and formed a unified optimization framework. Thus, we propose a joint client and modality selection framework to reduce communication overhead. Modality selection executed on each client assigns weights to modalities based on their contribution to training potential, aiming at accelerating the convergence. Client selection executed on the server assigns weights to clients by considering different metrics, especially total training potential after the modality selection. We validate our proposed method on the five widely used open-source datasets, achieving satisfactory accuracy while reducing the total communication overhead to 2.43%–14.24% compared to without selection on different datasets, significantly outperforming existing state-of-the-art (SOTA) methods. Code is available at https://github.com/1643204431/OCETPMMFL .

With the booming of Internet of Things (IoT), a content provider (CP) traditionally supported by the storage resources of a network service provider (NSP) can provide content services through the resources of IoT devices to significantly reduce the service latency. The CP, NSP, and IoT devices constitute an edge caching system, and it is crucial to efficiently utilize the storage resources in the system. Most existing studies ignore the idle storage resources of IoT devices. The few studies that consider the storage resources of IoT devices either are based on the assumption of complete information, or only utilize the storage resources of part of the IoT devices. In this article, we propose a contract theory and Stackelberg game-based storage resource allocation method to effectively utilize the storage resources in edge caching systems under information asymmetry. The interaction between the CP and the IoT is formalized as a contract design problem, and the interaction between the NSP and the CP is formulated as a two-stage Stackelberg game with a single leader and a single follower. We analyze the constraints in contract design and the Nash equilibrium of the Stackelberg game. We also propose a golden section search-based optimal contract design and pricing (GSSCP) algorithm to obtain the optimal contract of the CP and optimal price of the NSP storage resources. Simulation results demonstrate that the proposed method can make effective use of the storage resources and improve the CP utility in edge caching systems under information asymmetry.

In recent years, the blockchain-based Internet of Things (IoT) has been widely studied and applied, and every IoT device can act as a node in the blockchain. However, these lightweight nodes usually do not have enough computing power to complete the consensus or other computing-required tasks. Edge computing network gives a platform to provide computing power to IoT devices. A fundamental problem is how to allocate limited edge servers to IoT devices in a highly untrusted environment. In a fair competitive environment, the allocation mechanism should be online, truthful, and privacy-preserved. In order to meet these three challenges, we propose an online multi-item double auction (MIDA) mechanism by means of auction theory, where IoT devices are buyers and edge servers are sellers. However, ensuring truthfulness is often contradictory to protecting users’ privacy. The participants’ private information is at risk of being exposed to inference attacks, which may lead to malicious manipulation of the market by adversaries. Thus, we enhance our MIDA mechanism with differential privacy (DP) to protect sensitive information from being leaked. It slightly interferes with the auction results in performance but guarantees privacy protection with high confidence. In addition, we upgrade our privacy-preserved MIDA mechanism such that it adapts to more complex and realistic scenarios. In the end, the effectiveness and correctness of algorithms are evaluated and verified by theoretical analysis and numerical simulations.

The Network Function Virtualization (NFV) is the essential technology proposed to tackle the next-generation mobile system’s various flexibility features. In this article, we implement a thorough micro-architectural performance investigation on the NFV-enabled edge virtual Radio Access Network (vRAN) and the emerging 5G new-radio (nr) platform to unveil the main micro-architectural bottlenecks of the next-generation network’s vRAN system. Based on our experimental results, we find that the high core bound hinders the processing speed of the vRAN and 5G nr platforms. Several solutions alleviating the vRAN’s core bound are proposed to accelerate the vRAN system’s processing speed. Besides, we observe that the current co-location strategy cannot maximize the COTS servers’ CPU utilization and meanwhile eliminate the system hang-up caused by CPU resource contention. We fill this gap by proposing an optimized co-location strategy based on our observed vRAN co-location characterization. Finally, we detect that on the modern hyper-threading-enabled COTS servers, the current pin core policy of 5G nr will cause L3 cache contention, which will lead to severe system hang-up. A novel threads management mechanism is proposed to eliminate this system hang-up on the hyper-threading-enabled COTS servers.

Aiming at selecting a small subset of nodes with maximum influence on networks, the influence maximization (IM) problem has been extensively studied. Since it is #P-hard to compute the influence spread given a seed set, the state-of-the-art methods, including heuristic and approximation algorithms, are faced with great difficulties such as theoretical guarantee, time efficiency, generalization, and so on. This makes it unable to adapt to large-scale networks and more complex applications. On the other side, with the latest achievements of deep reinforcement learning (DRL) in artificial intelligence and other fields, lots of work have been focused on exploiting DRL to solve combinatorial optimization (CO) problems. Inspired by this, we propose a novel end-to-end DRL framework, ToupleGDD, to address the IM problem in this article, which incorporates three coupled graph neural networks (GNNs) for network embedding and double deep$Q$-networks (DQNs) for parameters learning. Previous efforts to solve the IM problem with DRL trained their models on subgraphs of the whole network and then tested them on the whole graph, which makes the performance of their models unstable among different networks. However, our model is trained on several small randomly generated graphs with a small budget and tested on completely different networks under various large budgets, which can obtain results very close to IMM and better results than OPIM-C on several datasets and shows strong generalization ability. Finally, we conduct a large number of experiments on synthetic and realistic datasets and experimental results prove the effectiveness and superiority of our model.

In monitoring station observation, for the best accuracy of rumor source detection, it is important to deploy monitors appropriately into the network. There are, however, a very limited number of studies on the monitoring station selection. This article will study the problem of detecting a single rumormonger based on an observation of selected infection monitoring stations in a complete snapshot taken at some time in an online social network (OSN) following the independent cascade (IC) model. To deploy monitoring stations into the observed network, we propose an influence-distance-based$k$-station selection method where the influence distance is a conceptual measurement that estimates the probability that a rumor-infected node can influence its uninfected neighbors. Accordingly, a greedy algorithm is developed to find the best$k$monitoring stations among all rumor-infected nodes with a 2-approximation. Based on the infection path, which is most likely toward the$k$infection monitoring stations, we derive that an estimator for the “most like” rumor source under the IC model is the Jordan infection center in a graph. Our theoretical analysis is presented in the article. The effectiveness of our method is verified through experiments over both synthetic and real-world datasets. As shown in the results, our$k$-station selection method outperforms off-the-shelf methods in most cases in the network under the IC model.

Blockchain technology, recognized for its decentralized and privacy-preserving capabilities, holds potential for enhancing privacy in contact tracing applications. Existing blockchain-based contact tracing frameworks often overlook one or more critical design details, such as the blockchain data structure, a decentralized and lightweight consensus mechanism with integrated tracing data verification, and an incentive mechanism to encourage voluntary participation in bearing blockchain costs. Moreover, the absence of framework simulations raises questions about the efficacy of these existing models. To solve above issues, this article introduces a fully third-party independent blockchain-driven contact tracing (BDCT) framework, detailed in its design. The BDCT framework features an Rivest-Shamir-Adleman (RSA) encryption-based transaction verification method (RSA-TVM), achieving over 96% accuracy in contact case recording, even with a 60% probability of individuals failing to verify contact information. Furthermore, we propose a lightweight reputation corrected delegated proof of stake (RC-DPoS) consensus mechanism, coupled with an incentive model, to ensure timely reporting of contact cases while maintaining blockchain decentralization. Additionally, a novel simulation environment for contact tracing is developed, accounting for three distinct contact scenarios with varied population density. Our results and discussions validate the effectiveness, robustness of the RSA-TVM and RC-DPoS, and the low storage demand of the BDCT framework.

Social media with online social networks has risen to be a prevalent force in information diffusion and public discourse. Despite its popularity and convenience, social media has been criticized for contributing to societal and ideological polarization as the result of trapping users in an echo chamber and filter bubbles. An emerging line of research focuses on ways to redesign content or link recommendation algorithms to mitigate the polarization phenomenon. However, existing works mainly concentrate on node-level balancing, while omitting the balancing effect that can be incurred by edge interaction in social networks. In this article, we take the first step to study the problem (CoAM) that assuming two campaigns are present in a network, how we should select seeds for each so as to maximize the interaction/activity between the followers of two campaigns (co-activity) after the diffusion process is finished. We begin our analysis by showing the hardness of CoAM under two diffusion models that are generalized from wildly used diffusion models and its objective function is neither submodular nor supermodular. This encourages us to design a submodular function that acts as a lower bound to the objective, by exploiting which we are able to devise a greedy algorithm with a provable approximation guarantee. To overcome the #P-hardness of diffusion calculation, we further extend the notion of random reverse-reachable (RR) set to devise a scalable instantiation of our approximation algorithm. We experimentally demonstrate the quality of our approximation algorithm on datasets collected from real-world social networks.

Due to important applications in viral marketing, influence maximization (IM) has become a well-studied problem. It aims at finding a small subset of initial users so that they can deliver information to the largest amount of users through the word-of-mouth effect. The original IM only considers a singleton item. And the majority of extensions ignore the relationships among different items or only consider their competitive interactions. In reality, the diffusion probability of one item will increase when users adopted supplementary products in advance. Motivated by this scenario, we propose a supplementary independent cascade (IC) and discuss the supplementary IM problem. Our problem is NP-hard, and the computation of the objective function is #P-hard. We notice that the diffusion probability will change when considering the impact of its supplementary product. Therefore, the efficient reverse influence sampling (RIS) techniques cannot be applied to our problem directly even though the objective function is submodular. To address this issue, we utilize the sandwich approximation (SA) strategy to obtain a data-dependent approximate solution. Furthermore, we define the supplementary-based reverse reachable (SRR) sets and then propose a heuristic algorithm. Finally, the experimental results on three real datasets support the efficiency and superiority of our methods.

Mobile Crowdsourcing (MCS) is a novel distributed computing paradigm that recruits skilled workers to perform location-dependent tasks. A number of mature incentive mechanisms have been proposed to address the worker recruitment problem in MCS systems. However, most of them assume that there is a large enough worker pool and a sufficient number of users can be selected. This may be impossible in large-scale crowdsourcing environments. To address this challenge, we consider the MCS system defined on a location-aware social network provided by a social platform. In this system, we can recruit a small number of seed workers from the existing worker pool to spread the information of multiple tasks in the social network, thus attracting more users to perform tasks. In this paper, we propose a Multi-Task Diffusion Maximization (MT-DM) problem that aims to maximize the total utility of performing multiple crowdsourcing tasks under the budget. To accommodate multiple tasks diffusion over a social network, we create a multi-task diffusion model, and based on this model, we design an auction-based incentive mechanism, MT-DM-L. To deal with the high complexity of computing the multi-task diffusion, we adopt Multi-Task Reverse Reachable (MT-RR) sets to approximate the utility of information diffusion efficiently. Through both complete theoretical analysis and extensive simulations by using real-world datasets, we validate that our estimation for the spread of multi-task diffusion is accurate and the proposed mechanism achieves individual rationality, truthfulness, computational efficiency, and$(1-1/\sqrt{e}-\varepsilon )$approximation with at least$1-\delta$probability.

Influence Maximization (IM) is a well-known topic in mobile networks and social computing that aims to find a small subset of users that maximize the influence spread through an online information cascade. Recently, some cautious researchers have paid attention to the diversity of information dissemination, especially community-aware diversity, and formulated the diversified IM problem. Diversity is ubiquitous in many real-world applications, but these applications are all based on a given community structure. In social networks, we can form heterogeneous community structures for the same group of users according to different metrics. Therefore, how to quantify diversity based on multiple community structures is an interesting question. In this paper, we propose a Composite Community-Aware Diversified IM (CC-DIM) problem, which aims to select a seed set to maximize the influence spread and the composite diversity over all possible community structures under consideration. To address the NP-hardness of the CC-DIM problem, we adopt the technique of reverse influence sampling and design a random Generalized Reverse Reachable (G-RR) set to estimate the objective function. The composition of a random G-RR set is much more complex than the RR set used for the IM problem, which will lead to the inefficiency of traditional sampling-based approximation algorithms. Because of this, we further propose a two-stage algorithm, Generalized HIST (G-HIST). It can not only return a$(1-1/e-\varepsilon)$approximate solution with at least$(1-\delta)$probability but also improve the efficiency of sampling and ease the difficulty of searching by significantly reducing the average size of G-RR sets. Finally, we evaluate our proposed G-HIST on real datasets against existing algorithms. The experimental results show the effectiveness of our proposed algorithm and its superiority over other baseline algorithms.

Electric Vehicles (EVs) are becoming more and more popular in our daily life, which replaces traditional fuel vehicles to reduce carbon emissions and protect the environment. EVs need to be charged, but the number of charging piles in a Charging Station (CS) is limited, and charging is usually more time-consuming than fueling. According to this scenario, we propose a secure and efficient charging scheduling system based on a Directed Acyclic Graph (DAG)-blockchain and double-auction mechanism. In a smart area, it attempts to assign EVs to the available CSs in the light of their submitted charging requests and status information. First, we design a lightweight charging scheduling framework that integrates DAG-blockchain and modern cryptography technology to ensure security and scalability during performing scheduling and completing tradings. In this process, a constrained multi-item double-auction problem is formulated because of the limited charging resources in a CS, which motivates EVs and CSs in this area to participate in the market based on their preferences and statuses. Due to this constraint, our problem is more complicated and harder to achieve truthfulness as well as system efficiency compared to the existing double-auction model. To adapt to it, we propose two algorithms, namely, Truthful Mechanism for Charging (TMC) and Efficient Mechanism for Charging (EMC), to determine an assignment between EVs and CSs and pricing strategies. Then, both theoretical analysis and numerical simulations show the correctness and effectiveness of our proposed algorithms.

Influence maximization (IM) is a representative and classic problem that has been studied extensively before. The most important application derived from the IM problem is viral marketing. Take us as a promoter, we want to get benefits from the influence diffusion in a given social network, where each influenced (activated) user is associated with a benefit. However, there is often competing information initiated by our rivals diffusing in the same social network at the same time. Consider such a scenario, a user is influenced by both my information and my rivals' information. Here, the benefit from this user should be weakened to certain degree. How to quantify the degree of weakening? Based on that, we propose an overall evaluations on benefits of influence (OEBI) problem. We prove the objective function of the OEBI problem is not monotone, not submodular, and not supermodular. Fortunately, we can decompose this objective function into the difference of two submodular functions and adopt a modular-modular procedure to approximate it with a data-dependent approximation guarantee. Because of the difficulty to compute the exact objective value, we design a group of unbiased estimators by exploiting the idea of reverse influence sampling, which can improve time efficiency significantly without losing its approximation ratio. Finally, numerical experiments on real datasets verified the effectiveness of our approaches regardless of performance and efficiency.

Attracted by the inherent security and privacy protection of the blockchain, incorporating blockchain into Internet of Things (IoT) has been widely studied in these years. However, the mining process requires high computational power, which prevents IoT devices from directly participating in blockchain construction. For this reason, edge computing service is introduced to help build the IoT blockchain, where IoT devices could purchase computational resources from the edge servers. In this paper, we consider the case that IoT devices also have other tasks that need the help of edge servers, such as data analysis and data storage. The profits they can get from these tasks is closely related to the amounts of resources they purchased from the edge servers. In this scenario, IoT devices will allocate their limited budgets to purchase different resources from different edge servers, such that their profits can be maximized. Moreover, edge servers will set “best” prices such that they can get the biggest benefits. Accordingly, there raise a pricing and budget allocation problem between edge servers and IoT devices. We model the interaction between edge servers and IoT devices as a multi-leader multi-follower Stackelberg game, whose objective is to reach the Stackelberg Equilibrium (SE). We prove the existence and uniqueness of the SE point, and design efficient algorithms to reach the SE point. In the end, we verify our model and algorithms by performing extensive simulations, and the results show the correctness and effectiveness of our designs.

Community partition is an important problem in many areas, such as biology networks and social networks. The objective of this problem is to analyze the relationships among data via the network topology. In this article, we consider the community partition problem under the independent cascade (IC) model in social networks. We formulate the problem as a combinatorial optimization problem that aims at partitioning a given social network into disjoint$m$communities. The objective is to maximize the sum of influence propagation of a social network through maximizing it within each community. The existing work shows that the influence maximization for community partition problem (IMCPP) is NP-hard. We first prove that the objective function of IMCPP under the IC model is neither submodular nor supermodular. Then, both supermodular upper bound and submodular lower bound are constructed and proved so that the sandwich framework can be applied. A continuous greedy algorithm and a discrete implementation are devised for upper and lower bound problems. The algorithm for both of the two problems gets a$1-1/e$approximation ratio. We also present a simple greedy algorithm to solve the original objective function and apply the sandwich approximation framework to it to guarantee a data-dependent approximation factor. Finally, our algorithms are evaluated on three real datasets, which clearly verifies the effectiveness of our method in the community partition problem, as well as the advantage of our method against the other methods.

Using the increasingly wireless communication capacity of 5G/6G technology, edge intelligence (EI) enables modern vehicles to leverage the powerful computing resources of edge servers scattered aside the roads to implement intelligent transportation applications (ITA). The running of these intelligent applications is always accompanied by the calculating and transmitting of massive amounts of road situation data. For the protection of drivers and passengers, these complex processes should be handled in an ultra-reliable and low latent manner. Intelligent processing function offloading from terminals to edge servers is a promising approach to address these issues. However, the runtime environment specification of each intelligent processing function and the interdependence between two consecutive functions pose a challenge for the assignment of the offloaded functions among edge servers. In this paper, we propose a dependence-aware edge intelligent function offloading scheme for 6G-based Internet of Vehicle (IoV). All traditional ITAs are split into different chains of standard intelligent functions. Each edge server can provide some specific intelligent functional services. These services can receive data from cars and serve as different intelligent functions. Then, an intelligent application offloading scheme is changed into an embedding scheme of a service chain. An NP-hard objective function is constructed using a multi-winner committee selection model for this offloading service chain embedding problem. We design two algorithms to get the optimal assignment of intelligent functions using a greedy strategy and dynamic programming strategy separately. Finally, experiments show that when the proportion of vehicles meeting the constraint conditions is not in [9%, 10%], our algorithms are fast.

Influence Maximization (IM) is a classical combinatorial optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems. It aims at selecting a small number of users such that maximizing the influence spread across the online social network. Because of its potential commercial and academic value, there are a lot of researchers focusing on studying the IM problem from different perspectives. The main challenge comes from the NP-hardness of the IM problem and #P-hardness of estimating the influence spread, thus traditional algorithms for overcoming them can be categorized into two classes: heuristic algorithms and approximation algorithms. However, there is no theoretical guarantee for heuristic algorithms, and the theoretical design is close to the limit. Therefore, it is almost impossible to further optimize and improve their performance. With the rapid development of artificial intelligence, technologies based on Machine Learning (ML) have achieved remarkable achievements in many fields. In view of this, in recent years, a number of new methods have emerged to solve combinatorial optimization problems by using ML-based techniques. These methods have the advantages of fast solving speed and strong generalization ability to unknown graphs, which provide a brand-new direction for solving combinatorial optimization problems. Therefore, we abandon the traditional algorithms based on iterative search and review the recent development of ML-based methods, especially Deep Reinforcement Learning, to solve the IM problem and other variants in social networks. We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research. Finally, the challenges that need to be solved urgently in future IM research are pointed out.

Real-time traffic monitoring is a fundamental mission in a smart city to understand traffic conditions and avoid dangerous accidents. In this article, we propose a reliable and efficient traffic monitoring system that integrates blockchain and the Internet of Vehicles technologies effectively. It can crowdsource its tasks of traffic information collection to vehicles that run on the road instead of installing cameras in every corner. First, we design a lightweight blockchain-based information trading framework to model the interactions between traffic administration and vehicles. It guarantees reliability, efficiency, and security during executing trading. Second, we define the utility functions for the entities in this system and come up with a budgeted auction mechanism that motivates vehicles to undertake the collection tasks actively. In our algorithm, it not only ensures that the total payment to the selected vehicles does not exceed a given budget but also maintains the truthfulness of the auction process that prevents some vehicles from offering unreal bids for getting greater utilities. Finally, we conduct a group of numerical simulations to evaluate the reliability of our trading framework and performance of our algorithms, whose results demonstrate their correctness and efficiency perfectly.

In the Internet of Vehicles (IoVs), vehicles generate and disseminate information, which makes the related vehicular services realized. However, the IoVs is an untrusted environment. Vehicles cannot evaluate the credibility of the received information, which makes it a challenge to implement data sharing in IoVs. Blockchain, constantly directed main attention, are considered as a feasible solution to address the challenge, due to its advantages of decentralization, unforgeability, and collective maintenance. The consensus mechanism of blockchain requires the miners in the system with strong computing power for mining, while the computing power of nodes in IoVs is limited, which restricts the application of blockchain in IoVs. In fact, the application of blockchain in IoVs can be implemented by employing edge computing. The key entity of edge computing is the edge servers(ESs). Roadside nodes (RSUs) can be deployed as ESs of edge computing in IoVs. In this article, we study the ESs deployment scheme for covering more vehicle nodes in IoVs, and propose a randomized algorithm to calculate approximation solutions. Finally, we simulated the performance of the proposed scheme and compared it with other deployment schemes.

Revenue maximization (RM) is one of the most important problems in social networks, which attempts to find a small subset of users that make the expected revenue maximized. It has been studied in depth before. However, most of the existing literature was based on nonadaptive seeding strategies and simple information diffusion models. It considered the number of influenced users as a measurement unit to quantify the revenue. Until the emergence of the collaborate game model, it considered the activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distances are within${k}$-hop from the initiator. Based on that, we adopt an adaptive seed strategy and formulate an RM under the size budget (RMSB) problem. If taking into account the product’s promotion, we extend it to an RM under the community budget problem, where the influence can be distributed over the whole network uniformly. We can prove that our objective function is adaptive monotone and not adaptive submodular, but it is adaptive submodular in some special cases. We study these two problems under both the special submodular cases and general nonsubmodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. In particular, we give a data-dependent approximation ratio by adaptive primal curvature for the RMSB in general nonsubmodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions.

With the normalization of epidemic prevention, many hotels regard pre-sale as a "life-saving straw", but it leaves a "sequelae" of booking cancellation. Therefore, based on risk aversion theory and attribution theory, this paper studies the influencing factors of hotel booking cancellation behavior of consumers through situational experiment. Results show that: (1) Electronic word-of-mouth dispersion has a significant positive impact on booking cancellation behavior of hotel consumers. (2) Attribution selection can mediate the influence of hotel electronic word-of-mouth dispersion on booking cancellation behavior of consumers. (3) Self-construal can moderate the influence of electronic word-of-mouth dispersion on attribution selection. Findings explore the important factor that influence the booking cancellation behavior of hotel consumers, and provides theoretical guidance and reference for the management of hotel booking cancellation phenomenon.

Along with the development in the Internet of Things technology and smart city, a distributed network has been formed among cities. This makes it easy to integrate distributed electric energy into the power grid, thus become an efficient way to use energy. However, how to guarantee the security and privacy protection of distributed electricity trading has not been solved effectively. In this article, we propose a blockchain-based electricity trading (B-ET) ecosystem and design a smart contract to ensure transactions are conducted in a safe and reliable manner. To overcome the shortcomings of high latency in traditional Proof-of-Work (PoW) consensus, we proposed a credit-based PoW consensus mechanism by integrating the concept of “stake” to improve the consortium blockchain under the B-ET ecosystem. Then, we take combined cooling, heating, and power (CCHP) system as an example that supplies distributed energy, and model its interactions with the agent of power grid by a novel Stackelberg game. We show that the optimal utilities of entities in a city can be obtained at the Stackelberg equilibrium by a distributed algorithm, which is guaranteed to exist and be unique. In the end, we conduct a number of numerical simulations to evaluate our proposed model and verify our algorithms, which demonstrate their correctness and efficiency completely.

Multidocument summarization problem deals with extracting main information and ideas from a set of related documents. Solution to this problem is to find an extraction strategy that aims at finding a small subset of sentences that is able to cover the most important information about the whole document set. Although a large number of machine-learning-based methods have shown great promise, the lack of high-quality training data poses an inherent obstacle to them. Furthermore, because of the proliferation of low-quality documents on the Internet, the existing summarization strategies, which are merely based on statistical features, get poor performance. In this article, we propose a new two-phase multidocument summarization strategy using content attention-based subtopic detection. First, inspired by distance dynamics-based community detection mechanism, we extract subtopics from the set of documents by having insight into their own content attention and also underlying semantic relations. Instead of complicated neural attention mechanisms, we propose a simple iteration-based content attention method to complete the subtopic detection task. Second, we formulate summarization from different subtopics as a combinatorial optimization problem of minimizing sentence distance and maximizing topic diversity. We prove the submodularity of the above optimization problem, which allows us to propose a new multidocument summarization algorithm based on the greedy mechanism. Finally, we experimentally validate our new algorithms on BBC news summary and wikiHow data. The results show our new algorithms outperform the state-of-the-art methods.

Blockchain can provide a dependable environment for the Internet of Things (IoT), while the high computing power and energy required by blockchain hinder its applications in IoT. Offloading the computation at the resource-limited IoT devices to a cloud/edge computing service provider (CESP) is a feasible solution to the execution of computation-intensive blockchain tasks. The CESP provides computing resources to IoT users with a cloud and multiple edge servers that work collaboratively such that the users are able to perform mobile blockchain services. Resource allocation and pricing of computing resources at the cloud/edges have a significant impact on the revenues of CESP and users. Most of the existing works on the cooperative edge-cloud for computation offloading assumes that a user is mapped to a prespecified edge server or the cloud. However, the CESP may choose a server from either the edge servers or the cloud to run the offloaded tasks by jointly considering the cost and income of the service provisioning. In this article, we formulate a Stackelberg game with CESP as the leader and users as the followers for cloud/edge computing resource management. We prove the existence of Stackelberg equilibrium and analyze the equilibrium. We then model the resource allocation and pricing at the CESP as a mixed-integer programming problem (MIP) with the objective to optimize the CESP's revenue and propose an efficient iterative greedy-and-search-based resource allocation and pricing algorithm (IGS). The algorithm solves two subproblems comprising the CESP's revenue optimization problem: resource allocation under a given resource price and resource pricing based on a specified resource allocation scheme. The first subproblem evaluates where to execute the computing tasks via a greedy-and-search-based approach, whereas the second subproblem estimates the resource price through golden section search. We conduct experiments through simulations. Simulation results show that the proposed algorithm can effectively improve the revenue of both the CESP and the IoT terminals.

Profit maximization (PM) is to select a subset of users as seeds for viral marketing in online social networks, which balances between the cost and the profit from influence spread. We extend PM to formulate a continuous PM under the general marketing strategies (CPM-MS) problem, whose domain is on integer lattices. The objective function of our CPM-MS is dr-submodular, but nonmonotone. It is a typical case of unconstrained dr-submodular maximization (UDSM) problem, and taking it as a starting point, we study UDSM systematically in this article, which is very different from those studied by existing researchers. First, we introduce the lattice-based double greedy algorithm, which can obtain a constant approximation guarantee. However, there is a strict and unrealistic condition that requiring the objective value is nonnegative on the whole domain or else no theoretical bounds. Thus, we propose a lattice-based iterative pruning technique. It can shrink the search space effectively, thereby greatly increasing the possibility of satisfying the nonnegative objective function on this smaller domain without losing approximation ratio. Then, to overcome the difficulty to estimate the objective value of CPM-MS, we adopt reverse sampling strategies and combine it with lattice-based double greedy, including pruning, without losing its performance but reducing its running time. The entire process can be considered as a general framework to solve the UDSM problem, especially for applying to social networks. Finally, we conduct experiments on several real data sets to evaluate the effectiveness and efficiency of our proposed algorithms.

Influence maximization problem attempts to find a small subset of nodes that makes the expected influence spread maximized, which has been researched intensively before. They all assumed that each user in the seed set we select is activated successfully and then spread the influence. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider each user associated with a probability with which we can activate her as a seed, and we can attempt to activate her many times. In this article, we study the adaptive influence maximization with multiple activations (Adaptive-IMMA) problem, where we select a node in each iteration, observe whether she accepts to be a seed, if yes, wait to observe the influence diffusion process; if no, we can attempt to activate her again with a higher cost or select another node as a seed. We model the multiple activations mathematically and define it on the domain of integer lattice. We propose a new concept, adaptive dr-submodularity, and show our Adaptive-IMMA is the problem that maximizing an adaptive monotone and dr-submodular function under the expected knapsack constraint. Adaptive dr-submodular maximization problem is never covered by any existing studies. Thus, we summarize its properties and study its approximability comprehensively, which is a non-trivial generalization of existing analysis about adaptive submodularity. Besides, to overcome the difficulty to estimate the expected influence spread, we combine our adaptive greedy policy with sampling techniques without losing the approximation ratio but reducing the time complexity. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed policies.

Cyberbullying has caused serious consequences especially for social network users in recent years. However, the challenge is how to fight against the cyberbullying effectively from the algorithmic perspective. In this article, we study the fighting against the cyberbullying problem, i.e., identify an initial witness set with a budget to spread the positive influence to protect the users in a specific target set such that the number of cybervictim users in the target set being activated by the seed set of cyberbullying is minimized. We first formulate this problem and show its NP-hardness. We further prove that the objective function is submodular with respect to the size of witnesses set when we convert the original problem into the maximal version. Then we propose a stochastic approach to solve this maximal version problem based on the Reverse Sampling Technique with a constant factor guarantee. In addition, we provide theoretical analysis and discuss the relationship between the optimal value and the value returned by the proposed algorithm. To evaluate the proposed approach, we implement extensive experiments on synthetic and real datasets. The experimental results show our approach is superior to the comparison methods.

Online social networks provide a convenient platform for the spread of rumors, which could lead to serious aftermaths such as economic losses and public panic. The classical rumor blocking problem aims to launch a set of nodes as a positive cascade to compete with misinformation in order to limit the spread of rumors. However, most of the related researches were based on a one-dimensional diffusion model. In reality, there is more than one feature associated with an object. A user's impression on this object is determined not just by one feature but by her overall evaluation of all features associated with it. Thus, the influence spread of this object can be decomposed into the spread of multiple features. Based on that, we design a multi-feature diffusion model (MF-model) in this paper and formulate a multi-feature rumor blocking (MFRB) problem on a multi-layer network structure according to this model. To solve the MFRB problem, we design a creative sampling method called Multi-Sampling, which can be applied to this multi-layer network structure. Then, we propose a Revised-IMM algorithm and obtain a satisfactory approximate solution to MFRB. Finally, we evaluate our proposed algorithm by conducting experiments on real datasets, which shows the effectiveness of our Revised-IMM and its advantage to their baseline algorithms.

The increasing availability of autonomous small-size Unmanned Aerial Vehicles (UAVs) has provided a promising way for data gathering from Wireless Sensor Networks (WSNs) with the advantages of high mobility, flexibility, and good speed. However, few works considered the situations that multiple UAVs are collaboratively used and the fine-grained trajectory plans of multiple UAVs are devised for collecting data from network including detailed traveling and hovering plans of them in the continuous space. In this paper, we investigate the problem of the Fine-grained Trajectory Plan for multi-UAVs (FTP), in which m UAVs are used to collect data from a given WSN, where m ≥ 1. The problem entails not only to find the flight paths of multiple UAVs but also to design the detailed hovering and traveling plans on their paths for efficient data gathering from WSN. The objective of the problem is to minimize the maximum flight time of UAVs such that all sensory data of WSN is collected by the UAVs and transported to the base station. We first propose a mathematical model of the FTP problem and prove that the problem is NP-hard. To solve the FTP problem, we first study a special case of the FTP problem when m = 1, called FTP with Single UAV (FTPS) problem. Then we propose a constant-factor approximation algorithm for the FTPS problem. Based on the FTPS problem, an approximation algorithm for the general version of the FTP problem when m > 1 is further proposed, which can guarantee a constant factor of the optimal solution. Afterwards, the proposed algorithms are verified by extensive simulations.

Mobile edge computing system provides cloud computing capabilities at the edge of wireless mobile networks, ensuring low latency, highly efficient computing, and improved user experience. At the same time, computationally intensive components are offloaded from mobile devices to edge servers and distributed among the servers. Due to the special constraints (mobile devices' battery capacities, limited computing resources of one single edge server, inevitable edge server failure, etc.), there emerges a following problem. 1) How to guarantee the reliability of the offloaded computing? This problem brings in the following two other problems. 2) How to find the appropriate offloading point in the mobile program such that the computing tasks offloaded to cloud can be maximized, while the transmission energy consumption is minimized? 3) What is the achievable minimum latency tasks allocation strategy among multiple users' mobile devices and multiple edge servers? In this paper, we try to address the aforementioned problems. First, for the appropriate offloading point problem, we consider the offloading valuable basic constraint and propose a task merging strategy based on mobile program component call graphs to minimize the computational complexity of the program partition. Second, we formulate the second problem as a combinatorial optimization problem and transform it into an n-fold integer programming problem by mapping the remaining computing resources to a virtual component. Third, we design a reliable shadow component scheme between multilevel severs for the reliability problem. Finally, we develop a fast algorithm for the mix problem and analyze its performance and conduct experiments to prove the accuracy of our theoretical results.

With the explosive growth in the scale of cloud computing infrastructures, reliability and energy efficiency have become important concerns considering the great complexity of cloud data centers. There is an urgent need for efficient task assignment that can dispatch tasks to appropriate cloud data center servers, which is critical to achieve reliability and energy efficiency in current cloud data centers. Most of the research on task assignment focuses on only one of the objectives of reliability and energy efficiency, while the two objectives are intrinsically conflicting with each other. In this paper, we deal with the problem of task assignment in data centers, with the objective of minimizing the energy consumption while providing failure tolerance to task execution failure. We propose a reliability-aware and energy-efficient task replica assignment algorithm based on running task replicas at a low speed and enabling multiple task replicas to share the same server resources. Each task in a job processed by the cloud computing platform has two instances: main task and task replica (shadow). Each main task runs on an individual server, and the task replica associated with the main task is assigned on a different server. The main tasks run at the full server speed, while the task replicas run at a lower rate than the main tasks. The task replicas can be mapped onto dedicated backup servers or be assigned to the servers on which the main tasks are running. Multiple task replicas can share the same server resources to reduce the number of servers required. We conduct experiments through simulations. Experimental results demonstrate that the proposed algorithm can effectively reduce the energy consumption, while achieving a good balance between the number of servers used and job completion time.

Electronic Health Record (EHR) and healthcare claim data provide rich clinical information for time series analysis. In this work, we provide a different angle of solving healthcare multivariate time series classification by turning it into a computer vision problem. We propose a Convolutional Feature Engineering (CFE) methodology, that can effectively extract long sequence dependency time series features. Combined with LightGBM, it can achieve the state-of-the-art results with 35X speed acceleration compared with LSTM based approaches on MIMIC-III In Hospital Mortality benchmark task. We deploy CFE based LightGBM into our Mortality Early Warning System at Humana, and train it on 1 million member samples. The offline metrics shows that this new approach generates better-quality predictions than previous LSTM based approach, and meanwhile greatly decrease the training and inference time.

As vehicles are becoming more and more intelligent, mobile data traffic in vehicular ad hoc network (VANET) has been increasing dramatically. This makes the communication capacity of VANET systems and the computing resources of vehicles insufficient. In the meantime, location-aware large-scale distributed services with very low latency and high reliability are demanded by most of the novel functions, such as accident alarming, and congestion warning, in the intelligent transportation system. To meet these claimed characteristics of VANET, we first present a novel architecture that integrates vehicular fog computing and vehicle-to-vehicle (V2V) communication technologies. Lower latency and higher quality services can be supplied to vehicles by nearby fog servers, which are virtualized from vehicles that locate close enough and communicate using the V2V link. However, like all collaborative systems, computing reliability is vital to collaborative VANET. In this article, we design a novel energy-efficient proactive replication mechanism. Follower vehicles calculate with a lazy rate act as backups of host vehicles to ensure the reliability of the system. Considering the time sensitivity of computing requirements in VANET, the upper bound on the total number of failures is proposed through theoretical analysis. Then, the lower bound on the lazy calculating rate of followers is derived by balancing the tradeoffs between delay and energy. A fast algorithm for searching this lower bound based on the discrete Newton method is also proposed. Results of numerical experiments show that our new mechanism is effective in energy saving and reliability enhancing.

In online social networks (OSNs), interpersonal communication and information sharing are happening all the time, and it is real time. If a user initiates an activity (game) in OSNs, she will cause a certain impact on her friendship circle naturally, namely, some users in this initiator's friendship circle will be attracted to participate in this activity. Based on such a fact, we design a k-hop collaborated game model, which means that an activity initiated by a user can only influence those users whose distance is within k-hop from this initiator. We introduce the problem of revenue maximization under k-hop collaborate game (RMKCG), which identifies a limited number of initiators in order to obtain revenue as much as possible. The collaborated game model describes in detail how to quantify revenue and the logic behind it. We do not know how many followers would be attracted by activity in advance, and thus, we need to adopt an adaptive strategy, where the decision who is the next potential initiator depends on the results of past decisions. The adaptive RMKCG problem can be considered as a new stochastic optimization problem, and we prove it is NP-hard, adaptive monotone, but not adaptive submodular. But in some special cases, it is adaptive submodular, and thus, we design an adaptive greedy algorithm. Due to the complexity of our model, it is hard to compute the marginal gain for each candidate user, and then we propose an efficient computational method to estimate it. The effectiveness and correctness of our algorithms are validated by heavy simulation on real-world graphs finally.

Nowadays, different innovations spread rapidly in online social networks. An activation state can indicate whether each user adopts the target information. The effector detection problem aims to find a way to generate an activation state as close to an observed one as possible. In this article, based on the influence spread, the unconstrained and constrained effector detection problems are proposed. To tackle them, we design two approximation algorithms since the problem is NP-hard, and the objective function is nonsubmodular. For the unconstrained case, our objective function can be best provided with the difference of two submodular functions. Thus, we address this problem through the modular-modular algorithm. For the constrained case, we devise the solutions for the original function, submodular upper bound, and lower bound according to an idea of reverse influence sampling. Then, there is a data-dependent approximate solution using the sandwich approximation algorithm. Finally, we show the correctness and superiority of our methods through massive experiments in three real-world networks.

Influence maximization problem attempts to find a small subset of nodes in a social network that makes the expected influence maximized, which has been researched intensively before. Most of the existing literature focus only on maximizing total influence, but it ignores whether the influential distribution is balanced through the network. Even though the total influence is maximized, but gathered in a certain area of social network. Sometimes, this is not advisable. In this article, we propose a novel seeding strategy based on community structure, and formulate the Influence Maximization with Community Budget (IMCB) problem. In this problem, the number of seed nodes in each community is under the cardinality constraint, which can be classified as the problem of monotone submodular maximization under the matroid constraint. To give a satisfactory solution for IMCB problem under the triggering model, we propose the IMCB-Framework, which is inspired by the idea of continuous greedy process and pipage rounding, and derive the best approximation ratio for this problem. In IMCB-Framework, we adopt sampling techniques to overcome the high complexity of continuous greedy. Then, we propose a simplified pipage rounding algorithm, which reduces the complexity of IMCB-Framework further. Finally, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms, as well as the advantage of IMCB-Framework against classical greedy method.

MapReduce jobs need to shuffle a large amount of data over the network between mapper and reducer nodes. The shuffle time accounts for a big part of the total running time of the MapReduce jobs. Therefore, optimizing the makespan of shuffle phase can greatly improve the performance of MapReduce jobs. A large fraction of production jobs in data centers are recurring with predictable characteristics, and the recurring jobs split the network into periodic busy and idle time slots, which allows us to better schedule the shuffle data in order to reduce the makespan of shuffle phase with the future predictable network status available. In this paper, we formulate the shuffle scheduling problem with the aim to minimize the makespan of MapReduce shuffle phase by leveraging the predictable periodic network status. We then propose a simple yet effective network-aware shuffle scheduling algorithm (NAS) to reduce the number of idle time slots required to transfer the shuffle data so as to reduce the shuffle makespan. We also prove that the proposed algorithm NAS is a 3/2-approximation algorithm to the shuffle scheduling problem when all the future idle time slots have the same duration. We finally conduct experiments through simulations. Experimental results demonstrate the proposed algorithm can effectively reduce the makespan of MapReduce shuffle phase and increase network utilization.

In dynamic networks, links are annotated with timestamps showing the emerging time and the link prediction problem is to infer the future links in networks. Universal link prediction methods are highly demanded in various applications, which require universal link features that are feasible for multiple kinds of network topological structures and capable to address the difference of links with different timestamps. In this paper, we propose a novel link feature called Structure Subgraph Feature (SSF). The SSF is an outstanding link feature that is feasible to various dynamic networks due to the following superiorities: (1) the proposed structure subgraph is so far the most effective manner to represent surrounding topological features of target link and (2) the normalized influence well specifies the influence of multiple links and different timestamps in structure subgraph. We finally propose two link prediction methods by applying SSF to a linear regression model and a neural machine. Experimental results on real-world dynamic network datasets indicate that the SSF-based methods consistently provide top-class performance on various dynamic networks.

Guiding users to actively expanding their online social circles is one of the primary strategies for enhancing user participation and growing online social networks. In this paper, we study the active friending problem which aims at providing users with the strategy for methodically sending invitations to successfully build a friendship with target users. We consider the prominent linear threshold model for the friending process and formulate the active friending problem as an optimization problem. The key observation is the relationship between the active friending problem and the minimum subset cover problem, based on which we present the first randomized algorithm with a data-independent approximation ratio and a controllable success probability for general graphs. The performance of the proposed algorithm is theoretically analyzed and supported by encouraging simulation results done on extensive datasets.

Viral marketing, the method of using a small set of users in social networks to propagate products through cascades, is a well-known and extreme research problem in recent years. Then, influence maximization (IM) is formulated, which aims to select the most influential seeds to maximize the expected total adoption eventually. IM expresses viral marketing perfectly. However, almost all prior work focused on cardinality constraint or considers only simple comparative products model. They neglected that composite complementary products (CCP) are widespread. In other words, when a customer adopts products A and B at the same time, it is possible for him to adopt product C. Therefore, we design a multi-layer network model under independent cascade (IC) model to adapt to multiple complementary products and define the seed selection problem for complementary products model [IM for complementary products (IMCP)] and CCP model (IMCCP) under knapsack constraint. Here, the seed for different products has a different cost. In this paper, we propose two efficient techniques to solve IMCP problem, called Greedy and general-TIM. The Greedy uses simple Greedy Hill-Climbing algorithm under knapsack constraint and obtain (1/2)(1-(1/e))-approximation, but the time complexity is hard to accept. The second algorithm, general-TIM, forms a weighted set cover problem by means of randomized sampling (close to Greedy in practice), which reduces the time-consuming significantly. For IMCCP problem, it is difficult to handle because no ready-made algorithms exist to optimize a function that is nonsubmodular and nonsupermodular. Then, we need to get help from sandwich method by finding an upper and lower bound. Finally, our algorithms are evaluated on several real data sets, which prove the correctness of our algorithms.

The growing importance of social network for sharing and spreading various contents is leading to the changes in the way of information diffusion. To what extent can social content be diffused highly depends on the size of seed nodes and connectivity of the network. If the seed set is predetermined, then the best way to maximize the content spread is to add connectivities among the users. The existing work shows the content spread maximization problem to be NP-hard. One of the difficulties of designing an effective and efficient algorithm for the content spread maximization problem lies in that the objective function we aim to maximize lacks submodularity. In our work, we formulate the maximize content spread problem from an incremental marginal gain perspective. Although the objective function we derive is not submodular, both submodular lower and upper bounds are constructed and proved. Therefore, we apply the sandwich framework and devise a marginal increment-based algorithm (MIS) that guarantees a data-dependent factor. Furthermore, a novel scalable content spread maximization algorithm influence ranking and fast adjustment (IRFA), which is based on the influence ranking of a single node and fast adjustment with each boosting step in the network, is proposed. Through extensive experiments, we demonstrate that both MIS and IRFA algorithms are effective and outperform other edge selection strategies.

In the past decade, tremendous research effort has been devoted to viral marketing. Most existing works on seed selection in social networks do not take into account the scenario when a profit can be generated from group activities. Each activity has a profit that can be measured by the excitement of the participants. The excitement about one piece of information can vary significantly among different groups of people. Given a social network and a profit function, how can we select the seed users to maximize the expected total amount of profit? This problem is essentially different from the classic influence maximization problem, and existing approaches cannot be directly applied to solve the problem. In this paper, we study the problem of activity profit maximization in social networks. We first prove that the maximizing activity profit problem is nondeterministic polynomial time-hard and cannot be approximated within a constant factor by the simple greedy algorithm. Supermodular degree of a function measures the extent to which it violates submodularity. We design an algorithm that achieves an approximation ratio of (1/(Δ+ 2)) provided that the supermodular degree of the social graph is bounded with A. We then develop an exchange-based technique to further improve the quality of the solution. We also devise a randomized variation approach to overcome the computational burden of the proposed algorithms. Extensive experimental results on three real benchmark data sets demonstrate the efficacy and efficiency of our algorithms over several baseline heuristics.

Group plays an important role in social society. Much of the world's decision or work is done by groups and teams. A group's decision should be made based on most of the members in the group that reach agreement on a concerned topic. If we want to spread a topic and maximize the total number of activated groups in a social network, which seed users should we choose. In this article, we will study a new influence maximization (IM) problem which focuses on the number of groups activated by some concerned topic or information. A group is said to be activated if β percent of users in this group are activated. Group IM (GIM) aims to select k seed users such that the number of eventually activated groups is maximized. We first analyze the complexity and approximability of GIM, which is NP-hard, and the objective function presented in this article is proven to be neither submodular nor supermodular. We develop an upper bound problem and a lower bound problem whose objective functions are submodular. Then, an algorithm based on group coverage will be proposed, and the Sandwich framework is formulated with theoretical analysis to solve GIM. Our experiments verify the effectiveness of our method, as well as the advantage of our method against the other heuristic methods.

In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized. We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods.

The widespread online misinformation could cause public panic and serious economic damages. The misinformation containment problem aims at limiting the spread of misinformation in online social networks by launching competing campaigns. Motivated by realistic scenarios, we present the first analysis of the misinformation containment problem for the case when an arbitrary number of cascades are allowed. This paper makes four contributions. First, we provide a formal model for multi-cascade diffusion and introduce an important concept called as cascade priority. Second, we show that the misinformation containment problem cannot be approximated within a factor of $\Omega(2^{\log^{1-\epsilon}n^4})$ in polynomial time unless $NP \subseteq DTIME(n^{\polylog{n}})$. Third, we introduce several types of cascade priority that are frequently seen in real social networks. Finally, we design novel algorithms for solving the misinformation containment problem. The effectiveness of the proposed algorithm is supported by encouraging experimental results.

Misinformation and rumor can spread rapidly and widely through online social networks and therefore rumor controlling has become a critical issue. It is assumed in the existing works that there is a single authority whose goal is to minimize the spread of rumor by generating a positive cascade. In this paper, we study a more realistic scenario when there is multiple positive cascades generated by different agents. For the multiple-cascade diffusion, we propose the peer-to-peer independent cascade model for private social communications. The main contribution of this paper is an analysis of the rumor blocking effect (i.e., the number of the users activated by rumor) when the agents noncooperatively generate the positive cascades. We show that the rumor blocking effect provided by the Nash equilibrium will not be arbitrarily worse even if the positive cascades are generated noncooperatively. In addition, we give a discussion on how the cascade priority and activation order affect the rumor blocking problem. We experimentally examine the Nash equilibrium of the proposed games by simulations done on real social network structures.

Understanding the community structure of social media is critical due to its broad applications such as friend recommendations, user modeling, and content personalization. Existing research uses structural metrics such as modularity and conductance and functional metrics such as ground truth to measure the quality of the communities discovered by various community detection algorithms, while overlooking a natural and important dimension, community size. Recently, the anthropologist Dunbar suggests that the size of a stable community in social media should be limited to 150, referred to as Dunbar's number. In this paper, we propose a systematic way of algorithm comparison by orthogonally integrating community size as a new dimension into existing structural metrics for consistently and holistically evaluating the community quality in the social media context. We design a heuristic clique-based algorithm which controls the size and overlap of communities with adjustable parameters and evaluate it along with six state-of-the-art community detection algorithms on both Twitter and DBLP networks. Specifically, we divide the discovered communities based on their size into four classes called a close friend, a casual friend, acquaintance, and just-a-face, and then calculate the coverage, modularity, triangle participation ratio, conductance, transitivity, and the internal density of communities in each class. We discover that communities in different classes exhibit diverse structural qualities and many existing community detection algorithms tend to output extremely large communities.

We study the problem of active friending in online social networks. Given an initiator who want to friend a target person on a social network, we propose a strategy to support active friending through a series of recommendation lists. The lists serve as a step-to-step guidance for the initiator. We formulate an optimization problem, Constrained Active Friending CAF), for configuring the recommendation lists in the active friending process. Our goal is to maximize the acceptance probability of the invitation from the initiator to the friending target, by recommending selective intermediate friends to approach the target. We prove that CAF problem is NP-hard under the linear threshold model. We propose an algorithm based on discrete super-differentials that derives a guaranteed approximation for this problem. Extensive evaluation results on benchmark social network datasets validate the effectiveness and efficiency of our algorithms.

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

Social networks allow rapid spread of ideas and innovations while the negative information can also propagate widely. When the cascades with different opinions reaching the same user, the cascade arriving first is the most likely to be taken by the user. Therefore, once misinformation or rumor is detected, a natural containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of the positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1 - 1/e- δ) by a classic greedy algorithm combined with Monte Carlo simulation with the running time of O(k3mn ln n/δ2), where n and m are the number of users and edges, respectively. Unfortunately, the Monte-Carlo-simulation-based methods are extremely time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized algorithm which runs in O(km ln n/δ2) expected time and provides a (1 - 1/e - δ)-approximation with a high probability. The experimentally results on both the real-world and synthetic social networks have shown that the proposed randomized rumor blocking algorithm is much more efficient than the state-of-the-art method and it is able to find the seed nodes which are effective in limiting the spread of rumor.

Influence maximization problem is to find a set of seeds in social networks such that the cascade influence is maximized. Traditional models assume that all nodes are willing to spread the influence once they are influenced, and they ignore the disparity between influence and profit of a product. In this paper, by considering the role that price plays in viral marketing, we propose price related (PR) frame that contains PR-I and PR-L models for classic independent cascade and linear threshold models, respectively, which is a pioneer work. Two pricing strategies are designed, one is binary pricing (BYC), in which the seeds are offered free samples. The other is panoramic pricing (PAP), in which the seeds are offered different discounts. Furthermore, we find that influence and profit are like two sides of the coin, high price hinders the influence propagation and to enlarge the influence some sacrifice on profit is inevitable. Based on this observation under PR frame, by adopting a parameter to denote the decision maker's preference toward influence and profit, we propose balanced influence and profit (BIP) maximization problem. We prove the NP-hardness of BIP maximization under PR-I and PR-L model. Unlike influence maximization, the BIP objective function is not monotone. Despite the nonmonotony, we show BIP objective function is submodular under certain conditions. Two unbudgeted greedy algorithms separately, named algorithm of BYC and algorithm of PAP are devised. We conduct extensive simulations on real world data sets, test the effectiveness of our proposed parameters, compare the algorithms' performances, and evaluate the superiority of our algorithms over existing ones.

Recently, the concept of barrier-coverage of wireless sensor network has been introduced for various civilian and military defense applications. This paper studies the problem of how to organize hybrid sensor network, which consists of a number of energy-scarce ground sensors with homogenous initial battery level and energy-plentiful mobile sensors, to maximum the lifetime of barrier-coverage. Two key observations are (a) as the lifetime of each mobile sensor is much longer than that of the static ground sensors, each mobile sensor is capable of contributing multiple sensor barrier formations, and (b) no mobile sensor node can join two hybrid barriers which will be successively used to continuously protect the area of interest due to the moving delay. Based on these, we introduce a new maximum lifetime barrier-coverage problem in hybrid sensor network. We first propose a simple heuristic algorithm by combining existing ideas along with our own. Then, we design another efficient algorithm for the problem and prove that the lifetime of hybrid barrier constructed by this algorithm is at least three times greater than the existing one on average. Our simulation result shows that the second algorithm outperforms the first algorithm at least 33 percent and up to 100 percent.

For the purpose of propagating information and ideas through a social network, a seeding strategy aims to find a small set of seed users that are able to maximize the spread of the influence, which is termed influence maximization problem. Despite a large number of works have studied this problem, the existing seeding strategies are limited to the models that cannot fully capture the characteristics of real-world social networks. In fact, due to high-speed data transmission and large population of participants, the diffusion processes in real-world social networks have many aspects of uncertainness. As shown in the experiments, when taking such uncertainness into account, the state-of-the-art seeding strategies are pessimistic as they fail to trace the influence diffusion. In this paper, we study the strategies that select seed users in an adaptive manner. We first formally model the dynamic independent Cascade model and introduce the concept of adaptive seeding strategy. Then, based on the proposed model, we show that a simple greedy adaptive seeding strategy finds an effective solution with a provable performance guarantee. Besides the greedy algorithm, an efficient heuristic algorithm is provided for better scalability. Extensive experiments have been performed on both the real-world networks and synthetic power-law networks. The results herein demonstrate the superiority of the adaptive seeding strategies to other baseline methods.

On-demand wireless data broadcast is an efficient way to disseminate data to a large number of mobile users. In many applications, such as stock quotes and flight schedules, users may have to download multiple data items per request. However the multi-item request scheduling has not yet been thoroughly investigated for on-demand wireless data broadcasts. In this paper, we step-up on investigating this problem from viewpoint of theory and simulation. We develop a two-stage scheduling scheme to arrange the requested data items with the objective of minimizing the average access latency. The first stage is to select the data items to be broadcast in the next time period and the second stage is to schedule the broadcasting order for the data items selected in the first stage. We develop algorithms for the two stages respectively and analyze them both theoretically and practically. We also compare the proposed algorithms with other well known scheduling methods through simulation. The theoretical findings and simulation results reveal that significantly better access latency can be obtained by using our scheduling scheme rather than its competitors.

Community detection aims to reveal the community structure in a social network, which is one of the fundamental problems. In this paper we investigate the community detection problem based on the concept of terminal set. A terminal set is a group of users within which any two users belong to different communities. Although the community detection is hard in general, the terminal set can be very helpful in designing effective community detection algorithms. We first present a 2-approximation algorithm running in polynomial time for the original community detection problem. In the other issue, in order to better support real applications we further consider the case when extra restrictions are imposed on feasible partitions. For such customized community detection problems, we provide two randomized algorithms which are able to find the optimal partition with a high probability. Demonstrated by the experiments performed on benchmark networks the proposed algorithms are able to produce high-quality communities.

In a social network, influence diffusion is the process of spreading innovations from user to user. An activation state identifies who are the active users who have adopted the target innovation. Given an activation state of a certain diffusion, effector detection aims to reveal the active users who are able to best explain the observed state. In this paper, we tackle the effector detection problem from two perspectives. The first approach is based on the influence distance that measures the chance that an active user can activate its neighbors. For a certain pair of users, the shorter the influence distance, the higher probability that one can activate the other. Given an activation state, the effectors are expected to have short influence distance to active users while long to inactive users. By this idea, we propose the influence-distance-based effector detection problem and provide a 3-approximation. Second, we address the effector detection problem by the maximum likelihood estimation (MLE) approach. We prove that the optimal MLE can be obtained in polynomial time for connected directed acyclic graphs. For general graphs, we first extract a directed acyclic subgraph that can well preserve the information in the original graph and then apply the MLE approach to the extracted subgraph to obtain the effectors. The effectiveness of our algorithms is experimentally verified via simulations on the real-world social network.

Many distributed systems use a client-server model in which client assignment strategy plays an important role on the system performance. People use two criteria to evaluate server loads-1) total load and 2) load balance. The total load increases when the load balance decreases, and vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design algorithms based on semidefinite programming. We study the identical server case and general server case, present two algorithms (BSP and ABSP), and analyze these algorithms' bounds. In simulation, we evaluate that our client assignement strategies give the satisfiable total load and load balancing using reasonable time compared to the state-of-the-art, thus proving the effectiveness of our algorithms.

Energy efficiency is an important issue in the study of wireless sensor networks. Given a set of targets and a set of sensors with bounded lifetime, the maximum lifetime k-coverage problem is to schedule active/sleeping status of sensors to maximize the time period during which every target is covered by at least k active sensors. Previously, it was known that when the sensing ranges are uniform, this problem has a polynomial time (4+ε)-approximation for k = 1 and (6+ε)-approximation for k = 2. In this paper, we make significant progress by showing that for any positive integer k, there exists a polynomial-time (3 + ε)-approximation.

Mobile hotspots have made the dream of ubiquitous Internet access come true, while the widespread applications are still hindered by the limited power of smart phones. To address this issue, we propose a novel distributed cooperative data transmission scheme for energy-rechargeable mobile devices. In particular, we not only let a mobile phone help the nearby client devices connect to the Internet via its cellular accessing, but also let those clients replenish the mobile hotspot energy via wireless power transfer. We mathematically formulate the mutually beneficial relationship between mobile hotspots and clients into an optimization problem, with the objective of conducting the cooperative wireless data and energy transmission to maximize the system utility. Resorting to methods from combinatorics and matching theory, we develop a near optimal solution for many-to-one matching when there is a single mobile hotspot and a distributed matching strategy for the general case by considering the nature of data communication and the characteristic of wireless power transfer. By extensive simulation, we show that the proposed distributed solution achieves a performance close to the centralized method, and it outperforms the greedy matching strategy and the classic Gale-Shapley matching strategy in different scenarios.

Energy efficiency is an important issue in the study of wireless sensor networks. Given a homogeneous set of sensors with unit lifetime and a set of target points, find an active/sleeping schedule for sensors to maximize the lifetime of k-coverage, i.e., the time period during which every target point is covered by at least k active sensors. This is a well known problem in wireless sensor networks concerning with energy efficiency. When k = 1, it is called the maximum lifetime coverage problem which has been proved to have a polynomial-time (4 + ε)-approximation. When k ≥ 2, it is the maximum lifetime fault-tolerant coverage problem. Previous to this work, only in the case k = 2, a polynomial-time (6 + ε)-approximation is found. In this paper, we will make a significant progress by showing that for any positive integer k, there exists a polynomial-time (4 + ε)-approximation, and for k = 1,2, the performance ratio can be improved to (3 + ε).

Effectiveness of MapReduce as a big data processing framework depends on efficiencies of scale for both map and reduce phases. While most map tasks are preemptive and parallelizable, the reduce tasks typically are not easily decomposed and often become a bottleneck due to constraints of data locality and task complexity. By assuming that reduce tasks are non-parallelizable, we study offline scheduling of minimizing makespan and minimizing total completion time, respectively. Both preemptive and non-preemptive reduce tasks are considered. On makespan minimization, for preemptive version we design an algorithm and prove its optimality, for non-preemptive version we design an approximation algorithm with the worst ratio of 3/2-1/2h where h is the number of machines. On total complete time minimization, for non-preemptive version we devise an approximation algorithm with worst case ratio of 2-1/h, and for preemptive version we devise a heuristic. We confirm that our algorithms outperform state-of-art schedulers through experiments.

One type of distributed systems is the client/server system consist of clients and servers. In order to improve the performance of such a system, client assignment strategy plays an important role. There are two criteria to evaluate the load on the servers - total load and load balance. The total load increases when the load balance decreases, vice versa. It has been proved that finding the best client assignment is NP-hard. In this paper, we propose a new model for the client assignment problem and design an algorithm based on Semidefinite programming (SDP). Our method has a (relaxed) performance ratio 0.87 when only 2 servers exist. In general case, our method becomes a heuristic, and the ratio of each iteration is 0.87. We are the first one to give these bounds. Our simulation results are compared with the state-of-art client assignment method, and our strategy outperforms it in terms of running time while keeps the load in similar level.

Social network is emerging as an inter-discipline and stepping deep into various fields from theoretical research and solutions of practical issues with an expanding trend, especially within the recent years. Undoubtedly, one of the reasons attributes to the large-scale body users gathering in the context of social networks through information-posting and knowledge-sharing, so that massive social networking datasets are generated, which make possible that researchers can utilize the datasets mined to model social community structure, further detect patterns, trends and rules using corresponding techniques. This survey provides an overview of popular fields (e.g., Viral marketing, influence propagation and social websites) for social network, moreover, introduces representative references, in which the well-known analytical methods and techniques (e.g., Graph theory, data mining techniques and analysis of social network) are briefly described.

Wireless data broadcast is an efficient way to disseminate data to a large number of users in mobile communication environments. In many applications, such as stock quotes, flight schedules and traffic news, the users may want to download multiple data items at one time and the applications may require the support of multi-channel architectures. This paper studies the problem of retrieving a set of data items from multiple wireless broadcasting channels such that all the requested data items can be downloaded with the least access time, namely Least Time Data Retrieval (LTDR). On one hand, we find that it is NP-hard to approximate this problem to within any non-trivial factor even if there are only two channels. On the other hand, we find that there exists a polynomial time (1+1/1-α)-approximation solution for an LTDR instance L if the optimal solution of L requirers τ time slots and (1-α)kT ≤ τ ≤ kT, where k is a positive integer, α is an arbitrary constant between 0 and 1, and T is the least common multiple of cycle lengths for all channels. We also derive a lower bound of polynomial time approximation for L matching that upper bound under the well known assumption P ≠ NP. To improve the practical efficiency of the approximation solution, a heuristic is exhibited and tested by simulations.

Due to technological advances in micro-electronics, digital electronics, and wireless data communications, we have witnessed the advent of Wireless Sensor Networks (WSNs) and related applications in many areas such as battlefield surveillance, environmental monitoring, and biomedical observation. In this paper, we investigate the Maximum Directional Target Coverage Problem (MDTCP) for a special group of wireless sensor networks in which each sensor has a specific coverage range and a limited coverage angle. Given a set of sensors and a set of target points in a finite area, the objective of MDTCP is to cover the maximum number of target points by adjusting the directions of sensors. We develop a polynomial time approximation algorithm with performance ratio 1-e/e for MDTCP. In addition, we also analyze the structure of MDTCP from the Combinatorics' point of view.

Describing the behavior of information dissemination in online social networks is propitious to understanding the transmission process of real users in the online social networking site. In this paper, we proposed a cellular automaton model to deal with the propagation characteristics of online social networks rumors spread. Experimental simulation was carried out under periodic boundary constraints in the process of rumor spread. The result showed that the cellular automaton model is indeed able to characterize the propagation behavior on online social networks. We also prescribed the immunization strategy to suppress the rumor spreading.

This paper investigates the problem of computing the optimal trajectories of multiple data MULEs (e.g., robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks. By relying on a slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood ( k-TSPN) and the k-rooted path cover problem with neighborhood ( k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them along with two simpler heuristic algorithms. We also conduct simulations to compare the performance of the proposed approaches with the existing alternatives. Our simulation results indicate that the proposed algorithms outperform the competitors on average.

Wireless data broadcast is a popular data dissemination method in mobile computing environments because of its capability of concurrently disseminating data to multiple users. In this paper, we study the data retrieval scheduling problem for multi-item requests in multi-channel broadcast environments. To maximize the number of downloads given a deadline, we define a problem called largest number data retrieval (LNDR). We prove the decision problem of LNDR is NP-hard, and we investigate approximation algorithm for it. We also define another problem called minimum cost data retrieval (MCDR), which aims at downloading a set of requested data items with the least response time and energy consumption. We prove MCDR is NP-hard to approximate to within any non-trivial factor. Therefore, we investigate heuristic algorithm for it. Finally we provide simulation results to demonstrate the practical efficiency of the proposed algorithms.

In many real-world scenarios, social network serves as a platform for information diffusion, alongside with positive information (truth) dissemination, negative information (rumor) also spread among the public. To make the social network as a reliable medium, it is necessary to have strategies to control rumor diffusion. In this article, we address the Least Cost Rumor Blocking (LCRB) problem where rumors originate from a community Cr in the network and a notion of protectors are used to limit the bad influence of rumors. The problem can be summarized as identifying a minimal subset of individuals as initial protectors to minimize the number of people infected in neighbor communities of Cr at the end of both diffusion processes. Observing the community structure property, we pay attention to a kind of vertex set, called bridge end set, in which each node has at least one direct in-neighbor in Cr and is reachable from rumors. Under the OOAO model, we study LCRB-P problem, in which α (0 < 1) fraction of bridge ends are required to be protected. We prove that the objective function of this problem is submodular and a greedy algorithm is adopted to derive a (1 -- 1/e)-approximation. Furthermore, we study LCRB-D problem over the DOAA model, in which all the bridge ends are required to be protected, we prove that there is no polynomial time o(ln n)-approximation for the LCRB-D problem unless P = NP, and propose a Set Cover Based Greedy (SCBG) algorithm which achieves a O(ln n)-approximation ratio. Finally, to evaluate the efficiency and effectiveness of our algorithm, we conduct extensive comparison simulations in three real-world datasets, and the results show that our algorithm outperforms other heuristics.

Social influence has been widely studied in areas of viral marketing, information diffusion and health care. Currently, most influence models only deal with a single influence without the interference of other influences. Also, the influence spreading in previous models must be triggered by individuals who have been activated by the influence. In this paper, we argue that it is the attraction from a specific influence makes an individual choose to spread it among multiple influences. Inspired by charged system theory in physics, a new influence model is proposed, considering individual features and social structure features. It also gives a natural description about how individuals make decisions among multiple influences. Then a novel algorithm based on this model is provided to predict human behavior. Extensive experiments on three real-world datasets demonstrate that our model and algorithm statistically outperform the state-of-the-art methods in terms of prediction accuracy.

Influence maximization problem is to find a set of seeds in social networks such that the cascade influence is maximized. Traditional models assume all nodes are willing to spread the influence once they are influenced, and they ignore the disparity between influence and profit of a product. In this paper by considering the role that price plays in viral marketing, we propose price related (PR) frame that contains PR-I and PR-L models for classic IC and LT models respectively, which is a pioneer work. We find that influence and profit are like two sides of the coin, high price hinders the influence propagation and to enlarge the influence some sacrifice on profit is inevitable. We propose Balanced Influence and Profit (BIP) maximization problem. We prove the NP-hardness of BIP maximization under PR-I and PR-L model. Unlike influence maximization, the BIP objective function is not monotone. Despite the non-monotony, we show BIP objective function is sub modular under certain conditions. Two unbudgeted greedy algorithms separately are devised. We conduct simulations on real-world datasets and evaluate the superiority of our algorithms over existing ones.

Given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r ln n) where r is the link radius of the sensor network and n is the number of sensors. In this paper, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1 - ε, producing an approximation solution with performance ratio O(log3n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

In this paper we present a middleware named SmartPrint to provide cloud print service in office, where many heterogeneous networks exist. The goal of the system is to shield the communication heterogeneity of the devices in the office and make authorized users freely connect to all the printers with no modification on their terminals. SmartPrint can manages all the printers in an office building, and it provides friendly service for the users who know nothing about the printers. SmartPrint can also automatically choose printers for the office staffs. We propose and implement two printer allocation methods, one aims to improve the experience of the user with short print job, and the other is a multiple attributes decision algorithm which considers all factors including spatial information that impact the user experiences. Through experiments we validate the methods, and prove that SmartPrint achieves high user satisfaction from collected real data.

As the wireless technology overwhelmingly occupies the consumer electronics market, the booming demands of the mobile users are largely unaccommodated. Thus wireless data broadcasting systems gain increasing attentions recently. Two wellknown metrics for evaluating wireless data broadcasting systems are Access Latency and Tuning Time. In order to reduce these two factors, many existing techniques have to make a tradeoff between the power consumption and the quality of services. In this paper, an energy-efficient Hybrid Asynchronous Multiple Hashing scheme named HAMHash for multi-channel broadcasting systems was proposed, which deals with variable data size and non-flat distribution of queries in multi-channel circumstance. Furthermore, algorithms of data allocation and retrieval for skewed broadcast are presented. Quantitative theoretical and experimental analysis of the system performance verifies the effectiveness of our scheme.

Wireless data broadcast is an efficient way of disseminating data to users in the mobile computing environments. From the server's point of view, how to place the data items on channels is a crucial issue, with the objective of minimizing the average access time and tuning time. Similarly, how to schedule the data retrieval process for a given request at the client side such that all the requested items can be downloaded in a short time is also an important problem. In this paper, we investigate the multi-item data retrieval scheduling in the push-based multichannel broadcast environments. We prove the decision version of this problem is NP-complete, and we devise an algebraic algorithm to search for the best solution. We also develop a heuristic that can employ the algebraic algorithm to download a large number of items efficiently. When there is no replicated item in a broadcast cycle, we show that an optimal retrieval schedule can be obtained in polynomial time. The performances of proposed algorithms are analyzed theoretically and evaluated through simulation. The experimental results show that our algorithms can significantly reduce the access time for multi-item requests.

In this paper, we study the problem of computing quality fault-tolerant virtual backbone in homogeneous wireless network, which is defined as the$k$-connected$m$-dominating set problem in a unit disk graph. This problem is NP-hard, and thus many efforts have been made to find a constant factor approximation algorithm for it, but never succeeded so far with arbitrary$k\geq 3$and$m\geq 1$pair. We propose a new strategy for computing a smaller-size 3-connected$m$-dominating set in a unit disk graph with any$m\geq 1$. We show the approximation ratio of our algorithm is constant and its running time is polynomial. We also conduct a simulation to examine the average performance of our algorithm. Our result implies that while there exists a constant factor approximation algorithm for the$k$-connected$m$-dominating set problem with arbitrary$k\leq 3$and$m\geq 1$pair, the$k$-connected$m$-dominating set problem is still open with$k>3$.

Inspired by the backbone concept in wired networks, virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). Virtual backbone construction based on Connected Dominating Set (CDS) is a competitive approach among the existing methods used to establish virtual backbone in WSNs. Traditionally, CDS size was the only factor considered in the CDS-based approach. The motivation was that smaller CDS leads to simplified network maintenance. However, routing cost in terms of routing path length is also an important factor for virtual backbone construction. In our research, both of these two factors are taken into account. Specifically, we attempt to devise a polynomial-time constant-approximation algorithm that leads to a CDS with bounded CDS size and guaranteed routing cost. We prove that, under general graph model, there is no polynomial-time constant-approximation algorithm unless P = NP. Under Unit Disk Graph (UDG) model, we propose an innovative polynomial-time constant-approximation algorithm, GOC-MCDS-C, that produces a CDS D whose size I D is within a constant factor from that of the minimum CDS. In addition, for each node pair u and v, there exists a routing path with all intermediate nodes in D and path length at most 7 · d(u, v), where d(u, v) is the length of the shortest path between u and v. Our theoretical analysis and simulation results show that the distributed version of the proposed algorithm, GOC-MCDS-D, outperforms the existing approaches.

MultiMedia DataBase Management System (MMDBMS) becomes more popular in recent years, which supports complex and large multimedia data like images, audios, and videos etc. Data Broadcasting is an attractive approach for data dissemination to improve the limitations in mobile environment, such as narrow bandwidth, unreliable connections, and battery limitation. However, existing data broadcast schemes are inefficient for MMDBMS. In this paper, we present four novel multimedia data broadcast schemes (namely, SDAA, MDAA, AEA, and COA) specifically for wireless multichannel communications. The major strategies are scalable coding to generate data segments to different qualities, indexing and channel assignment to minimize the expected waiting time for clients. We prove theoretically that SDAA is a 2-approximation. COA performs best when we release the constraints and it can be judged as an theoretical lower bound, while AEA outputs local optimal solution with quality allocation constraints. Finally, SDAA+AEA form a best scheduling for practical applications. We also provide numerical experiments to evaluate the system performance, proving the efficiency of our schemes.

When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ∈)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4 + ξ)-approximation algorithm for MLCP, where ∈ >; 0, ξ >; 0.

This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e.g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the k-rooted path cover problem with neighborhood (k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate our algorithms outperform their alternatives.

Wireless data broadcast is an efficient technique of disseminating data simultaneously to a large number of mobile clients. In many information services, the users may query multiple data items at a time. In this paper, we study the data retrieval scheduling problem from the client's point of view. We formally define the Largest Number Data Retrieval (LNDR) problem with the objective of downloading the largest number of requested data items in a given time duration, and the Minimum Cost Data Retrieval (MCDR) problem which aims at downloading a set of data items with the minimum energy consumption. When the time needed for channel switching can be ignored, a Maximum Matching optimal algorithm is exhibited for LNDR which requires only polynomial time; when the switching time cannot be neglected, LNDR is proven to be NP-hard and a greedy algorithm with constant approximation ratio is developed. We also prove that the MCDR problem is NP-hard to be approximated within to any nontrivial factor and a parameterized heuristic is devised to solve MCDR non-optimally.

Directional antennas can divide the transmission range into several sectors. Thus, through switching off sectors in unnecessary directions in wireless networks, we can save bandwidth and energy consumption. In this paper, we will study a directional virtual backbone (VB) in the network where directional antennas are used. When constructing a VB, we will take routing and broadcasting into account since they are two common operations in wireless networks. Hence, we will study a VB with guaranteed routing costs, named α Minimum rOuting Cost Directional VB (α-MOC-DVB). Besides the properties of regular VBs, α-MOC-DVB also has a special constraint - for any pair of nodes, there exists at least one path all intermediate directions on which must belong to α-MOC-DVB and the number of intermediate directions on the path is smaller than α times that on the shortest path. We prove that construction of a minimum α-MOC-DVB is an NP-hard problem in a general directed graph. A heuristic algorithm is proposed and theoretical analysis is also discussed in the paper. Extensive simulations demonstrate that our α-MOC-DVB is much more efficient in the sense of VB size and routing costs compared to other VBs.

In this paper, we studied the minimum latency conflict-free many-to-one data aggregation scheduling problem in multi-channel multi-hop wireless sensor networks: Given locations of all sensors and a base station, some sensors which are called as sources, find a schedule such that data from all sources can be transmitted to the base station without any conflict and the latency is minimized. In this model, each sensor has three parameters which are transmission range r, interference range ar and carrier sensing range βr where α, and β are constant. There are λ ≥ 1 available channels for communications. We designed an approximation algorithm with ratio (⌈a/λ⌉ + 11 ⌈b/λ⌉) This work improves our previous work when λ = 1. Extensive simulations valuate the performance of the algorithm.

It is well-known that the application of directional antennas can help conserve bandwidth and energy consumption in wireless networks. Thus, to achieve efficiency in wireless networks, we study a special virtual backbone (VB) using directional antennas, requiring that from one node to any other node in the network, there exists at least one directional shortest path all of whose intermediate directions should belong to the VB, named as Minimum rOuting Cost Directional VB (MOC-DVB). In addition, VB has been well studied in Unit Disk Graph (UDG). However, radio wave based communications in wireless networks may be interrupted by obstacles (e.g., buildings and mountains). Thus, in this paper, we model a network as a general directed graph. We prove that construction of a minimum MOC-DVB is an NP-hard problem in a general directed graph and in term of the size of MOC-DVB, there exists an unreachable lower bound of the polynomial-time selected MOC-DVB. Therefore, we propose a distributed approximation algorithm for constructing MOC-DVB with approximation ratio of 1 + ln K + 2ln δD, where K is the number of antennas on each node and δDis the maximum direction degree in the network. Extensive simulations demonstrate that our constructed MOC-DVB is much more efficient in the sense of MOC-DVB size and routing cost compared to other VBs.

In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size |D| is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

In this paper, we propose a new multiple-sink positioning problem in wireless sensor networks to best support real-time applications. We formally define this problem as thek-Sink Placement Problem (k-SPP) and prove that it is APX-complete. We show that an existing approximation algorithm for the well-knownk-center problem is a constant factor approximation ofk-SPP. Furthermore, we introduce a new greedy algorithm fork-SPP and prove its approximation ratio is very near to the best achievable, 2. Via simulations, we show our algorithm outperforms its competitor on average.

Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named \alpha Minimum rOuting Cost CDS (\alpha-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum \alpha-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of \alpha-MOC-CDS.

In this paper, we will study a special Connected Dominating Set (CDS) problem - between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in a special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. Thus, energy consumption and delivery delay can be reduced greatly. CDS has been studied extensively in Unit Disk Graph (UDG) or Disk Graph (DG). However, nodes in networks may have different transmission ranges and some communications may be obstructed by obstacles. Therefore, we model network as a bidirectional general graph in this paper. We prove that constructing a minimum MOC-CDS in general graph is NPhard. We also prove that there does not exist a polynomial-time approximation algorithm for constructing a minimum MOCCDS with performance ratio plnδ, where p is an arbitrary positive number (p <; 1) and δ is the maximum node degree in network. We propose a distributed heuristic algorithm (called as FlagContest) for constructing MOC-CDS with performance ratio (1 - ln2) + 2lnδ. Through extensive simulations, we show that the results of FlagContest is within the upper bound proved in this paper. Simulations also demonstrate that the average length of routing paths through MOC-CDS reduces greatly compared to regular CDSs.

In this paper, we study the problem of constructing quality fault-tolerant Connected Dominating Sets (CDSs)in homogeneous wireless networks, which can be defined as minimum k-Connected m-Dominating Set ((k,m)-CDS) problem in Unit Disk Graphs (UDGs). We found that every existing approximation algorithm for this problem is incomplete for k ¿3 in a sense that it does not generate a feasible solution in some UDGs. Based on these observations, we propose a new polynomial time approximation algorithm for computing (3,m)-CDSs. We also show that our algorithm is correct and its approximation ratio is a constant.

A Virtual Backbone (VB) of a wireless network is a subset of nodes such that only VB nodes are responsible for routing-related tasks. Since a smaller VB causes less overhead, size is the primary quality factor of VB. Frequently, Unit Disk Graphs (UDGs) are used to model 2D homogeneous wireless networks, and the problem of finding minimum VBs in the networks is abstracted as Minimum Connected Dominating Set (MCDS) problem in UDGs. In some applications, the altitude of nodes can be hugely different and UDG cannot abstract the networks accurately. Then, Unit Ball Graph (UBG) can replace UDG. In this paper, we study how to construct quality CDSs in UBGs in distributed environments. We first give an improved upper bound of the number of independent nodes in a UBG, and use this result to analyze the Performance Ratio (PR) of our new centralized algorithm C-CDS-UBG, which computes CDSs in UBGs. Next, we propose a distributed algorithm D-CDS-UBG originated from C-CDS-UBG and analyze its message and time complexities. Our theoretical analysis shows that the PR of D-CDS-UBG is 14.937, which is better than current best, 22. Our simulations also show that D-CDS-UBG outperforms the competitor, on average.

In this study, we formalize a multi-focal learning problem, where training data are partitioned into several different focal groups and the prediction model will be learned within each focal group. The multi-focal learning problem is motivated by numerous real-world learning applications. For instance, for the same type of problems encountered in a customer service center, the problem descriptions from different customers can be quite different. The experienced customers usually give more precise and focused descriptions about the problem. In contrast, the inexperienced customers usually provide more diverse descriptions. In this case, the examples from the same class in the training data can be naturally in different focal groups. As a result, it is necessary to identify those natural focal groups and exploit them for learning at different focuses. The key developmental challenge is how to identify those focal groups in the training data. As a case study, we exploit multi-focal learning for profiling problems in customer service centers. The results show that multifocal learning can significantly boost the learning accuracies of existing learning algorithms, such as Support Vector Machines (SVMs), for classifying customer problems.

In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With majority voting protocol, a location is survived for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.

Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a "trade-off" scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in [2].

Unlike a cellular or wired network, there is no base station or network infrastructure in a wireless ad-hoc network, in which nodes communicate with each other via peer communications. In order to make routing and flooding efficient in such an infrastructureless network, Connected Dominating Set (CDS) as a virtual backbone has been extensively studied. Most of the existing studies on the CDS problem have focused on unit disk graphs, where every node in a network has the same transmission range. However, nodes may have different powers due to difference in functionalities, power control, topology control, and so on. In this case, it is desirable to model such a network as a disk graph where each node has different transmission range. In this paper, we define Minimum Strongly Connected Dominating and Absorbent Set (MSCDAS) in a disk graph, which is the counterpart of minimum CDS in unit disk graph. We propose a constant approximation algorithm when the ratio of the maximum to the minimum in transmission range is bounded. We also present two heuristics and compare the performances of the proposed schemes through simulation.

This paper targets the identification of outlying sensors (that is, outlying reading sensors) and the detection of the reach of events in sensor networks. Typical applications include the detection of the transportation front line of some vegetation or animalcule's growth over a certain geographical region. We propose and analyze two novel algorithms for outlying sensor identification and event boundary detection. These algorithms are purely localized and, thus, scale well to large sensor networks. Their computational overhead is low, since only simple numerical operations are involved. Simulation results indicate that these algorithms can clearly detect the event boundary and can identify outlying sensors with a high accuracy and a low false alarm rate when as many as 20 percent sensors report outlying readings. Our work is exploratory in that the proposed algorithms can accept any kind of scalar values as inputs-a dramatic improvement over existing work, which takes only 0/1 decision predicates. Therefore, our algorithms are generic. They can be applied as long as "events" can be modeled by numerical numbers. Though designed for sensor networks, our algorithms can be applied to the outlier detection and regional data analysis in spatial data mining.

Recent research in sensor networks highlights the low-power mode operation of sensor networks. In wireless sensor networks, network lifetime can be extended by organizing sensors into mutually exclusive subsets and alternatively activating each subset. Coverage breach occurs when a subset fails to cover all the targets. In bandwidth-constrained sensor networks, coverage breach is more likely to happen because when active sensors periodically send data to the base station, contention for channel access must be considered. Channel bandwidth imposes a limit on the cardinality of each subset. To make efficient use of both energy and bandwidth with minimum coverage breach requires optimal arrangement of sensor nodes. This article addresses three coverage breach problems related to the low-power operation of wireless sensor networks where channel bandwidth is limited. The three coverage breach problems are formulated using integer linear programming models. A greedy approximation algorithm and a heuristic based on the LP-relaxation method are proposed. Effects of changing different network resources on sensor network coverage are studied through simulations. One consistent result is that when the number of sensors increases, network lifetime can be improved without loss of network coverage only if there is no bandwidth constraint; with bandwidth constraints, network lifetime may be improved further at the cost of coverage breach.

Data compression is an effective technique to improve the performance of data warehouses. Since cube operation represents the core of online analytical processing in data warehouses, it is a major challenge to develop efficient algorithms for computing cube on compressed data warehouses. To our knowledge, very few cube computation techniques have been proposed for compressed data warehouses to date in the literature. This paper presents a novel algorithm to compute cubes on compressed data warehouses. The algorithm operates directly on compressed data sets without the need of first decompressing them. The algorithm is applicable to a large class of mapping complete data compression methods. The complexity of the algorithm is analyzed in detail. The analytical and experimental results show that the algorithm is more efficient than all other existing cube algorithms. In addition, a heuristic algorithm to generate an optimal plan for computing cube is also proposed.

Abstract This paper addresses the problem of broadcasting and multicasting in large scale multihopad hocwireless networks. We focus on the energy‐efficient broadcast routing in stationary networks and consider the case where wireless nodes can dynamically control their transmission power for each broadcast session. Minimum spanning tree (MST) has the property that the longest edge in the tree is the shortest among all the spanning trees. We introduce a new algorithm called minimum longest edge (MLE) that constructs a broadcast tree based on MST, and for networks where nodes have different energy reserves, we introduce minimum weight incremental arborescence (MWIA) algorithm to compute the broadcast tree. Multicast tree can be obtained by pruning broadcast tree. These algorithms provide a scheme to balance the energy consumption among all nodes. The simulation results show that MLE and MWIA improved the energy balance and network lifetime for a wide range of networks, and the improvement is more significant when the network size grows. Copyright © 2006 John Wiley & Sons, Ltd.

A critical aspect of applications with wireless sensor networks is network lifetime. Power-constrained wireless sensor networks are usable as long as they can communicate sensed data to a processing node. Sensing and communications consume energy, therefore judicious power management and sensor scheduling can effectively extend network lifetime. To cover a set of targets with known locations when ground access in the remote area is prohibited, one solution is to deploy the sensors remotely, from an aircraft. The lack of precise sensor placement is compensated by a large sensor population deployed in the drop zone, that would improve the probability of target coverage. The data collected from the sensors is sent to a central node (e.g. cluster head) for processing. In this paper we propose un efficient method to extend the sensor network life time by organizing the sensors into a maximal number of set covers that are activated successively. Only the sensors from the current active set are responsible for monitoring all targets and for transmitting the collected data, while all other nodes are in a low-energy sleep mode. By allowing sensors to participate in multiple sets, our problem formulation increases the network lifetime compared with related work [M. Cardei et al], that has the additional requirements of sensor sets being disjoint and operating equal time intervals. In this paper we model the solution as the maximum set covers problem and design two heuristics that efficiently compute the sets, using linear programming and a greedy approach. Simulation results are presented to verify our approaches.

This paper addresses the coverage breach problem in wireless sensor networks with limited bandwidths. In wireless sensor networks, sensor nodes are powered by batteries. To make efficient use of battery energy is critical to sensor network lifetimes. When targets are redundantly covered by multiple sensors, especially in stochastically deployed sensor networks, it is possible to save battery energy by organizing sensors into mutually exclusive subsets and alternatively activating only one subset at any time. Active nodes are responsible for sensing, computing and communicating. While the coverage of each subset is an important metric for sensor organization, the size of each subset also plays an important role in sensor network performance because when active sensors periodically send data to base stations, contention for channel access must be considered. The number of available channels imposes a limit on the cardinality of each subset. Coverage breach happens when a subset of sensors cannot completely cover all the targets. To make efficient use of both energy and bandwidth with a minimum coverage breach is the goal of sensor network design. This paper presents the minimum breach problem using a mathematical model, studies the computational complexity of the problem, and provides two approximate heuristics. Effects of increasing the number of channels and increasing the number of sensors on sensor network coverage are studied through numerical simulations. Overall, the simulation results reveal that when the number of sensors increases, network lifetimes can be improved without loss of network coverage if there is no bandwidth constraint; with bandwidth constraints, network lifetimes may be improved further at the cost of coverage breach.

A hyperclique pattern [H. Xiong et al. (2003)] is a new type of association pattern that contains items which are highly affiliated with each other. More specifically, the presence of an item in one transaction strongly implies the presence of every other item that belongs to the same hyperclique pattern. We present a new algorithm for mining maximal hyperclique patterns, which are desirable for pattern-based clustering methods [H. Xiong et al. (2004)]. This algorithm exploits key advantages of both the depth first search (DFS) strategy and the breadth first search (BFS) strategy. Indeed, we adapt the equivalence pruning method, one of the most efficient pruning methods of the DFS strategy, into the process of the BFS strategy. As demonstrated by our experimental results, the performance of our algorithm can be orders of magnitude faster than standard maximal frequent pattern mining algorithms, particularly at low levels of support.

This paper investigates the optimal placement of proxies of a Web server on the Internet, with the consideration of both read and update operations to the data on the Web server. We first study the problem of optimal placement of $k$ proxies in a system to minimize the total access cost to the Web server. Then, for an unknown number of proxies, we find the optimal number of proxies required in the system. The problems are formulated by using the dynamic programming method and the optimal solutions are obtained. Simulations have been conducted to evaluate the performance of the proposed algorithms and to demonstrate how the effectiveness of proxy placement is affected by various factors, such as network traffic load, number of proxies, read–write ratio and proxy hit ratio.

Abstract A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum‐connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum‐connected dominating set in unit‐disk graphs. In this paper, we design a (1 + 1/s)‐approximation for the minimum‐connected dominating set in unit‐disk graphs, running in timenO((slogs)2). © 2003 Wiley Periodicals, Inc.

Modeling spatial context (e.g., autocorrelation) is a key challenge in classification problems that arise in geospatial domains. Markov random fields (MRF) is a popular model for incorporating spatial context into image segmentation and land-use classification problems. The spatial autoregression (SAR) model, which is an extension of the classical regression model for incorporating spatial dependence, is popular for prediction and classification of spatial data in regional economics, natural resources, and ecological studies. There is little literature comparing these alternative approaches to facilitate the exchange of ideas. We argue that the SAR model makes more restrictive assumptions about the distribution of feature values and class boundaries than MRF. The relationship between SAR and MRF is analogous to the relationship between regression and Bayesian classifiers. This paper provides comparisons between the two models using a probabilistic and an experimental framework.

1 Introduction Widespread use of spatial databases[24] is leading to an increasing interest in mining interesting and useful but implicit spatial patterns[14, 17, 10, 22]. Efficient tools for extracting information from geo-spatial data, the focus of this work, are crucial to organizations which make decisions based on large spatial data sets. These organizations are spread across many domains including ecology and environment management, public safety, transportation, public health, business, travel and tourism[2, 12].