I'm trying to group the chart by maximizing the modularity

where modularity is given by:

$ Q = frac {1} {2m} sum limits_ {i, j} left (A_ {ij} – frac {d_i d_j} {2m} right) delta (c_i, c_j) $

or form of equality

$ Q = frac {1} {4m} sum_ {i, j} (A_ {ij} – frac {d_id_j} {2m} x_ix_j x_i, x_j in left {- 1 1 right } $

I'm trying to optimize using the SDP + relaxation roundness of the hyperplan, as Goemans and Williamson's approach to the max-cut

but I've read an article here

on page 5, he states that:

"

One of the reasons why modularity resists

approximation approaches such as semi-defined rounding is that

the matrix $ B = sum_ {i, j} (A_ {ij} – frac {d_id_j} {2m}) $ contains negative and non-negative entries. "

how come?