This assignment aims to enhance your practical expertise in Python programming through the application of class$-$learned concepts to generate graphical representations. These representations aid in identifying critical edges and nodes. The program's specific tasks include computing cluster coefficients and neighborhood overlaps within an input graph. Furthermore, the graphs will be partitioned to emphasize primary groups and store it in a new graph. Mastery of these skills will not only reinforce your programming capabilities, essential for upcoming assignments but also heighten your proficiency and competitiveness in the dynamic field of Computer Science.

Requirement

The assignment requires that you create the Python program that runs in a terminal. The program accepts optional parameters. The syntax to run the program is shown in the following line:

python $./$graph$\_$analysis.py graph$\_$file.gml $--$components n $--$plot $[$C$|$N$|$P$]--$verify$\_$homophily $--$verify$\_$balanced$\_$graph $--$output out$\_$graph$\_$file.gml

Description of Parameters

This is the command to execute the Python script graph$\_$analysis.py located in the current directory and reads the file graph$\_$file.gml$.$ Here, graph$\_$file.gml is the file that will be used for the analysis and the format is Graph Modelling Language $(.$gml$),$ which describes the graph's structure with attributes. The program should read the attributes of the nodes and edges in the file.

$--$components n

Specifies that the graph should be partitioned into n components. This divides the graph into n subgraphs or clusters. Compute the betweenness and remove the edge with the highest value. Repeat this process until you have n components.

$--$plot $[$C$|$N$|$P$]$

Determines how the graph should be plotted.

C: If this option is selected, the script will plot the graph highlighting clustering coefficients $($which measure how nodes are tightly grouped$).$

The Cluster coefficient is proportional to its size. Let cluster$\_$min, and cluster$\_$max be the min and max cluster coefficients, and let cv be the clustering coefficient of node v and pv $=($cv$-$ cluster$\_$min$)/($cluster$\_$max $-$ cluster$\_$min$)$ of node v$.$ The siz v is proportional to pv$.$ Let max$\_$pixel and min$\_$pixel be the minimum and maximum pixel sizes of the nodes. Therefore, the node v will have size min$\_$pixel $+$ pv$($max$\_$pixel $-$min$\_$pixel $).$

The color of v is proportional to the degree. Similar as before, let dv be the degree of node v$,$ max be the maximum degree in the graph. Let sv $=$ dv$/$max be the size of node v$.$ The RGB color of v is set to $(254*$sv$,0,254)$ so the node with the lowest degree is Blue and the node with the highest degree is Magenta.

N: If this option is selected, the script will plot the graph highlighting neighborhood overlap $($which measures how much overlap there is between neighborhoods of adjacent nodes$).$ Similar to the clustering coefficient.

P: If this option is selected, the script will color the node according to the attribute if it is assigned, or a default color if not.

$--$verify$\_$homophily

Tests for homophily in the graph based on the assigned node colors using the Student t$-$test. Homophily measures whether nodes with the same color are more likely to be connected.

$--$verify$\_$balanced$\_$graph

Check if the graph is balanced based on the assigned edge signs. A balanced graph is one where the signs on the edges are consistent with the node attributes.

$--$output out$\_$graph$\_$file.gml

Specify the file to which the final graph and results should be saved. In this case, out$\_$graph$\_$file.gml is the output file that will receive the updated graph data$$the node attributes and edge attributes should be also saved in the out$\_$graph$\_$file.gml$.$

Examples

python $./$graph$\_$analysis.py graph$\_$file.gml $--$components $3--$plot C $--$output out$\_$graph$\_$file.gml

Read graph$\_$file.gml and partition it into $3$ connected components, plot the graph and highlight the clustering coefficient, and save the graph in out$\_$graph$\_$file.gml

python $./$graph$\_$analysis.py homophily.gml $--$plot P $--$verify$\_$homophily

Read homophily.gml$,$ plot the graph and verify if there is evidence of homophily in the graph

python $./$graph$\_$analysis.py balanced$\_$graph.gml $--$plot P $--$verify$\_$balanced$\_$graph

Read balanced$\_$graph.gml$,$ plot the graph and verify if there is the graph is balanced

Evaluation:

Your implementation will be evaluated based on correctness, efficiency, clarity of code, and the quality of graph visualization. Ensure your program handles edge cases such as empty graphs, non$-$existent files, and invalid inputs gracefully.