# US 2021/0279260 A1 · Method and system for identifying at least one community in a dataset comprising a plurality of elements > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0279260 A1 - Document ID: US20210279260A1 - Status: Published application - Kind: A1 - Application number: 17/254,661 - Filed: 2019-06-20 - Published: 2021-09-09 - Earliest claimed: 2018-06-22 - Assignees: 1Qb Information Technologies Inc. - Applicants: 1Qb Information Technologies Inc. - Inventors: Jaspreet S. OBEROI; Sourav MUKHERJEE; Clemens ADOLPHS; Ehsan ZAHEDINEJAD; Daniel J. CRAWFORD - Web page: https://patentgrep.com/patent/US20210279260A1 ## CPC - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F 16/285: {Clustering or classification} - G06Q 10/40: Business processes related to social networking or social networking services - G06Q 30/0201: Market modelling; Market analysis; Collecting market data - H04W 4/21: for social networking applications - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) ## Abstract A method and a system are disclosed for identifying at least one community, the method comprising providing an indication of a graph, the graph comprising a plurality of nodes and edges, wherein each node is representative of a given element and each edge is representative of a relationship between two given elements; providing a metric indicative of an underlying community detection algorithm; obtaining an indication of an upper bound value for a given maximum number of communities to identify; encoding each node using a one-hot encoding method and the indication of an upper bound value; generating a quadratic unconstrained binary optimization problem using the metric and the encoded nodes; providing the generated quadratic unconstrained binary optimization problem to an optimization oracle and obtaining a solution. ## Claims ### Claim 1 A method for identifying at least one community in a dataset comprising a plurality of elements, the method comprising: providing, using a digital computer, an indication of a graph, the graph comprising a plurality of nodes and edges, wherein each node is representative of a given element and each edge is representative of a relationship between two given elements of the dataset: providing, using the digital computer, a metric indicative of an underlying community detection algorithm; obtaining, using the digital computer, an indication of an upper bound value for a given maximum number of communities to identify in the dataset; encoding, using the digital computer, each node of the graph using a one-hot encoding method and the indication of an upper bound value for the given maximum number of communities to identify in the dataset; generating, using the digital computer, a quadratic unconstrained binary optimization problem using the metric indicative of an underlying community detection algorithm and the encoded nodes of the graph; providing, using the digital computer, the generated quadratic unconstrained binary optimization problem to an optimization oracle; obtaining, using the digital computer, a solution to the generated quadratic unconstrained binary optimization problem from the optimization oracle, the solution being indicative of the identified communities in the dataset; and providing, using the digital computer, an indication of the identified communities in the dataset. ### Claim 2 (depends on 1) The method as claimed in claim 1, wherein the providing of the indication of a graph comprises at least one of obtaining the indication of a graph from a remote processing unit operatively coupled to the digital computer, obtaining the indication of a graph from a memory unit of the digital computer and obtaining the indication of a graph from a user interacting with the digital computer. ### Claim 3 (depends on 1) The method as claimed in claim 1, wherein the providing of the indication of a graph comprises providing a dataset comprising a plurality of elements and generating a graph representative of the dataset. ### Claim 4 (depends on 1) The method as claimed in claim 1, wherein the providing of the indication of the identified communities in the dataset comprises at least one of providing the indication of the identified communities to a remote processing unit operatively coupled with the digital computer, saving the indication of the identified communities in a memory unit of the digital computer and displaying the indication of the identified communities to a user interacting with the digital computer. ### Claim 5 (depends on 1) The method as claimed in claim 1, wherein the metric indicative of an underlying community detection algorithm comprises at least one of a modularity metric and a frustration metric. ### Claim 6 A digital computer comprising: a central processing unit; a display device; a communication port for operatively connecting the digital computer to an optimization oracle comprising a quantum processor; a memory unit comprising an application for identifying at least one community in a dataset comprising a plurality of elements, the application comprising: instructions for providing an indication of a graph, the graph comprising a plurality of nodes and edges, wherein each node is representative of a given element and each edge is representative of a relationship between two given elements of the dataset; instructions for providing a metric indicative of an underlying community detection algorithm; instructions for obtaining an indication of an upper bound value for a given maximum number of communities to identify in the dataset; instructions for encoding each node of the graph using a one-hot encoding method and the indication of an upper bound value for the given maximum number of communities to identify in the dataset; instructions for generating a quadratic unconstrained binary optimization problem using the metric indicative of an underlying community detection algorithm and the encoded nodes of the graph; instructions for providing the generated quadratic unconstrained binary optimization problem to an optimization oracle; instructions for obtaining a solution to the generated quadratic unconstrained binary optimization problem from the optimization oracle, the solution being indicative of the identified communities in the dataset; and instructions for providing an indication of the identified communities in the dataset. ### Claim 7 A non-transitory computer readable storage medium for storing computer-executable instructions which, when executed, cause a digital computer to perform a method for identifying at least one community in a dataset comprising a plurality of elements, the method comprising: providing an indication of a graph, the graph comprising a plurality of nodes and edges, wherein each node is representative of a given element and each edge is representative of a relationship between two given elements of the dataset; providing a metric indicative of an underlying community detection algorithm; obtaining an indication of an upper bound value for a given maximum number of communities to identify in the dataset; encoding each node of the graph using a one-hot encoding method and the indication of an upper bound value for the given maximum number of communities to identify in the dataset; generating a quadratic unconstrained binary optimization problem using the metric indicative of an underlying community detection algorithm and the encoded nodes of the graph; providing the generated quadratic unconstrained binary optimization problem to an optimization oracle; obtaining a solution to the generated quadratic unconstrained binary optimization problem from the optimization oracle, the solution being indicative of the identified communities in the dataset; and providing an indication of the identified communities in the dataset. ### Claim 8 A method for identifying at least one community in a dataset comprising a plurality of elements, the method comprising: providing an indication of a graph, the graph comprising a plurality of nodes and edges, wherein each node is representative of a given element and each edge is representative of a relationship between two given elements of the dataset; providing a metric indicative of an underlying community detection algorithm; obtaining an indication of an upper bound value for a given maximum number of communities to identify in the dataset; encoding each node of the graph using a one-hot encoding method and the indication of an upper bound value for the given maximum number of communities to identify in the dataset; generating a quadratic unconstrained binary optimization problem using the metric indicative of an underlying community detection algorithm and the encoded nodes of the graph; providing the generated quadratic unconstrained binary optimization problem to an optimization oracle; solving the generated quadratic unconstrained binary optimization problem using the optimization oracle to provide a solution to the generated quadratic unconstrained binary optimization problem, the solution being indicative of the identified communities in the dataset; and providing an indication of the identified communities in the dataset. ### Claim 9 (depends on 1) The method as claimed in claim 1, wherein the graph is one of a signed graph and a general graph. ### Claim 10 (depends on 6) The digital computer comprising the application as claimed in claim 6, wherein the graph is one of a signed graph and a general graph. ### Claim 11 (depends on 7) The non-transitory computer readable storage medium for storing computer-executable instructions as claimed in claim 7, wherein the graph is one of a signed graph and a general graph. ### Claim 12 (depends on 1) The method as claimed in claim 1, wherein the optimization oracle comprises a quantum annealer.