Near optimal adjacency labeling schemes for power-law graphs

TY - GEN

T1 - Near optimal adjacency labeling schemes for power-law graphs

AU - Petersen, Casper

AU - Rotbart, Noy Galil

AU - Simonsen, Jakob Grue

AU - Wulff-Nilsen, Christian

N1 - Conference code: 43

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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( α√ p n) for power law graphs with coefficient α, 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.

AB - 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( α√ p n) for power law graphs with coefficient α, 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.

U2 - 10.4230/LIPIcs.ICALP.2016.133

DO - 10.4230/LIPIcs.ICALP.2016.133

M3 - Article in proceedings

SN - 978-3-95977-013-2

T3 - Leibniz International Proceedings in Informatics

BT - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

A2 - Chatzigiannakis, Ioannis

A2 - Mitzenmacher, Michael

A2 - Rabani, Yuval

A2 - Sangiorgi, Davide

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 43rd International Colloquium on Automata, Languages and Programming

Y2 - 12 July 2016 through 15 July 2016

ER -