# [Cryptography] graph theory and sybil attack

jamesd at echeque.com jamesd at echeque.com
Thu Jul 11 04:12:14 EDT 2019

```On 2019-07-05 7:13 pm, Jerry Leichter wrote:
> - Finding groups of nodes that are strongly-connected to each other but weakly connected to the rest of the graph is a generalization of the clique-finding problem (finding maximal groups of nodes that are fully connected to each other).  Finding cliques is NP-complete.  This very strongly suggests that the problem you suggest is as well.

Most NP complete problems have approximate or near optimal solutions
that are merely polynomial, and/or solutions that in some real world
application reliably and rapidly converge to optimal solutions for the
kind of data that usually turns up in that real world application.  This
is related to the smart car problem, where 99.99% of the time the car is
smart, smarter than a human driver, because it rapidly and efficiently
comes up with good solution to an NP complete problem, and it only
idiotically and blindly kills someone 0.01% of the time.

> - It's not clear that this algorithm really solves the problem you set out to solve!  There are going to be a lot of naturally-occurring, legitimate groups of nodes in a network of buyers.  Consider fans of a particular not very widely known musician in a network that sells recordings and allows reviews of songs and shows.  Can you distinguish a group of legitimate fans from an artificial group trying to make the musician look more popular?

Legitimate fans are likely to be fans of other musicians as well, and
likely to have genuine interactions with fans of other musicians.

So, is this musician connected to graph as a whole through fan/fan
interactions.
```