US 8,949,237 B2Granted

Detecting overlapping clusters

AssigneeMicrosoft Corporation

InventorsMaria Florina Balcan, Christian H. Borgs, Mark Braverman, Jennifer T. Chayes, Shanghua Teng

Life of this patent

Estimating the term…

Loading patent…

Abstract

A technique for identifying overlapping clusters of items in a data set. The technique may be used in connection with a social network or other on-line environment in which users express approval for other users, such as through votes, tags or other inputs. These expressions of approval may be used to form clusters such that entities assigned to a cluster have a higher metric of approval from other entities within the cluster than from outside the cluster. Such clusters may be arrived at through a computationally efficient approach that involves randomly selecting one or more entities as a seed for a cluster. The cluster may be grown by testing other entities, similar to those already in the cluster, to determine whether they are more preferred by those already in the cluster than those outside the cluster. Once a cluster is grown to a desired size, it may be pruned.

Claims15

Dependent claims

At least one computer-readable memory, which is not a signal, comprising computer-executable instructions that, when executed by at least one processor, perform a method, the method comprising acts of:

receiving inputs relating to a plurality of entities in a set, each input indicating approval of an entity in the set for another entity in the set;
maintaining a database storing indications of approval associated with each of the plurality of entities in the set;
processing the database to determine one or more clusters in the set, the clusters each comprising entities for which a metric of approval of members within the cluster exceeds a metric of approval from entities in the set that are not in the cluster, the processing the database to determine one or more clusters in the set includes:
selecting an entity as a seed for the cluster;
adding entities to the cluster, the adding comprising iteratively:
for a candidate entity determining a fraction of indications of approval for the candidate entity received from entities within the cluster;
and
selectively adding the candidate entity based, at least in part, on the fraction being above a threshold;
and
after selectively adding the candidate item, selectively removing items from the cluster that do not meet at least one relatedness criteria;
and
presenting a suggestion, the suggestion relating to an action involving one or more entities and the suggestion being developed based on the one or more clusters such that the one or more entities are within at least one of the one or more clusters.

9 more elements

A method comprising:

receiving inputs relating to a plurality of entities in a set, each input indicating approval of an entity in the set for another entity in the set;
maintaining a database storing indications of approval associated with each of the plurality of entities in the set;
processing the database to determine one or more clusters in the set, the clusters each comprising entities for which a metric of approval of members within the cluster exceeds a metric of approval from entities in the set that are not in the cluster, the processing the database to determine one or more clusters in the set includes:
selecting an entity as a seed for the cluster;
adding entities to the cluster, the adding comprising iteratively:
for a candidate entity determining a fraction of indications of approval for the candidate entity received from entities within the cluster;
and
selectively adding the candidate entity based, at least in part, on the fraction being above a threshold;
and
after selectively adding the candidate item, selectively removing items from the cluster that do not meet at least one relatedness criteria;
and
presenting a suggestion, the suggestion relating to an action involving one or more entities and the suggestion being developed based on the one or more clusters such that the one or more entities are within at least one of the one or more clusters.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/345,593Filed 6 Jan 2012
Published: US 2013/0179449 A111 Jul 2013
Granted: 3 Feb 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06Q 10/10
Administration; Management: office automation; Time management
G06F 16/9535
Querying, e.g. by the use of web search engines: search customisation based on user profiles and personalisation
G06F 16/9536
Querying, e.g. by the use of web search engines: search customisation based on social or collaborative filtering
G06Q 10/42
Business processes related to social networking or social networking services: determination of affinities or common interests between users