There are a few ways that people get recommended on social networks.
One, as you guessed, is that you allow access to your contact list, through your email account.
Another, is that someone else may have given them access to their contact list, and you may be on it.
Initially, that person would be given the opportunity to add or invite you, first, but if they don't, you might be offered the opportunity, later on, to add them. The fact that there is a relationship between the 2 of you, has already been established through their email contact list, and the site now knows this.
This is a rather nasty underhanded thing for social networks to do, but any social network that encourages you to share your contact list with them, must be assumed to be doing this, since most do.
People really need to stop sharing their data with sites in this way, because the privacy implications affect other people as you have been a witness to.
About the only way you can control things and prevent other people from sharing your data in a way that connects the 2 of you on their site is to sign up for each social network with a brand new email address that is used only for signing up for social networks. It won't be in anybody else's contact list.