I know that Google penalizes sites that participate in link schemes. I imagine PLNs are very easy to detect, but like if someone contacts another website that that doesn’t publicly offer guest posting or some obvious giveaway like that, how would Google know?
2 Answers
In general they don't know and guess based on more or less obvious indicators.
There is plenty of false positives (punishing innocent pages) and false negatives (failing to detect some of manipulations).
Exact methods will vary, even if Google would leak/document/imply something it is liable to quickly change.
There are a few different methods to identify linkspam networks.
I have checked several SEO tools and one way is to filter out pages from the same IP. If you build up a large amount of links in a short time from a network of sites with the same IP, Google will know.
The second method is to look at the link patterns. You can easily see if a website has outgoing spam links in every article that do not add any value. I can personally look at a website and can see if a page is selling links or has another intention. Sometimes you get lists from linkbrokers. If this list is redirected to Google, the page will be scrutinized. All these factors come together.
