Estimating influence using sketches

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.

What is claimed: 
     
         1 . A method comprising:
 receiving a graph comprising a plurality of nodes, by a computing device;   for each node of the graph, computing a sketch by the computing device;   receiving an influence query by the computing device, wherein the influence query is a query for one of (1) an estimate of an influence of a subset of nodes of the plurality of nodes or (2) an estimate of a subset of nodes of the plurality of nodes of a 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 result in response to the influence query using one or more of the computed sketches by the computing device; and   providing the determined result in response to the influence query 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 generating a plurality of instances from the graph, and computing a sketch for a node comprises:
 computing a sketch for the node for each of the generated instances; and   combining the computed sketches for each of the generated instances.   
     
     
         4 . The method of  claim 3 , wherein the combined computed sketches are combined all-distances sketches or combined reachability sketches. 
     
     
         5 . The method of  claim 3 , wherein the plurality of instances are randomly generated from the graph. 
     
     
         6 . The method of  claim 5 , wherein the graph further comprises a plurality of edges, and wherein randomly generating an instance of the graph comprises randomly assigning a value to each edge of the graph. 
     
     
         7 . The method of  claim 6 , wherein an assigned value is either a one or a zero. 
     
     
         8 . The method of  claim 6 , wherein an assigned value is any non-zero value. 
     
     
         9 . The method of  claim 1 , wherein the influence query identifies a subset of nodes from graph, and wherein determining the result in response to the influence query using one or more of the computed sketches comprises estimating an influence of the nodes of the subset of nodes using the sketches computed for each of the nodes in the subset of nodes. 
     
     
         10 . The method of  claim 9 , wherein the influence is estimated based on a union of the sketches computed for each of the nodes in the subset of nodes. 
     
     
         11 . The method of  claim 1 , wherein the influence query is a query for a subset of nodes from the graph of a specified size having a maximum influence, and determining the result in response to the influence query using one or more of the computed sketches comprises using a greedy algorithm to determine the subset of nodes. 
     
     
         12 . The method of  claim 11 , wherein using the greedy algorithm to determine the subset of nodes comprises:
 determining a node of the plurality of nodes that when added to the subset of nodes increases an influence of the subset of nodes by the greatest amount using the sketch computed for the determined node and the sketches computed for the nodes of the subset of nodes; and   adding the determined node to the subset of nodes.   
     
     
         13 . 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, wherein the influence query is a query for an estimate of an influence of a subset of nodes of the plurality of nodes, 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 result in response to the influence query using one or more of the computed sketches; and 
 provide the determined result in response to the influence query. 
   
     
     
         14 . The system of  claim 13 , wherein each sketch is one or more of an all-distances sketch or a reachability sketch. 
     
     
         15 . The system of  claim 13 , 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.   
     
     
         16 . The system of  claim 15 , wherein the plurality of instances are randomly generated from the graph. 
     
     
         17 . The system of  claim 16 , wherein the graph further comprises a plurality of edges, and wherein randomly generating an instance of the graph comprises randomly assigning a value to each edge of the graph. 
     
     
         18 . A method comprising:
 generating a plurality of instances from a graph comprising a plurality of nodes, by a computing device;   for each node of the graph, computing a sketch by the computing device, wherein computing a sketch for a node comprises computing a sketch for the node for each of the generated instances and combining the computed sketches for each of the generated instances;   receiving an influence query by the computing device, wherein the influence query is a query for an estimate of an influence of a subset of nodes of the plurality of node, 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 result in response to the influence query using one or more of the computed sketches by the computing device; and   providing the determined result in response to the influence query by the computing device.   
     
     
         19 . The method of  claim 18 , wherein the plurality of instances are randomly generated from the graph, wherein the graph further comprises a plurality of edges, and wherein randomly generating an instance of the graph comprises randomly assigning a value to each edge of the graph. 
     
     
         20 . The method of  claim 18 , wherein the influence query identifies a subset of nodes from graph, and wherein determining the result in response to the influence query using one or more of the computed sketches comprises estimating an influence of the nodes of the subset of nodes using the sketches computed for each of the nodes in the subset of nodes.