Systems and methods for generating a dense graph

• US 9,652,875 B2
• Filed: 10/28/2013
• Issued: 05/16/2017
• Est. Priority Date: 10/29/2012
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Ravikumar, Shanmugasundaram, Vassilvitskii, Sergei, Bahmani, Bahman
• Primary Examiner(s): Tryder, Gregory J
• Assistant Examiner(s): Le, Michael
• Application Number:
  US14/065,108
• Publication Number:
  US 20140118355A1
• Time in Patent Office: 1,296 Days
• Field of Search: 345440
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

Methods and systems for generating a dense graph are described. One of the methods includes receiving a graph and computing a threshold to apply to the graph. The method further includes determining whether the graph includes a first set of at least one node, determining whether a second set of at least one node from the first set meets the threshold, and removing the at least one node of the second set concurrently from the graph upon determining that the at least one node of the second set meets the threshold. The operation of removing is performed to generate an updated graph. The method includes determining whether a density of the updated graph is greater than a density of the graph and replacing the graph within the updated graph upon determining that the density of the updated graph is greater than the density of the density of the graph.

Claims

1. A method for generating a dense graph, the method comprising:

(a) receiving a graph;

(b) calculating a density of the graph;

(c) computing a threshold to apply to the graph, the threshold including the density of the graph;

(d) determining whether the graph includes a first set of at least one node;

(e) determining whether a second set of at least one node from the first set meets the threshold;

(f) removing the at least one node of the second set from the graph upon determining that the at least one node of the second set meets the threshold, wherein the removing is performing to generate an updated graph;

(g) determining whether a density of the updated graph is greater than a density of the graph;

(h) replacing the graph with the updated graph upon determining that the density of the updated graph is greater than the density of the graph calculated during execution of the method;

(i) controlling a number of iterations of the method by changing a multiple of the density of the graph, wherein the multiple is greater than one,

wherein the method is executed by one or more processors.

2. The method of claim 1, wherein the graph includes an undirected graph or a directed graph.

3. The method of claim 1, wherein each node includes a network node, a web account, a web page, a web site, or a gene.

4. The method of claim 1, wherein computing the threshold comprises determining the multiple of the density of the graph.

5. The method of claim 1, wherein the density of the graph is equal to a ratio of size of edges within the graph to a size of nodes in the graph.

6. The method of claim 1, wherein the at least one node of the second set includes two or more nodes, wherein the two or more nodes of the second set include a first node and a second node, wherein determining whether the second set meets the threshold comprises determining whether the two or more nodes of the second set meet the threshold, wherein determining whether the two or more nodes of the second set meet the threshold comprises concurrently determining by a first one of the one or more processors and a second one of the one or more processors whether the two or more nodes of the second set meet the threshold, wherein the first processor determines whether a degree of the first node is less than or equal to the threshold, wherein the second processor determines whether a degree of the second node is less than or equal to the threshold.

7. The method of claim 1, wherein the at least one node of the second set includes two or more nodes, wherein the two or more nodes of the second set include a first node and a second node, wherein removing the at least one node of the second set comprises removing the two or more nodes of the second set concurrently, wherein removing the two or more nodes of the second set comprises deleting by a first one of the one or more processors the first node from the graph simultaneous with deleting by a second one of the one or more processors the second node from the graph.

8. The method of claim 1, further comprising (i) repeating (a) thru (h) by using the updated graph instead of the graph upon determining that the density of the updated graph is greater than the density of the graph.

9. The method of claim 1, wherein the at least one node of the second set includes two or more nodes, wherein removing the at least one node of the second set comprises removing two or more nodes of the second set, wherein removing the two or more nodes comprises removing a constant fraction of nodes from the graph during each iteration of the method.

10. The method of claim 1, further comprising determining whether a size of nodes of the updated graph is greater than a size of nodes of the graph, wherein the replacing the graph with the updated graph is performed upon determining that the size of the nodes of the updated graph is greater than the size of the nodes of the graph.

11. The method of claim 1, wherein the graph includes a directed graph that includes a From group of nodes and a To group of nodes, wherein computing the threshold comprises calculating a ratio of a size of edges from the From group to the To group and a size of the nodes within the To group.

