Patent application EP17174858A (EP), filed 2017-06-07
Publication number: EP3258604A1
Title: SYSTEM AND METHOD FOR COMPRESSING GRAPHS VIA CLIQUES
Abstract: Embodiments of the present invention provide a system for fast parallel graph compression based on identifying a set of large cliques, which is used to encode the graph. The system provides both permanently-stored and in-memory graph encoding and reduces the space needed to represent and store a graph, the I/O traffic to use the graph, and the computation needed to perform algorithms involving the graph. The system thereby improves computing technology and graph computation. During operation, the system obtains data indicating vertices and edges of a graph. The system executes a clique-finding method to identify a maximum clique in the graph. The system then removes the clique from the graph, adds the clique to a set of found cliques, and generates a compressed representation of the graph based on the set of found cliques.
IPC codes: G06F  17/    30            A I
H03M   7/    30            A I
Claims: number: 1
text: A computer-implemented method for compressing a representation of a graph, comprising:
number: 2
text: The method of claim 1, wherein generating the compressed representation of the graph further comprises replacing, in the graph, a respective clique in the set of found cliques with a clique pseudo-vertex.
number: 3
text: The method of claim 1, wherein the set of vertices belonging to the cliques in the set of found cliques is ordered such that:
number: 4
text: The method of claim 1, wherein identifying the maximum clique comprises:
number: 5
text: A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for compressing a representation of a graph, the method comprising:
number: 6
text: The computer-readable storage medium of claim 5, wherein generating the compressed representation of the graph further comprises replacing, in the graph, a respective clique in the set of found cliques with a clique pseudo-vertex.
number: 7
text: The non-transitory computer-readable storage medium of claim 5, wherein the set of vertices belonging to the cliques in the set of found cliques is ordered such that:
number: 8
text: The non-transitory computer-readable storage medium of claim 5, wherein identifying the maximum clique comprises:
number: 9
text: A computing system for compressing a representation of a graph, the system comprising:
number: 10
text: The computing system of claim 9, wherein generating the compressed representation of the graph further comprises replacing, in the graph, a respective clique in the set of found cliques with a clique pseudo-vertex.
Office action: search_report, dated 2017-12-20
Prior art cited: ref_id: US9171046B1
ref_type: patent
severity: background
ref_id: - SHAUN FALLAT ET AL: "Compressed cliques graphs, clique coverings and positive zero forcing", THEORETICAL COMPUTER SCIENCE, 28 August 2015 (2015-08-28), NL, XP055416282, ISSN: 0304-3975, DOI: 10.1016/j.tcs.2017.08.018
ref_type: npl
severity: background
ref_id: - ANNA C GILBERT ET AL: "Compressing Network Graphs", PROCEEDINGS OF THE LINKKDD WORKSHOP AT THE 10TH ACM CONFERENCE ON KDD, 1 August 1994 (1994-08-01), XP055094462
ref_type: npl
severity: background
ref_id: US2010083194A1
ref_type: patent
severity: background
ref_id: US2009315890A1
ref_type: patent
severity: background
ref_id: - T. FEDER ET AL: "Clique Partitions, Graph Compression and Speeding-Up Algorithms", JOURNAL OF COMPUTER AND SYSTEM SCIENCES, vol. 51, no. 2, 1 October 1995 (1995-10-01), pages 261 - 272, XP055094467, ISSN: 0022-0000, DOI: 10.1006/jcss.1995.1065
ref_type: npl
severity: background
ref_id: - ANONYMOUS: "Power graph analysis", WIKIPEDIA, 5 June 2016 (2016-06-05), XP055416285, Retrieved from the Internet <URL:https://en.wikipedia.org/w/index.php?title=Power_graph_analysis&oldid=723776105> [retrieved on 20171017]
ref_type: npl
severity: background
ref_id: US2009315890
ref_type: patent
severity: background
ref_id: US2010083194
ref_type: patent
severity: background
ref_id: - T. FEDER ET AL, "Clique Partitions, Graph Compression and Speeding-Up Algorithms", JOURNAL OF COMPUTER AND SYSTEM SCIENCES, (19951001), vol. 51, no. 2, doi:10.1006/jcss.1995.1065, ISSN 0022-0000, pages 261 - 272, XP055094467 [I] 1-10 * Section 2-4 *
ref_type: npl
severity: background
ref_id: - Anonymous, "Power graph analysis", Wikipedia, (20160605), URL: https://en.wikipedia.org/w/index.php?title=Power_graph_analysis&oldid=723776105, (20171017), XP055416285 [A] 1,5,10 * the whole document *
ref_type: npl
severity: background
Final disposition: pending (2017-12-20)