Извлечение подграфов (кликов) внутри графа на Netlogo

У меня вопрос по нетлого. У меня есть несколько графовых структур узлов, связанных (ненаправленными) ссылками. Мне нужно выяснить, какой из них является наименьшим подграфом в одной из этих структур. В основном подграф означает, какие узлы связаны друг с другом. Итак, если у меня есть структура из 5 узлов, а узел 1 подключен к 2 и 3; узел 2 к 3, 1 и 4; и узлы с 3 по 1, 2 и 5. Мне нужно обнаружить подграф узлов 1, 2 и 3, поскольку все они взаимосвязаны.

Есть ли простой способ сделать это или это в принципе невозможно с точки зрения вычислений?

Изменить: я понял, что если я использую расширение netlogo nw, я могу использовать метод nw:maximal-cliques для вычисления того, что я хочу. Хотя сейчас у меня другая проблема. Я пытаюсь заполнить список списков клик таким образом

let lista-cliques [nw:maximal-cliques] of turtles with [guild = g]

lista-cliques обычно имеет длину два, но первым элементом, который должен быть списком черепах клики, является список, подобный этому

[[[nobody] [nobody] [nobody] [nobody]...etc

с длиной 300, когда графы, сделанные черепахами с guild = g, имеют длину около 2-8 черепах. Правильно ли сделан вызов nw:maximal-cliques?

Любые идеи о том, что я делаю неправильно?

Редактировать 2: я понял, как исправить длину списка, выполнив это

let lista-cliques (list ([nw:maximal-cliques] of turtles with [guild = g]))

Теперь список не из 300 узлов, а равен количеству узлов на графе с узлами с guild = g.

Это означает, что

length item 1 lista-cliques

равно

count turtles with [guild = g]

что также явно неверно, поскольку я вижу графы с узлами, связанными только с одним или двумя узлами. Я думаю, что приближаюсь, но я не знаю, почему nw:maximal-cliques создает не список максимальных клик, а список всех узлов на графе.

Любые идеи?

Спасибо


networking subgraph netlogo clique
person Atirag    schedule 09.02.2013    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Ваше использование nw:maximal-cliques не совсем корректно.

Я думаю, что то, что вы пытаетесь выразить, указав of turtles with [guild = g], это что-то вроде «учитывая только черепах, которые являются частью гильдии g», но на самом деле это означает для NetLogo «запустить репортера, который предшествует of для каждой черепахи, которая является частью гильдии g, и составить из этого список». (Точно так же, как, например, [color] of turtles запустит блок репортера [color] один раз для каждой черепахи и создаст список цветов с результатами.)

nw:maximal-cliques — это примитив, который работает со всей сетью, поэтому вам не нужно запускать его по одному разу для каждой черепахи. И точно так же, как и для большинства примитивов в расширении nw, вам нужно указать ему, с какими черепахами и ссылками работать, используя примитив nw:set-snapshot.

Я думаю, вы можете добиться того, чего хотите, просто выполнив:

nw:set-snapshot (turtles with [guild = g]) links
let lista-cliques nw:maximal-cliques

(Обратите внимание, что nw:set-snapshot делает статическую «картинку» вашей сети, на которой работают дальнейшие вызовы примитивов nw. Если что-то изменится в вашей сети, вам нужно вызвать nw:set-snapshot, чтобы сделать новую картинку. Это, вероятно, изменится в будущей версии расширение.)

person Nicolas Payette    schedule 10.02.2013