I would say either with spam mass estimation (http://infolab.stanford.edu/~zoltan/publications/gyongyi2006link-tr.pdf) or anti-trust rank (http://i.stanford.edu/~kvijay/krishnan-raj-airweb06.pdf)

Both are pagerank-like algos but here having a high-value means bad.

However, these black-lists aren't the solution imo, because updating them costs more than creating a new npub for the attacker.

Conversely, white-lists are the way to go, because the cost is on the attacker (work hard to be included in such lists). 

 We could set up a special purpose relay and post various labels there, like nostr.build's content-moderation labels or "profiles with 'replyguy wss' mentioned". Ideally clients would let users choose which labelling pubkeys to pay attention to, and then would use the labels to filter stuff. Relays could use it too, but that's a bit trickier. 

I also agree that it's much easier to make blacklists explode than to get spammer's pubkey into a "trusted" status (whitelist). We could publish "trusted" labels in the same way on special purpose relays.