Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009, Revised Papers, Part 2

Research Article

Extremal Dependencies and Rank Correlations in Power Law Networks

Download69 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-02469-6_43,
        author={Yana Volkovich and Nelly Litvak and Bert Zwart},
        title={Extremal Dependencies and Rank Correlations in Power Law Networks},
        proceedings={Complex Sciences. First International Conference, Complex 2009, Shanghai, China, February 23-25, 2009, Revised Papers, Part 2},
        proceedings_a={COMPLEX PART 2},
        year={2012},
        month={5},
        keywords={Extremal dependencies Statistical analysis Power laws PageRank Web Wikipedia Preferential attachment},
        doi={10.1007/978-3-642-02469-6_43}
    }
    
  • Yana Volkovich
    Nelly Litvak
    Bert Zwart
    Year: 2012
    Extremal Dependencies and Rank Correlations in Power Law Networks
    COMPLEX PART 2
    Springer
    DOI: 10.1007/978-3-642-02469-6_43
Yana Volkovich1,*, Nelly Litvak1,*, Bert Zwart2,*
  • 1: University of Twente
  • 2: CWI, Science Park Amsterdam, Kruislaan 413
*Contact email: y.volkovich@ewi.utwente.nl, n.litvak@ewi.utwente.nl, bert.zwart@cwi.nl

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.