In one embodiment, a device obtains certificate information for a plurality of network addresses. The device constructs, based on the certificate information, a bipartite graph that maps nodes representing common names from the certificate information to nodes representing autonomous systems. The device determines edge counts from the bipartite graph for the nodes representing the autonomous systems. The device identifies, based on the edge counts, a particular one of the common names as botnet-related by comparing edge counts for the autonomous systems associated with that particular common name to edge counts for the autonomous systems associated with one or more of the other common names.