Abstract
The centrality of a vertex v in a network intuitively captures how important v is for communication in the network. The task of improving the centrality of a vertex has many applications, as a higher centrality often implies a larger impact on the network or less transportation or administration cost. In this work we study the parameterized complexity of the NP-complete problems Closeness Improvement and Betweenness Improvement in which we ask to improve a given vertex’ closeness or betweenness centrality by a given amount through adding a given number of edges to the network. Herein, the closeness of a vertex v sums the multiplicative inverses of distances of other vertices to v and the betweenness sums for each pair of vertices the fraction of shortest paths going through v. Unfortunately, for the natural parameter “number of edges to add” we obtain hardness results, even in rather restricted cases. On the positive side, we also give an island of tractability for the parameter measuring the vertex deletion distance to cluster graphs.
MS supported by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007–2013) under REA grant agreement number 631163.11 and the Israel Science Foundation (grant no. 551145/14).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
Recall that the H-index of a graph is the largest integer h such that there are h vertices of degree at least h.
- 3.
It is easy to check that all our results also hold if the closeness centrality is measured by sum of the multiplicative inverse distances from the other vertices to z.
References
Ambalath, A.M., Balasundaram, R., Rao H., C., Koppula, V., Misra, N., Philip, G., Ramanujan, M.S.: On the kernelization complexity of colorful motifs. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 14–25. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17493-3_4
Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theor. Comput. Syst. 58(2), 357–376 (2016)
Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163–177 (2001)
Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Soc. Netw. 30(2), 136–145 (2008)
Crescenzi, P., D’angelo, G., Severini, L., Velaj, Y.: Greedily improving our own closeness centrality in a network. ACM Trans. Knowl. Discov. Data 11(1), 9 (2016)
Csermely, P., London, A., Wu, L.-Y., Uzzi, B.: Structure and dynamics of core/periphery networks. J. Complex Netw. 1(2), 93–123 (2013)
Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-319-21275-3
D’Angelo, G., Severini, L., Velaj, Y.: On the maximum betweenness improvement problem. Electron. Notes Theor. Comput. Sci. 322, 153–168 (2016)
Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl. 16(2), 543–567 (2012)
Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40, 35–41 (1977)
Freeman, L.C.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215–239 (1978)
Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196–217 (2010)
Impagliazzo, R., Paturi, R.: Complexity of k-SAT. In: Proceeding of the 14th Annual IEEE Conference on Computational Complexity (CCC 1999), pp. 237–240 (1999)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? In: Proceedings 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 653–662 (1998)
Lokshtanov, D., Misra, N., Philip, G., Ramanujan, M.S., Saurabh, S.: Hardness of r-dominating set on Graphs of Diameter (\(r + 1\)). In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 255–267. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03898-8_22
Newman, M.: Networks: An Introduction. Oxford University Press, Oxford (2010)
Newman, M.E.: A measure of betweenness centrality based on random walks. Soc. Netw. 27(1), 39–54 (2005)
Okamoto, K., Chen, W., Li, X.-Y.: Ranking of closeness centrality for large-scale social networks. In: Preparata, F.P., Wu, X., Yin, J. (eds.) FAW 2008. LNCS, vol. 5059, pp. 186–195. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-69311-6_21
Opsahl, T., Agneessens, F., Skvoretz, J.: Node centrality in weighted networks: generalizing degree and shortest paths. Soc. Netw. 32(3), 245–251 (2010)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 5th edn. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53622-3
Rubinov, M., Sporns, O.: Complex network measures of brain connectivity: uses and interpretations. Neuroimage 52(3), 1059–1069 (2010)
White, D.R., Borgatti, S.P.: Betweenness centrality measures for directed graphs. Soc. Netw. 16(4), 335–346 (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Hoffmann, C., Molter, H., Sorge, M. (2018). The Parameterized Complexity of Centrality Improvement in Networks. In: Tjoa, A., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds) SOFSEM 2018: Theory and Practice of Computer Science. SOFSEM 2018. Lecture Notes in Computer Science(), vol 10706. Edizioni della Normale, Cham. https://doi.org/10.1007/978-3-319-73117-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-73117-9_8
Published:
Publisher Name: Edizioni della Normale, Cham
Print ISBN: 978-3-319-73116-2
Online ISBN: 978-3-319-73117-9
eBook Packages: Computer ScienceComputer Science (R0)