Document Open Access Logo

Near Optimal Adjacency Labeling Schemes for Power-Law Graphs

Authors Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, Christian Wulff-Nilsen

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.133.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Subject Classification

Keywords
  • Labeling schemes
  • Power-law graphs

Metrics

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

Abstract

An adjacency labeling scheme labels the n nodes of a graph with bit strings in a way that allows, given the labels of two nodes, to determine adjacency based only on those bit strings. Though many graph families have been meticulously studied for this problem, a non-trivial labeling scheme for the important family of power-law graphs has yet to be obtained. This family is particularly useful for social and web networks as their underlying graphs are typically modelled as power-law graphs. Using simple strategies and a careful selection of a parameter, we show upper bounds for such labeling schemes of ~O(sqrt^{alpha}(n)) for power law graphs with coefficient alpha;, as well as nearly matching lower bounds. We also show two relaxations that allow for a label of logarithmic size, and extend the upper-bound technique to produce an improved distance labeling scheme for power-law graphs.

Cite As Get BibTex

Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, and Christian Wulff-Nilsen. Near Optimal Adjacency Labeling Schemes for Power-Law Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 133:1-133:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.133

Author Details

Casper Petersen
Noy Rotbart
Jakob Grue Simonsen
Christian Wulff-Nilsen

References

  1. Ittai Abraham, Daniel Delling, Andrew V Goldberg, and Renato F Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Experimental Algorithms, pages 230-241. Springer, 2011. Google Scholar
  2. Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM, 56(4), 2009. URL: http://dx.doi.org/10.1145/1538902.1538905.
  3. David Adjiashvili and Noy Rotbart. Labeling schemes for bounded degree graphs. In Automata, Languages, and Programming, pages 375-386. Springer, 2014. Google Scholar
  4. Aditya Akella, Shuchi Chawla, Arvind Kannan, and Srinivasan Seshan. Scaling properties of the internet graph. In Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, PODC 2003, pages 337-346, 2003. URL: http://dx.doi.org/10.1145/872035.872087.
  5. Noga Alon and Vera Asodi. Sparse universal graphs. J. Comput. Appl. Math., 142(1):1-11, May 2002. URL: http://dx.doi.org/10.1016/S0377-0427(01)00455-1.
  6. Stephen Alstrup, Søren Dahlgaard, and Mathias Bæk Tejs Knudsen. Optimal induced universal graphs and adjacency labeling for trees. In Proceedings of the 58th Symposium on Foundations of Computer Science, FOCS'15, Washington, DC, USA, 2015. IEEE Computer Society. Google Scholar
  7. Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat. Sublinear distance labeling for sparse graphs. CoRR, abs/1507.02618, 2015. URL: http://arxiv.org/abs/1507.02618.
  8. Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick. Adjacency labeling schemes and induced-universal graphs. To appear in the 47th symposium on Theory of computing (STOC), 2015. Google Scholar
  9. Stephen Alstrup and Theis Rauhe. Small induced-universal graphs and compact implicit graph representations. In Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS'02, pages 53-62, Washington, DC, USA, 2002. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=645413.652151.
  10. Srinivasa R Arikati, Anil Maheshwari, and Christos D Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78(1):1-16, 1997. Google Scholar
  11. Laszlo Babai, Fan RK Chung, Pál Erdös, Ronald L Graham, and J Spencer. On graphs which contain all sparse graphs. Ann. Discrete Math, 12:21-26, 1982. Google Scholar
  12. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. Google Scholar
  13. Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th international conference on World Wide Web, pages 587-596. ACM, 2011. Google Scholar
  14. Paolo Boldi and Sebastiano Vigna. The webgraph framework I: compression techniques. In Proceedings of the 13th international conference on World Wide Web, pages 595-602. ACM, 2004. Google Scholar
  15. Béla Bollobás, Oliver Riordan, Joel Spencer, and Gábor E. Tusnády. The degree sequence of a scale-free random graph process. Random Struct. Algorithms, 18(3):279-290, 2001. URL: http://dx.doi.org/10.1002/rsa.1009.
  16. Pawek Brach, Marek Cygan, Jakub Lacki, and Piotr Sankowski. Algorithmic complexity of power law networks. In To appear in Proceedings of the thirty third annual ACM-SIAM symposium on Discrete algorithms, SODA'16, 2014. URL: http://arxiv.org/abs/1507.02426.
  17. Arthur Brady and Lenore J Cowen. Compact routing on power law graphs with additive stretch. In ALENEX, volume 6, pages 119-128. SIAM, 2006. Google Scholar
  18. Sonja Buchegger, Doris Schiöberg, Le-Hung Vu, and Anwitaman Datta. Peerson: P2p social networking: early experiences and insights. In Proceedings of the Second ACM EuroSys Workshop on Social Network Systems, pages 46-52. ACM, 2009. Google Scholar
  19. Kenneth L Calvert, Matthew B Doar, and Ellen W Zegura. Modeling internet topology. Communications Magazine, IEEE, 35(6):160-163, 1997. Google Scholar
  20. Saverio Caminiti, Irene Finocchi, and Rossella Petreschi. Engineering tree labeling schemes: A case study on least common ancestors. In Algorithms-ESA 2008, pages 234-245. Springer, 2008. Google Scholar
  21. Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang. A compact routing scheme and approximate distance oracle for power-law graphs. ACM Transactions on Algorithms, 9(1):4, 2012. Google Scholar
  22. Fan Chung and Linyuan Lu. The average distance in a random graph with given expected degrees. Internet Mathematics, 1(1):91-113, 2004. Google Scholar
  23. Fan RK Chung and Linyuan Lu. Complex Graphs and Networks, volume 107. American mathematical society Providence, 2006. Google Scholar
  24. Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM review, 51(4):661-703, 2009. Google Scholar
  25. Edith Cohen, Haim Kaplan, and Tova Milo. Labeling dynamic xml trees. SIAM Journal on Computing, 39(5):2048-2074, 2010. Google Scholar
  26. Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. Google Scholar
  27. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Noy Rotbart. Dynamic and multi-functional labeling schemes. In Algorithms and Computation, pages 141-153. Springer, 2014. Google Scholar
  28. YH Eom, S Fortunato, and Matjaz Perc. Characterizing and modeling citation dynamics. PLoS ONE, 6(9):e24926, 2011. Google Scholar
  29. Johannes Fischer. Short labels for lowest common ancestors in trees. In Algorithms-ESA 2009, pages 752-763. Springer, 2009. Google Scholar
  30. Cyril Gavoille and Arnaud Labourel. Shorter implicit representation for planar graphs and bounded treewidth graphs. In Algorithms-ESA 2007, pages 582-593. Springer, 2007. Google Scholar
  31. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, SODA'01, pages 210-219, Philadelphia, PA, USA, 2001. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=365411.365447.
  32. Cyril Gavoille, David Peleg, Stéphane Pérennesc, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53:85-112, 2004. Google Scholar
  33. Pawel Gawrychowski, Adrian Kosowski, and Przemyslaw Uznanski. Even simpler distance labeling for (sparse) graphs. CoRR, abs/1507.06240, 2015. URL: http://arxiv.org/abs/1507.06240.
  34. Gaurav Goel and Jens Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In Graph-Theoretic Concepts in Computer Science, pages 159-167. Springer, 2006. Google Scholar
  35. Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. OSDI, 12(1):2, 2012. Google Scholar
  36. Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. In SIAM Journal On Discrete Mathematics, pages 334-343, 1992. Google Scholar
  37. Michal Katz, Nir A Katz, Amos Korman, and David Peleg. Labeling schemes for flow and connectivity. SIAM Journal on Computing, 34(1):23-40, 2004. Google Scholar
  38. Amos Korman. General compact labeling schemes for dynamic trees. Distributed Computing, 20(3):179-193, 2007. Google Scholar
  39. Amos Korman and Shay Kutten. Labeling schemes with queries. In Structural Information and Communication Complexity, pages 109-123. Springer, 2007. Google Scholar
  40. Amos Korman and David Peleg. Compact separator decompositions in dynamic trees and applications to labeling schemes. In Distributed Computing, pages 313-327. Springer, 2007. Google Scholar
  41. Amos Korman and David Peleg. Labeling schemes for weighted dynamic trees. Inf. Comput., 205(12):1721-1740, December 2007. URL: http://dx.doi.org/10.1016/j.ic.2007.08.004.
  42. Łukasz Kowalik. Approximation scheme for lowest outdegree orientation and graph density measures. In Algorithms and computation, pages 557-566. Springer, 2006. Google Scholar
  43. Dmitri Krioukov, Kevin Fall, and Xiaowei Yang. Compact routing on internet-like graphs. In INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, volume 1. IEEE, 2004. Google Scholar
  44. Yucheng Low, Danny Bickson, Joseph Gonzalez, Carlos Guestrin, Aapo Kyrola, and Joseph M Hellerstein. Distributed graphlab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8):716-727, 2012. Google Scholar
  45. Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 135-146. ACM, 2010. Google Scholar
  46. Robert Ryan McCune, Tim Weninger, and Greg Madey. Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. CoRR, abs/1507.04405, 2015. URL: http://arxiv.org/abs/1507.04405.
  47. Michael Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226-251, 2004. Google Scholar
  48. JW Moon. On minimal n-universal graphs. Proceedings of the Glasgow Mathematical Association, 7(01):32-33, 1965. Google Scholar
  49. Noy Rotbart, Marcos Vaz Salles, and Iasonas Zotos. An evaluation of dynamic labeling schemes for tree networks. In Experimental Algorithms, pages 199-210. Springer, 2014. Google Scholar
  50. Georgos Siganos, Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. Power laws and the as-level internet topology. IEEE/ACM Trans. Netw., 11(4):514-524, 2003. URL: http://dx.doi.org/10.1109/TNET.2003.815300.
  51. Jeremy P Spinrad. Efficient graph representations. American mathematical society, 2003. Google Scholar
  52. Isabelle Stanton and Gabriel Kliot. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1222-1230. ACM, 2012. Google Scholar
  53. Bernard M Waxman. Routing of multipoint connections. Selected Areas in Communications, IEEE Journal on, 6(9):1617-1622, 1988. Google Scholar
  54. Cong Xie, Ling Yan, Wu-Jun Li, and Zhihua Zhang. Distributed power-law graph computing: Theoretical and empirical analysis. In Advances in Neural Information Processing Systems, pages 1673-1681, 2014. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact