Guess the hidden communities Background

This challenge is about the stochastic block model.
Basically, you are given an undirected graph, where the nodes represent people, and the edges represent social connections between them.
The people are divided into two "communities", and two people are more likely to have a connection if they are in the same community.
Your task is to guess these hidden communities based on the connections.

Input

Your input is a 2D array of bits of size 100&times;100.
It represents the adjacency matrix of an undirected graph of size 100.
The graph is generated by the following random process:


Each node is placed in community 0 with probability 0.5, otherwise it's placed in community 1. The communities are not visible in the input.
For each pair of distinct nodes that are in the same community, put an edge between them with probability 0.3.
For each pair of distinct nodes that are in different communities, put an edge between them with probability 0.1.


All random choices are independent.

Output

Your output is a 1D array of bits of length 100.
It represents your program's guess about the underlying communities.
You are not required to correctly guess which nodes belong to community 0 and which to community 1 (which would be impossible), just the partition into two communities.

Scoring

In this repository, you'll find a text file containing 30 lines.
Each line represents a graph generated by the above process, and it consists of the array of the hidden communities, a semicolon, and a comma-separated list of rows of the adjacency matrix.
You should read this text file, call your submission program on the adjacency matrix of each line, and compare its output to the underlying community structure.

Your submission's score on a particular graph is

min(sum_i(V[i] == W[i]), sum_i(V[i] == 1-W[i]))


where V is the array of hidden communities, W is your program's guess based on the adjacency matrix, and i ranges over their indices.
Basically, this measures the number of mis-classified nodes, taking into account that you're not required to guess which community is which.
The lowest average score over all 30 test cases wins, with byte count used as a tie breaker.

Example

Consider the input matrix (6&times;6 for clarity)

011000
101100
110000
010011
000101
000110


It corresponds to the 6-node graph

a-b-d
|/ /|
c e-f


consisting of two triangles with one edge between them.
Your program might guess that each triangle is a separate community, and output 000111, where the first three nodes are in community 0 and the rest in community 1.
The output 111000 is equivalent, since the order of the communities doesn't matter.
If the true community structure was 001111, then your score would be 1, because one node is mis-classified.

Additional rules

Your program should take no more than 5 seconds on any single test case on a reasonably modern computer (I'm unable to test most answers, so I'll just trust you here).

You can write a full program or a function, and standard loopholes are disallowed.
You are allowed to optimize your answer toward the parameters used here (size 100, probabilities 0.3 and 0.1), but not the actual test cases.
I keep the right to generate a new set of graphs if I suspect foul play.

Test program

Here's a Python 3 function that computes the score of a Python 3 function submission.

import time

def test_from_file(submission, filename):
    f = open(filename)
    num_graphs = 0
    total_score = 0
    for line in f:
        num_graphs += 1
        a, _, c = line.partition(';')
        V = [int(node) for node in a]
        E = [[int(node) for node in row] for row in c[:-1].split(',')]
        start = time.perf_counter()
        W = submission(E)
        end = time.perf_counter()
        x = sum(V[i]==W[i] for i in range(len(V)))
        score = min(x, len(V) - x)
        print("Scored {0:&gt;2d} in {1:f} seconds".format(score, end - start))
        total_score += score
    f.close()
    return total_score / num_graphs
R, 16/30 = 0.53333...

Edit:
Here is a version that has been golfed down to 259 bytes. I am sure a much better bytecount is possible. This version takes advantage of the fact that T is a global variable in R which can be treated as having a value of 1. If T has been reassigned in your R environment, results may differ.
The code produces some warnings, but they can be ignored.

f=function(A){L=function(p){q=1-p;z=.1*p%o%q;x=z+t(z)+.3*(p%o%p+q%o%q);c(sum(log(x^A*(1-x)^(1-A))),(A/x-(1-A)/(1-x))%*%(2*p-1))};x=tanh(rnorm(100))/2+.5;for(i in x){t=.5+tanh(atanh(2*x-1)+T*2*(L(x)[2:101]&gt;0)-T)/2;if(L(t)&gt;L(x)){x=t;T=2*T}else{T=T/2}};round(x)}

If the adjacency matrix of your graph is saved as a 100x100 matrix A in R, then the vector of communities is f(A). It will probably make less than one mistake!

Explanation
It treats the problem as fitting a statistical model (it helps that it knows the values 0.3 and 0.1) and fits it using a sort of gradient ascent algorithm. The community membership vector is treated as containing values in [0,1], rather than just zeroes and ones. This enables the model to be fitted using a sort of gradient ascent. (Ascent and descent is actually by a fixed amount delta in each coordinate, to avoid various problems. If a step of gradient ascent fails, delta is adjusted down.) It's quite fast and does pretty well.
I used today's date as the random seed.
LL &lt;- function(p, A){
# log-lieklihood of the model
  q &lt;- 1-p
  x &lt;- 0.1*(p %o% q) + 0.1*(q %o% p) + 0.3*(p %o% p) + 0.3*(q %o% q)
  sum(A*log(x) + (1-A)*log(1-x))
}

expit &lt;- function(x) exp(x)/(1+exp(x))

gradLL &lt;- function(p, A){
# (scalar multiple of) the gradient of the log-likelihood
  q &lt;- 1-p
  x &lt;- 0.1*(p %o% q) + 0.1*(q %o% p) + 0.3*(p %o% p) + 0.3*(q %o% q)
  drop((A/x - (1-A)/(1-x)) %*% (0.4*p - 0.2))
}

fit_model &lt;- function(A, N=100){
# gradient ascent
  x &lt;- rnorm(100)
  score &lt;- LL(expit(x), A)
  delta &lt;- 1
  for (i in 1:N){
    grad &lt;- gradLL(expit(x), A)
    test &lt;- x + delta*((grad &gt; 0) - (grad &lt; 0))

    test_score &lt;- LL(expit(test), A)
    if (test_score &gt; score){
      score &lt;- test_score
      x &lt;- test
      #print(score)
      delta &lt;- (1/0.7)*delta
    } else {
      delta &lt;- 0.7*delta
    }
  }
round(expit(x))
}

generate_A &lt;- function(){
# generate a matrix for testing
  comms &lt;- sample(0:1, 100, replace=T)
  A &lt;- matrix(rep(0, 100^2), nc=100)
  for (i in 1:(nrow(A)-1)){
    for (j in (i+1):ncol(A)){
      prob &lt;- ifelse(comms[i]==comms[j], 0.3, 0.1)
      if (runif(1) &lt; prob) A[i,j] &lt;- 1
    }
  }
  A &lt;- (A + t(A))/2
  list(A=A, comms=comms)
}

test &lt;- function(){
# test the fitting function once
  dat &lt;- generate_A()
  fit &lt;- fit_model(dat$A)
  sum(fit==dat$comms)
}

### performance ###

strings &lt;- readLines(&quot;community-graphs.txt&quot;, 30)

total &lt;- 0

set.seed(011215) # note that output is random!

for (i in 1:30){
  str_data &lt;- strsplit(strings[i], &quot;;&quot;)[[1]]
  comms &lt;- as.numeric(strsplit(str_data[1], &quot;&quot;)[[1]])
  A_str &lt;- strsplit(str_data[2], &quot;,&quot;)[[1]]
  A &lt;- matrix(rep(0, 100^2), nc=100)
  for (r in 1:100){
    A[r,] &lt;- as.numeric(strsplit(A_str[r], &quot;&quot;)[[1]])
  }
  out &lt;- fit_model(A)
  total &lt;- total + min(sum(out==comms), sum(out!=comms))
}

total # 16