12. The method of claim 1, wherein the graph includes a directed graph that includes a From group of nodes and a To group of nodes, wherein determining whether the graph includes the first set of at two nodes comprises determining whether the From group includes at least one node and the To group includes at least one node.

13. The method of claim 1, wherein the graph includes a directed graph that includes a From group of nodes and a To group of nodes, wherein the at least one node of the second set includes two or more nodes, wherein the two or more nodes of the second set include a first node and a second node, the first node belonging to the From group, the second node belonging to the To group, wherein the threshold includes a first threshold, wherein determining whether the second set meets the threshold comprises determining by a first one of the one or more processors whether an outdegree of the first node meets the first threshold, wherein determining whether the outdegree of the first node meets the first threshold is performed concurrently with determining by a second one of the one or more processors whether an indegree of the second node meets a second threshold.

14. The method of claim 1, wherein the at least one node of the second set includes two or more nodes, wherein the two or more nodes of the second set include a first node and a second node, wherein the graph includes a directed graph that includes a From group of nodes and a To group of nodes, the updated graph including an updated From group of nodes and an updated To group of nodes, wherein removing the at least one node of the second set comprise removing two or more nodes of the second set, wherein removing the two or more nodes of the second set comprises deleting the first node from the From group simultaneous with deleting the second node from the To group, wherein the deleting the first node from the From group is performed to generate the updated From group and the deleting the second node from the To group is performed to generate the updated To group.

15. The method of claim 1, wherein the graph includes a directed graph that includes a From group of nodes and a To group of nodes, wherein the updated graph includes a directed graph that includes an updated From group of nodes and an updated To group of nodes, wherein the density of the directed graph is equal to a ratio of size of edges within the directed graph to a size of a geometric mean of sizes of nodes within the From and To groups, wherein the density of the updated graph is equal to a ratio of size of edges within the updated graph to a size of a geometric mean of sizes of nodes within the updated From and To groups.

16. The method of claim 1, wherein the graph includes a directed graph that includes a From group of nodes and a To group of nodes, wherein the updated graph includes a directed graph that includes an updated From group of nodes and an updated To group of nodes, wherein replacing the graph with the updated graph includes replacing the From group with the updated From group and the To group with the updated To group.

17. A system for determining a subgraph within a graph, the system comprising:

a memory device configured to receive the graph;

one or more processors configured to;

(a) calculate a density of the graph;

(b) compute a threshold to apply to the graph, the threshold including the density of the graph;

(c) determine whether the graph includes a first set of at least one node;

(d) determine whether a second set of at least one node from the first set meets the threshold;

(e) remove the at least one node of the second set from the graph upon determining that the at least one node of the second set meets the threshold, wherein the removal is performed to generate an updated graph;

(f) determine whether a density of the updated graph is greater than a density of the graph;

(g) replace the graph within the updated graph upon determining that the density of the updated graph is greater than the density of the graph calculated in (b); and

(h) control a number of iterations of the method by changing a multiple of the density of the graph, wherein the multiple is greater than one.

18. The system of claim 17, wherein the at least one node of the second set includes two or more nodes, wherein the two or more nodes of the second set include a first node and a second node, wherein the one or more processors include a first processor and a second processor, the first and second processors configured to concurrently determine whether the two or more nodes of the second set meet the threshold, wherein the first processor determines whether a degree of the first node is less than or equal to the threshold, wherein the second processor determines whether a degree of the second node is less than or equal to the threshold.

19. The system of claim 17, wherein each node includes a network node, a web account, a web page, a web site, or a gene.

20. A non-transitory computer-readable medium having instructions for causing a computer to execute a method comprising:

(a) receiving a graph;

(b) calculating a density of the graph;

(c) computing a threshold to apply to the graph, the threshold including the density of the graph;

(d) determining whether the graph includes a first set of at least one node;

(e) determining whether a second set of at least one node from the first set meets the threshold;

(f) removing the at least one node of the second set from the graph upon determining that the at least one node of the second set meets the threshold, wherein said removing is performed to generate an updated graph;

(g) determining whether a density of the updated graph is greater than a density of the graph;

(h) replacing the graph within the updated graph upon determining that the density of the updated graph is greater than the density of the graph calculated during execution of the method; and

(i) controlling a number of iterations of the method by changing a multiple of the density of the graph, wherein the multiple is greater than one.