赞
踩
1)P(k) = ,代表Degree为k的节点概率分布。在真实图中,P(k)满足幂律分布。
2)路径参数(连通图):
Diamter:d = ,任意两点最短路径的最大值为直径
Average path length:,所有最短路径*2/degree
3)距离系数(邻居节点的紧密程度)
Ei:vi点的neighbor有多少相连的边
ki:点的degree
Ei条边/ki理论上可以组成所有边,衡量该点的邻居节点的紧密程度
,衡量整个图的紧密情况
4)连接度(Connectivity)
最大连通分量
1、Friendster(已于2015年shut down的组合)
P(k) = 介于2~3,即度集中在个别点上。
avg path length= 5;90%节点在8跳内可达。
= 0.0746(属于社区型较强)
最大连通分量聚集99%节点
-small world模型:L 相关与 log N(随机节点的distance和节点数目成对数相关)
1、随机图模型(E-R图模型)
无向图有n个点,(u,v)边的存在概率是p,即每条边的存在概率是p,不存在的概率为1-p。节点的分布满足二项分布。
1)概率见
2)Cavg = E(Ci) =
即,平均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 = 。
BA模型的四个指标:
1)概率为幂律分布,γ = 3;
求概率时特殊:
2)路径参数Path:直径为O(log n/log logn)
3)距离系数:
4)最大连通分量:
5、KG图
是一种递归的图。
Kronecker积为 K1✖K1
概率KG图:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。