nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Fast Approximation of Centrality and Distances in Hyperbolic Graphs

verfasst von : V. Chepoi, F. F. Dragan, M. Habib, Y. Vaxès, H. Alrasheed

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We show that the eccentricities (and thus the centrality indices) of all vertices of a \(\delta \)-hyperbolic graph \(G=(V,E)\) can be computed in linear time with an additive one-sided error of at most \(c\delta \), i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimate \(\hat{e}(v)\) of its eccentricity \(ecc_G(v)\) such that \(ecc_G(v)\le \hat{e}(v)\le ecc_G(v)+ c\delta \) for a small constant c. We prove that every \(\delta \)-hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, \(ecc_G(v)\le ecc_T(v)\le ecc_G(v)+ c\delta \). We also show that the distance matrix of G with an additive one-sided error of at most \(c'\delta \) can be computed in \(O(|V|^2\log ^2|V|)\) time, where \(c'< c\) is a small constant. Recent empirical studies show that many real-world graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nächstes Kapitel Rectilinear Shortest Paths Among Transient Obstacles

Abboud, A., Wang, J., Vassilevska Williams, V.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: SODA (2016)

Abboud, A., Grandoni, F., Vassilevska Williams, V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: SODA, pp. 1681–1697 (2015)

Abu-Ata, M., Dragan, F.F.: Metric tree-like structures in real-world networks: an empirical study. Networks 67, 49–68 (2016)MathSciNetCrossRef

Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (w/o matrix multiplication). SIAM J. Comput. 28, 1167–81 (1999)MathSciNetCrossRef

Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 541–552. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73951-7_47CrossRef

Borassi, M., Crescenzi, P., Habib, M.: Into the square - on the complexity of quadratic-time solvable problems. Electron. Notes Theor. Comput. Sci. 322, 51–67 (2016)MathSciNetCrossRef

Brandstädt, A., Chepoi, V., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Appl. Math. 82, 43–77 (1998)MathSciNetCrossRef

Brandstädt, A., Chepoi, V., Dragan, F.F.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms 30, 166–184 (1999)MathSciNetCrossRef

Bridson, M.R., Haefiger, A.: Metric Spaces of Non-Positive Curvature, Grundlehren der Mathematischen Wissenschaften. vol. 319, Springer (1999). https://doi.org/10.1007/978-3-662-12494-9CrossRef

10.

Chechik, S., Larkin, D., Roditty, L., Schoenebeck, G., Tarjan, R.E.: and Williams, V.V.: Better approximation algorithms for the graph diameter. In: SODA (2014)

11.

Chalopin, J., Chepoi, V., Dragan, F.F., Ducoffe, G., Mohammed, A., Vaxès, Y.: Fast approximation and exact computation of negative curvature parameters of graphs. In: SoCG (2018)

12.

Chepoi, V., Dragan, F.: A linear-time algorithm for finding a central vertex of a chordal graph. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 159–170. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0049406CrossRef

13.

Chepoi, V.D., Dragan, F.F., Estellon, B., Habib, M., Vaxès, Y.: Diameters, centers, and approximating trees of \(\delta \)-hyperbolic geodesic spaces and graphs. In: SoCG (2008)

14.

Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vaxès, Y., Xiang, Y.: Additive spanners and distance and routing schemes for hyperbolic graphs. Algorithmica 62, 713–732 (2012)MathSciNetCrossRef

15.

Chepoi, V., Dragan, F.F., Habib, M., Vaxès, Y., Al-Rasheed, H.: Fast approximation of centrality and distances in hyperbolic graphs. arXiv:1805.07232 (2018)

16.

Chepoi, V., Dragan, F.F., Vaxès, Y.: Center and diameter problems in plane triangulations and quadrangulations. In: SODA, pp. 346–355 (2002)

17.

Chepoi, V., Dragan, F.F., Vaxès, Y.: Core congestion is inherent in hyperbolic networks. In: SODA, pp. 2264–2279 (2017)

18.

Chepoi, V., Estellon, B.: Packing and covering \(\delta \)-hyperbolic spaces by balls. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX/RANDOM -2007. LNCS, vol. 4627, pp. 59–73. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74208-1_5CrossRefMATH

19.

Corneil, D.G., Dragan, F.F., Köhler, E.: On the power of BFS to determine a graph’s diameter. Networks 42, 209–222 (2003)MathSciNetCrossRef

20.

Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29, 1740–1759 (2000)MathSciNetCrossRef

21.

Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discr. Math. 307, 208–229 (2007)MathSciNetCrossRef

22.

Dragan, F.F.: Centers of graphs and the Helly property (in Russian), Ph.D. thesis, Moldova State University (1989)

23.

Dragan, F.F.: Estimating all pairs shortest paths in restricted graph families: a unified approach. J. Algorithms 57, 1–21 (2005)MathSciNetCrossRef

24.

Dragan, F.F., Köhler, E., Alrasheed, H.: Eccentricity approximating trees. Discrete Appl. Math. 232, 142–156 (2017)MathSciNetCrossRef

25.

Dragan, F.F., Nicolai, F., Brandstädt, A.: LexBFS-orderings and powers of graphs. In: d’Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG 1996. LNCS, vol. 1197, pp. 166–180. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62559-3_15CrossRef

26.

Edwards, K., Kennedy, W.S., Saniee, I.: Fast approximation algorithms for p-centres in large \(delta\)-hyperbolic graphs, CoRR, vol. abs/1604.07359 (2016)

27.

Ghys, E., de la Harpe, P. (eds.) Les groupes hyperboliques d’après Gromov, M. Progress in Mathematics, Vol. 83 Birkhäuser (1990)

28.

Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8. Springer, New York (1987). https://doi.org/10.1007/978-1-4613-9586-7_3CrossRef

29.

Hakimi, S.L.: Optimum location of switching centers and absolute centers and medians of a graph. Oper. Res. 12, 450–459 (1964)CrossRef

30.

Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512–530 (2001)MathSciNetCrossRef

31.

Jordan, C.: Sur les assemblages des lignes. J. Reine Angew. Math. 70, 185–190 (1869)MathSciNetCrossRef

32.

Kratsch, D., Le, H.-O., Müller, H., Prisner, E., Wagner, D.: Additive tree spanners. SIAM J. Discrete Math. 17, 332–340 (2003)MathSciNetCrossRef

33.

Narayan, O., Saniee, I.: Large-scale curvature of networks. Phys. Rev. E 84(6), 066108 (2011)CrossRef

34.

Prisner, E.: Distance approximating spanning trees. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 499–510. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0023484CrossRef

35.

Prisner, E.: Eccentricity-approximating trees in chordal graphs. Discr. Math. 220, 263–269 (2000)MathSciNetCrossRef

36.

Roditty, L., Vassilevska Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: STOC, pp. 515–524 (2013)

37.

Shavitt, Y., Tankel, T.: Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Trans. Netw. 16, 25–36 (2008)CrossRef

38.

Verbeek, K., Suri, S.: Metric embedding, hyperbolic space, and social networks. In: SoCG, pp. 501–510 (2014)

39.

Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1227–1237. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27836-8_101CrossRefMATH

Titel: Fast Approximation of Centrality and Distances in Hyperbolic Graphs
verfasst von: V. Chepoi
F. F. Dragan
M. Habib
Y. Vaxès
H. Alrasheed
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"