Graph clustering

One or more computer-readable storage media storing instructions that, when executed by one or more server devices, cause the one or more server devices to implement a clustering tool configured to:

• obtain an undirected bipartite graph that connects entities to relationships of the entities using undirected edges between vertices that represent the entities and vertices that represent the relationships;
• create a directed graph by replacing the undirected edges in the undirected graph with directed edges;
• assign directional weights to the directed edges;
• construct an auxiliary bipartite graph from the directed graph by connecting the vertices representing an entity to an arbitrary sink vertex;
• select one of the entities as a target;
• employ a minimum-cut algorithm on the target to obtain a cluster having a set of vertices on a side of the cut that includes the target.

A computing system comprising:

• one or more processors;
• and
• computer readable storage media having one or more modules stored thereon, that, when executed via the one or more processors, cause the computing system to perform acts including:
• obtaining a participation graph that includes vertices representing advertisers and edges connecting vertices when advertisers represented by the vertices participate in the same auctions for ad space from a service provider;
• constructing an auxiliary graph based on the participation graph, the auxiliary graph being a bipartite graph based on the participation graph and modified to include directed edges having directional weights;
• determining clusters by solving an objective function defined for the auxiliary graph;
• and
• translating the clusters determined for the auxiliary graph to clusters corresponding to the participation graph.