Exacting Eccentricity for Small-World Networks ICDE 18’ 前几天会议刚结束,所以网上很难找到 近似算法效果很差
Preliminary Eccentricity:ecc(u) = maxv∈Vdist(u,v) small world network: n个点,边数m=O(n),度数分布满足power law, 直径d=O(logn/loglogn) PLL: 点v的一个label定义为(x,dist(v,x)) 每个点v一个label的极小集合S(v),使得对于任意点对u,v dist(u,v) = minx∈S(u)∩S(v) dist(u,x) + dist(x,v) PLL在small world Networks中每个点的label集合的平均大小不超过100,所以可以认为O(1)时间(类似merge sort的方法)得到dist(u,v) 离线算法,虽然运行时间取决于图的结构,大致可以解决几百万个点,几千万条边的图
BoundEcc(state of art) 直接对每个点一边BFS O(mn) 优先队列的设计:1.按照度数递减 2.按照上下界的差递减 3.按照上下界的差递增 Bottleneck在于每个u都要做一遍BFS(其实很多距离近的点是不需要访问的)
ECC PLL RefPool EccentricityOneNode 核心思想: x与z的距离接近,则离z近的点低概率成为离x远的点,所以希望不计算这些点与z的距离之前得到exx(z)。 核心在于prune 先讲EccentricityOneNode
EccentricityOneNode z为reference node,x为要求的点的Eccentricity Bounded set 里点的距离兵不直接算出来,而是通过bound来约束
EccentricityOneNode(con’d) dist(x,z)的大小影响收敛的速度,所以希望dist(x,z)尽可能小
RefPool 按照度排序是small world network的常用方法 K的数目可变 由lemma2可知,0<ecc(v)<=2*d
ECC vs BoundEcc ECC is, on average, 203.03 times faster than BoundEcc On Wiki-temporal, ECC is 467 times faster than MaxGap
LocalSpread 时间复杂度:每次更新上下界的差最少减1,初始时上下界的差最多为2d(d为直径),所以每个点最多被访问2d次,所以LS的总时间为O(dm) 依然采用prune的思想
ECC-LS vs ECC we only report the cost of the third phase: Eccentricity This shows that the processing time for Eccentricity is proportional to the number of PLL inquiries
Distance to Reference Nodes 动态图没法做 我觉得这个算法思路很trivial,效果却极好,但是这种需求很难找,希望大家有类似的问题能和我讨论,说不定能想出些什么东西