Fast and accurate graphlet estimation
US11030246B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 10, 2016 |
| Grant date | Jun 8, 2021 |
| Priority date | — |
| Expiry date | Dec 25, 2038 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06N7/01
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Embodiments of the present invention provide a system for fast, accurate, and scalable unbiased graphlet estimation. The system utilizes neighborhood sampling and combinatorial relations to estimate graphlet counts, statistics, and frequency distributions in a small fraction of the computing time of existing systems. The obtained unbiased estimates are highly accurate, and have applications in the analysis, mining, and predictive modeling of massive real-world networks. During operation, the system obtains data indicating vertices and edges of a graph. The system samples a portion of the graph and counts a number of graph features in the sampled portion of the graph. The system then computes an occurrence frequency of a graphlet pattern and a total number of graphlets associated with the graphlet pattern in the graph.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.