Guess the hidden communities

Question

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×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×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:>2d} in {1:f} seconds".format(score, end - start))
        total_score += score
    f.close()
    return total_score / num_graphs

Answer 1

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]>0)-T)/2;if(L(t)>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 <- function(p, A){
# log-lieklihood of the model
  q <- 1-p
  x <- 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 <- function(x) exp(x)/(1+exp(x))

gradLL <- function(p, A){
# (scalar multiple of) the gradient of the log-likelihood
  q <- 1-p
  x <- 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 <- function(A, N=100){
# gradient ascent
  x <- rnorm(100)
  score <- LL(expit(x), A)
  delta <- 1
  for (i in 1:N){
    grad <- gradLL(expit(x), A)
    test <- x + delta*((grad > 0) - (grad < 0))

    test_score <- LL(expit(test), A)
    if (test_score > score){
      score <- test_score
      x <- test
      #print(score)
      delta <- (1/0.7)*delta
    } else {
      delta <- 0.7*delta
    }
  }
round(expit(x))
}

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

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

### performance ###

strings <- readLines("community-graphs.txt", 30)

total <- 0

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

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

total # 16

Answer 2

JavaScript (ES6), Score 16.83

Just a quick and simple solution that doesn't get a very good score. I know this isn't code-golf but here's my (lightly golfed) solution in 134 bytes:

m=>(l=m.split`,`,n=l.map((_,i)=>[!i,0]),l.map((g,a)=>[...g].map((h,b)=>n[b][n[a][0]<n[a][1]==h|0]++)),n.map(g=>o+=g[0]<g[1]|0,o=""),o)

Explanation

m=>(                                    // m = comma delimited input matrix string

  // Initialisation
  l=m.split`,`,                         // l = input matrix as array
  n=l.map((_,i)=>                       // n = array of each node with a count of their
                                        //     graphs to nodes of each community
    [!i,0]                              // initialise the first node to community 0
  ),

  // Find graphs
  l.map(                                // compute each node
    (g,a)=>                             // a = index of node A, g = graphs of node A
      [...g].map(                       // compute each of the node's graphs
        (h,b)=>                         // b = index of node B
                                        // h = 1 if node A has a graph to node B
          n[b][n[a][0]<n[a][1]==h|0]++  // increment node B's number of graphs to node A's
      )                                 //     community if they have a graph, else
  ),                                    //     assume and increment the other community

  // Output the results
  n.map(                                // iterate over the graphs
    g=>                                 // g = current node's graphs
      o+=g[0]<g[1]|0,                   // add the number of the predominant community to
                                        //     the output
      o=""                              // o = output string
  ),
  o                                     // return o
)

Possible Improvements

• I could implement two passes in the "Find graphs" step, with the first pass getting the probable community of each node and reinitialising each node to that community

Test

var solution = m=>(l=m.split`,`,n=l.map((_,i)=>[!i,0]),l.map((g,a)=>[...g].map((h,b)=>n[b][n[a][0]<n[a][1]==h|0]++)),n.map(g=>o+=g[0]<g[1]|0,o=""),o);

function test() {
  var lines = input.value.split("\n"),
      output = [],
      totalScore = 0;
  for(var i = 0; i < lines.length; i++) {
    var parts = lines[i].split(";"),
        correct = parts[0],
        matrix = parts[1],
        result = solution(matrix);
    var sum = 0,
        sumInverse= 0;
    for(var c = 0; c < correct.length; c++) {
      if(correct[c] == result[c]) sum++;
    }
    for(var c = 0; c < correct.length; c++) {
      if(correct[c] == 1 - result[c]) sumInverse++;
    }
    var score = Math.min(sum, sumInverse);
    totalScore += score;
    output.push("Test " + (i + 1) + ": Score = " + score + ", Result = " + result);
  }
  output.splice(0, 0, "Average Score: " + (totalScore / lines.length));
  results.innerHTML = output.join("\n");
}

Enter the correct result followed by ";" then the input matrix delimited by ",".<br />
Put each test on a separate line.<br />
<textarea id="input" rows="5" cols="60">111000;011000,101100,110000,010011,000101,000110</textarea><br />
<button onclick="test()">Go</button>
<pre id="results"></pre>

Answer 3

Mathematica, score 31/15 = 2.066666...

Range[100]/.Thread[Alternatives@@@FindGraphCommunities[AdjacencyGraph[#,Method->{"Modularity","StopTest"->(Length[#2]==2&)}]]->{0,1}]&

Please don't make me recalculate the score.