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.07–13.09.
Q13.07. Choose a real graph-mining case study and identify a dataset suitable for reproducing the analysis. The post lists communication patterns, fraud detection, changes in communication networks, web projections, and connection subgraphs.
Answer. Reproducible case study. Use nx.karate_club_graph() (the Zachary Karate Club social network) as a small real-network dataset to study community structure. Task: compute edge betweenness; run Girvan–Newman or Louvain; compare detected communities with the graph’s recorded club factions using agreement metrics. Then scale to a larger openly licensed research network, documenting source rights and missing data. This is a reproducible historical social-network case, not personal data.
Q13.08. Can you represent dengue case or contact observations as a graph and study possible patterns of spread?
Answer. Ethical synthetic study. Dengue cases may be summarized as regions over time, not unconsented person-level contacts. Construct vertices for geographic regions and edges for adjacency or measured travel, then annotate each region with week-specific case counts. Graph structure can help identify potentially connected areas for further public-health review; it cannot establish which person infected whom or provide a diagnosis.
Q13.09. Select a large-scale graph-mining function, apply it to a large graph, and investigate how an algorithm could be improved. Examples in the post include graph partitioning, clustering, connected components, similarity and link models, streaming graphs, centrality, and graph construction.
Answer. Scalable challenge. Take connected-components detection on a large undirected edge stream. Compare a NetworkX batch baseline with a union–find (disjoint-set union) streaming implementation. Report correctness on the same graph, edge-processing time, memory usage, and complexity. Define graph-size ranges and hardware limits; do not claim a speedup without measured results.
Mini case study: Karate Club network
import networkx as nx
from networkx.algorithms.community import greedy_modularity_communities
G=nx.karate_club_graph()
communities=list(greedy_modularity_communities(G))
print("Vertices:",len(G), "edges:",G.number_of_edges())
print("Community sizes:",sorted(map(len,communities), reverse=True))
print("Modularity:",nx.community.modularity(G,communities))
# Compare against node attribute G.nodes[v]["club"].
# The number and size of algorithmic groups can vary by method.
Synthetic dengue-area graph (not patient-level data)
import networkx as nx
G=nx.Graph()
G.add_edges_from([("North","Central"),
("Central","South"),
("Central","East")])
weekly_cases={"North":6,"Central":10,"South":3,"East":2}
# Toy descriptive neighborhood aggregate, not infection prediction:
neighbor_total={v:sum(weekly_cases[u] for u in G.neighbors(v))
for v in G.nodes}
print("Synthetic neighboring case totals:",neighbor_total)
# Validate rates using population denominators, time and reporting bias.
Streaming connected components with union–find
import random, time, networkx as nx
class DSU:
def __init__(self,n):
self.parent=list(range(n)); self.rank=[0]*n
def find(self,x):
while self.parent[x]!=x:
self.parent[x]=self.parent[self.parent[x]]
x=self.parent[x]
return x
def union(self,a,b):
a,b=self.find(a),self.find(b)
if a==b:return
if self.rank[a]
Evaluation: Benchmark input construction separately from algorithm execution, compare output correctness, use consistent graph sizes and repeated runs, and measure peak memory. For streamed contacts and public-health examples, follow data-governance and ethics requirements.
