Sybil
attacks are the fundamental problem in peer-topeer
and other distributed systems. In a Sybil
attack, a malicious attacker creates multiple fake
identities to influence the working of systems
that depend on open membership, such as recommendation
and delivery systems. Recently, a
number of social network-based schemes, such
as SybilGuard, Sybillimit, SybilInfer, and SumUp,
have been proposed to mitigate Sybil attacks.
Viswanath et al. [19] develop a deep understanding
of these approaches. It shows that existing
Sybil defense schemes, which can be viewed as
graph partitioning algorithms, work by identifying
local communities (i.e., clusters of nodes
more tightly knit than the rest of the graph)
around a trusted node. Therefore, the substantial
amount of prior research on general community
detection algorithms can be used to design
effective and novel Sybil defense schemes.