Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP9312 - 23T2 - Data Analytics for Graphs

Project Homepage / Q2

Q2 (15 marks)

Structure Diversity.

Problem Statement:

In this question, you need to design a solution to compute the structure diversity of all nodes in an undirected unweighted graph.

Background & Marking Criterias

Given an input graph, you are expected to compute the structure diverseity of all nodes in the graph. The structure diversity of a node is defined as the number of connected components in its neighborhood induced subgraph. Consider the graph in Figure 1. A graph is presented on the left hand side. To determine the structure diveristy of the vertex H, you need to focus on the grey area, which represents the subgraph formed by all neighbors of H. The right side indicates that there are two connected components in this subgraph. As a result, the structure diveristy of vertex H is 2.

The marking tutors will evaluate the goodness of your soution. A good solution should consider the correctness first and then focus on the processing time and space usage. In addition to writing out the code, it is also important to understand what you have achieved. You need to provide a document to describe your solution. The document helps us  understand your code, and let us know you have already got an idea to solve the problem at least, which may provide you some marks even if your code cannot run correctly. The  document can be in any format. The content should include but not limited to your designing ideas, theoretical analysis for space and time complexity. Example figures will be helpful if you design some complex solutions. You are also welcome to discuss multiple potential solutions/baselines and demonstrate why your solution is the best.

Doing this Project

Open the code template file Q2.ipynb and make a copy of the file in your own google drive. You need to implement a function named StructureDiversity. Below is the code template for StructureDiversity shown in Q2.ipynb.

############################################################################

# Add any modules you want to use here~

############################################################################

############################################################################

# You can define any auxiliary functions~

############################################################################

def StructureDiversity(G):

# intialization of the result

result = [0] * G.vertex_num

############################################################################

# TODO: Your code here~

# Input: G

# Output: The structure diversity of all vertices

# analyze the time complexity of StructureDiversity(G)

############################################################################

return result

You can also find the input graph data stucture defined in the UndirectedGraph class and an example about how we test your code. The file is running on the Google Colab plarform, which has already integrated the Python environment. As shown in our tutorials, you can directly write and run your code without any configuration. You can directly add any description for your solution and theoretical analysis in your your Q2.ipynb instead of creating a seperated PDF report. Ask your tutor if you have any difficult to run the code.

Notes:

a.  A detailed report is required to describe your algorithm and analysis the time complexity and space complexity. You can directly write them in Q2.ipynb or in a separated Q2.pdf.

b.  Any reasonable algorithm is acceptable as long as you have a detailed description and analysis in the report.

c.  You can add additional variables and functions for StructureDiversity. Do not change the input/output format in the code template.

d.  We may use a different and much larger dataset to test your algorithm.