Estimating influence using sketches

Patent metadata

Field	Value
Publication number	US-9443034-B2
Application number	US-201414290209-A
Country	US
Kind code	B2
Filing date	May 29, 2014
Priority date	May 29, 2014
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

A graph that includes multiple nodes and edges is received. Multiple instances of the graph are generated by randomly instantiating the edges according to either a binary independent cascade model or a randomized edge length independent cascade model. Where the binary independent cascade model is used, combined reachability sketches are generated for each node across all instances of the graph. Where the randomized edge length independent cascade model is used, combined all-distances sketches are generated for each node across all instances of the graph. Depending on which model is used, the combined reachability or all-distances sketches are used to estimate the influence of nodes in the graph or to estimate a subset of nodes from a graph of a specified size with a maximum influence using a greedy algorithm.

First claim

What is claimed:

1. A method comprising:
receiving a plurality of sketches by a computing device, wherein each sketch is associated with a node of a plurality of nodes of a graph;
receiving an influence query for a subset of the plurality of nodes of a specified size having a maximum influence by the computing device, wherein the influence query is a query for an estimate of the subset of nodes of the plurality of nodes of the specified size with a maximum combined influence, wherein the influence of a node is a measure of how connected the node in the graph is to the other nodes of the graph;
determining a first node of the plurality of nodes that when added to the subset of the plurality of nodes increases an influence of the subset of the plurality of nodes by a greatest amount using the sketch associated with the first node and the sketches associated with the nodes in the subset of the plurality of nodes by the computing device;
adding the determined first node to the subset of the plurality of nodes by the computing device;
determining that the subset of the plurality of nodes is of the specified size by the computing device; and
in response to the determination, providing the subset of the plurality of nodes by the computing device.

2. The method of claim 1 , wherein each sketch is one or more of an all-distances sketch or a reachability sketch.

3. The method of claim 1 , further comprising:
determining that the subset of the plurality of nodes is less than the specified size;
determining an additional node of the plurality of nodes that when added to the subset of the plurality of nodes increases the influence of the subset of the plurality of nodes by a greatest amount using the sketch associated with the additional node and the sketches associated with the nodes in the subset of the plurality of nodes, wherein the additional node is different from the first node; and
adding the determined additional node to the subset of the plurality of nodes.

4. The method of claim 1 , further comprising determining the influence of the nodes of the subset of nodes based on a union of the sketches associated with each of the nodes in the subset of the plurality of nodes.

5. A system comprising:
a computing device; and
an influence engine adapted to:
receive a graph comprising a plurality of nodes;
for each node of the graph, compute a sketch;
receive an influence query for a subset of the plurality of nodes of a specified size having a maximum influence, wherein the influence query is a query for an estimate of the subset of nodes of the plurality of nodes of the specified size with a maximum combined influence, wherein the influence of a node is a measure of how connected the node in the graph is to the other nodes of the graph;
determine a first node of the plurality of nodes that when added to the subset of the plurality of nodes increases an influence of the subset of the plurality of nodes by a greatest amount using the sketch computed for the first node and the sketches computed for the nodes in the subset of the plurality of nodes;
add the determined first node to the subset of the plurality of nodes;
determine that the subset of the plurality of nodes is of the specified size; and
in response to the determination, providing the subset of the plurality of nodes in response to the influence query.

6. The system of claim 5 , wherein the influence engine is further adapted to:
determine that the subset of the plurality of nodes is less than the specified size;
determine an additional node of the plurality of nodes that when added to the subset of the plurality of nodes increases the influence of the subset of the plurality of nodes by a greatest amount using the sketch associated with the additional node and the sketches associated with the nodes in the subset of the plurality of nodes, wherein the additional node is different from the first node; and
add the determined additional node to the subset of the plurality of nodes.

7. The system of claim 5 , wherein the influence engine is further adapted to generate a plurality of instances from the graph, and the influence engine adapted to compute a sketch for a node comprises the influence engine adapted to:
compute a sketch for the node for each of the generated instances; and
combine the computed sketches for each of the generated instances.

8. The system of claim 5 , wherein each sketch is one or more of an all-distances sketch or a reachability sketch.

Assignees

• Microsoft Corp
• Microsoft Technology Licensing Llc

Inventors

• Werneck Renato F
• Delling Daniel
• Pajor Thomas
• Cohen Edith

Classifications

• G06F17/10 Primary

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F16/24569 Primary

  Query processing with adaptation to specific hardware, e.g. adapted for using GPUs or SSDs · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30519

  Physics · mapped topic