Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 11638))
Included in the following conference series:
713Accesses
Abstract
Inspired by the feedback scenario, which characterizes online social networks, we introduce a novel domination problem, which we callDual Domination (DD). We assume that the nodes in the input network are partitioned into two categories: Positive nodes (\(V^+\)) and negative nodes (\(V^-\)). We are looking for a set\(D\subseteq V^+\) that dominates the largest number of positive nodes while avoiding as many negative nodes as possible. In particular, we study theMaximum Bounded Dual Domination (MBDD) problem, where given a boundk, the problem is to find a set\(D\subseteq V^+\), which maximizes the number of nodes dominated in\(V^+,\) dominating at mostk nodes in\(V^-.\) We show that the MBDD problem is hard to approximate to a factor better than\((1-1/e)\). We give a polynomial time approximation algorithm with approximation guaranteed\((1-e^{-1/\varDelta })\), where\(\varDelta \) represents the maximum number of neighbors in\(V^+\) of any node in\(V^-.\) Furthermore, we give an\(O(|V|k^2)\) time algorithm to solve the problem on trees.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 8464
- Price includes VAT (Japan)
- Softcover Book
- JPY 10581
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We can assume that no edge exists between two nodes in\(V^-\), since such edges are irrelevant for our problem.
- 2.
(Notice that\(S^0 \subseteq \mathtt{OPT}\) and since\(\mathtt{OPT}\) is an optimal solution we have\(P_{\mathtt{OPT}} \subseteq \mathtt{OPT}\) and then\(P^0 \subseteq \mathtt{OPT}\).)
References
Abebe, R., Adamic, L., Kleinberg, J.: Mitigating overexposure in viral marketing. In: The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018), pp. 241–248 (2018)
Berger, J., Heath, C.: Where consumers diverge from others: identity signaling and product domains. J. Consum. Res.34(2), 121–134 (2007)
Byers, J.W., Mitzenmacher, M., Zervas, G.: The groupon effect on yelp ratings: a root cause analysis. In: Proceedings of 13th ACM Conference on Electronic Commerce, EC 2012, pp. 248–265 (2012)
Chen, Y., Li, H., Qu, Q.: Negative-aware influence maximization on social networks. In: Proceedings of AAAI Conference on Artificial Intelligence (2018)
Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Optimizing spread of influence in social networks via partial incentives. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 119–134. Springer, Cham (2015).https://doi.org/10.1007/978-3-319-25258-2_9
Cordasco, G., Gargano, L., Rescigno, A.A.: Influence propagation over large scale social networks. In: Proceedings of ASONAM 2015, pp. 1531–1538 (2015)
Cordasco, G., et al.: Whom to befriend to influence people. Theoret. Comput. Sci. (to appear)
Cordasco, G., Gargano, L., Mecchia, M., Rescigno, A.A., Vaccaro, U.: Discovering small target sets in social networks: a fast and effective algorithm. Algorithmica80(6), 1804–1833 (2018)
Cordasco, G., Gargano, L., Rescigno, A.A.: Active influence spreading in social networks. Theoret. Comput. Sci.764, 15–29 (2019)
Cordasco, G., Gargano, L., Rescigno, A.A., Vaccaro, U.: Evangelism in social networks: algorithms and complexity. Networks71(4), 346–357 (2018)
Cravens, K., Goad Oliver, E., Ramamoorti, S.: The reputation index: measuring and managing corporate reputation. Eur. Manag. J.21(2), 201–212 (2003)
Cretu, A.E., Brodie, R.J.: The influence of brand image and company reputation where manufacturers market to small firms: a customer value perspective. Ind. Mark. Manag.36(2), 230–240 (2007)
Delbot, F., Laforest, C., Phan, R.: Graphs with forbidden and required vertices. In: 17th Rencontres Francophones sur les Aspects Algorithmiques des Télécom (ALGOTEL 2015) (2015)
Dunbar, J.E., Hedetniemi, S.T., Henning, M.A., Slater, P.J.: Signed domination in graphs. In: Proceedings of the Seventh International Conference in Graph Theory, Combinatorics, Algorithms, and Applications, pp. 311–321 (1995)
Dunbar, J., Hedetniemi, S., Henning, M.A., McRae, A.: Minus domination in graphs. Discret. Math.199(1), 35–47 (1999)
Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York (2010)
Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs (Pure and Applied Mathematics (Marcel Dekker)). CRC, Boca Raton (1998)
Hu, Y., Van den Bulte, C.: Nonmonotonic status effects in new product adoption. Mark. Sci.33(4), 509–533 (2014)
Joshi, Y.V., Reibstein, D.J., Zhang, Z.J.: Turf wars: product line strategies in competitive markets. Mark. Sci.35(1), 128–141 (2016)
Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett.70(1), 39–45 (1999)
Li, Y., Chen, W., Wang, Y., Zhang, Z.-L.: Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In: Proc. of WSDM 2013, pp. 657–666 (2013)
Liu, X., Kong, X., Yu, P.S.: Active opinion maximization in social networks. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, (KDD 2018) (2018)
Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest K-subgraph. In: Proceedings of the 49th ACM SIGACT Symposium on Theory of Computing (STOC 2017), pp. 954–961 (2017)
Miyano, E., Ono, H.: Maximum domination problem. In: Proceedings of the 17th Computing on The Australasian Theory Symposium (CATS 2011), vol. 119, pp. 55–62 (2011)
Neiheisel, J.R., Niebler, S.: On the limits of persuasion: campaign ads and the structure of voters’ interpersonal discussion networks. Polit. Commun.32(3), 434–452 (2015)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Prog.14(1), 265–294 (1978)
Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett.32(1), 41–43 (2004)
Wakefield, M., Flay, B., Nichter, M., Giovino, G.: Effects of anti-smoking advertising on youth smoking: a review. J. Health Comm.8(3), 229–247 (2003)
Author information
Authors and Affiliations
Università della Campania “Luigi Vanvitelli”, Caserta, Italy
Gennaro Cordasco
Department of Computer Science, Università di Salerno, Fisciano, Italy
Luisa Gargano & Adele Anna Rescigno
- Gennaro Cordasco
You can also search for this author inPubMed Google Scholar
- Luisa Gargano
You can also search for this author inPubMed Google Scholar
- Adele Anna Rescigno
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toGennaro Cordasco.
Editor information
Editors and Affiliations
Arizona State University, Tempe, AZ, USA
Charles J. Colbourn
University of Pisa, Pisa, Italy
Roberto Grossi
University of Pisa, Pisa, Italy
Nadia Pisanti
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Cordasco, G., Gargano, L., Rescigno, A.A. (2019). Dual Domination. In: Colbourn, C., Grossi, R., Pisanti, N. (eds) Combinatorial Algorithms. IWOCA 2019. Lecture Notes in Computer Science(), vol 11638. Springer, Cham. https://doi.org/10.1007/978-3-030-25005-8_14
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-25004-1
Online ISBN:978-3-030-25005-8
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative