Guess the hidden communities
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