[Cryptography] graph theory and sybil attack

Jerry Leichter leichter at lrw.com
Fri Jul 5 07:13:25 EDT 2019

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.

- 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?
                                                        -- Jerry

More information about the cryptography mailing list