Document Open Access Logo

Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node

Authors Ruben Brokkelkamp , Sven Polak , Guido Schäfer, Yllka Velaj

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.13.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Ruben Brokkelkamp
  • Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands
Sven Polak
  • Korteweg-de Vries Institute for Mathematics, University of Amsterdam, Netherlands
Guido Schäfer
  • Centrum Wiskunde & Informatica (CWI), Amsterdam, Netherlands
  • Vrije Universiteit Amsterdam, Netherlands
Yllka Velaj
  • ISI Foundation, Turin, Italy

Funding

Part of this research was funded by the NWO Gravitation Project NETWORKS, Grant Number 024.002.003.

Cite AsGet BibTex

Ruben Brokkelkamp, Sven Polak, Guido Schäfer, and Yllka Velaj. Approximate Pricing in Networks: How to Boost the Betweenness and Revenue of a Node. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.13

Abstract

We introduce and study two new pricing problems in networks: Suppose we are given a directed graph G = (V, E) with non-negative edge costs (c_e)_{e in E}, k commodities (s_i, t_i, w_i)_{i in [k]} and a designated node u in V. Each commodity i in [k] is represented by a source-target pair (s_i, t_i) in V x V and a demand w_i>0, specifying that w_i units of flow are sent from s_i to t_i along shortest s_i, t_i-paths (with respect to (c_e)_{e in E}). The demand of each commodity is split evenly over all shortest paths. Assume we can change the edge costs of some of the outgoing edges of u, while the costs of all other edges remain fixed; we also say that we price (or tax) the edges of u. We study the problem of pricing the edges of u with respect to the following two natural objectives: (i) max-flow: maximize the total flow passing through u, and (ii) max-revenue: maximize the total revenue (flow times tax) through u. Both variants have various applications in practice. For example, the max flow objective is equivalent to maximizing the betweenness centrality of u, which is one of the most popular measures for the influence of a node in a (social) network. We prove that (except for some special cases) both problems are NP-hard and inapproximable in general and therefore resort to approximation algorithms. We derive approximation algorithms for both variants and show that the derived approximation guarantees are best possible.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Shortest paths
  • Theory of computation → Network flows
