I don't use social media like Facebook or Twitter, but most likely an app on my phone or others' phones sold my contact info. I try to avoid installing third-party apps. Since I began using smart phones, I could count the number on two hands. But it only takes one bad app, and there are plenty out there.
I don't doubt telco call logs are available on the black market, but apps are the simplest and most likely vector.
I'm rather skeptical of going after Google and other big tech companies for anti-trust violations. The web is a big place. But it's much easier to distinguish Google's control of Android and the Android app market, both from a technical and legal perspective. And Google has deliberately made it difficult to limit app data access. I remember the brief period where Android by default provided a prompt of requested permissions and the ability to uncheck them before installing. They removed it because few people made use of it, few apps worked correctly without all their requested permissions, and most importantly Google was no longer worried about privacy concerns hindering Android adoption. But with the current attention being given to data privacy I believe the public is finally prepared to make effective use of such a capability. But now Google has even less incentive to provide such a simple and transparent opt-out prompt, so fat chance they'll bring it back without being legally forced. Tripe fat chance they'll make any of those permissions opt-in.