当前位置:   article > 正文

图生成模型

图生成模型

1、图(网络结构)的参数

        1)P(k) = \frac{N_{k}}{N},代表Degree为k的节点概率分布。在真实图中,P(k)满足幂律分布。

        2)路径参数(连通图):

                Diamter:d = MAX_{i\neq j}(h_{ij}),任意两点最短路径的最大值为直径

                Average path length:\bar{h} = \frac{\sum_{i\neq j}^{}h_{ij}}{n*(n-1)},所有最短路径*2/degree

       3)距离系数(邻居节点的紧密程度)

                Ei:vi点的neighbor有多少相连的边

                ki:点的degree

                C_{local}(v_{i}) = \frac{2E_{i}}{k_{i}*(k_{i} - 1)}        Ei条边/ki理论上可以组成所有边,衡量该点的邻居节点的紧密程度

                

                C_{avg}(G) = \frac{\sum_{i = 1}^{n}C_{local}(v_{i})}{n},衡量整个图的紧密情况

        4)连接度(Connectivity)

                最大连通分量

2、真实图的性质

        1、Friendster(已于2015年shut down的组合)

           P(k) = k^{-\gamma },\gamma介于2~3,即度集中在个别点上。

          avg path length= 5;90%节点在8跳内可达。

           C_{avg} = 0.0746(属于社区型较强)

           最大连通分量聚集99%节点

           -small world模型:L 相关与 log N(随机节点的distance和节点数目成对数相关)    

3、图生成模型

        1、随机图模型(E-R图模型)

        无向图有n个点,(u,v)边的存在概率是p,即每条边的存在概率是p,不存在的概率为1-p。节点的分布满足二项分布。

        1)概率见 

        2)Cavg = E(Ci) =  \frac{2E_{i}}{k_{i}*(k_{i} - 1)}=  \frac{2*p*k_{i}*(k_{i} - 1)*1/2}{k_{i}*(k_{i} - 1)}=  p = \frac{k}{n}

        即,平均degree/n。即使在degree和真实图相同情况下,Cavg明显小于small-world,不具备社区性。

        3) 取log n后每增长1个数量级,path只增加1,和真实图相对比较类似

        4)最大连通分量:如果平均degree k>1,则和真实图类似,有某个聚集了99%的点的连通分量。

        

          真实图和ER随机图的PATH相差不大,主要差距在C,也就是距离系数相差过大。(大概是4个数量级)

        2、K-regular Gaph

        

        K - regular:距离系数高,随之而来的PATH较高。

        3、WS形small-world

        先从低维的K-regular graph开始构建,再对所有边,将某个端点以概率p随机移动到另一个点上。考虑极端情况,p=0,为regular graph;p = 1,为ER图;而且其聚集度只会更高,Path也会更短。

        4、BA模型-动态生成

         这是一个点不断增长的图模型,在生长过程中遵循2-8原则,富者更富,本就频繁的节点会更加频繁。

        step1:随机生成m0个点。

        step2:增加一个新点v,v和m个点相连。已有的每个点和v相连接的概率是P  = \frac{d(v)}{\sum d(w)}

        BA模型的四个指标:

        1)概率为幂律分布,γ = 3;

        求概率时特殊:  

        2)路径参数Path:直径为O(log n/log logn)

        3)距离系数:

        4)最大连通分量:

         5、KG图

        是一种递归的图。

     

        Kronecker积为 K1✖K1

        概率KG图:

 

 

 

 

 

        

        

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/932264
推荐阅读
相关标签
  

闽ICP备14008679号