[Cryptography] graph theory and sybil attack

[jamesd at echeque.com]

On 2019-07-05 7:13 pm, Jerry Leichter wrote:
> Two comments:
> - 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.