ESTIMATING INFLUENCE USING SKETCHES

摘要

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.

主权项

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.