精华内容
下载资源
问答
  • 2022-02-14 11:09:52

    子图同构即subgraph isomorphism,
    假设G为图,S为子图,如果S中所有node(节点)和之间的edge(边)都可以映射到G中的话(结构相同就行),就称之为子图同构。
    induced subgraph isomorphism:G和S中对应的node之间的edge一一对应
    non-induced subgraph isomorphism:G中对应的node之间的某些edge不存在于S中

    子图匹配(Subgraph matching computation):

    1. 计算候选node(Candidate computation)
      即帮助每个S中的node寻找G中的有可能互相对应的节点
      伪代码:
    candidate_node=list()
    for node_u in S:
        for node_v in G:
            if v拥有所有u的label and len(v.neighbours)>=len(u.neighbours):
                candidate_node.append(v)
    
    1. 设定查找顺序
      简易方法中按照随即顺序查找

    2. 同构搜寻
      使用递归的形式挨个将S中每个node对应的G中的候选node放入新建子图,并匹配(回溯算法,backtracking,有点类似于树的遍历)
      query_node: S中的node
      data_node: G中的node(那些对应S的candidate node)
      O:query_node的查找顺序(就是一个query_node的list)
      Φ \Phi Φ:所有同构的集合
      ϕ \phi ϕ:一个同构对象(包含了query_node和对应的data_node)
      v:一个data node
      u:一个query node
      伪代码:

    def IsomorphismSearch(G,S,C,O,i,$\phi$,$\Phi$):
        if $\phi$.query_node=S.node:
            $\Phi$.append($\phi$)
        else:
            u=O[i]
            for v in u的candidate node:
                if v not in $\phi$.data_node and IsValid(G,S,$\phi$,u,v):
                    $\phi$[U]=v
                    IsomorphismSearch(G,S,C,O,i,$\phi$,$\Phi$)
                    $\phi$.query_node.remove(u)
        return $\Phi$
    
    def IsValid(G,S,$\phi$,u,v):
        for u' in u.neighbours:
            if neighbour在$\phi$.query_node中,但是u和u'映射的edge(v,$\phi$(u'))却在G中不存在:
                return False
        if isomorphism是induced的:
            for u' in u.query_node:
                if u'和u之间不相连,但是他们在G中的映射(v,$\phi$(u'))是相连的:
                    return False
        return True
    
    更多相关内容
  • 子图同构定义 子图同构的映射关系 Reference 写在后面的话写在前面的话谨以此片献给 my best love, grandpa.时光匆匆流逝,我们永远无能为力,我能做的就是脚踏实地,变成你的骄傲~和你在一起的时光,是我所有的宝藏...

    目录索引



    写在前面的话

    谨以此片献给 my best love, grandpa.

    时光匆匆流逝,我们永远无能为力,我能做的就是脚踏实地,变成你的骄傲~和你在一起的时光,是我所有的宝藏。从你身上继承的美好品质,我要努力把它变得更加迷人。如果时空真的可以扭转,我希望有个奇点,我们可以一直在一起不分开。



    1.子图同构定义

    我使用的定义是来自这篇参考文献:
    http://theory.stanford.edu/~virgi/cs267/lecture1.pdf

    这里写图片描述

    假设有两个图 H=(VH,EH) 和图 G=(V,E) 子图 同构即从H到G存在这样一个函数 f:VHV 并且 (u,v)EH 使得 (f(u),f(v))E 同样成立 f 叫做子图同构的一个映射。

    不过我觉得wiki讲的更好,子图同构定义
    是英文的,如果你看英文不成问题的话,可以仔细看。
    我觉得看英文的这个还是很锻炼的,毕竟我们不是native speaker.



    2.子图同构的映射关系

    说明,在这里的图,我们考虑的是没有标签的图。只有顶点序号的图。
    如下图,左图与右图子图同构:

    这里写图片描述

    我们看一下他们存在的一种映射关系:

    这里写图片描述

    我们把左边的图叫做图 A ,把右边的图叫做图 B

    MA,MB 分别表示左图 A, 和右图 B 的对应的邻接矩阵,其中MA[i][j]=1表示顶点 vi vj 存在一条边, A[i][j]=0 表示无边. M' 表示映射g从 MA MB 的映射矩阵, M'[i][j]=1 表示 A 中第i个顶点 vi 对应到 MB 中的第 j 个顶点,否则为0表示没有对应

    这里写图片描述

    根据我们上面的例子,我们来描述一下在Ullmann algorithm 算法中的一个定理


    定理1:
    如果图A关于映射 f 子图同构与图B,令

    MC=M(MMB)T

    其中T表示的是矩阵的转置。

    则有:
    这里写图片描述

    在A矩阵中是1的地方在C矩阵中也要为1


    根据定理一 MC=M(MMB)T 我们可以计算得到MC的矩阵值:

    这里写图片描述

    所以我们找到的映射矩阵 M 是一个满足图 A 和图 B子图同构的矩阵。



    下面我们来亲自实践一遍这个过程:

    这里写图片描述

    这里写图片描述

    由于这两个图的子图同构的映射比较好找出来,刚才我们就找出来一组,就是这个例子,
    这里写图片描述

    那我我们可以很容易的构建出子图同构的映射矩阵 M'

    这里写图片描述
    这里写图片描述
    这里写图片描述

    下面我们要做的事情就是看有没有这样一个MC 满足我们的定理1。

    这里写图片描述

    我们找的映射矩阵完全满足我们的要求能构造出我们的MC,其实MC对应的就是我们的矩阵MB当中的一块,如果你仔细观察可以发现:

    这里写图片描述

    我们发现其实第4列和第1列是完全一致的,这个时候调换一下位置,可以发现下面的规律:

    这里写图片描述

    这个时候我们可以找到另外一种映射关系,如下图所示:

    这里写图片描述

    那么,这个时候问题就来了,有没有下面这种可能呢:

    这里写图片描述

    那么它对应的映射矩阵就是下面这个样子的:

    这里写图片描述

    我们来亲自实践一下:

    这里写图片描述
    这里写图片描述
    这里写图片描述

    这个时候我们发现我们找到的MC是满足定理1的,那就是我们找的映射矩阵是其中的一个同构映射。

    其实根据图论中的子图同构的定义,我们发现,只要点对点,边对边是一致的,那么这两个图就是子图同构,他是NPC(NP complete)问题。

    如果我们的图是没有被设置标签的,标签就是图中的A,B,C这些,在有的时候如果我们的图已经被设置了标签,那就要求两个比较的图的点对点,边对边,标签对标签要形成双射,也就是单射和满射。

    如果这样的情况,就像下面两个博客说的一样是存在两个映射,如果这个图的点或者是边没有被设置标签,那么和图 A 它同构的子图就要很多我们可以在图B中找到。

    http://www.cnblogs.com/huadongw/p/4154295.html
    http://blog.csdn.net/luo123n/article/details/49787183

    并不是只有两个子图同构的映射,这两个图中有很多的子图同构的映射。



    Reference

    http://www.cnblogs.com/huadongw/p/4154295.html



    今天写这个花了两个小时,手已经抓了





    写在后面的话

    这里写图片描述

    我望着碧海蓝天 看云朵在兜圈
    慢慢兜成你的淘气鬼脸 忽近忽远

    微风在摇手轻吹 阳光睡在我的右侧脸
    我笑着脸去迎接 你给的誓~言
    YA~~~~~~~

    没发现 紫外线 太强烈 我爱你没有防备
    等你牵手带着我漫游世界 幸福快乐瞬间一起体会

    没发现 紫外线 太强烈 后知后觉的逃远
    我们躲在秘密的空中花园 爱情蝴蝶也和我们相约

    眼圈熬成黑看你更深邃
    只怕还不够爱 Time’s going by












    展开全文
  • 子图同构问题Ullmann 算法(二)

    千次阅读 多人点赞 2016-10-07 12:19:05
    对于图的同构问题,Ullmann 算法是一个简单的图同构算法,它采取的手段就是利用枚举找到子图同构。 这个算法的目的就是 对于一个给定的图Q,要找出在图G当中的和图Q同构的所有的子图。 用我们上一张的例子来说:...

    #目录索引


    写在前面的话

    以上的内容均出自这篇论文ullmann algorithm,所有的表述竟可能的和论文中的表述保持一致。 我要做的事情就是竟可能的讲的很清楚,尽可能的做到准确完备。

    谨以此系列献给 my best love, grandpa~ 还有昆明宝石蓝的天空,2月的梨花,三月的樱花,10月的桂花,星光璀璨的星空陪我入梦乡,安静而又安抚人的环境,总是让我心很静,那些美好的事物总是想让我保持一颗干净温暖的内心。

    要写点没有中国人写的,要搞点没有人做的事情才有意思,能做点推动中国计算机科学发展的事情,才有意义。老嚼别人吃过的东西,没有任何意义。不能推陈出新是件非常失败的事情。

    这个世界是你们的,也是我的,终究还是我们的,这个世界不够完美不够好,一定是在等我们把它变美好!

    还是那句话,focus on security! 认定好什么事情就要做到极致,做到很难被人超越。



    #1.Ullmann算法的定义

    1.1背景知识

    对于图的同构问题,Ullmann 算法是一个简单的图同构算法,它采取的手段就是利用枚举找到子图同构。

    这个算法的目的就是 对于一个给定的图Q,要找出在图G当中的和图Q同构的所有的子图。

    用我们上一张的例子来说:

    这里写图片描述

    我们把左边的这个图叫做图A,右边的这个图叫做图B,那么我们要找出在图B中和图A同构的所有子图。

    我们先找出几个看看。我们说过,子图同构就是根据点和边的关系,在另外一个图中找到对应的点,并且对应的点,边之间完全一样,就是存在相同的关联矩阵。

    说明,我们考虑的还是不带标签的图,请忽略下面的A,B,C,D

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    当然我们举完全,你可以自己再看一下,但是绝对不像其他的博客当中说的只有两个,这是不对的。

    Ullmann算法的基本思想我们在说一遍,就是要找到一个映射矩阵,然后找出这个映射矩阵对我们的图B做变换之后得到的矩阵中,只要图A的关联矩阵中数值为1的位置,对应的变换矩阵C也为1。

    看不懂的看前一篇文章。


    1.2 数学定义和描述

    对于一个给定的图 $ G_{\alpha} = (V_{\alpha},E_{\alpha}) $ 和一个给定的图 $ G_{\beta}= (V_{\beta},E_{\beta}) $ ,我们的任务就是找出在 G β G_{\beta} Gβ 中和 G α G_{\alpha} Gα 同构的所有子图。 我们把在图
    G α = ( V α , E α ) G_{\alpha} = (V_{\alpha},E_{\alpha}) Gα=(Vα,Eα) 和 $ G_{\beta}= (V_{\beta},E_{\beta}) $ 的顶点数和边数分别记为 $ p_{\alpha} ,q_{\alpha}$ ; p β , q β p_{\beta},q_{\beta} pβ,qβ

    其中图 $ G_{\alpha} = (V_{\alpha},E_{\alpha}) $ 和 $ G_{\beta}= (V_{\beta},E_{\beta}) $ 的邻接矩阵 分别是$ A = [a_{ij}], B=[b_{ij}] $

    之后我们定义一个映射矩阵 M ′ M^{'} M 它由 $ p_{\alpha} * p_{\beta} $ 个元素组成,其中每一行只能包含一个1,每一列至多只能包含一个1。我们通过这个矩阵 M ′ M^{'} M 要对矩阵 B B B进行一系列的行列变换,得到我们的矩阵 C C C , 我们的矩阵C定义如下:

    C = [ C i j ] = M ′ ( M ′ B ) T C = [C_{ij}] = M^{'} (M^{'}B)^{T} C=[Cij]=M(MB)T

    其中T是表示矩阵的转置。

    如果在图B中有图A的同构矩阵,那么一定满足:

    这里写图片描述

    那么 $ M^{’}$就指出了 图 G α = ( V α , E α ) G_{\alpha} = (V_{\alpha},E_{\alpha}) Gα=(Vα,Eα) 和 $ G_{\beta}= (V_{\beta},E_{\beta}) $ 的一个同构映射


    为啥我的CSDN的latex的代码显示出来的东西为啥总是后面有条线。为啥????

    本小节涉及到Latex代码:

    $ G_{\alpha} = (V_{\alpha},E_{\alpha}) $
    $G_{\beta}= (V_{\beta},E_{\beta})$
    $G_{\beta}$
    $G_{\alpha}$ 
    
    $$C = [C_{ij}] = M^{'} (M^{'}B)^{T}  $$ 
    
    


    #2.Ullmann算法实现

    对于Ullman算法的主要目的就是找到我们的 $ M^{’} $

    开始的时候我们先定义一个矩阵, $M^{0} $ 这个矩阵由 $ p_{\alpha} *p_{\beta} $ 个元素构成

    这里写图片描述

    其中这个矩阵中为1的元素满足B这个图中的度大于等于A中元素的度。现在我们就来构建这个初始的矩阵$M^{0} $。

    我们还是以我们的那个例子来说明:

    这里写图片描述

    构建我们的M0这个矩阵。

    这里写图片描述

    这里写图片描述

    可以发现在图A中,每个顶点的度都是小于图B中任何顶点的度。所以这个矩阵的初始矩阵应该全是1。

    这里写图片描述

    这个怎么看,我们的矩阵的行表示的是我们的图A各个顶点,列表示的我们的图B的每个点。

    先看第一行,A的元素都是小于或者等于B中的每个元素的度,以此类推,构成这个矩阵。

    然后我们要得到最后的映射矩阵,对这个初始矩阵M0进行变换,使得最后每一行有且只有一个1,每一列最多只有一个1。这样就找到我们的矩阵。之后按照定理1算矩阵C看和A之间额对应关系。

    算法如下:

    这里写图片描述

    update@2016-10-8 19:55

    在这个算法中使用了两个二进制的向量 F ⃗ \vec{F} F H ⃗ \vec{H} H

    我们要找一个映射矩阵 M ′ M^{'} M, 这个矩阵由 p α p_{\alpha} pα行 $ p_{\beta} 列 , 我 们 的 初 始 矩 阵 是 列,我们的初始矩阵是 M{0}$和我们的$M{’}$大小是一致的。我们就是要将 M 0 M^{0} M0一步一步变换到我们需要的 M ′ M^{'} M矩阵。

    这里写图片描述

    这里写图片描述

    这个深度d其实就是我们运算到了哪一行

    H d = k H_{d} = k Hd=k表示的是运算到第d行的时候(当深度为d)的时候第k列已经被用了。

    下面我们亲自实践一下整个算法的运算过程。

    首先执行算法的第一部,初始矩阵 M 0 M^{0} M0赋值给矩阵M

    设置遍历深度为1,H1=0

    设置向量F的前 p α p_{\alpha} pα都为0

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    这里写图片描述

    就这样我们就找到了一个我们需要的映射矩阵,这个时候按照定理1,我们发现找到了我们需要的矩阵C,在不断枚举和验证我们可以找到其他的映射矩阵。

    这个就是我们的Ullmann算法的实现的基本思想。

    今天就更新到这里了,滚回去学习了。

    有啥大家一起交流吧~~~

    biubiu~~~



    写在后面的话

    无意中发现了一个巨牛的人工智能教程,忍不住分享一下给大家。教程不仅是零基础,通俗易懂,而且非常风趣幽默,像看小说一样!觉得太牛了,所以分享给大家。点这里可以跳转到教程 https://www.captainbed.net/chichoxian

    在这里插入图片描述

    这里写图片描述

    我望着碧海蓝天
      看云朵在兜圈
      慢慢兜成你的淘气鬼脸
      忽近忽远woo……
      微风在摇手轻吹
      阳光睡在我的右侧脸
      我笑着脸去迎接
      你给的誓言yeah……
      没发现紫外线太强烈
      我爱你没有防备
      等你牵手带着我漫游世界
    幸福快乐瞬间一起体会
      后知后觉地逃远
      我们躲在秘密的空中花园
      爱情蝴蝶也和我们相约
      夜色倒垂还看你更沉睡
      只怕还不够爱time’s going by
      oh~yeah……
    这里写图片描述

    展开全文
  • 关于子图同构算法VF2的论文,实现和测试数据。用于学习子图同构算法,用作借鉴。
  • 子图同构算法如何判定子图同构定义判定方法Ullmann算法1.Ullmann算法的定义2.Ullmann算法实现伪代码:步骤:判断同构的代码 如何判定子图同构 定义 有个Gα和Gβ, Gα有pa个点,qa条边,Gβ有pb个点,qb条边。A是G...

    如何判定子图同构

    定义

    有个Gα和Gβ, Gα有pa个点,qa条边,Gβ有pb个点,qb条边。A是Gα的邻接矩阵,相应的B是Gβ的邻接矩阵。Gα中的每一个边和点在Gβ中也有相对应的边和点。那么如何判断同构呢。

    判定方法

    设A是子图,B是原图。那么有一个A的点到B的点的映射。这个映射的模式叫做M。M是pa行,pb列的。M有一个性质就是每行只有一个1,每列至多一个1。这个就是一个A中的点到B中的点的一个映射。我们定义一个C = [cij] = M(MB)T。如果在图A中i和j有边能推导出图C中i和j有边。那为什么是对的呢。因为M是映射,MB就是把B中被映射的点按照顺序抽出来在和B点对应。 M中第i行j列为1的意义是A的第i个点对应,B的第j个点。MB中第i行j列为1的意义是现在A的第i个点对应到的点到B的第j个点有一条边。把这个矩阵转置在乘以M。C就是B中和A对应的点和在B中的边全部抽出来组成的图。

    那么如果aij = 1能推导出cij = 1。A就是B的一个子图的同构。

    Ullmann算法

    1.Ullmann算法的定义

    对于图的同构问题,Ullmann 算法是一个简单的图同构算法,它采取的手段就是利用枚举找到子图同构。
    这个算法的目的就是 对于一个给定的图Q,要找出在图G当中的和图Q同构的所有的子图。

    2.Ullmann算法实现

    伪代码:

    在这里插入图片描述

    步骤:

    Step 1 :
    建立矩阵 M n × m M_{n\times m} Mn×m。 使得 M [ i ] [ j ] = 1 M[i][j]=1 M[i][j]=1,如果
    Q中第 i i i-个顶点与 G G G中第 j j j-个顶点有相同的标签;
    Q中第 i i i-个顶点的度小于等于 G G G中第 j j j-个顶点的度;
    在这里插入图片描述

    Step 2. 从矩阵 M n × m M_{n\times m} Mn×m生成矩阵 M ′ M' M. 即对 M n × m M_{n\times m} Mn×m进行逐行检查,将部分不为0的元素变成0,使得矩阵 M ′ M' M满足每行有且仅有一个元素为1,每列最多只有一个元素不为0.(最大深度为 ∣ M A ∣ |MA| MA.)
    在这里插入图片描述

    Step 3 按照以下规则判断矩阵 M ′ M' M是否满足条件:
    MC=M′(M′⋅MB)T, ∀i∀j:(MA[i][j]=1)⇒(MC[i][j]=1).

    Step 4 迭代以上步骤,列出所有可能的矩阵 M ′ M' M.

    判断同构的代码

    需要输入两个图,以及映射图M,执行step3的步骤

    #include<bits/stdc++.h>
    using namespace std;
    //typedef long long int ll;
    const int maxn = 1e5+10;
    class Matrix{
       public:
                int **cont;
                //int **du;
                int a, b;
       public:
           Matrix(){
              cont = 0;
              //du = 0;
              a = b = 0;
          }
          Matrix(int a, int b){
              this->a = a;
              this->b = b;
              cont = new int*[a];
              //du = new int*[a];
              for (int i = 0; i < a; i++){
                  cont[i] = new int[b];
                 // du[i] = new int[b];
                  for (int j = 0; j < b; j++){
                      cont[i][j] = 0;
                      //du[i][j] = 0 ;
                  }
              }
          }
          Matrix(int *x, int a, int b){
              this->a = a;
              this->b = b;
              cont = new int*[a];
              for (int i = 0; i < a; i++){
                  cont[i] = new int[b];
                  for (int j = 0; j < b; j++){
                      cont[i][j] = x[i*a + j];
                      //cout<<cont[i][j]<<" ";
                  }
                  //cout<<endl;
              }
          }
         Matrix(const Matrix& x){
              if (x.isNULL()){
                  cont = 0;
                  a = b = 0;
              }
              else{
                  //x.print();
                  a = x.a; b = x.b;
                  //cout<<x.a<<" "<<x.b<<endl;
                  cont = new int*[a];
                  for (int i = 0; i < a; i++){
                      cont[i] = new int[b];
                      for (int j = 0; j < b; j++){
                          cont[i][j] = x.cont[i][j];
                          //cout<<x.cont[i][j]<<" ";
                      }
                      //cout<<endl;
                  }
              }
          }
          ~Matrix(){
              for (int i = 0; i < b; i++){
                  delete[] cont[i];
              }
              delete cont;
          }
          Matrix Muiltply(Matrix y){
              if (isNULL() || y.isNULL() || b != y.a){
                  return Matrix();
              }
              Matrix z(a, y.b);
              for (int i = 0; i < a; i++){
                  for (int j = 0; j < y.b; j++){
                      for (int k = 0; k < b; k++){
                          z.cont[i][j] += cont[i][k] * y.cont[k][j];
                      }
                  }
              }
              return z;
          }
          //布尔矩阵乘法
        Matrix boolMuiltply(Matrix y){
              if (isNULL() || y.isNULL() || b != y.a){
                  return Matrix();
              }
              Matrix z(a, y.b);
              for (int i = 0; i < a; i++){
                  for (int j = 0; j < y.b; j++){
                      for (int k = 0; k < b; k++){
                          z.cont[i][j] += cont[i][k] * y.cont[k][j];
                      }
                      if(z.cont[i][j] > 0){
                          z.cont[i][j] = 1;
                     }
                  }
              }
              return z;
        }
         bool isNULL() const{
            if (cont == 0){
                return true;
             }
            else{
                return false;
             }
         }
        bool isequal(Matrix& y){
            if(a == y.a && b == y.b){
                 for (int i = 0; i < a; i++){
                     for (int j = 0; j < a; j++){
                         if(cont[i][j] != y.cont[i][j]){
                             return false;
                        }
                     }
                }
                return true;
             } else{
                 return false;
             }
         }
         //转置
        Matrix Trans(){
            Matrix x(b,a);
            for (int i = 0; i < a; i++){
                for (int j = 0; j < b; j++){
                     x.cont[j][i] = cont[i][j];
                }
             }
             return x;
         }
        bool iscontent(const Matrix &A)const{
            if(a == A.a && b == A.b){
                 for (int i = 1; i <= a; i++){
                    for (int j = 1; j <= b; j++){
                        if(A.cont[i][j] == 1 && cont[i][j] == 0){
                            return 0;
                         }
                    }
                 }
                 return 1;
             }
             return 0;
         }
         void print(){
             if (isNULL()){
                 printf("NULL\n");
            }
             for (int i = 0; i < a; i++){
                 for (int j = 0; j < b; j++){
                     cout << cont[i][j] << " ";
                 }
                 cout << std::endl;
             }
         }
    };
    int main(){
         typedef Matrix Map;
         typedef Matrix T;
         //A为子图,B为原图,M为映射关系
         Map A,B;T M;
         //根据公式判断
         Map x = M.boolMuiltply(M.boolMuiltply(B).Trans());
         x.iscontent(A);
    }
    
    展开全文
  • 图匹配和子图同构检测的并行网络组织算法 图匹配和子图同构检测的并行网络组织算法 Keita Maehara 计算机与系统工程系,神户大学,神户,日本 657-8501 Kuniaki Uehara 城市研究中心安全与安保,神户大学,神户,...
  • Clique(G=(V,E),k) { for each subgraph G' in G and |V'|=k { 子图同构(G,G') } }
  • 提出了一种新的虚拟网络嵌入(VNE)算法,该算法改进了原始子图同构搜索过程,克服了现有VNE算法的缺陷。 首先,提出了一种节点资源评估方法,该方法同时考虑了节点资源需求(能力)和拓扑属性,以改善虚拟节点的...
  • python – 子图同构

    2021-01-14 17:24:58
    一种方法是制作长度为4的简单路径的图形并使用子图同构vf2函数.这是最好/最快的方式吗?我没有源节点,我想在整个图中存在长度为4的所有简单路径.在我的数据中,可能很少有这样的路径,我希望能够有效地迭代它们.解决...
  • 子图同构----复杂网络分析(一)

    千次阅读 2020-11-02 09:49:36
    就是一些零散的知识,当然,自己在完成导师给的任务、自己通过互联网寻找解决问题的方法,对我自己的相应能力的提升都是很重要的。也希望大家能在互联网上找到自己想要的东西。如果你对这方面感兴趣的话,可以自己做...
  • 基于大图处理框架的分布式子图同构研究,刘杨,张熙,在大数据时代,越来越多的实际计算问题都涉及到大图的处理,例如互联网和各式各样的社交网络。子图同构是图处理领域的基础性研究
  • 为了找出随采掘进行而开挖的高联巷道因风流不稳定导致危险性较高的区域,提出了一种基于子图同构的煤矿高风险区域自动识别方法。分析了典型高危区域的拓扑结构特性,构建了高风险区域的等效图模型;实现了通风系统的...
  • 图说子图同构算法——VF2算法(一)

    万次阅读 多人点赞 2016-10-09 01:53:47
    写在前面的话谨以此系列献给 my grandpa~体验过...1.2你必需知道的事情虽然子图同构问题没有图的同构问题要求这么严,图的同构必须要求结点的度必须相同,否则不同构。如果在一个图中某个节点的度大于要匹配的图形的
  • 人工智能-机器学习-有向图子图同构计算算法研究.pdf
  • 基于子图同构的三维CAD模型局部匹配.pdf
  • 电子政务-基于子图同构的子电路签名方法.zip
  • 基于子图同构的三维CAD模型局部匹配探讨.pdf
  • 上图两棵树就是同构的 也就是说,两棵树通过交换树链位置可以变成完全相同的树,这两棵树就是同构的 于是算法就出来了,我们可以把每棵树按一定规则交换树链位置,判断是否完全相同 *怎么做呢? 1、首先用括号...
  • 当对单个或批量查询的静态设置,子图同构搜索问题得到了相当多的关注,但现有方法不能扩展到连续查询流的动态设置。在本文中,我们通过缓存和重用以前的结果来解决由子图同构查询流引起的可伸缩性挑战。首先,我们...
  • 子图同构计数与匹配的双消息传递图卷积网络_Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching.pdf
  • 子图同构算法-VF2(java实现)

    千次阅读 2020-03-30 09:39:36
    最近在项目中用到了子图同构算法VF2在这里记录一下。内容主要来自一篇论文(A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs)
  • vf3lib:VF3算法-解决大型图和密集图上子图同构的最快算法
  • local candidate reduction 在之前的compute candidate的基础上增加一个profile选项,profile包含S中每个node的neighbour所拥有的label(可以重复),按照字母顺序排序,在判断candidate时考虑是否G中对应的node(v)的...
  • 超图查询&子图同构

    2014-04-05 13:42:57
    本文档细致的讲述了超图查询问题、子图同构问题,比给出常用的计算方法。
  • 子图同构算法实现,Ullman算法,用java代码实现。
  • 子图同构

    2014-12-09 21:56:00
    子图同构定义: 给定图$Q=(V(Q),E(Q),L_V,F)$和$G=(V(G),E(G),L_V',F')$, 称$Q$子图同构于$G$ 当且仅当存在一个映射$g:V(Q)\rightarrow V(G)$ 使得 \[\forall x\in V(Q), F(v)=F'(g(v))\] 和 \[\forall v_1 ,v_...
  • 子图同构的Ullmann算法的matlab实现

    千次阅读 2014-05-18 13:58:03
    %Ullmann算法:子图同构算法中最简单的一种 %判断图b中是否有子图同构于a %a和b是图的邻接布尔矩阵 %返回0代表没有找到,1代表找到了. %p1和p2代表a和b的阶  [p1,tmp]=size(a);  [p2,tmp]=size(b);  %ab...
  • (子)图同构算法VF2实现(1)

    万次阅读 2015-11-11 09:00:54
    子图同构问题本质上就是一种匹配,VF2算法加了很多feasibility rules,保证了算法的高效性。这里只是实现最基本的判断子图同构的算法: 参考文献有(其实google一把就能出来这些): ... ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,332
精华内容 532
关键字:

子图同构问题