The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 28, 2023
Filed:
Feb. 14, 2018
Google Llc, Mountain View, CA (US);
Alessandro Epasto, New York, NY (US);
Renato Purita Paes Leme, Brooklyn, NY (US);
Silvio Lattanzi, Zurich, CH;
GOOGLE LLC, Mountain View, CA (US);
Abstract
The present disclosure provides a new framework and associated techniques, referred to herein as 'ego-splitting,' that enable the detection of clusters in graphs that are descriptive of networks, including highly complex networks. Ego-splitting leverages local structures within a graph known as ego-nets to de-couple overlapping clusters. For example, an ego-net can be the subgraph induced by the neighborhood of each node. Ego-splitting is a highly scalable and flexible framework, with provable theoretical guarantees. Ego-splitting reduces the complex overlapping clustering problem to a simpler and more amenable non-overlapping (also known as partitioning) problem. Ego-splitting enables the scaling of community detection to graphs with tens of billions of edges and outperforms previous solutions.