Community-based rumor blocking maximization in social networks: Algorithms and analysis.

Social networks provide us a convenient platform to communicate and share information or ideas with each other, but it also causes many negative effects at the same time, such as, the spread of misinformation or rumor in social networks may cause public panic and even serious economic or political crisis. In this paper, we propose a Community-based Rumor Blocking Problem (CRBMP), i.e., selecting a set of seed users from all communities as protectors with the constraint of budget b such that the expected number of users eventually not being influenced by rumor sources is maximized. We consider the community structure in social networks and solve our problem in two stages, in the first stage, we allocate budget b for all the communities, this sub-problem whose objective function is proved to be monotone and DR-submodular, so we can use the method of submodular function maximization on an integer lattice, which is different from most of the existing work with the submodular function over a set function. Then a greedy community budget allocation algorithm is devised to get an 1 - 1 / e approximation ratio; we also propose a speed-up greedy algorithm which greatly reduces the time complexity for the community budget allocation and can get an 1 - 1 / e - ϵ approximation guarantee meanwhile. Next we solve the Protector Seed Selection (PSS) problem in the second stage after we obtained the budget allocation vector for communities, we greedily choose protectors for each community with the budget constraints to achieve the maximization of the influence of protectors. The greedy algorithm for PSS problem can achieve a 1/2 approximation guarantee. We also consider a special case where the rumor just originates from one community and does not spread out of its own community before the protectors are selected, the proposed algorithm can reduce the computational cost than the general greedy algorithm since we remove the uninfected communities. Finally, we conduct extensive experiments on three real world data sets, the results demonstrate the effectiveness of the proposed algorithm and its superiority over other methods.

EDDA: An Efficient Distributed Data Replication Algorithm in VANETs.

Efficient data dissemination in vehicular ad hoc networks (VANETs) is a challenging issue due to the dynamic nature of the network. To improve the performance of data dissemination, we study distributed data replication algorithms in VANETs for exchanging information and computing in an arbitrarily-connected network of vehicle nodes. To achieve low dissemination delay and improve the network performance, we control the number of message copies that can be disseminated in the network and then propose an efficient distributed data replication algorithm (EDDA). The key idea is to let the data carrier distribute the data dissemination tasks to multiple nodes to speed up the dissemination process. We calculate the number of communication stages for the network to enter into a balanced status and show that the proposed distributed algorithm can converge to a consensus in a small number of communication stages. Most of the theoretical results described in this paper are to study the complexity of network convergence. The lower bound and upper bound are also provided in the analysis of the algorithm. Simulation results show that the proposed EDDA can efficiently disseminate messages to vehicles in a specific area with low dissemination delay and system overhead.

BCDP: Budget constrained and delay-bounded placement for hybrid roadside units in vehicular ad hoc networks.

In vehicular ad hoc networks, roadside units (RSUs) placement has been proposed to improve the the overall network performance in many ITS applications. This paper addresses the budget constrained and delay-bounded placement problem (BCDP) for roadside units in vehicular ad hoc networks. There are two types of RSUs: cable connected RSU (c-RSU) and wireless RSU (w-RSU). c-RSUs are interconnected through wired lines, and they form the backbone of VANETs, while w-RSUs connect to other RSUs through wireless communication and serve as an economical extension of the coverage of c-RSUs. The delay-bounded coverage range and deployment cost of these two cases are totally different. We are given a budget constraint and a delay bound, the problem is how to find the optimal candidate sites with the maximal delay-bounded coverage to place RSUs such that a message from any c-RSU in the region can be disseminated to the more vehicles within the given budget constraint and delay bound. We first prove that the BCDP problem is NP-hard. Then we propose several algorithms to solve the BCDP problem. Simulation results show the heuristic algorithms can significantly improve the coverage range and reduce the total deployment cost, compared with other heuristic methods.