Efficient Core Maintenance of Dynamic Graphs 读感

作者:Wen Bai1, Yuxiao Zhang1, Xuezheng Liu1, Min Chen3, and DiWu1,2

摘要

kcore 是一个内聚子图,计算整个图的kcore耗费的时间长,又因为图总是处在变化当中,会带来很大的开销,如果我们自己只计算由于增长或者减少而受影响的点的kcore会大大减少工作量。

1、介绍

kcore是一个图G的最大子图,其中kcore中的每个节点的degree>=k;寻找顶点的核数问题被叫做核分解。如果更新更新整个动态的core数,代价太大,所以只更新受影响的节点。
本文主要有三点贡献:

  • 拟kcore,不像kcore定义那么严格,如果借助某一点能成为kcore这些点就叫做拟kcore
  • 更新受影响的顶点,从稀疏到密集

2、前沿(定义才是难理解的,哈哈哈)

|G|=|V(G)|+|E(G)|K0 是一个空图,没有任何顶点和边;N(G,v)表示顶点v在G中的邻居顶点集;|N(G,v)|表示顶点v的度用d(G,v)表示;Gc表示插入或者删除节点之后的图,Gp表示插入和删除之前的图
集合有四种关系:相交、 属于、并集、查集

定义1

kcore是最大的子图,任何顶点的度大于等于k。如果k=0,表示的图G本身。φ(G, v) = k顶点v在G中的最大核数。φ(G)图G的最大核数。

定义2

邻居图,通俗一点讲就是,新插入的顶点的集合V(s),原来的图Gp中和这些新插入的顶点相邻的顶点的集合{v : v ∈ N(G, u) ∧ u ∈ V (S)},这两个集合的并集。

定义3

拟kcore,quasi−k−core ˆ C(S, G, k)我理解就是当你插入顶点或者边时,这些新插入的顶点有可能已经成为真正的kcore,也有可能包含一些节点需要算原来的图中的节点才能成为kcore。 为了看哪些顶点借助了原来图的顶点,以及原来的图中哪些顶点受到新插入顶点的影响,所有需要知道新插入的图和原来图之间的关系也即边。所以有了邻居图的定义。

定义4

由于Gp也就是原来的顶点的帮助,这些拟kcore才能成为真正的kcore,而这些起辅助作用的顶点,有可能原来就是kcore或者由于新增加顶点从而成为kcore,也有可能成不了kcore这三种顶点的类型。而第一种本身就是kcore的新增加的节点并不会产生实际性的左右所以排除掉。所以通过拟kcore来扩展成候选图。
候选图F(k):Gc的所有(k-1)core,但是去除Gp中的已经成为kcore的图。P(k) = C(Gc, k) \ C(Gp, k),ˆ C(P(k), C(Gp, k), k) = P(k).

算法

Algorithm 1: Insertion Case (IC)

Input: Si: the insertion graph, Gc: the current graph, φ: a map of vertices
and their core number.
Output: φ: a map of vertices and their core number.
1 decompose Si to a set of quasi−k−cores;//把插入的节点分解
2 φ(v) ← 1 for v ∈ Si; // 每个节点最少是一,如果不是1,就相当于没有和Gp连接
3 k ← 2; // 我认为 如果k=1,也就是因为添加新节点才变成1,原来k=0,是个孤立的顶点,不考虑
4 while k ≤ ˆφ(Si,Gc) do// 分层遍历Si
5 expand the quasi−k−core to a candiadte graph;
6 if k ≤ φ(Gp) then
7 get ˆ C(F(k), C(Gp, k), k) from F(k);// 把任何受到影响的节点都更新core number,所有从k=2开始
8 φ(v) ← k for v ∈ ˆ C(F(k), C(Gp, k), k);
9 k ← k + 1;
10 else
11 execute core decomposition on F(k);
12 for v ∈ F(k) do
13 φ(v) ← φ(F(k), v) if φ(F(k), v) ≥ k;
14 break;
15 return φ;

Algorithm 2: Removal Case (RC)

firstly, we decompose Sr to a set
of quasi−k−cores with the aid of Gp; secondly, we delete the common edges in
ˆ C(Sr,Gp, k) ∩ C(Gp, k) and recursively remove influenced vertices that cannot
be located in C(Gp, k); thirdly, we continue the loop until all affected k−cores
are updated.
共包括三步:

  1. 按层分解被删除的顶点
  2. 删除ˆ C(Sr,Gp, k) ∩ C(Gp, k)的公共边,移除那些在Gp中被删除的顶点而影响的顶点
Input: Sr: the removal graph, Gp: the previous graph, φ: a map of vertices
and their core number.
Output: φ: a map of vertices and their core number.
1 decompose Sr to a set of quasi−k−cores;
2 ˆφ(Sr,Gp) ← φ(Gp) if ˆφ(Sr,Gp) > φ(Gp);// 我感觉这没有用
3 k ← 1;
4 while k ≤ ˆφ(Sr,Gp) do
5 let Q be an empty queue;
6 for (u, v) ∈ ˆ C(Sr,Gp, k) ∩ C(Gp, k) do // 我认为 这个是被删除顶点和未被删除顶点之间的边
7 remove (u, v) from C(Gp, k);
8 push u (v) into Q if d(C(Gp, k), u) < k (d(C(Gp, k), v) < k);//找出被删除顶点中因为依靠原来顶点才成为kcore的点
9 adjust C(Gp, k) by removing vertices in Q;
10 update core number of affected vertices in φ;
11 k ← k + 1;
12 return φ;

说明:本文章对这篇论文都是自己的理解,如果不对请提出

上一篇:Win10家庭版找不到组策略gpedit.msc怎么办


下一篇:GP--大表分区管理(一)