Как объединить два узла в один узел с помощью igraph

Question

Я пытаюсь объединить два узла (называть их «V» и «U») в графе (G) в один узел (V).

G - это гиперссылка из 779 узлов (сайтов). Каждое ребро представляет собой гиперссылку. V и U на самом деле являются одним и тем же веб-сайтом, но, к сожалению, веб-страницы с этого сайта разделились на два отдельных узла. Поэтому я хочу объединить их в один узел.

Я исследовал функцию contract.vertices, но я не могу понять, как ее приспособить.

Ниже перечислены атрибуты моего графа (G).

> G 
IGRAPH D--- 779 3544 -- 
+ attr: Image File (v/c), Ringset (v/n), Country Code TLD (v/n), Generic TLD (v/n), Number of Pages (v/n), Categorical 1 (v/n), Categorical 2 (v/n), 
    Categorical 3 (v/n), id (v/c), label (v/c), Width (e/n) 

У меня есть два узла, которые я хочу объединить вместе:

> V(g)$id[8] 
[1] "http://www.police.uk/" 

и

> V(g)$id[14] 
[1] "http://police.uk/" 

В общей сложности Есть 779 узлов и 3544 Грани в графе.

Я хочу, чтобы эти два узла стали единым узлом на графике (т. Е. Они будут иметь одинаковый «id»). Все inlinks и outlinks от/до других узлов теперь будут указывать только на этот новый единственный узел.

Все остальные атрибуты будут оставаться неизменными, за исключением Number of Pages (значение этого будет суммой обоих узлов до их объединения).

Answer 1

contract.vertices действительно является правильной функцией, но его API немного сложнее, поскольку он предназначен для объединения не только одной пары узлов, но и нескольких пар за один проход. (Он также может переставлять вершины). Для этого требуется картирование от старых идентификаторов вершин к новым.

Если вы не знакомы с идентификаторами вершин: igraph идентифицирует каждую вершину графа с целым числом в диапазоне от 1 до N, где N - количество вершин. Отображение, которое требуется contract.vertices, должно быть списком длины N, где i-й элемент списка содержит новый ID узла, соответствующего ID i , до слияния.

Предположим, что ваш график содержит 10 узлов. Следующий вектор отображение будет просто отображения каждого узла в тот же идентификатор, что у него уже есть, так что не будет никакого слияния:

c(1,2,3,4,5,6,7,8,9,10) 

Теперь предположим, что вы хотите объединить узел 7 в узел 4. Вы должны сказать igraph, что новый ID узла 7 будет 4, так что вы должны изменить 7-й элемент в векторе выше 4:

c(1,2,3,4,5,6,4,8,9,10) 

Это почти сделать работу; проблема в том, что igraph требует, чтобы идентификаторы узлов находились в диапазоне от 1 до N, и поскольку у вас все еще есть узел с идентификатором 10 в соответствии с приведенным выше отображением, igraph не будет удалять старый узел 7.Вы можете удалить его вручную с помощью delete.vertices после того, как вы сократили вершины, или вы можете указать другое сопоставление, которое не только объединяет узел 7 в узел 4, но также изменяет идентификатор узла 8-7, узел 9-8 и узел 10-9 :

c(1,2,3,4,5,6,4,7,8,9) 

Теперь, так как вы хотите, чтобы атрибут нового узла Number of Pages быть суммой значений двух старых узлов, вы должны сказать igraph, что делать с вершиной атрибутов в процессе слияния. Для этой цели служит параметр vertex.attr.combcontract.vertices. В вашем случае, значение vertex.attr.comb должно быть что-то вроде этого:

list("Number of Pages"="sum", "first") 

где "Number of Pages"="sum" означает, что новое значение атрибута Number of Pages должно быть рассчитывается путем суммирования старых значений атрибутов и "first" означает, что для всех остальных атрибутов не упомянутое здесь, новое значение должно определяться старым значением первого узла среди множества узлов, которые объединены в один. См. ?attribute.combination в R для получения более подробной информации о формате этого аргумента.