Single-сообщество алгоритм обнаружения

Question

Вот презентация моего набора данных:

• Большая социально-сеть, состоящая из Twitter счета последователей очень крупных связанных счетов, последователи этого последователей и последователь этих последователей, на каждом итерация чистили бот счета, личные счета и т.д.
• Всего узлов: около 500 000
• Всего соединений: 95 миллионов
• 4 узлов имеют более 3 миллионов соединений
• 567 узлов имеют более 100000 соединений
• Половина набора данных имеют 3 или меньше соединений

Это сказало, Я хочу, чтобы очистить эту сеть для того, чтобы получить «лучшее» сингл-сообщество выходит из необработанный начальный график перед дальнейшей кластеризацией в субобменах. Имейте в виду эти несколько фактов:

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

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

Основная проблема может быть сведена по этой идее:Я рассматривал возможность использования следующего алгоритма. Начиная с большой сети; удаление «самого слабого» узла на каждой итерации; а модульность целого улучшается. Но это приведет к очень крошечной общине в конце.

Есть ли у вас какие-либо направления, где искать? Способ изменить методологию существующего алгоритма? Или даже документ, связанный с этой проблемой, даже если он совсем другой?

спасибо.

Answer 1

Здесь вы можете попробовать несколько подходов. Размер вашей сети является сложной задачей, но не все методы обнаружения сообщества способны работать в разумные сроки в такой большой сети. Вы можете попробовать те методы, которые имеют настраиваемые параметры, и эмпирически выяснить, как эти параметры влияют на их разрешение. При определенных значениях вы можете ожидать, что основная сеть будет покрыта одним кластером. Например, в igraph есть метод walktrap и spinglass.Если изменить количество шагов в walktrap, вы можете наблюдать изменение размера самого большого сообщества:

g <- barabasi.game(n = 10000, m = 2) 

steps <- seq(1, 10, 1) 
steps <- c(steps, seq(11, 200, 10)) 
w <- list() 
ccount <- NULL 
clargest <- NULL 

for(s in steps){ 
    cat(paste('Running walktrap with steps =', s, '\n')) 
    w0 <- walktrap.community(g, steps = s) 
    ccount <- c(ccount, length(levels(as.factor(w0$membership)))) 
    clargest <- c(clargest, max(tapply(w0$membership, w0$membership, length))) 
    w[[s]] <- w0 
} 

plot(ccount ~ steps, 
    xlab = 'Number of steps', 
    ylab = 'Number of communities', 
    main = 'Walktrap with increasing number of steps') 
plot(clargest ~ steps, 
    xlab = 'Number of steps', 
    ylab = 'Size of largest community', 
    main = 'Walktrap with increasing number of steps') 

Аналогично с изменением параметра гамма для spinglass:

gamma <- c(0.05, 0.1, 0.2, 0.5, 0.7, 0.85, 1.0, 1.2, 1.5, 1.8, 2.0, 2.5, 3.0, 3.5, 5.0, 10.0, 20.0, 50.0, 100.0, 500.0) 
sg <- list() 
sgsize <- NULL 

for(gm in gamma){ 
    cat(paste('Running spinglass with gamma =', gm, '\n')) 
    sg0 <- spinglass.community(g, vertex = 1, gamma = gm) 
    sgsize <- c(sgsize, length(sg0$community)) 
    sg[[as.character(gm)]] <- sg0 
    } 

plot(sgsize ~ log10(gamma), 
    xlab = 'Gamma (log)', 
    ylab = 'Size of the community', 
    main = 'Spinglass with increasing value of gamma', 
    xaxt = 'n' 
    ) 

Другой метод infomap , в соответствии с его описанием разработано именно для таких проблем, как ваша. Вы можете использовать не реализацию igraph, а original, так как последнее дает больше свободы в настройке параметров. Существует больше реализаций Python, но я не знаю, насколько они гибкие.

Вы также можете попробовать семейство методов moduland. Здесь вы можете выбрать между четырьмя методами ландшафтного строительства: nodeland, linkland, perturland и edgeweight; и два метода обнаружения горных пород: total_hill и percentional_hill; Кроме того, в perturland вы можете установить параметр x. Пожалуйста, прочитайте документы для получения дополнительной информации. Как я уже упоминал в комментарии, вы можете проверить сходство и установить порог для выбора своей основной сети. Эти методы не имеют интерфейса Python, но вы можете просто экспортировать текстовый файл и вызвать двоичные файлы на subprocess и прочитать их вывод обратно на Python.

Для обзора большого количества других методов see here from page 52 --- это уже не актуально, но всеобъемлюще.

Другая идея состоит в том, что вы можете запускать ряд методов и сравнивать их результаты, находить основную сеть как большой раздел, ограниченный границами кластера, постоянными по различным методам. Это также вопрос, как точное решение вам нужно. Учитывая, что ваши данные довольно шумные, вероятно, вы можете ожидать, что тысячи узлов будут классифицированы любым способом. Для сравнения различных кластеров вы можете использовать что-то вроде нормализованной взаимной информации, которая реализована в igraph (see more here.