US 9,439,053 B2Granted

Identifying subgraphs in transformed social network graphs

AssigneeMicrosoft Technology Licensing, LLC

InventorsIttai Abraham, Joseph K. Bradley, Shiri Chechik, Moises Goldszmidt, Aleksandrs Slivkins, David Kempe

Life of this patent

Estimating the term…

Loading patent…

Abstract

A graph of a social network is received. The graph may include a node for each user account and an edge between nodes that represent social networking relationships such as messages between the user accounts or a friend relationship. The graph is transformed into a transformed graph where nodes have direct edges depending on a local test among its neighbors in the original graph. Small subsets of the transformed graph are categorized. The categories are used to identify subgraphs in the transformed graph. Each subgraph is grown by adding an edge from the transformed graph to the subgraph depending on local tests among nodes associated with the edge that have at least one edge that is already in the subgraph. The categorized subgraphs are used to provide targeted advertising, suggest new connections, identify different personalities and interests of users, or to provide other services.

Claims20

Dependent claims

A method comprising:

receiving a graph by a computing device through a network, the graph comprising a plurality of edges and a plurality of nodes;
generating a transformed graph from the received graph by the computing device by, for each pair of nodes of the plurality of nodes:
determining a threshold based on a degree of one of the nodes of the pair of nodes by the computing device;
determining if a number of paths in the graph between the pair of nodes exceeds the threshold by the computing device;
in response to determining that the number of paths in the graph between the pair of nodes exceeds the threshold, adding an edge between the pair of nodes to the transformed graph by the computing device;
and
in response to determining that the number of paths in the graph between the pair of nodes does not exceed the threshold, omitting the edge between the pair of nodes from the transformed graph by the computing device;
receiving a request for a distance between a first node in the received graph and a second node in the received graph by the computing device;
determining the distance between the first node and the second node using the transformed graph by the computing device;
and
providing the determined distance through the network as a response to the request by the computing device.

8 more elements

A method comprising:

receiving a graph by a computing device through a network, the graph comprising a plurality of edges and a plurality of nodes, wherein each edge of the plurality of edges is connected to a pair of nodes of the plurality of nodes;
identifying a plurality of subgraphs of the received graph by the computing device, wherein each subgraph includes a subset of the edges of the graph;
for each identified subgraph:
for each edge in the graph that is not in the subgraph:
determining a threshold based on a degree of one of the nodes of the pair of nodes associated with the edge in the graph by the computing device;
for the pair of nodes associated with the edge in the graph, determining if a number of paths between the pair of nodes in the graph that include an edge from the subgraph exceeds the threshold by the computing device;
in response to determining that the number of paths between the pair of nodes in the graph that include an edge from the subgraph exceeds the threshold, adding the edge in the graph to the identified subgraph by the computing device;
and
in response to determining that the number of paths between the pair of nodes in the graph that include an edge from the subgraph does not exceed the threshold, omitting the edge in the graph from the identified subgraph by the computing device;
and
providing the subgraphs in response to the received graph through the network by the computing device.

8 more elements

Dependencies are inferred from the claim text.