\chapter{Group Trust Metrics}
\label{groupmetric}

This chapter presents the concept of \emph{group trust metrics,} which
have significantly better attack resistance properties than trust
metrics under the scalar assumption.

The key feature of a group trust metric is that it calculates a trust
value for all the nodes in the graph at once, rather than
calculating independently the trust value independently for each
node. Thus, a successful attack causing one bad node to be trusted
need not necessarily result in catastrophic compromise of the trust
metric. Indeed, in this chapter we will present a simple trust metric,
also based on max-flow over the trust graph, which has significantly
better attack resistance than the theoretical best-case for scalar
trust metrics.

To achieve attack-resistance, a group trust metric must sacrifice the
monotonicity property - if the algorithm accepts a set of nodes $S$ for
graph $G$, then for a graph consisting of $G$ plus additional edges, the
set of nodes accepted may not be a superset of $S$. Otherwise, the
attack mentioned in Section~\ref{TODO} would be feasible.

However, for the trust metric presented below, a weaker monotonicity
property does hold. As edges are added to the graph, the \emph{number}
of nodes accepted increases monotonically. As we will show in
Section~\ref{TODO}, this weaker monotonicity property fits some
applications well, particularly those based on finding a majority or
other consensus from the nodes accepted by the trust metric.

\section{The Advogato network-flow trust metric}

Capacity constrained flow network.

Capacities of nodes are set as a function of distance from seed.

\includegraphics{cap}

\section{Comparison with Flake's Self-Organization work}

The Advogato trust metric is quite similar to the Exact-Flow-Commnuity
algorithm designed to discover communities existing on the
Web\cite{flake02self-organization}. Similarities include infinite flow
to the seeds, finite, bounded capacities for the intermediate graph,
unit capacity edges from all nodes to a supersink, and reaping of flow
through these edges after a max-flow computation to determine
membership in a community. The differences are worth noting:

\begin{itemize}

\item Exact-Flow-Community makes all edges bidirectional.

\item Advogato places capacity constraints on nodes, while
Exact-Flow-Community places capacity constraints on edges.

\item Advogato uses distance from the seed to assign capacities, while
Exact-Flow-Community uses a single constant capacity $k$ for all
intermediate graph edges.

\end{itemize}

The goals of Exact-Flow-Community and Advogato are somewhat
different. The former is intended primarily to identify existing
communities, based on patterns in Web links. Advogato also defines a
community, but with the specific goal of attack resistance, in other
words ensuring that an attacker cannot add an arbitrary number of
false nodes to the true community.

For this goal, preserving the directionality of edges is crucial.
Edges from bad nodes to good may be under the attacker's control, but
edges from good nodes to bad are assumed not to be. Failure to
distinguish between the two clearly leads to a loss of attack
resistance.

Similarly, as described in Section~\ref{tmetric-quant}, constraining
node capacities yields better attack resistance than constraining edge
capacities.

The relative significance of the two capacity assignment strategies is
harder to determine. Advogato uses capacities dependent on the
distance from the seed to accept a large number of nodes, even when
the number of seed nodes (and their total outdegree) is small. The
Exact-Flow-Community algorithm does not have this property. Thus, the
authors propose an Approximate-Flow-Community algorithm that
heuristically adds more seeds, then computes Exact-Flow-Community over
this augmented seed set. It is quite plausible the results are similar
to Advogato's, but we have not tested this hypothesis.