The t -latency bounded strong target set selection problem in some kinds of special family of graphs
- PDF / 340,665 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 133 Views
The t-latency bounded strong target set selection problem in some kinds of special family of graphs Xianliang Liu1 · Zishen Yang2 · Wei Wang2 Accepted: 2 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract For a given simple graph G = (V , E), a latency bound t and a threshold function θ (v) = ρd(v), where ρ ∈ (0, 1) and d(v) denotes the degree of the vertex v(∈ V ), a subset S ⊆ V is called a strong target set if for each vertex v ∈ S, the number of its neighborhood in S not including itself is at least θ (v), and all vertices in V can be activated by S through a process with t rounds. Initially, all vertices in S become activated. At the ith round of the process, each vertex is activated if the number of active vertices in its neighbor after i − 1 rounds exceeds its threshold. The t-Latency Bounded Strong Target Set Selection (t-LBSTSS) problem is to find such a strong target set S with the minimum cardinality in G. In general graphs, the t-LBSTSS problem is not only NP-hard, but also hard to be approximated. The aim of this paper is to find an optimal t-latency bounded strong target set for some special family of graphs. For a given simple graph G, a simple, tight but nontrivial inequality in terms of the number of edges in G is proposed to obtain the lower bound of the sum of degrees in a strong target set S to the t-LBSTSS problem. Moreover, a necessary and sufficient condition is presented for equality to hold. Finally, we give the exact formulas for the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graphs, while it seems difficult to tell without the inequality given in this paper. Keywords Social networks · Viral marketing · Target set selection · Toroidal mesh · Toriadal cross
This work is supported by the National Natural Science Foundation of China (Nos. 11701236, 11471005 and 11971376).
B
Wei Wang [email protected]
1
College of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013, China
2
School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an 710049, China
123
Journal of Combinatorial Optimization
1 Introduction Social networks, as a major scientific object, have attracted more attention from researchers. One type of typical problems considered by many scholars is how to spread influence through a social network, such as promoting novel ideas, marketing new products, or spreading innovation. Domingos and Richardson (2001) initially proposed the influential nodes selection problem in social networks. Kempe et al. (2015, 2005) further formulated the influential nodes selection problem as an optimization problem which is called influence maximization problem is how to select k nodes in the network which generate the largest expected cascade based on a given probabilistic diffusion model. They presented a natural greedy algorithm that achieves a performance ratio of 1 − 1e − ε for any ε > 0. The target set selection (TSS) problem was considered by Chen (2009) that is how to
Data Loading...
