Сгруппируйте 200 образцов в 10 групп, чтобы минимизировать общую сумму меры

Question

У меня есть сетевой граф из 200 человек, где каждый узел - это человек, ребро - это, если они когда-либо говорили раньше, а вес ребра - это то, как много они общаются, и мне нужно разбить их на 10 групп по 20 человек, чтобы мы минимизировать количество общения между группами. Чтобы прояснить это, мы хотим создать сетевую встречу, где каждый стол заполнен людьми, которые в прошлом мало разговаривали, чтобы улучшить сотрудничество.

Бонус

во время одной встречи будет 2 сетевых события, и каждый человек будет сидеть за 2 разными столами, поэтому нам нужно сделать это дважды, учитывая тот факт, что первая таблица повлияет на решение второй таблицы.

Для этого мы подсчитали промежуточность и получили значение для всех 200 человек. Я думаю, что если мы сможем создать группы, которые минимизируют сумму промежуточности, мы, по сути, создадим группы, которые, скорее всего, не взаимодействовали бы раньше (или столько же).

df = data.frame(id=1:200,measure=rnorm(200,mean=50,sd=10))

Я немного не понимал, как начать здесь, не прибегая к методу грубой силы и сначала заполняя каждый стол 20 лучшими людьми, а затем просто просматривая их один за другим. Есть ли другие предложения?

Answer 1

Мы можем упорядочить df по мере, а затем разделить его на равные группы так, чтобы 10 лучших человек были в разных группах, следующие 10 лучших также были в разных группах и т. Д. c.

groups <- split( df[order(df$measure),], rep(1:10,20) )

Если мы просуммируем меры в каждой группе, мы обнаружим, что все они примерно равны

 sapply(groups, function(x) sum(x$measure))

        1         2         3         4         5         6         7         8         9        10 
 990.9206  996.3302 1001.2337 1007.6482 1012.3790 1016.2626 1020.7649 1024.2977 1034.4867 1038.0016 

---

Изменить: мы можем сделать группы еще более ровными, изменив порядок сетки во второй половине так, чтобы лучший человек был в паре с худшим человеком

groups <- split( df[order(df$measure),], c(rep(1:10,10),rep(10:1,10)) )

sapply(groups, function(x) sum(x$measure))
       1        2        3        4        5        6        7        8        9       10 
990.1134 991.6504 994.7865 997.4595 996.7483 995.9476 995.3022 995.1354 995.2223 995.9747