Near Optimal Adjacency Labeling Schemes for Power-Law Graphs
Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, Christian Wulff‐Nilsen · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
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 Õ( α √ 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.