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.
In a wireless sensor network, the virtual backbone plays an important role. Due to accidental damage or energy depletion, it is desirable that the virtual backbone is fault-tolerant. A fault-tolerant ...virtual backbone can be modeled as a k-connected m-fold dominating set ((k, m)-CDS for short). In this paper, we present a constant approximation algorithm for the minimum weight (k, m)-CDS problem in unit disk graphs under the assumption that k and m are two fixed constants with m ≥ k. Prior to this paper, constant approximation algorithms are known for k = 1 with weight and 2 ≤ k ≤ 3 without weight. Our result is the first constant approximation algorithm for the (k, m)-CDS problem with general k, m and with weight. The performance ratio is (α+5ρ) fork ≥ 3 and (α+2.5ρ) for k = 2, where α is the performance ratio for the minimum weight m-fold dominating set problem and ρ is the performance ratio for the subset k-connected subgraph problem (both problems are known to have constant performance ratios).
Barrier Coverage plays a vital role in wireless sensor networks. Research on barrier coverage has mainly focused on the lifetime maximization and the critical conditions to achieve <inline-formula> ...<tex-math notation="LaTeX">k </tex-math></inline-formula>-Barrier Coverage under various sensing models. When sensors are randomly deployed along the boundary of an area of interest, they may form several disjoint barrier covers. To maximize the lifetime of barrier coverage, those barrier covers need to be scheduled to avoid a security problem, call breach . In a heterogeneous wireless sensor network, given a set of barrier-covers each with a lifetime, we study the problem of finding a lifetime-maximizing subset with a breach-free sleep-wakeup scheduling. We first prove that it can be judged in polynomial time whether a given sleep-wakeup schedule is breach-free or not, but given a set of barrier-covers, it is NP-Complete to determine whether there exists a breach-free schedule. Then, we show that the problem of finding a lifetime-maximizing breach-free schedule is equivalent to the maximum node weighted path problem in a directed graph, and design a parameterized algorithm. Experimental results show that our algorithm significantly outperforms the heuristics proposed in the literature.
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.
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.
Admittedly, innovations can spread rapidly in online social networks, while the spread of malicious rumors can lead to a series of negative consequences. Therefore, it is necessary to take effective ...measures to limit the influence of negative information. In reality, people will become an adopter of innovations after being influenced by their friends. Meanwhile, they can be more likely to become a follower if they have received relevant information in advance. Motivated by these observations, we study the rumor correction maximization problem using both seed and boost nodes. We first focus on the boost nodes and propose the Boosting Rumor Correction Maximization (BRCM) problem under the Boosting Independent Cascade model. We prove that the BRCM problem is NP-hard, and the objective function is non-submodular. To handle it, we devise an efficient algorithm with a data-dependent approximation ratio. To explore the seed nodes, the Seed Selection problem and Minimum Seed Selection problem are proposed, respectively. Accordingly, we design two efficient algorithms. Finally, extensive empirical results in three networks manifest the efficiency of our approaches and show superiority over other baselines.
Wireless sensor networks (WSNs) have been widely used in a plenty of applications. To achieve higher efficiency for data collection, WSNs are often partitioned into several disjointed clusters, each ...with a representative cluster head in charge of the data gathering and routing process. Such a partition is balanced and effective, if the distance between each node and its cluster head can be bounded within a constant number of hops, and any two cluster heads are connected. Finding such a cluster partition with minimum number of clusters and connectors between cluster heads is defined as minimum connected d-hop dominating set (d-MCDS) problem, which is proved to be NP-complete. In this paper, we propose a distributed approximation named CS-Cluster to address the d-MCDS problem under unit disk graph. CS-Cluster constructs a sparser d-hop maximal independent set (d-MIS), connects the d-MIS, and finally checks and removes redundant nodes. We prove the approximation ratio of CS-Cluster is (2d + 1)λ, where λ is a parameter related with d but is no more than 18.4. Compared with the previous best result O(d 2 ), our approximation ratio is a great improvement. Our evaluation results demonstrate the outstanding performance of our algorithm compared with previous works.
Given a graph
G
=
(
V
,
E
)
and a function
r
:
V
↦
{
0
,
1
,
2
}
, a node
v
∈
V
is said to be
Roman dominated
if
r
(
v
)
=
1
or there exists a node
u
∈
N
G
v
such that
r
(
u
)
=
2
, where
N
G
v
...is the closed neighbor set of
v
in
G
. For
i
∈
{
0
,
1
,
2
}
, denote
V
r
i
as the set of nodes with value
i
under function
r
. The cost of
r
is defined to be
c
(
r
)
=
|
V
r
1
|
+
2
|
V
r
2
|
. Given a positive integer
Q
≤
|
V
|
, the
minimum partial connected Roman dominating set
(MinPCRDS) problem is to compute a minimum cost function
r
such that at least
Q
nodes in
G
are Roman dominated and the subgraph of
G
induced by
V
r
1
∪
V
r
2
is connected. In this paper, we give a
(
3
ln
|
V
|
+
9
)
-approximation algorithm for the MinPCRDS problem.
Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's ...traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. In this paper, we propose a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We show that CDSA has guaranteed quality by proving that the size of the CDSA constructed 2-connected backbone is within a constant factor of the optimal 2-connected virtual backbone size. Through extensive simulations, we demonstrate that in practice, CDSA can build a 2-connected virtual backbone with only small overhead.
In this paper, we consider the wireless sensor network in which the power of each sensor is adjustable. Given a set of sensors and a set of targets, we study a problem of minimizing the total power ...such that the coverage of targets meets
partial multi-cover requirement
, that is, there are at least a given number of targets each covered by a given number of sensors (this number is called the
covering requirement
for the target). This is called the minimum power partial multi-cover problem (MinPowerPMC) in a wireless sensor network. Under the assumption that the covering requirements for all targets are upper bounded by a constant, we design the first PTAS for the MinPowerPMC problem, that is, for any
ε
>
0
, a polynomial-time
(
1
+
ε
)
-approximation.
PDF
