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

Algorithm for finding strongly connected componentsbased on vertex granules

作　　者：徐泰华 程富豪 宋晶晶 杨习贝 杨洁 崔芸 XU Taihua;CHENG Fuhao;SONG Jingjing;YANG Xibei;YANG Jie;CUI Yun(School of Computer,Jiangsu University of Science and Technology,Zhenjiang 212100,China;The Key Laboratory of Oceanographic Big Data Mining&Application of Zhejiang Province,Zhoushan 316022,China;School of Physics and Electronic Science,Zunyi Normal University,Zunyi 563002,China)

机构地区：[1]江苏科技大学计算机学院,镇江212100 [2]浙江省海洋大数据挖掘与应用重点实验室,舟山316022 [3]遵义师范大学物理与电子科学学院,遵义563002

出　　处：《江苏科技大学学报（自然科学版）》2024年第3期77-83,共7页Journal of Jiangsu University of Science and Technology:Natural Science Edition

基　　金：国家自然科学青年科学基金项目(62006099,61906078,62076111,62006128);江苏省高等学校自然科学基金项目(20KJB520010);浙江省海洋大数据挖掘与应用重点实验室开放课题(OBDMA202104,OBDMA202002)。

摘　　要：强连通分量问题的实质是将有向图分解为一组互不相交的极大强连通子图.每个子图中的任一顶点到其它顶点都是可达的,既是其它顶点的祖先,又是后代.利用宽度优先搜索(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 components based on BFS.The efficiency of BSCC depends on the invocation times of BFS.Therefore,three heuristic information are used in BSCC algorithm to reduce the invocation times of BFS.Secondly,two SCCs correlations 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 granules 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.Finally,the experimental results show that the proposed GSCC algorithm performs better than the BSCC algorithm and Tarjan algorithm of linear complexity.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]