如何使用igraph将两个节点合并为单个节点 [英] How do I merge two nodes into a single node using igraph

问题描述

我正在尝试将图形(G)中的两个节点(称为"V"和"U")合并为一个节点(V).

I am trying to merge two nodes (call them 'V' and 'U') in a graph (G) into a single node (V).

G是一个由779个节点(网站)组成的超链接网络.每个边缘代表一个超链接. V和U实际上是同一个网站，但不幸的是，该网站的网页已分成两个单独的节点.所以我想将它们放回一个节点中.

G is a hyperlink network of 779 nodes (websites). Each edge represents a hyperlink. V and U are actually the same website, but unfortunately the webpages from that website have become split into two separate nodes. So I want to put them back together into a single node.

我已经研究了contract.vertices函数，但是在这里我不明白如何适应它.

I have researched the contract.vertices function, but I cannot understand how to adapt it here.

这是我的图表(G)的属性.

Here are the attributes of my graph (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)

我有两个要合并在一起的节点:

I have two nodes that I want to merge together:

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

和

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

图中总共有779个节点和3544个边.

In total there are 779 nodes and 3544 edges in the graph.

我希望这两个节点成为图中的单个节点(即，它们将具有相同的"id").现在，其他节点之间的所有入站和出站都将仅指向该新的单个节点.

I want these two nodes to become a single node in the graph (i.e. they will have the same "id"). All inlinks and outlinks from/to other nodes will now point only to this new single node.

除Number of Pages以外，所有其他属性将保持不变(该值将是两个节点在合并之前的总和).

All other attributes will remain the same, with the exception of Number of Pages (the value of this will be the sum of both the nodes before they are merged).

推荐答案

contract.vertices确实是可以尝试的正确函数，但是它的API有点复杂，因为它被设计为不仅能够合并一对.节点，但也可以在一次传递中获得几对. (它也可以置换顶点).为此，它需要从旧的顶点ID到新的顶点ID进行映射.

contract.vertices is indeed the right function to try, but its API is a bit complicated since it is designed to be able to merge not only a single pair of nodes but also several pairs in a single pass. (It can also permute vertices). To this end, it requires a mapping from the old vertex IDs to the new ones.

如果您不熟悉顶点ID:igraph用1到N范围内的整数标识图的每个顶点，其中N是顶点数. contract.vertices要求的映射必须是长度为N的列表，其中列表的第i个元素包含与合并之前ID i 相对应的节点的 new ID

In case you are unfamiliar with vertex IDs: igraph identifies each vertex of the graph with an integer in the range 1 to N where N is the number of vertices. The mapping that contract.vertices requires must be a list of length N where the i-th element of the list contains the new ID of the node corresponding to ID i before merging.

假设您的图形包含10个节点.以下映射向量将简单地将每个节点映射到它已经具有的相同ID，因此不会进行任何合并:

Suppose that your graph contains 10 nodes. The following mapping vector will simply map each node to the same ID that it already has, so it will not do any merging:

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

现在，假设您要将节点7合并到节点4中.您必须告诉igraph节点7的 new ID将为4，因此您必须更改节点7中的第7个元素.以上向量为4:

Now, suppose that you want to merge node 7 into node 4. You have to tell igraph that the new ID of node 7 will be 4, so you have to change the 7th element in the above vector to 4:

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

这将几乎完成任务；问题是igraph要求节点ID在1到N的范围内，并且根据上述映射，由于您仍有ID为10的节点，因此igraph不会删除旧节点7.您可以在收缩顶点后使用delete.vertices手动将其删除，或者可以指定其他映射，不仅可以将节点7合并到节点4中，还可以将节点8的ID更改为7，将节点9的ID更改为8，将节点10的ID更改为9:

This will almost do the job; the problem is that igraph requires the node IDs to be in the range 1 to N and since you still have a node with ID 10 according to the above mapping, igraph will not delete the old node 7. You can either delete it manually with delete.vertices after you contracted the vertices, or you can specify a different mapping that not only merges node 7 into node 4 but also changes the ID of node 8 to 7, node 9 to 8 and node 10 to 9:

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

现在，由于您还希望新节点的Number of Pages属性是两个旧节点的值之和，因此您必须告诉igraph在合并过程中如何处理顶点属性. contract.vertices的vertex.attr.comb参数用于此目的.在您的情况下，vertex.attr.comb的值应类似于以下内容:

Now, since you also want the Number of Pages attribute of the new node to be the sum of the values of the two old nodes, you must tell igraph what to do with the vertex attributes during the merge. The vertex.attr.comb parameter of contract.vertices serves this purpose. In your case, the value of vertex.attr.comb should be something like this:

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

其中，"Number of Pages"="sum"表示Number of Pages属性的新值应通过将旧属性值相加来计算，而"first"表示对于此处未提及的所有其他属性，新值应由合并到一个节点中的节点集中第一个节点的旧值.有关此参数的格式的更多详细信息，请参见R中的?attribute.combination.

where "Number of Pages"="sum" means that the new value of the Number of Pages attribute should be calculated by summing the old attribute values, and "first" means that for all other attributes not mentioned here, the new value should be determined by the old value of the first node among the set of nodes that are merged into a single one. See ?attribute.combination in R for more details about the format of this argument.

这篇关于如何使用igraph将两个节点合并为单个节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！