 Solution

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.

 Read the full article

 New to topics? Read the docs here!