[Cryptography] graph theory and sybil attack

[John Denker]

On 7/3/19 6:02 PM, James A. Donald wrote in part:

> Page rank and analogous measures such as seller reputation are a 
> measure of connection to the graph as a whole, and the sibyl attack 
> is faking good connection to the graph as a whole by creating a 
> seemingly large subgraph that is well connected to itself but poorly 
> connected to the rest of the graph.

> It would be nice to be able to state this problem as a graph
> theoretic problem and to relate it to well known graph traversal
> algorithms.

Here's a closely related problem:

This arises in the context of communication networks.  The weak links
make the network vulnerable to partition, where some subgroup is
unable to communicate with the rest of the rest of the group, and
no amount of re-routing will fix the problem.  A milder version of
the problem manifests itself by congestion on the weak links.

This is in some ways the opposite problem, because there are no
"bad" nodes and you are trying to prevent a partition rather than
create a partition.  However, the mathematics of identifying the
relevant nodes and links is the same.

This has been verrrry heavily researched:
  https://scholar.google.com/scholar?q=network+routing+reliability+"graph+theory"+links+nodes+partition