[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