GraphFragments.jl

Introduction

GraphFragments.jl implements the fragmentation metric introduced by Borgatti. The package includes standard implementation, distance-based fragmentation, and serial and distributed approaches.

Use

The fragmentation of the graph can be calculated using the fragmentation function. This function will automatically try to run in parallel if the keyword argument parallel_approach = true (default) is set; this can be fixed to run serially if desired or in parallel (if a script is setup to automatically run in parallel).

Fragmentation relies on the calculation of shortest paths across the graph from each starting node; if parallelized, the calculation will use synchronous data parallelization to distribute each source node on an available compute node. A dictionary of DistributedArrays.DArray objects for use by the distance algorithm can be passed using the dict_arrays argument, though the user should ensure these arrays match those necessary for the algorithm specificed by distance_algorithm. These arrays can include intermediate algorithmic vectors as well as any applicable heap cache arrays.

The user can access information about these arguments using the docstrings for fragmentation in Julia.

fragmentation( graph::Union{AbstractGraph, Nothing}, dict_arrays::Union{Dict{Symbol, Vector}, Dict{Symbol, DArray}, Nothing} = nothing; D_invs::Union{Matrix{Int64}, Matrix{Float64}, Nothing} = nothing, distance_algorithm::Symbol = :auto, parallel_approach::Symbol = :auto, use_distance_weighting::Bool = true, kwargs... )

fragmentation( adj::Union{SparseMatrixCSC{Float64, Int64}, Matrix{Float64}}; kwargs... )

Data

The code only needs a Graph to work off of. This can be loaded in a Julia session using Graphs.jl. If using DiscreteGraphAlgorithms.jl, then the graph property of a GraphWrapper can be used.

Project information

The authors are grateful to RAND Center for Global Risk and Security Advisory Board members Michael Munemann and Paul Cronson for funding this project. All code was developed between April 2023 and October 2024.

References/Bibliography

Borgatti, Steve, The Key Player Problem (September 21, 2002). Available at SSRN: https://ssrn.com/abstract=1149843 or http://dx.doi.org/10.2139/ssrn.1149843

Copyright and License

Copyright (C) <2024> RAND Corporation. This code is made available under the MIT license.

Authors and Reference

James Syme, 2024.

@misc{GDA2024, author = {Syme, James}, title = {GraphFragments.jl: Distributed implementation of Key-Player Problem negative (KPP-Negative) metric.}, year = 2024, url = {URLHERE} }