A Parallel Algorithm for Finding Robust Spanners in Large Social Networks

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Khanda, Arindam, Roy, Satyaki, Roy, Prithwiraj, Das, Sajal K.
Format:	Preprint
Published:	2025
Subjects:	Social and Information Networks Distributed, Parallel, and Cluster Computing
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1866918112283066368
author	Khanda, Arindam Roy, Satyaki Roy, Prithwiraj Das, Sajal K.
author_facet	Khanda, Arindam Roy, Satyaki Roy, Prithwiraj Das, Sajal K.
contents	Social networks, characterized by community structures, often rely on nodes called structural hole spanners to facilitate inter-community information dissemination. However, the dynamic nature of these networks, where spanner nodes may be removed, necessitates resilient methods to maintain inter-community communication. To this end, we introduce robust spanners (RS) as nodes uniquely equipped to bridge communities despite disruptions, such as node or edge removals. We propose a novel scoring technique to identify RS nodes and present a parallel algorithm with a CUDA implementation for efficient RS detection in large networks. Empirical analysis of real-world social networks reveals that high-scoring nodes exhibit a spanning capacity comparable to those identified by benchmark spanner detection algorithms while offering superior robustness. Our implementation on Nvidia GPUs achieves an average speedup of 244X over traditional spanner detection techniques, demonstrating its efficacy to identify RS in large social networks.
format	Preprint
id	arxiv_https___arxiv_org_abs_2508_01485
institution	arXiv
publishDate	2025
record_format	arxiv
spellingShingle	A Parallel Algorithm for Finding Robust Spanners in Large Social Networks Khanda, Arindam Roy, Satyaki Roy, Prithwiraj Das, Sajal K. Social and Information Networks Distributed, Parallel, and Cluster Computing Social networks, characterized by community structures, often rely on nodes called structural hole spanners to facilitate inter-community information dissemination. However, the dynamic nature of these networks, where spanner nodes may be removed, necessitates resilient methods to maintain inter-community communication. To this end, we introduce robust spanners (RS) as nodes uniquely equipped to bridge communities despite disruptions, such as node or edge removals. We propose a novel scoring technique to identify RS nodes and present a parallel algorithm with a CUDA implementation for efficient RS detection in large networks. Empirical analysis of real-world social networks reveals that high-scoring nodes exhibit a spanning capacity comparable to those identified by benchmark spanner detection algorithms while offering superior robustness. Our implementation on Nvidia GPUs achieves an average speedup of 244X over traditional spanner detection techniques, demonstrating its efficacy to identify RS in large social networks.
title	A Parallel Algorithm for Finding Robust Spanners in Large Social Networks
topic	Social and Information Networks Distributed, Parallel, and Cluster Computing
url	https://arxiv.org/abs/2508.01485