US Patent 11074274 Large scale social graph segmentation

A method of complementary clustering of a vast population of objects is disclosed. The method aims at maximizing a global measure of object affinity within naturally-formed clusters. A first clustering procedure produces primary centroids of clusters of objects and a second clustering procedure produces secondary clusters of the primary centroids and corresponding secondary centroids. Refined clusters of the population of objects are formed based on object proximity to the secondary centroids. The first clustering procedure is preferably based on a variation of the K-means method, and the second clustering procedure is preferably based on the Density-Based Spatial Clustering of Applications with Noise (DBSCAN). An apparatus implementing the method is devised to facilitate conflict-free parallel processing.