**INLAB PROGRAM 1:** Construct a random graph consisting of 30 nodes with a
probability of 0.05 for edge creation.
a) Plot the graph with the appropriate layout and detect the communities using
the best_partition() function.
b) Generate a dendrogram for the created graph and print the partitions at each
level.
# Python 3.x
# Requirements:
# pip install networkx matplotlib python-louvain
import sys
import subprocess
# Ensure python-louvain is available
try:
import community.community_louvain as community_louvain
except ImportError:
subprocess.check_call([sys.executable, "-m", "pip", "install", "python-
louvain"])
import community.community_louvain as community_louvain
import networkx as nx
import matplotlib.pyplot as plt
from collections import defaultdict
def build_graph(n=30, p=0.05, seed=42):
"""Construct an Erdős–Rényi G(n, p) random graph."""
return nx.erdos_renyi_graph(n=n, p=p, seed=seed)
def detect_communities(G, seed=42):
"""Louvain best partition: dict node -> community id."""
return community_louvain.best_partition(G, random_state=seed)
def plot_graph(G, partition, title="Louvain communities on G(30, 0.05)", seed=42):
"""Plot the graph with a fixed layout and nodes colored by community."""
pos = nx.spring_layout(G, seed=seed)
# Color nodes by community id
communities = [partition[n] for n in G.nodes()]
cmap = plt.get_cmap("tab20")
# Normalize community ids into [0, 1] for colormap if needed
unique_comms = sorted(set(communities))
comm_to_idx = {c: i for i, c in enumerate(unique_comms)}
colors = [cmap(comm_to_idx[c] % 20) for c in communities]
plt.figure(figsize=(7, 5))
nx.draw_networkx_nodes(G, pos, node_color=colors, node_size=180,
linewidths=0.5, edgecolors="k")
nx.draw_networkx_edges(G, pos, alpha=0.5)
nx.draw_networkx_labels(G, pos, font_size=8)
plt.title(title)
plt.axis("off")
plt.tight_layout()
plt.show()
def print_dendrogram_partitions(G, seed=42):
"""Generate Louvain dendrogram and print partition at each level."""
dendrogram = community_louvain.generate_dendrogram(G, random_state=seed)
print(f"Number of dendrogram levels: {len(dendrogram)}")
for level in range(len(dendrogram)):
part = community_louvain.partition_at_level(dendrogram, level)
# Invert mapping to list nodes by community
comm_to_nodes = defaultdict(list)
for node, cid in part.items():
comm_to_nodes[cid].append(node)
print(f"\nLevel {level}: {len(comm_to_nodes)} communities")
for cid in sorted(comm_to_nodes.keys()):
nodes_sorted = sorted(comm_to_nodes[cid])
print(f" Community {cid}: {nodes_sorted}")
def main():
G = build_graph(n=30, p=0.05, seed=42)
partition = detect_communities(G, seed=42)
plot_graph(G, partition, title="Louvain communities on G(30, 0.05)", seed=42)
print_dendrogram_partitions(G, seed=42)
if __name__ == "__main__":
main()
**2.** Apply the Girvan Newman Algorithm by considering a path graph with 10
nodes and implement 2 functions namely ‘Girvan’ and ‘edge_to_remove()’.
a) Construct the function wherein the functions return count of connected
component subgraph and the edge to be removed respectively.
b) Display the various communities as the end result.
# Requirements:
# pip install networkx
import networkx as nx
def edge_to_remove(G):
"""
Return the edge with the highest edge betweenness centrality.
"""
# Compute edge betweenness centrality
betw = nx.edge_betweenness_centrality(G)
# Select the edge with maximum betweenness
edge = max(betw, key=betw.get)
return edge
def Girvan(G, k=2, verbose=True):
"""
Apply a simple Girvan–Newman procedure:
- Iteratively remove the current max-betweenness edge
- Stop when the graph has k connected components
Returns:
comp_count: number of connected components
communities: list of communities (each a sorted list of nodes)
"""
H = G.copy()
step = 0
# Continue removing edges until desired number of components is reached
while nx.number_connected_components(H) < k and H.number_of_edges() > 0:
e = edge_to_remove(H)
H.remove_edge(*e)
step += 1
if verbose:
print(f"Step {step}: removed edge {e}")
print(f" Connected components: {nx.number_connected_components(H)}")
# Final communities
comps = [sorted(list(c)) for c in nx.connected_components(H)]
comp_count = len(comps)
return comp_count, comps
if __name__ == "__main__":
# a) Build a path graph with 10 nodes (0..9)
G = nx.path_graph(10)
# b) Apply Girvan–Newman: count components and show communities
comp_count, communities = Girvan(G, k=2, verbose=True)
print("\nFinal result:")
print(f"Count of connected component subgraphs: {comp_count}")
for i, comm in enumerate(communities, 1):
print(f"Community {i}: {comm}")
**POST LAB 1.** Import the facebook_combined.txt file and then,
a) Detect the communities from the data using the best_partition() function.
b) Plot the detected communities with an appropriate layout.
c) Generate a dendrogram for the created graph and print the partitions at each
level.
# Requirements:
# pip install networkx matplotlib python-louvain
import os
from collections import defaultdict
from urllib.request import urlretrieve
import matplotlib.pyplot as plt
import networkx as nx
# Import python-louvain using the recommended namespace
# (community.community_louvain provides best_partition, generate_dendrogram,
partition_at_level)
try:
import community.community_louvain as community_louvain
except Exception as e:
raise SystemExit(
"Please install python-louvain: pip install python-louvain\n"
f"Original import error: {e}"
)
DATA_URL = "https://raw.githubusercontent.com/KLDataAnalytics/Introduction-to-
Graph-and-Web-Analytics/master/facebook_combined.txt"
DATA_FILE = "facebook_combined.txt"
def ensure_data(path=DATA_FILE, url=DATA_URL):
if not os.path.exists(path):
print(f"Downloading dataset to {path} ...")
urlretrieve(url, path)
return path
def load_graph(path):
# The file is a whitespace-delimited edge list of integer node IDs
# nodetype=int converts node labels from strings to ints for analysis
G = nx.read_edgelist(path, nodetype=int)
# Ensure the graph is undirected (dataset is undirected)
if not isinstance(G, nx.Graph):
G = nx.Graph(G)
return G
def detect_communities(G, seed=42):
# Louvain best partition: dict node -> community id
# random_state provides reproducibility
part = community_louvain.best_partition(G, random_state=seed)
return part
def plot_communities(G, partition, seed=42, title="Louvain communities
(facebook_combined)"):
# Use a force-directed (spring) layout
pos = nx.spring_layout(G, seed=seed)
# Map community id -> color
comm_ids = sorted(set(partition.values()))
# Build a simple color palette by cycling tab20
cmap = plt.get_cmap("tab20")
color_map = {cid: cmap(i % 20) for i, cid in enumerate(comm_ids)}
node_colors = [color_map[partition[n]] for n in G.nodes()]
plt.figure(figsize=(12, 9))
nx.draw_networkx_nodes(
G, pos,
node_color=node_colors,
node_size=10,
linewidths=0.0,
alpha=0.9
)
nx.draw_networkx_edges(
G, pos,
width=0.2,
alpha=0.2,
edge_color="#666666"
)
plt.title(title)
plt.axis("off")
plt.tight_layout()
plt.show()
def print_dendrogram_levels(G, seed=42, max_nodes_to_show=10):
"""
Generate the Louvain dendrogram and print partitions at each level.
Set max_nodes_to_show=None to print all members of every community.
"""
dendrogram = community_louvain.generate_dendrogram(G, random_state=seed)
print(f"Number of dendrogram levels: {len(dendrogram)}")
for level in range(len(dendrogram)):
part = community_louvain.partition_at_level(dendrogram, level)
comm_to_nodes = defaultdict(list)
for node, cid in part.items():
comm_to_nodes[cid].append(node)
print(f"\nLevel {level}: {len(comm_to_nodes)} communities")
for cid in sorted(comm_to_nodes.keys()):
nodes = sorted(comm_to_nodes[cid])
if max_nodes_to_show is None:
preview = nodes
else:
preview = nodes[:max_nodes_to_show]
suffix = "" if (max_nodes_to_show is None or len(nodes) <=
max_nodes_to_show) else f" ... (+{len(nodes)-max_nodes_to_show} more)"
print(f" Community {cid} (size={len(nodes)}): {preview}{suffix}")
def main():
path = ensure_data()
G = load_graph(path)
print(f"Graph loaded: {G.number_of_nodes()} nodes, {G.number_of_edges()}
edges")
# a) Detect communities
partition = detect_communities(G, seed=42)
# b) Plot communities
plot_communities(G, partition, seed=42)
# c) Dendrogram and partitions per level
print_dendrogram_levels(G, seed=42, max_nodes_to_show=10)
if __name__ == "__main__":
main()
