Design an index-based solution for k-triangle core queries.
Given a simple, undirected graph G, a triangle is a set of three vertices that are pairwise
connected. A k-triangle core is a maximal (connected) induced subgraph of G in which every
vertex is contained in at least k triangles in the subgraph. Given an integer k and a vertex v, the problem of k-triangle core search aims to find all vertices in the k-triangle core containing v.
Design an index-based solution for k-triangle core search.
Figure 1 shows a connected graph.
Example query outputs (the first parameter of the query is the integer k and the second parameter is the vertex ID):
query(1, 0) returns [0, 1, 2, 3, 4, 5]
query(1, 6) returns [6, 7, 8, 9]
query(3, 3) returns [0, 1, 2, 3]
query(4, 0) returns []
Open the code template file
Q2.ipynb. The notebook
already defines the graph structure, the code template, and local tests. You only need to implement KTriangleIndex.build() and
KTriangleIndex.query(k, v) in the KTriangleIndex cell. The build() method is for preprocessing the input graph and storing data structures for answering queries. The query(k, v) method answers the query using the preprocessed data structures. Add helper methods or classes as needed.
The local tests generate graphs using fixed seeds and compare your outputs with precomputed expected results. The largest local test has 10,000 vertices and 80,000 edges.
In addition to the implementation, write a supporting document named Q2.pdf. The document must include theoretical analysis of your algorithm, including the time complexity of the query algorithm, the time complexity of the index construction algorithm, and the space complexity of the data structure needed for query processing. The document should also include an explanation of your algorithm and index design. Diagrams, figures, and examples are encouraged to illustrate your ideas.
For complexity analysis, use the following notations: n for the number of vertices, m for the number of
edges, d(v) for the degree of vertex v, max_deg for the maximum
degree, min_deg for the minimum degree, and avg_deg for the average degree
2m/n. Use any standard mathematical notations including but not limited to: sum, +,
-, *, /, min, max, and ^.
Submit Q2.ipynb and Q2.pdf on Moodle.
Marks will be awarded based on: