Estimating influence using sketches
US9443034B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 29, 2014 |
| Grant date | Sep 13, 2016 |
| Priority date | — |
| Expiry date | Nov 11, 2034 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/10
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.