首页|基于顶点粒的强连通分量挖掘算法

基于顶点粒的强连通分量挖掘算法

Algorithm for finding strongly connected components based on vertex granules

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
强连通分量问题的实质是将有向图分解为一组互不相交的极大强连通子图.每个子图中的任一顶点到其它顶点都是可达的,既是其它顶点的祖先,又是后代.利用宽度优先搜索(BFS)可得到目标有向图中任一顶点的祖先顶点集与后代顶点集,两个集合的交集即为包含当前顶点的强连通分量.首先,基于BFS的强连通分量挖掘方法(BSCC)的效率取决于BFS被调用次数,因此,引入了3种启发式信息来减少BFS调用次数.对强连通分量进行深入分析,发现了顶点间的两种相关性.满足任一相关性的两个顶点不会分属两个有价值强连通分量.根据这两种相关性提出了一种顶点粒化策略,可构建每个顶点所对应的顶点粒,继而提出了基于顶点粒的强连通分量挖掘算法(GSCC),优化了BSCC算法中顶点调用BFS的方式,提高了强连通分量挖掘效率.实验结果表明,相比BSCC算法和线性复杂度的Tarjan算法,GSCC算法具有更好的性能.
The essence of strongly connected components(SCCs)is to decompose a directed graph into a set of maximally disjoint strongly connected subgraphs.In every subgraph,each vertex is reachable to other vertices,is both ancestor and descendant of other vertices.For an arbitrary vertex,the sets of descendants and ancestors of it can be obtained by using of breadth-first search(BFS),then the intersection of the two sets is exactly the SCC containing this vertex.Firstly,this paper introduces an algorithm called BSCC of finding strongly connected com-ponents based on BFS.The efficiency of BSCC depends on the invocation times of BFS.Therefore,three heuris-tic information are used in BSCC algorithm to reduce the invocation times of BFS.Secondly,two SCCs correla-tions between vertices are found.Two vertices satisfying any correlation cannot induce two different nontrivial SCCs.Thus,a vertex granulation strategy is proposed based on the two SCCs correlations,and the vertex gran-ules corresponding to each vertex are formed by using the granulation strategy.As a result,an algorithm called GSCC for finding SCCs based on the vertex granules is proposed.GSCC optimizes the invocation way of BFS by comparison with BSCC algorithm,and improves the efficiency of computing strongly connected components.Fi-nally,the experimental results show that the proposed GSCC algorithm performs better than the BSCC algorithm and Tarjan algorithm of linear complexity.

strong connected componentsgraph theorybreadth-first searchgranulation strategyvertex gran-ules

徐泰华、程富豪、宋晶晶、杨习贝、杨洁、崔芸

展开 >

江苏科技大学 计算机学院,镇江 212100

浙江省海洋大数据挖掘与应用重点实验室,舟山 316022

遵义师范大学 物理与电子科学学院,遵义 563002

强连通分量 图论 宽度优先搜索 粒化策略 顶点粒

国家自然科学青年科学基金项目国家自然科学青年科学基金项目国家自然科学青年科学基金项目国家自然科学青年科学基金项目江苏省高等学校自然科学基金项目浙江省海洋大数据挖掘与应用重点实验室开放课题浙江省海洋大数据挖掘与应用重点实验室开放课题

6200609961906078620761116200612820KJB520010OBDMA202104OBDMA202002

2024

10.20061/j.issn.1673-4807.2024.03.012

江苏科技大学学报(自然科学版)
江苏科技大学

江苏科技大学学报(自然科学版)

影响因子：0.373
ISSN：1673-4807
年,卷(期)：2024.38(3)