King's College London

Research portal

A fast algorithm to find all high degree vertices in graphs with a power law degree sequence

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages165-178
Number of pages14
Volume7323 LNCS
DOIs
Published2012
Event9th Workshop on Algorithms and Models for the Web Graph, WAW 2012 - Halifax, NS, Canada
Duration: 22 Jun 201223 Jun 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7323 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference9th Workshop on Algorithms and Models for the Web Graph, WAW 2012
Country/TerritoryCanada
CityHalifax, NS
Period22/06/201223/06/2012

King's Authors

Abstract

We develop a fast method for finding all high degree vertices of a connected graph with a power law degree sequence. The method uses a biassed random walk, where the bias is a function of the power law c of the degree sequence. Let G(t) be a t-vertex graph, with degree sequence power law c ≥ 3 generated by a generalized preferential attachment process which adds m edges at each step. Let S a be the set of all vertices of degree at least t a in G(t). We analyze a biassed random walk which makes transitions along undirected edges {x,y} proportional to (d(x)d(y)) b, where d(x) is the degree of vertex x and b>0 is a constant parameter. Choosing the parameter b=(c-1)(c-2)/(2c-3), the random walk discovers the set S a completely in Õ(t 1-2ab(1-ε)) steps with high probability. The error parameter ε depends on c,a and m. We use the notation Õ(x) to mean O(x log k x) for some constant k>0. The cover time of the entire graph G(t) by the biassed walk is Õ(t). Thus the expected time to discover all vertices by the biassed walk is not much higher than in the case of a simple random walk Θ(t logt). The standard preferential attachment process generates graphs with power law c=3. Choosing search parameter b=2/3 is appropriate for such graphs. We conduct experimental tests on a preferential attachment graph, and on a sample of the underlying graph of the www with power law c ∼3 which support the claimed property.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454