Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2024 / Paper 2 / D12

For an undirected graph with adjacency matrix

A

, degrees of vertices

k_{i}

and

m

edges, network modularity is

Q = \frac{1}{2 m} \sum_{C} \sum_{i, j \in C} (A_{ij} - \frac{k _{i} k _{j}}{2 m}) .

(1)

Each undirected edge contributes twice to the double sum, explaining the denominator

2 m

. Include the terms with

i = j

: even though the observed graph has no self-loops, the null-model contribution on the diagonal is part of this definition.

An independent implementation forms the modularity matrix and sums its within-community blocks. Initializing the best value to negative infinity also handles a candidate collection whose scores are all negative:

def modularity(adjacency,communities):
    a=np.asarray(adjacency);degrees=a.sum(axis=1);twom=degrees.sum()
    if twom==0:raise ValueError('positive edge count required')
    B=a-np.outer(degrees,degrees)/twom
    return sum(B[np.ix_(group,group)].sum() for group in communities)/twom

best_score = -np.inf
best_partition = None
for candidate in community_partitions:
    value = modularity(adjacency_matrix, candidate)
    if value > best_score:
        best_score, best_partition = value, candidate
print(best_partition, best_score)

The best partition is ${0, 1, 2} ∣ {3, 4, 5}$ , with $Q = 5/14 ≃ 0.357143$ . There are seven edges, and each selected community has three internal edges and total degree seven, so independently

Q = 2 (\frac{3}{7} - (\frac{7}{14})^{2}) = \frac{5}{14} .

(2)

The supplied candidates include the optimum, but do not exhaust even the balanced two-community set partitions: there are

(2 5) = 10

of those, rather than six. To substantiate a best partition among all community counts, the following short recursion enumerates all 203 unlabeled set partitions of the six vertices:

def partitions(items):
    if not items:
        yield [];return
    first,*rest=items
    for part in partitions(rest):
        yield [[first]]+[g.copy() for g in part]
        for j in range(len(part)):
            new=[g.copy() for g in part];new[j]=[first]+new[j];yield new

candidates = list(partitions(list(range(len(adjacency_matrix)))))
best_partition = max(candidates, key=lambda p: modularity(adjacency_matrix, p))
print(len(candidates), best_partition, modularity(adjacency_matrix, best_partition))

This exhaustive calculation returns the same two triangles and the same network modularity. Enumerating every set partition becomes impractical rapidly as the number of vertices increases, but is small enough here to verify the global optimum.

Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2024 / Paper 2 / D12

Solution

 Ancestors (11)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2024 / Paper 2 / D12

Solution

 Ancestors (11)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)