Abstract
Analyzing the authority or reputation of entities that are connected by a graph
structure and ranking these entities is an important issue that arises in the
Web, in Web 2.0 communities, and in other applications. The problem is
typically addressed by computing the dominant eigenvector of a matrix that is
suitably derived from the underlying graph, or by performing a full spectral
decomposition of the matrix.
Although such analyses could be performed by a centralized server, there are
good reasons that suggest running theses computations in a decentralized manner
across many peers, like scalability, privacy, censorship, etc. There exist a
number of approaches for speeding up the analysis by partitioning the graph
into disjoint fragments. However, such methods are not suitable for a
peer-to-peer network, where overlap among the fragments might occur. In
addition, peer-to-peer approaches need to consider network characteristics,
such as peers unaware of other peers' contents, susceptibility to malicious
attacks, and network dynamics (so-called churn).
In this thesis we make the following major contributions.
We present JXP, a decentralized algorithm for computing authority scores of
entities distributed in a peer-to-peer (P2P) network that allows peers to have
overlapping content and requires no a priori knowledge of other peers' content.
We also show the benefits of JXP in the Minerva distributed Web search engine.
We present an extension of JXP, coined \emph{TrustJXP}, that contains a
reputation model in order to deal with misbehaving peers.
We present another extension of JXP, that handles dynamics on peer-to-peer
networks, as well as an algorithm for estimating the current number of entities
in the network.
This thesis also presents novel methods for embedding JXP in peer-to-peer
networks and applications.
We present an approach for creating links among peers, forming \emph{semantic
overlay networks}, where peers are free to decide which connections they create
and which they want to avoid based on various usefulness estimators. We show
how peer-to-peer applications, like the JXP algorithm, can greatly benefit from
these additional semantic relations.
