Back to results
US 10,650,047 B2Granted
Dense subgraph identification
AssigneeInternational Business Machines Corporation
InventorHiroki Yanagisawa
Life of this patent
Estimating the term…
Abstract
Embodiments are directed to a computer implemented method of analyzing a graph having a plurality of vertices and edges to identify a subgraph of the graph, wherein the subgraph includes an exact subset. The method includes applying, by a first processor, a heuristic analysis to the graph to determine an initial subset of the graph. The method further includes applying, by either the first processor or a second processor, an exact analysis to the initial subset to determine an exact subset of the initial subset.
Claims17
A computer implemented method comprising:
- performing, using a first processor, operations configured to generate a computer model of a system;
- wherein the computer model identifies relationships between objects of the system;
- wherein the system is selected from a group consisting of a physical system, a biological system, a social system, an information systems, and a social network system;
- and
- wherein the operations include:
- generating a graph (G) having a plurality of vertices (V) and edges (E);
- and
- analyzing the graph to identify a subgraph (S) of vertices (V′) of the graph;
- wherein the subgraph comprises an exact subset;
- wherein analyzing the subgraph comprises:
- applying, by said first processor, a heuristic analysis to the graph to determine an initial subset of the graph;
- and
- applying, by either said first processor or a second processor, an exact analysis to said initial subset to determine an exact subset of said initial subset;
- wherein said exact subset of said initial subset comprises a dense subset of the graph;
- wherein applying said exact analysis comprises applying a density function comprising:
- a function e[S] divided by |S|a;
- wherein, in the function e[S], e comprises a number of the edges (E), and the function e[S] comprises a number of the edges (E) in S;
- and
- wherein the superscript parameter a in the density function comprises a fixed parameter set to be greater than or equal to one (1) or less than or equal to two (2).
16 more elements
A computer system comprising:
- a first processor configured to perform operations configured to generate a computer model of a system;
- wherein the computer model identifies relationships between objects of the system;
- wherein the system is selected from a group consisting of a physical system, a biological system, a social system, an information systems, and a social network system;
- and
- wherein the operations include:
- generating a graph (G) having a plurality of vertices (V) and edges (E);
- and
- analyzing the graph to identify a subgraph (S) of vertices (V′) of the graph;
- wherein the subgraph comprises an exact subset;
- wherein analyzing the subgraph comprises:
- using the first processor to apply a heuristic analysis to the graph to determine an initial subset of the graph;
- and
- using either said first processor or a second processor to apply an exact analysis to said initial subset to determine an exact subset of said initial subset;
- wherein said exact subset of said initial subset comprises a dense subset of the graph;
- wherein applying said exact analysis comprises applying a density function comprising:
- a function e[S] divided by |S|a;
- wherein, in the function e[S], e comprises a number of the edges (E), and the function e[S] comprises a number of the edges (E) in S;
- and
- wherein the superscript parameter a in the density function comprises a fixed parameter set to be greater than or equal to one (1) or less than or equal to two (2).
16 more elements
A computer program product comprising:
- a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions being readable by a processor circuit to cause the processor circuit to perform a method comprising:
- performing, using a first processor of the processor circuit, operations configured to generate a computer model of a system;
- wherein the computer model identifies relationships between objects of the system;
- wherein the system is selected from a group consisting of a physical system, a biological system, a social system, an information systems, and a social network system;
- and
- wherein the operations include:
- generating a graph (G) having a plurality of vertices (V) and edges (E);
- and
- analyzing the graph to identify a subgraph (S) of vertices (V′) of the graph;
- wherein the subgraph comprises an exact subset;
- wherein analyzing the subgraph comprises:
- applying, by the first processor, a heuristic analysis to the graph to determine an initial subset of the graph;
- and
- applying, by either said first processor or a second processor of the processor circuit, an exact analysis to said initial subset to determine an exact subset of said initial subset;
- wherein said exact subset of said initial subset comprises a dense subset of the graph;
- wherein applying said exact analysis comprising applying a density function comprising:
- a function e[S] divided by |S|a;
- wherein, in the function e[S], e comprises a number of the edges (E), and the function e[S] comprises a number of the edges (E) in S;
- and
- wherein the superscript parameter a in the density function comprises a fixed parameter set to be greater than or equal to one (1) or less than or equal to two (2).
17 more elements
Dependencies are inferred from the claim text.