Item

Abstract

Page{R}ank-style authority analyses of Web graphs are of great importance for {W}eb mining. Such authority analyses also apply to hot ``Web 2.0'' applications that exhibit a natural graph structure, such as social networks (e.g., My{S}pace, {F}acebook) or tagging communities (e.g., Flickr, Del.icio.us). Finding the most trustworthy or most important authorities in such a community is a pressing need, given the huge scale and also the anonymity of social networks. Computing global authority measures in a Peer-to-Peer ({P2P}) collaboration of autonomous peers is a hot research topic, in particular because of the incomplete local knowledge of the peers, which typically only know about (arbitrarily overlapping) sub-graphs of the complete graph. We demonstrate a self-organizing {P2P} collaboration that, based on the local sub-graphs, efficiently computes global authority scores. In hand with the loosely-coupled spirit of a {P2P} system, the computation is carried out in a completely asynchronous manner without any central knowledge or coordinating instance. We demonstrate the applicability of authority analyses to large-scale distributed systems.