Graph Mining – 1 | 13. Assignments and Project Prompts — Part 2 (Worked Answers)

AI Generated Answers. Original assignment/project questions on this blog are attributed to Sayed Ahmed. The new AI-generated worked solutions and examples are offered for reuse without copyright restrictions asserted by the blog; external datasets and linked resources retain their own rights. These are instructional examples; test code before classroom use.

Graph Mining – 1 course index · Original prompt source: Graph Mining: Misc. Topics to Learn · This part covers prompts 13.04–13.06.

Q13.04. Run graph-property queries on small and large datasets. Find isolated vertices, count bidirectional edges and cliques, find the 10 highest in-degrees and 100 highest out-degrees, and count disconnected subgraphs.

Answer. Worked solution. For a directed graph, use in/out degrees, reciprocal (mutual) edge pairs, weakly and strongly connected components. Isolated nodes have zero incident edges. Enumerating all cliques can be exponential, so report exact counts only for small graphs or explicitly bounded clique sizes on large graphs. The Python example below runs the requested property queries.

Q13.05. Implement vertex betweenness, edge betweenness, and closeness centrality on a graph dataset such as political blogs.

Answer. Worked solution. Select a lawful, research-appropriate graph dataset (for a small built-in example, use Zachary’s Karate Club); compute betweenness centrality for vertices and edges, plus closeness centrality. State whether the graph is directed and how to interpret disconnected vertices. Compare the top-ranked nodes and bridges; the scores are structural measures, not moral judgments.

Q13.06. Implement page-ranking methods such as HITS and analyze hubs and authorities.

Answer. Worked solution. Create a directed hyperlink graph and calculate HITS hub/authority vectors and PageRank ranks. Check that the PageRank vector sums to one, HITS vectors have unit norm if L2-normalized, and results match a trusted library within numerical tolerance. The full HITS/PageRank from-scratch lesson provides complete Python functions.

Graph property queries (directed graph)

import networkx as nx
D=nx.DiGraph()
D.add_nodes_from(range(9))
D.add_edges_from([(0,1),(1,0),(0,2),(1,2),(2,3),
                  (3,4),(4,3),(4,5),(5,6),(6,5)])

isolated=list(nx.isolates(D))
reciprocal={frozenset((u,v)) for u,v in D.edges()
            if u!=v and D.has_edge(v,u)}
top_in=sorted(D.in_degree(),key=lambda x:x[1],reverse=True)[:10]
top_out=sorted(D.out_degree(),key=lambda x:x[1],reverse=True)[:100]
weak=list(nx.weakly_connected_components(D))
strong=list(nx.strongly_connected_components(D))
# Cliques are defined on the undirected projection.
U=D.to_undirected()
maximal_cliques=list(nx.find_cliques(U))
print("Isolated:",isolated)
print("Reciprocal pairs:",len(reciprocal))
print("Maximal cliques:",len(maximal_cliques))
print("Top in degree:",top_in)
print("Top out degree:",top_out[:10])
print("Weak/strong components:",len(weak),len(strong))
# All-clique enumeration is exponential; avoid on huge graphs.

Centrality comparison on a real small graph

import networkx as nx
G = nx.karate_club_graph()
node_bc = nx.betweenness_centrality(G)
edge_bc = nx.edge_betweenness_centrality(G)
closeness = nx.closeness_centrality(G)
print("Top 5 vertex betweenness:",
      sorted(node_bc.items(),key=lambda x:-x[1])[:5])
print("Top 5 edge betweenness:",
      sorted(edge_bc.items(),key=lambda x:-x[1])[:5])
print("Top 5 closeness:",
      sorted(closeness.items(),key=lambda x:-x[1])[:5])
# Compare different centrality notions; high score is not a label.

For a large graph, stream or partition queries where feasible, and limit clique enumeration. Report whether counts refer to strongly versus weakly connected components and to maximal versus all cliques.

Leave a Reply