Extremal dependencies and rank correlations in power law networks

Y. Volkovich, Nelli Litvak, B. Zwart

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

7 Citations (Scopus)
64 Downloads (Pure)

Abstract

We analyze dependencies in complex networks characterized by power laws (Web sample, Wikipedia sample and a preferential attachment graph) using statistical techniques from the extreme value theory and the theory of multivariate regular variation. To the best of our knowledge, this is the first attempt to apply this well developed methodology to comprehensive graph data. The new insights this yields are striking: the three above-mentioned data sets are shown to have a totally different dependence structure between graph parameters, such as in-degree and PageRank. Based on the proposed approach, we suggest a new measure for rank correlations. Unlike most known methods, this measure is especially sensitive to rank permutations for top-ranked nodes. Using the new correlation measure, we demonstrate that the PageRank ranking is not sensitive to moderate changes in the damping factor.
Original languageUndefined
Title of host publicationComplex Sciences, Proceedings of the First International Conference on Complex Sciences: Theory and Applications (COMPLEX '2009)
EditorsZ. Jie
Place of PublicationShanghai
PublisherICST
Pages1642-1653
Number of pages12
ISBN (Print)978-3-642-02468-9
DOIs
Publication statusPublished - 2009
EventFirst International Conference on Complex Sciences: Theory and Applications (COMPLEX '2009) - Shanghai, China
Duration: 23 Feb 200925 Feb 2009

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
PublisherSpringer
Volume5
ISSN (Print)1867-8211

Conference

ConferenceFirst International Conference on Complex Sciences: Theory and Applications (COMPLEX '2009)
Period23/02/0925/02/09
Other23-25 Feb 2009

Keywords

  • Web
  • PageRank
  • Statistical Analysis
  • Power laws
  • IR-65407
  • EWI-15152
  • Extremal dependencies
  • Wikipedia
  • METIS-263755
  • Preferential attachment

Cite this