# Graph Coarsening And multi-source BFS

2016/05/16 13:49

### Coarsening

[何慧, 胡铭曾, 张宏莉, 裴晓峰, & 杨志. (2005). 网络拓扑图多级分割塌缩阶段算法改进. 华中科技大学学报:自然科学版, 33(S1), 82-85.]

2.1 关键顶点塌缩(KV)算法

a.统计计算图顶点的 a (v),依序保存在二 叉树 S 中;
b .依大小顺序 ,访问 a(v)最大顶点 v_i ,从图的邻接表 B 中查询与 v_i 相邻顶点 , 与 v_i 一起塌缩成一个顶点v′_i,从二叉树 中删除这些顶点 ;
c.生成新图的邻接表 B′, 原本与 v_i 相邻顶 点关联的边都附着到 v′_i 上去;
d .修改塌缩后顶点权值 ,其值等于所有塌缩 顶点权值和;
e.在新邻接表 B′中查询新顶点 v′_i 的相邻顶 点,把这些顶点从二叉树 S 中删除;
f.如果二叉树中还有顶点,则返回 b ,否则算 法结束.

2.2 顶点团塌缩(Vertex Clique)算法

### Multi-source BFS

[ The More the Merrier: Efficient Multi-Source Graph Traversal ]

• Text Note, page 1
算法的大概意思: 在将遍历的当前顶点的邻居压如 NearestQueue <v′, bfs_operator′>时, 加入即将要对它进行遍历的 bfs_operator, 下次遍历的时候, 仅仅选择一个 operator 进行操作.

• Anchored Note, page 1
I

• Highlight, page 1
(i) shares common computation across concurrent BFSs; (ii) greatly reduces the number of random memory accesses during BFS; and (iii) does not in- cur synchronization costs.

• Highlight, page 1
ever-growing 日益增长

• Highlight, page 1
To better comprehend and assess the relationships between entities in this data, and to uncover patterns and new insights, graph analytics has become essential.

• Highlight, page 1
Often, the best one can do with existing approaches in order to reduce the overall runtime is to execute multiple single-threaded BFSs in par- allel, instead of running parallel BFSs sequentially, because the former avoids synchronization and data transfer costs,

• Highlight, page 2
MS-BFS takes an orthogonal approach from previ- ous work: instead of parallelizing a single BFS, we focus on processing a large number of BFSs concurrently in a sin- gle core, while still allowing to scale up to multiple cores. This approach allows us to share the computation between different BFSs without paying the synchronization cost.

• Highlight, page 3
Notably, Beamer et al. [8] propose a bottom-up ap- proach to avoid many failed checks to seen as mentioned before. I

• Underline, page 4
B, S

• Highlight, page 4
we propose an approach to concurrently run multiple BFSs and to share the exploration of vertices across these BFSs by leveraging the properties of small-world networks.

• Highlight, page 4
presented in the previous sec- tion, are orthogonal to our goal: they optimize the runtime execution of a single BFS, while we want to optimize the run- time execution for multiple BFSs.

• Highlight, page 4
Figure 1 depicts, for every BFS level, the percentage of vertex explorations that can be shared by at least 2, 50, 100, and 250 BFSs out of 512 concurrent BFSs as indicated by the bar height and color. Note that the exploration of more than 70% of the vertices in levels 3 and 4 can be shared among at least 100 BFSs, and in level

• Highlight, page 5
4, more than 60% of them can be shared by at least 250 BFSs.

• Highlight, page 5
B = {b1,...,bω}, where each bi represents a BFS, and ω is the total number of BFSs to be executed. Another input is the set S = {s1,...,sω} that contains the source vertex si for each BFS bi.

• Highlight, page 5
Instead of having a single set seen of discovered vertices, each vertex v has its own set seenv ⊆ B of BFSs that have already discovered it; furthermore, the sets visit and visitNext comprise tuples (v′, B′), where the set B′ ⊆ B contains the BFSs that must explore v′.

• Highlight, page 5
each vertex v has its own set seenv ⊆ B of BFSs that have already discovered it; furthermore, the sets visit and visitNext comprise tuples (v′, B′), where the set B′ ⊆ B contains the BFSs that must explore v′.

• Highlight, page 5
includes in

• Highlight, page 5
mergesallBFSsetsfromvisitthatrefertovintoasetB′v

• Highlight, page 5
Thus, B′v contains all BFSs that will explore v in the current level, and v can then be explored only once for all of them.

• Highlight, page 5
visitNext is used as the visit set for the next BFS level

2
0 收藏

0 评论
0 收藏
2