问题标签 [subgraph]

例如，有一个图，它可以表示为一个邻接矩阵

G = {{ 0, 1, 0 }, { 1, 0, 1 }, { 1, 0, 0 }}

因此，有四个有向 边：

我想要的是计算子图（路径） {node_2 到 node_3} 和子图（路径） {node_2 到 node_3 到 node_1} 之间的相似性。

我能发现最多的是子图同构问题，它试图确定一个子图是否匹配（是一个更大的图的一部分）。这不是我的愿望。

我的主要任务是确定两个子图（路径）有多相似，它们都存在于我知道的图中。

您可以推荐任何现有的方法吗？文件？示例代码？

提前致谢。

我想使用更大的图作为源从一组种子节点生成第一个交互器子图。源图很大，有超过 300,000 条边，我的种子节点约为 300。子图（或多个子图）应包含每个种子节点的第一个交互器。

我已经在这篇文章中使用 R 中的 igraph 创建子图应用了代码， 但它只给了我一个很大的子图。我期望一个大的子图（大陆）和另一个与这个更大的图（岛屿）没有联系的子图。

示例代码：

该图为g1我提供了decompose.graph. 该图包含我的种子节点和其他不是种子节点的第一个交互器的节点。我正在寻找的是一个子图或子图列表，其中包含种子节点及其第一个交互器。也许我应该尝试使用neighborhood组功能？

提前谢谢了

编辑1：

按照 Gabor 的建议，我使用neigborhood了函数 with order=1。但是，我仍然没有得到我预期的结果。请在下面找到详细示例：

.

结果显示节点“5143742”和“9987134”之间有一条边。我的预期结果只是种子节点（种子）以及它们与第一个交互器之间的边，不包括第一个交互器之间的那些边

再次感谢

我正在使用 Networkx 来计算图形的一些度量，例如直径、聚类系数等。如何对整个图形执行此操作很简单。我感兴趣的是在具有相同属性（比如颜色）的节点之间找到这些度量。我在想如果我可以将图划分为不同的子图，其中每个子图中的节点具有相同的颜色，那么我可以完成并在这个子图中测量直径。所以我的问题是：有没有办法将图划分为包含相同颜色节点的子图？

我真的很感激任何见解。

我正在尝试制作一个从 .txt （类似于http://pastebin.com/g4cgaHJB）文件中读取图形的程序，然后创建并将它们放入向量中。（这部分工作完美）

想法：我试图迭代图，从第一条边开始（并从中创建一个图，我们称之为 testg ），并测试这个图是否频繁（我将测试 testg 和每个图之间的子图同构dataG 向量，然后我将计算有多少时间是真实的，如果有很多时间那么 2 所以 testg 是频繁的），如果 testg 是频繁的，那么我将添加另一个相邻边（并再次进行子图同构测试），如果 testg 不再频繁，我将删除最后添加的边缘（回溯）并将其更改为另一个（并再次进行子图同构测试）。如果没有更多的优势可以添加，我会说 testg 已关闭。并将其放入向量中，我们称其为 closedG。

我通过这样做开始了这个想法：

但是，它不起作用！这是错误：

我有下图，我需要从左到右 GHKMNOP 排列集群/子图。每个子图的内容都很好。我该如何做到这一点？我已经尝试按照其他问题中的描述添加不可见的边缘，但它没有按预期工作。

G/H 盒子需要按照正确的顺序排列，但是使用重量是行不通的……

下面的代码在底部呈现图像。00/01 节点设置为可见以显示顺序混淆的位置。

I want to know if there are some predefined functions to get those two tests results as a boolean in BOOST, then i will put the code (in an UPDATE).

1- if graph g1 is a subgraph of g2 (by giving g1 and g2 as a function parameter).

here http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/subgraph.html subgraph is used as a class not a function.

2- graph g connectivity (by giving g as a function parameter).

In the official documentation here http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/connected_components.html I found that connected_components function computes how many connected components are in the graph, and assigning each component an integer label. The algorithm then records which component each vertex in the graph belongs to by recording the component number in the component property map.

我正在尝试使用 SPARQL 查询存储数据集的三重存储（我说的是存储在三重存储数据集的全局图中存储的特定数据组）和元数据。元数据描述了如何计算数据。每个数据集都有自己的元数据，由两种节点类型和两种属性类型描述。

因此，当我只知道 URI 时，我看不到如何使用 SPARQL 查询我想要的所有三元组，它们定义了我的数据集eg:myDataSet元数据。当然，我不希望存储其他图表的元数据。

任何想法 ？

我已经尝试不在这里转发，但我认为我的请求非常简单，我只是对网络图缺乏经验。在python中使用networkx模块时，我想从连接图中恢复所有节点相互连接的子图（节点数大于2）。有没有一种简单的方法可以做到这一点？

这是我的例子：

一个有七个节点的简单图。节点1、2、3是共享连接，节点1、2、4都是共享连接，节点5、6、7都是共享连接。

我想要的输出是： ([1,2,3],[1,2,4],[5,6,7])

我可以想到编写这个稍微费力的方法，但想知道是否有一个简单的内置函数。

我一直在尝试使用graph.unionigraph 中的函数组合保留原始边缘属性的子图。操作成功，但新图忘记了它的边缘属性。我什至尝试过这里提到的选项，但在我看来有一些错误。

在我的工作中，我使用了两列数据作为由制表符分隔的边缘列表（作为分隔符）。

我有的方法：

幸运的是，图形已成功合并，但原始边缘属性（颜色和重量）丢失了。

如何发送我的输入文件？

我想保留原始图形的边缘颜色，因为它在合并的新图形中。

我正在尝试使用dot. 下面给出了我到现在为止的图表，并且还给出了代码。

代码

我面临的问题是关于子图的布局。我有兴趣以垂直方式排列盒子“ Box 13”、“ Box 11”和“ ”。Box 6我有兴趣将“ Box 6”和“ Box 11”放在第一行，将“ Box 13”放在第二行。这种安排将在“Box 5”内。我知道此处提供的布局选项。我可以将三个盒子 (6,11,13) 放入单独的文件中并合并。但我不清楚如何在“Box 5”内布置三个盒子。

提前致谢。