Keywords
  • Network pricing
  • Stackelberg network pricing
  • betweenness centrality
  • revenue maximization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nederland is een aantrekkelijk belastingland. NOS, Nov. 6, 2014. Google Scholar
  2. Konstantin Avrachenkov and Nelly Litvak. The Effect of New Links on Google Pagerank. Stoc. Models, 2006. Google Scholar
  3. Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling, Andrea Schumm, and Dorothea Wagner. The Shortcut Problem - Complexity and Algorithms. J. Graph Algorithms Appl., 16(2):447-481, 2012. Google Scholar
  4. Elisabetta Bergamini, Pierluigi Crescenzi, Gianlorenzo D'Angelo, Henning Meyerhenke, Lorenzo Severini, and Yllka Velaj. Improving the Betweenness Centrality of a Node by Adding Links. ACM J. of Experimental Algorithmics, 23, 2018. Google Scholar
  5. Davide Bilò, Luciano Gualà, and Guido Proietti. Improved approximability and non-approximability results for graph diameter decreasing problems. Theor. Comput. Sci., 417:12-22, 2012. Google Scholar
  6. Patrick Briest. Uniform Budgets and the Envy-Free Pricing Problem. In ICALP, pages 808-819, 2008. Google Scholar
  7. Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, and Danupon Nanongkai. Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. In Internet and Network Economics, 2010. Google Scholar
  8. Patrick Briest, Martin Hoefer, and Piotr Krysta. Stackelberg Network Pricing Games. Algorithmica, 62(3), 2012. Google Scholar
  9. Luce Brotcorne, F. Cirinei, Patrice Marcotte, and Gilles Savard. An exact algorithm for the network pricing problem. Discrete Optimization, 8(2):246-258, 2011. Google Scholar
  10. Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, and Sanjeev Khanna. Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. In APPROX-RANDOM, pages 73-84, 2012. Google Scholar
  11. Pierluigi Crescenzi, Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Greedily improving our own centrality in a network. In SEA 2015, volume 9125 of Lecture Notes in Computer Science, pages 43-55, 2015. Google Scholar
  12. Pierluigi Crescenzi, Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Greedily Improving Our Own Closeness Centrality in a Network. ACM Trans. Knowl. Discov. Data, 11(1):9:1-9:32, 2016. Google Scholar
  13. Gianlorenzo D'Angelo, Martin Olsen, and Lorenzo Severini. Coverage Centrality Maximization in Undirected Networks. CoRR, abs/1811.04331, 2019. URL: http://arxiv.org/abs/1811.04331.
  14. P. de Waard. Nederland belastingparadijs voor veel multinationals. De Volkskrant, Oct. 14, 2011. Google Scholar
  15. Erik D. Demaine and Morteza Zadimoghaddam. Minimizing the Diameter of a Network Using Shortcut Edges. In SWAT, volume 6139 of Lecture Notes in Computer Science, pages 420-431, 2010. Google Scholar
  16. Edsger W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numer. Math., 1(1):269-271, 1959. Google Scholar
  17. Iftah Gamzu and Danny Segev. A Sublogarithmic Approximation for Highway and Tollbooth Pricing. In Proc. 37th International Colloquium Conference on Automata, Languages and Programming, ICALP'10, pages 582-593, 2010. Google Scholar
  18. Fabrizio Grandoni and Thomas Rothvoss. Pricing on Paths: A PTAS for the Highway Problem. SIAM J. Comput., 45(2):216-231, 2016. Google Scholar
  19. Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry. On Profit-maximizing Envy-free Pricing. In SODA, pages 1164-1173, 2005. Google Scholar
  20. Vatche Ishakian, Dóra Erdös, Evimaria Terzi, and Azer Bestavros. A Framework for the Evaluation and Management of Network Centrality. In Proc. 12th SIAM Int. Conf. on Data Mining (SDM), pages 427-438, 2012. Google Scholar
  21. Martine Labbe, Patrice Marcotte, and Gilles Savard. A Bilevel Model of Taxation and Its Application to Optimal Highway Pricing. Management Science, 44(12):1608-1622, December 1998. Google Scholar
  22. Ahmad Mahmoody, Charalampos E. Tsourakakis, and Eli Upfal. Scalable Betweenness Centrality Maximization via Sampling. In Proc. 22nd ACM SIGKDD Int. Conf. on KDD, pages 1765-1773, 2016. Google Scholar
  23. Paolo Malighetti, Gianmaria Martini, Stefano Paleari, and Renato Redondi. The Impacts of Airport Centrality in the EU Network and Inter-Airport Competition on Airport Efficiency. Technical Report MPRA-7673, University Library of Munich, Germany, 2009. Google Scholar
  24. Adam Meyerson and Brian Tagiku. Minimizing Average Shortest Path Distances via Shortcut Edge Addition. In APPROX, volume 5687, 2009. Google Scholar
  25. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions-I. Math. Program., 14(1):265-294, 1978. Google Scholar
  26. Martin Olsen and Anastasios Viglas. On the approximability of the link building problem. TCS, 518:96-116, 2014. Google Scholar
  27. Manos Papagelis, Francesco Bonchi, and Aristides Gionis. Suggesting Ghost Edges for a Smaller World. In Proc. 20th ACM Int. Conf. on Information and Knowledge Management, CIKM '11, pages 2305-2308. ACM, 2011. Google Scholar
  28. Nikos Parotsidis, Evaggelia Pitoura, and Panayiotis Tsaparas. Selecting Shortcuts for a Smaller World. In Proc. SIAM Int. Conf. on Data Mining, pages 28-36. SIAM, 2015. Google Scholar
  29. Senni Perumal, Prithwish Basu, and Ziyu Guan. Minimizing Eccentricity in Composite Networks via Constrained Edge Additions. In Military Communications Conference, MILCOM 2013 - 2013 IEEE, pages 1894-1899, 2013. Google Scholar
  30. Sven C. Polak. Algorithms for the Network Analysis of Bilateral Tax Treaties. MSc. thesis, University of Amsterdam, The Netherlands, 2014. Google Scholar
  31. Sébastien Roch, Gilles Savard, and Patrice Marcotte. An approximation algorithm for Stackelberg network pricing. Networks, 46(1):57-67, 2005. Google Scholar
  32. D. Milmo S. Goodley. Dutch masters of tax avoidance. The Guardian, Oct. 19, 2011. Google Scholar
  33. Thomas W. Valente and Kayo Fujimoto. Bridging: Locating critical connectors in a network. Soc. Netw., 32(3):212-220, 2010. Google Scholar
  34. Leslie Valiant. The Complexity of Enumeration and Reliability Problems. SICOMP, 8(3):410-421, 1979. Google Scholar
  35. Maarten van `t Riet and Arjan M. Lejour. Ranking the Stars: Network Analysis of Bilateral Tax Treaties. CPB Discussion Paper, 2014. Google Scholar
  36. Maarten van ‘t Riet and Arjan M. Lejour. Optimal tax routing: network analysis of FDI diversion. International Tax and Public Finance, 25(5):1321-1371, 2018. Google Scholar
  37. Baoning Wu and Brian D. Davison. Identifying link farm spam pages. In Proc. 14th Int. Conf. on World Wide Web, WWW 2005, pages 820-829, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact