2015/02/13 by Casper Petersen, Petersen, Casper, Noy Rotbart +5
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Data Visualization and Analytics #Distributed #E.1 #FOS: Computer and information sciences #G.2.2 #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1502.03971
openalex publication_date 2015/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An adjacency labeling scheme is a method that assigns labels to the vertices of a graph such that adjacency between vertices can be inferred directly from the assigned label, without using a centralized data structure. We devise adjacency labeling schemes for the family of power-law graphs. This family that has been used to model many types of networks, e.g. the Internet AS-level graph. Furthermore, we prove an almost matching lower bound for this family. We also provide an asymptotically near- optimal labeling scheme for sparse graphs. Finally, we validate the efficiency of our labeling scheme by an experimental evaluation using both synthetic data and real-world networks of up to hundreds of thousands of vertices.