Dense subgraph identification

1. 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).

2. The computer implemented method of claim 1 , wherein said heuristic analysis comprises a greedy algorithm.

3. The computer implemented method of claim 1 , wherein said exact analysis comprises a fractional programming technique.

4. The computer implemented method of claim 1 , wherein the operations further include setting, by either said first processor or said second processor, a parameter t to a value within a predetermined range of values.

5. The computer implemented method of claim 4 , wherein said parameter t impacts:

a quality level of said exact subset of said initial subset; and

a speed at which the method is implemented.

6. The computer implemented method of claim 4 , wherein said predetermined range of values comprises from three-hundred (300) to five-hundred (500).

7. 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).

8. The computer system of claim 7 , wherein said heuristic analysis comprises a greedy algorithm.

9. The computer system of claim 7 , wherein said exact analysis comprises a fractional programming technique.

10. The computer system of claim 7 , wherein the operations further include using either said first processor or said second processor to receive a parameter t, wherein said parameter has been set to a value within a predetermined range of values.

11. The computer system of claim 10 wherein said parameter t impacts:

a quality level of said exact subset of said initial subset; and

a speed at which the method is implemented.

12. The computer system of claim 10 , wherein said predetermined range of values comprises from three-hundred (300) to five-hundred (500).

13. 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).

14. The computer program product of claim 13 , wherein said heuristic analysis comprises a greedy algorithm.

15. The computer program product of claim 13 , wherein said exact analysis comprises a fractional programming technique.

16. The computer program product of claim 13 further comprising setting, by either said first processor or said second processor, a parameter t to a value within a predetermined range of values.

17. The computer program product of claim 16 wherein said parameter t impacts:

a quality level of said exact subset of said initial subset; and

a speed at which the method is implemented.