大规模网络中k点连通分量的分布式计算  

Distributed Computation of k-Vertex Connectivity Components in Large-scale Networks

作　　者：王立松 WANG Lisong(School of Information,North China University of Technology,Beijing 100144)

机构地区：[1]北方工业大学信息学院,北京100144

出　　处：《软件》2024年第7期172-174,共3页Software

摘　　要：近年来,k点连通分量(k-VCC)由于其结构内聚性而成为图分析中的一个关键点。k-VCC是指在删除k-1个顶点后剩余的图仍然连通的子图。现有算法对k-VCC问题的研究主要集中在单机环境下,为此,本文设计了一个分布式计算框架,挖掘给定图中的所有k-VCC,将挖掘大图的问题划分为多个更小的子图以并发执行挖掘任务。通过实验证明了所提出的分布式方法的有效性和高效性。In recent years,the k-vertex connected component(k-VCC)has become a key point in graph analysis due to its structural cohesion.k-VCCs are subgraphs whose remaining graphs are still connected after removing k-1 vertices.Existing algorithms for the k-VCC problem mainly focus on a single-computer environment.For this reason,in this paper,we design a distributed computational framework to mine all the k-VCCs in a given graph,and divide the problem of mining a large graph into multiple smaller subgraphs to perform the mining task concurrently.The effectiveness and efficiency of the proposed distributed approach is demonstrated experimentally.

关 键 词：k点连通分量 分布式计算 图划分 

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