I am trying to implement my own version of the following modularity definition for a graph: Graph modularity metric
I am using graph-tool Python library to define a single layer graph structure and have defined several graphs using my singlelayer_graph method. Precisely, I have constructed several graphs from this paper (Figure 4): Clustering attributed graphs. My problem is that I am getting slighly different modularity values to those reported in the paper.
Here is my single graph construction method:
def singlelayer_graph(edges: Edges, directed: bool = True, edge_colors: dict[tuple[int, int]] = None) -> gt.Graph:
"""
Initializes a single-layer directed graph with optional edge colors.
Args:
edges: A list of tuples of the form (source_id, target_id, weight).
directed: Optional. A boolean flag that defines the directionality of edges (directed by default)
edge_colors: Optional. A dictionary where keys are (source, target) tuples and values
are RGB color lists for the edges.
Returns:
A gt.Graph object with the following properties:
- original_id (vertex property): The original node ID mapping.
- weight (edge property): The weight of each edge.
- edge_color (edge property, if provided): The color of each edge.
"""
G = gt.Graph(directed=directed)
# Define graph properties
G.gp["num_edges"] = G.new_graph_property("int")
G.gp["num_nodes"] = G.new_graph_property("int")
G.gp["num_edges"] = len(edges)
num_nodes = len(set(node for edge in edges for node in edge[:2]))
G.gp["num_nodes"] = num_nodes
# Define vertex properties
G.vp["original_id"] = G.new_vertex_property("int") # Store original IDs
G.ep["weight"] = G.new_edge_property("int")
# Add edge color property if edge_colors is provided
if edge_colors:
G.ep["edge_color"] = G.new_edge_property("vector<double>")
# Create a mapping from original node IDs to graph vertices
node_map = {}
for source, target, weight in edges:
# Ensure both source and target nodes exist in the graph
if source not in node_map:
v_source = G.add_vertex()
G.vp["original_id"][v_source] = source
node_map[source] = v_source
if target not in node_map:
v_target = G.add_vertex()
G.vp["original_id"][v_target] = target
node_map[target] = v_target
# Add edge using mapped vertices
edge = G.add_edge(node_map[source], node_map[target])
G.ep["weight"][edge] = weight # Assign weight
# Assign edge color if edge_colors is provided
if edge_colors and (source, target) in edge_colors:
G.ep["edge_color"][edge] = edge_colors[(source, target)] # Assign color
return G
Here is my graph definition:
def bothorel_graph_3():
es = [(1, 2, 1),
(1, 3, 1),
(2, 3, 1),
(3, 4, 1),
(2, 4, 1),
(4, 5, 1),
(5, 6, 1),
(4, 7, 1),
(6, 7, 1),
(7, 8, 1)]
# Create graph
G = singlelayer_graph(edges=es, directed=False)
# Assign communities by (original) node ID
communities = {
1: 0, 2: 0, 3: 0,
4: 1, 5: 1, 6: 1, 7: 1, 8: 1
}
# Create a new vertex property for communities
G.vp["community"] = G.new_vertex_property("int")
# Assign communities based on original IDs
for v in G.vertices():
G.vp["community"][v] = communities[G.vp["original_id"][v]]
return G
And my modularity function:
def graph_modularity(graph: gt.Graph) -> float:
"""
Computes the modularity of the input graph (supports both directed and undirected graphs).
Args:
graph (gt.Graph): The graph-tool Graph object.
Returns:
float: The modularity score of the graph.
"""
# Ensure the graph has community assignments
if "community" not in graph.vp:
raise ValueError("Community assignment missing. Ensure 'community' vertex property is set.")
# Check if the graph is directed
is_directed = graph.is_directed()
print(f"Graph is directed: {is_directed}")
# Set m to the sum of weights (total number of edges in an undirected graph)
# Convert edge weight sum to Decimal
m = Decimal(sum(Decimal(graph.ep["weight"][e]) for e in graph.edges()))
print(f"Total edge weight (m): {m}")
modularity = Decimal(0)
# List of all vertices and their corresponding communities
all_vertices = list(graph.vertices())
# Compute modularity contribution for all pairs (i, j)
for i in range(len(all_vertices)):
for j in range(len(all_vertices)): # Consider all pairs for directed graphs
if i == j:
continue # Skip self-loops
vi, vj = all_vertices[i], all_vertices[j]
ci, cj = graph.vp["community"][vi], graph.vp["community"][vj]
# Check if there is an edge between vi and vj
edge = graph.edge(vi, vj)
A_ij = Decimal(graph.ep["weight"][edge]) if edge is not None else Decimal(0) # Edge weight or 0 if no edge
# Compute degree based on directed or undirected graph
if is_directed:
k_i_out = sum(Decimal(graph.ep["weight"][e]) for e in vi.out_edges()) # Out-degree
k_j_in = sum(Decimal(graph.ep["weight"][e]) for e in vj.in_edges()) # In-degree
expected_weight = (k_i_out * k_j_in) / m
else:
k_i = sum(Decimal(graph.ep["weight"][e]) for e in vi.all_edges())
k_j = sum(Decimal(graph.ep["weight"][e]) for e in vj.all_edges())
expected_weight = (k_i * k_j) / (2 * m)
if ci == cj:
contribution = A_ij - expected_weight
else:
contribution = Decimal(0)
modularity += contribution
# Debugging prints for each pair (optional)
# Print detailed debug info
print(f"Pair ({graph.vp["original_id"][i]}, {graph.vp["original_id"][j]}):")
print(f" Community of {graph.vp["original_id"][i]}: {ci}, Community of {graph.vp["original_id"][j]}: {cj}")
print(f" A_ij: {A_ij}, k_i: {k_i}, k_j: {k_j}")
print(f" Expected Weight: {expected_weight:.6f}")
print(f" Contribution: {contribution:.6f}")
print(f" Modularity So Far: {modularity:.6f}\n")
if is_directed:
# Normalize and return modularity with precision
modularity = (modularity / m).quantize(Decimal("0.000001"), rounding=ROUND_HALF_UP)
else:
# Normalize and return modularity with precision
modularity = (modularity / (2 * m)).quantize(Decimal("0.000001"), rounding=ROUND_HALF_UP)
return modularity
I am getting modularity value 0.42 while the paper reports a value of 0.28. I do not understand what is wrong with my implementation. See full code output below.
Graph is directed: False
Total edge weight (m): 10
Pair (1, 2):
Community of 1: 0, Community of 2: 0
A_ij: 1, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.700000
Modularity So Far: 0.700000
Pair (1, 3):
Community of 1: 0, Community of 3: 0
A_ij: 1, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.700000
Modularity So Far: 1.400000
Pair (1, 4):
Community of 1: 0, Community of 4: 1
A_ij: 0, k_i: 2, k_j: 4
Expected Weight: 0.400000
Contribution: 0.000000
Modularity So Far: 1.400000
Pair (1, 5):
Community of 1: 0, Community of 5: 1
A_ij: 0, k_i: 2, k_j: 2
Expected Weight: 0.200000
Contribution: 0.000000
Modularity So Far: 1.400000
Pair (1, 6):
Community of 1: 0, Community of 6: 1
A_ij: 0, k_i: 2, k_j: 2
Expected Weight: 0.200000
Contribution: 0.000000
Modularity So Far: 1.400000
Pair (1, 7):
Community of 1: 0, Community of 7: 1
A_ij: 0, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 1.400000
Pair (1, 8):
Community of 1: 0, Community of 8: 1
A_ij: 0, k_i: 2, k_j: 1
Expected Weight: 0.100000
Contribution: 0.000000
Modularity So Far: 1.400000
Pair (2, 1):
Community of 2: 0, Community of 1: 0
A_ij: 1, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.700000
Modularity So Far: 2.100000
Pair (2, 3):
Community of 2: 0, Community of 3: 0
A_ij: 1, k_i: 3, k_j: 3
Expected Weight: 0.450000
Contribution: 0.550000
Modularity So Far: 2.650000
Pair (2, 4):
Community of 2: 0, Community of 4: 1
A_ij: 1, k_i: 3, k_j: 4
Expected Weight: 0.600000
Contribution: 0.000000
Modularity So Far: 2.650000
Pair (2, 5):
Community of 2: 0, Community of 5: 1
A_ij: 0, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 2.650000
Pair (2, 6):
Community of 2: 0, Community of 6: 1
A_ij: 0, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 2.650000
Pair (2, 7):
Community of 2: 0, Community of 7: 1
A_ij: 0, k_i: 3, k_j: 3
Expected Weight: 0.450000
Contribution: 0.000000
Modularity So Far: 2.650000
Pair (2, 8):
Community of 2: 0, Community of 8: 1
A_ij: 0, k_i: 3, k_j: 1
Expected Weight: 0.150000
Contribution: 0.000000
Modularity So Far: 2.650000
Pair (3, 1):
Community of 3: 0, Community of 1: 0
A_ij: 1, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.700000
Modularity So Far: 3.350000
Pair (3, 2):
Community of 3: 0, Community of 2: 0
A_ij: 1, k_i: 3, k_j: 3
Expected Weight: 0.450000
Contribution: 0.550000
Modularity So Far: 3.900000
Pair (3, 4):
Community of 3: 0, Community of 4: 1
A_ij: 1, k_i: 3, k_j: 4
Expected Weight: 0.600000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (3, 5):
Community of 3: 0, Community of 5: 1
A_ij: 0, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (3, 6):
Community of 3: 0, Community of 6: 1
A_ij: 0, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (3, 7):
Community of 3: 0, Community of 7: 1
A_ij: 0, k_i: 3, k_j: 3
Expected Weight: 0.450000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (3, 8):
Community of 3: 0, Community of 8: 1
A_ij: 0, k_i: 3, k_j: 1
Expected Weight: 0.150000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (4, 1):
Community of 4: 1, Community of 1: 0
A_ij: 0, k_i: 4, k_j: 2
Expected Weight: 0.400000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (4, 2):
Community of 4: 1, Community of 2: 0
A_ij: 1, k_i: 4, k_j: 3
Expected Weight: 0.600000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (4, 3):
Community of 4: 1, Community of 3: 0
A_ij: 1, k_i: 4, k_j: 3
Expected Weight: 0.600000
Contribution: 0.000000
Modularity So Far: 3.900000
Pair (4, 5):
Community of 4: 1, Community of 5: 1
A_ij: 1, k_i: 4, k_j: 2
Expected Weight: 0.400000
Contribution: 0.600000
Modularity So Far: 4.500000
Pair (4, 6):
Community of 4: 1, Community of 6: 1
A_ij: 0, k_i: 4, k_j: 2
Expected Weight: 0.400000
Contribution: -0.400000
Modularity So Far: 4.100000
Pair (4, 7):
Community of 4: 1, Community of 7: 1
A_ij: 1, k_i: 4, k_j: 3
Expected Weight: 0.600000
Contribution: 0.400000
Modularity So Far: 4.500000
Pair (4, 8):
Community of 4: 1, Community of 8: 1
A_ij: 0, k_i: 4, k_j: 1
Expected Weight: 0.200000
Contribution: -0.200000
Modularity So Far: 4.300000
Pair (5, 1):
Community of 5: 1, Community of 1: 0
A_ij: 0, k_i: 2, k_j: 2
Expected Weight: 0.200000
Contribution: 0.000000
Modularity So Far: 4.300000
Pair (5, 2):
Community of 5: 1, Community of 2: 0
A_ij: 0, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 4.300000
Pair (5, 3):
Community of 5: 1, Community of 3: 0
A_ij: 0, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 4.300000
Pair (5, 4):
Community of 5: 1, Community of 4: 1
A_ij: 1, k_i: 2, k_j: 4
Expected Weight: 0.400000
Contribution: 0.600000
Modularity So Far: 4.900000
Pair (5, 6):
Community of 5: 1, Community of 6: 1
A_ij: 1, k_i: 2, k_j: 2
Expected Weight: 0.200000
Contribution: 0.800000
Modularity So Far: 5.700000
Pair (5, 7):
Community of 5: 1, Community of 7: 1
A_ij: 0, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: -0.300000
Modularity So Far: 5.400000
Pair (5, 8):
Community of 5: 1, Community of 8: 1
A_ij: 0, k_i: 2, k_j: 1
Expected Weight: 0.100000
Contribution: -0.100000
Modularity So Far: 5.300000
Pair (6, 1):
Community of 6: 1, Community of 1: 0
A_ij: 0, k_i: 2, k_j: 2
Expected Weight: 0.200000
Contribution: 0.000000
Modularity So Far: 5.300000
Pair (6, 2):
Community of 6: 1, Community of 2: 0
A_ij: 0, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 5.300000
Pair (6, 3):
Community of 6: 1, Community of 3: 0
A_ij: 0, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 5.300000
Pair (6, 4):
Community of 6: 1, Community of 4: 1
A_ij: 0, k_i: 2, k_j: 4
Expected Weight: 0.400000
Contribution: -0.400000
Modularity So Far: 4.900000
Pair (6, 5):
Community of 6: 1, Community of 5: 1
A_ij: 1, k_i: 2, k_j: 2
Expected Weight: 0.200000
Contribution: 0.800000
Modularity So Far: 5.700000
Pair (6, 7):
Community of 6: 1, Community of 7: 1
A_ij: 1, k_i: 2, k_j: 3
Expected Weight: 0.300000
Contribution: 0.700000
Modularity So Far: 6.400000
Pair (6, 8):
Community of 6: 1, Community of 8: 1
A_ij: 0, k_i: 2, k_j: 1
Expected Weight: 0.100000
Contribution: -0.100000
Modularity So Far: 6.300000
Pair (7, 1):
Community of 7: 1, Community of 1: 0
A_ij: 0, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.000000
Modularity So Far: 6.300000
Pair (7, 2):
Community of 7: 1, Community of 2: 0
A_ij: 0, k_i: 3, k_j: 3
Expected Weight: 0.450000
Contribution: 0.000000
Modularity So Far: 6.300000
Pair (7, 3):
Community of 7: 1, Community of 3: 0
A_ij: 0, k_i: 3, k_j: 3
Expected Weight: 0.450000
Contribution: 0.000000
Modularity So Far: 6.300000
Pair (7, 4):
Community of 7: 1, Community of 4: 1
A_ij: 1, k_i: 3, k_j: 4
Expected Weight: 0.600000
Contribution: 0.400000
Modularity So Far: 6.700000
Pair (7, 5):
Community of 7: 1, Community of 5: 1
A_ij: 0, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: -0.300000
Modularity So Far: 6.400000
Pair (7, 6):
Community of 7: 1, Community of 6: 1
A_ij: 1, k_i: 3, k_j: 2
Expected Weight: 0.300000
Contribution: 0.700000
Modularity So Far: 7.100000
Pair (7, 8):
Community of 7: 1, Community of 8: 1
A_ij: 1, k_i: 3, k_j: 1
Expected Weight: 0.150000
Contribution: 0.850000
Modularity So Far: 7.950000
Pair (8, 1):
Community of 8: 1, Community of 1: 0
A_ij: 0, k_i: 1, k_j: 2
Expected Weight: 0.100000
Contribution: 0.000000
Modularity So Far: 7.950000
Pair (8, 2):
Community of 8: 1, Community of 2: 0
A_ij: 0, k_i: 1, k_j: 3
Expected Weight: 0.150000
Contribution: 0.000000
Modularity So Far: 7.950000
Pair (8, 3):
Community of 8: 1, Community of 3: 0
A_ij: 0, k_i: 1, k_j: 3
Expected Weight: 0.150000
Contribution: 0.000000
Modularity So Far: 7.950000
Pair (8, 4):
Community of 8: 1, Community of 4: 1
A_ij: 0, k_i: 1, k_j: 4
Expected Weight: 0.200000
Contribution: -0.200000
Modularity So Far: 7.750000
Pair (8, 5):
Community of 8: 1, Community of 5: 1
A_ij: 0, k_i: 1, k_j: 2
Expected Weight: 0.100000
Contribution: -0.100000
Modularity So Far: 7.650000
Pair (8, 6):
Community of 8: 1, Community of 6: 1
A_ij: 0, k_i: 1, k_j: 2
Expected Weight: 0.100000
Contribution: -0.100000
Modularity So Far: 7.550000
Pair (8, 7):
Community of 8: 1, Community of 7: 1
A_ij: 1, k_i: 1, k_j: 3
Expected Weight: 0.150000
Contribution: 0.850000
Modularity So Far: 8.400000
Modularity for graph 3: 0.420000