猜一下隐藏的社区

Question

背景

这个挑战是关于随机块模型的。基本上，我们给出了一个无向图，其中节点代表人，边代表人之间的社会联系。人们被分成两个“社区”，如果两个人在同一个社区里，他们更有可能有联系。您的任务是根据连接猜出这些隐藏的社区。

输入

您的输入是一个大小为100×100的二维位数组。它表示大小为100的无向图的邻接矩阵。图是由下列随机过程生成的：

• 每个节点被放置在社区0中，概率为0.5，否则被放置在社区1中，社区在输入中不可见。
• 对于同一社区中的每一对不同的节点，在它们之间放置一个边界，概率为0.3。
• 对于位于不同社区中的每一对不同的节点，在它们之间放置一个边界，概率为0.1。

所有的随机选择都是独立的。

输出

您的输出是长度为100的一维位数组。它代表了你的程序对潜在社区的猜测。不需要正确猜测哪些节点属于社区0，哪些节点属于社区1(这是不可能的)，只需将分区划分成两个社区。

评分

在这个储存库中，您将找到一个包含30行的文本文件。每一行表示由上述过程生成的图，它由隐藏社区的数组、分号和邻接矩阵中以逗号分隔的行列表组成。您应该读取这个文本文件，在每一行的邻接矩阵上调用您的提交程序，并将其输出与底层社区结构进行比较。

您提交的在特定图形上的得分是

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

其中V是隐藏社区的数组，W是基于邻接矩阵的程序猜测，i是它们的索引的范围。基本上，这是衡量错误分类节点的数量，考虑到您不需要猜测哪个社区是哪个社区。在所有30个测试用例中，平均得分最低，字节数被用作平局。

示例

考虑输入矩阵(清晰度为6×6)

011000
101100
110000
010011
000101
000110

它对应于6节点图。

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

由两个三角形组成，在它们之间有一个边。您的程序可能会猜测每个三角形是一个单独的社区，输出000111，其中前三个节点位于社区0，其余节点位于社区1中。输出111000是等效的，因为社区的顺序并不重要。如果真正的社区结构是001111，那么您的分数将是1，因为一个节点是错误分类的。

附加规则

在一台相当现代的计算机上，你的程序在任何一个测试用例上都不应该超过5秒(我无法测试大多数答案，所以我相信你)。

您可以编写完整的程序或函数，标准漏洞是不允许的。您可以针对这里使用的参数(大小为100，概率为0.3和0.1)优化您的答案，而不是实际的测试用例。如果我怀疑是谋杀，我有权生成一组新的图表。

测试程序

这里有一个Python 3函数，它计算Python 3函数提交的分数。

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

JavaScript (ES6)，成绩16.83

只是一个快速和简单的解决方案，没有得到一个很好的分数。我知道这不是密码-高尔夫，但这是我的(以134个字节为单位的)解决方案：

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)

解释

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
)

可能的改进

• 我可以在“查找图”步骤中实现两次传递，第一次传递得到每个节点的可能社区，并将每个节点重新初始化为该社区。

测试

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 2

数学，分数31/15 =2.066666.

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

请不要让我重新计算分数。