Dismantling
Algorithms for network dismantling and influencer search.
Erdos.dismantle_ci
— Methoddismantle_ci(g::AGraph, l::Integer, nrem; verbose=false)
Applies the Collective Influence (CI) heuristic of Ref. [1] with distance parameter l
(tipically l=3,4
). Removes a maximum of nrem
vertices from g
, trying to minimize the size of the maximum connected component of the resulting graph. It stops earlier if the maximum CI goes to zero.
Set verbose
to true
for info printing in each iteration.
Returns (gnew, vmap, remlist)
, where gnew
is the reduced graph, vmap
is a vertex map of the vertices of gnew
to the old ones (see also rem_vertices!
) and remlist
contains the removed vertices by removal order.
For more fine grained control see dismantle_ci_init
and dismantle_ci_oneiter!
.
Usage
g = Graph(100, 1000)
l=3
nrem=10
gnew, vmap, remlist = dismantle_ci(g, l, nrem)
# or equivalently
gnew, heap, lneigs = dismantle_ci_init(g, l)
for it=1:nrem
irem = dismantle_ci_oneiter!(gnew, heap, lneigs, l)
irem <= 0 && break
push!(remlist, irem)
println("Size Max Component: ", maximum(length, connected_components(g)))
end
vmap = rem_vertices!(gnew, remlist)
[1] Morone F., Makse H. Influence maximization in complex networks through optimal percolation. Nature (2015)
Erdos.dismantle_ci_init
— Methoddismantle_ci_init(g, l)
Initialization part of dismantle_ci
algorithm. Returns (gnew, heap, lneigs)
.
Erdos.dismantle_ci_oneiter!
— Methoddismantle_ci_oneiter!(g, heap, lneigs, l)
One step of dismantle_ci
algorithm. To be called after dismantle_ci_init
Returns the cleaned vertex if any (see clean_vertex!
), -1 otherwise.