A method of generating a centroid set of mutually repulsing centroids for segmenting a vast social graph is disclosed. Each object of a collection of tracked objects of the social graph is characterized by a respective descriptor vector of multiple descriptor types. Starting with an empty centroid set, an object joins the centroid set as a centroid upon ascertaining that an affinity measure of the object to each centroid of the centroid set is less than a specified affinity threshold. The affinity threshold may be tuned to generate a target number of centroids. The affinity measure may be a dual radial-angular affinity measure. Rather than selecting the centroids from the collection of objects, a distribution function of descriptors of each descriptor type may be determined, candidate descriptor vectors may be generated by random sampling of each distribution, and a candidate descriptor vector joins the centroid set upon satisfying affinity conditions.
展开▼
