Exacting Eccentricity for Small-World Networks

Presentation on theme: "Exacting Eccentricity for Small-World Networks"— Presentation transcript:

1 Exacting Eccentricity for Small-World Networks
ICDE 18’ 前几天会议刚结束，所以网上很难找到 近似算法效果很差

2 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) 离线算法，虽然运行时间取决于图的结构，大致可以解决几百万个点，几千万条边的图

3 BoundEcc(state of art)
直接对每个点一边BFS O(mn) 优先队列的设计：1.按照度数递减 2.按照上下界的差递减 3.按照上下界的差递增 Bottleneck在于每个u都要做一遍BFS（其实很多距离近的点是不需要访问的）

4 ECC PLL RefPool EccentricityOneNode 核心思想：
x与z的距离接近，则离z近的点低概率成为离x远的点，所以希望不计算这些点与z的距离之前得到exx(z)。 核心在于prune 先讲EccentricityOneNode

5 EccentricityOneNode z为reference node，x为要求的点的Eccentricity
Bounded set 里点的距离兵不直接算出来，而是通过bound来约束

6 EccentricityOneNode(con’d)
dist(x,z)的大小影响收敛的速度，所以希望dist(x,z)尽可能小

7 RefPool 按照度排序是small world network的常用方法 K的数目可变
由lemma2可知，0<ecc(v)<=2*d

8 ECC vs BoundEcc ECC is, on average, 203.03 times faster than BoundEcc
On Wiki-temporal, ECC is 467 times faster than MaxGap

9 LocalSpread 时间复杂度：每次更新上下界的差最少减1，初始时上下界的差最多为2d(d为直径)，所以每个点最多被访问2d次，所以LS的总时间为O(dm) 依然采用prune的思想

10 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

11 Distance to Reference Nodes
动态图没法做 我觉得这个算法思路很trivial，效果却极好，但是这种需求很难找，希望大家有类似的问题能和我讨论，说不定能想出些什么东西