Реализация модульности графика в Python ⇐ Python

[Anonymous]

Я пытаюсь реализовать свою собственную версию следующего определения модульности для графика:
graph modular metric < /p>
Я использую график-tool < /code> библиотека Python Чтобы определить одну структуру графика слоя и определить несколько графиков, используя мой метод SingleLayer_graph . Точно, я построил несколько графиков из этой статьи (рис. 4): кластеризационные графики. Моя проблема заключается в том, что я получаю казненно разные значения модульности с теми, которые сообщают в статье.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")

# 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
< /code>
Вот мое определение графика: < /p>
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
< /code>
и моя функция модульности: < /p>
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, 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"]}, {graph.vp["original_id"][j]}):")
print(f" Community of {graph.vp["original_id"]}: {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
< /code>
Я получаю значение модульности 0,42, в то время как в статье сообщается о значении 0,28. Я не понимаю, что не так с моей реализацией. См. Полный код вывод ниже. < /P>
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


Подробнее здесь: https://stackoverflow.com/questions/794 ... -in-python