These functions return values relating to how connected a network is and the number of nodes or edges to remove that would increase fragmentation.
net_by_cohesion() measures the minimum number of nodes to remove
from the network needed to increase the number of components.
net_by_toughness() measures the number of nodes that would need to be
removed from a network to increase its number of components.
net_by_adhesion() measures the minimum number of ties to remove
from the network needed to increase the number of components,
or the minimum total weight of such ties in a weighted network.
net_by_strength() measures the number of ties that would need to be
removed from a network to increase its number of components.
net_by_robustness() measures how slowly the network's largest component
shrinks as its nodes are removed one at a time,
either at random or in order of some node measure.
net_by_cohesion(.data)
net_by_adhesion(.data)
net_by_strength(.data, limit = 20)
net_by_toughness(.data, limit = 20)
net_by_robustness(.data, node_measure = NULL, times = 100)A network object of class stocnet, igraph, tbl_graph, network, or similar.
Internally any of these will be coerced to an efficient implementation.
For more information on possible coercions, see e.g. manynet::as_stocnet().
The largest network net_by_strength() and
net_by_toughness() will enumerate: the number of ties for the first and
of nodes for the second. By default 20. Above this each stops rather than
running for hours. Raise it to measure a larger network anyway.
How the nodes to remove are chosen.
By default NULL, which removes nodes at random,
so that the network suffers failure rather than attack.
Otherwise, at each step the node that node_is_max() marks is removed,
choosing at random among any tied for the maximum.
Give a node_by_*() function, such as node_by_degree,
to recompute the measure on the network remaining after each removal,
which is an adaptive attack.
Give a node_measure object, such as node_by_degree(.data),
to remove nodes in the order of the scores the intact network gives them,
which is a static attack.
To pass further arguments, give a function of the network,
e.g. \(x) node_by_closeness(x, normalized = FALSE).
Integer scalar, how many times the algorithm repeats its work. Where the algorithm is stochastic, this is how many times it runs, and the best or the most frequent result is kept. Where the algorithm searches, this is how many steps the search takes. More repetitions give a more reliable result and take longer, so each function documents its own default.
A network_measure numeric score.
The object also carries the measure it computed, the range its values
can fall within, and whether and how those values were normalized.
These are shown as a one-line header when the object is printed.
Where a measure offers a choice between several ways of counting the
same thing, it also carries the variant it used.
All can be retrieved with attr().
For weighted networks, net_by_adhesion() reads a tie's weight as its capacity,
and so returns the smallest total weight of ties whose removal would
increase the number of components, the network's minimum cut,
rather than the smallest number of such ties.
This is also the smallest maximum flow between any two of its nodes;
see node_by_flow() for the flow between particular nodes.
Use manynet::to_unweighted() first to count ties instead.
The other measures documented here count nodes or ties whatever
their weight.
For signed networks, net_by_adhesion() considers only the positive
ties, and says so.
It asks what holds a network together,
and a negative tie is hostility rather than a channel along which
cohesion travels.
Use manynet::to_unsigned() first to control this yourself.
net_by_robustness() also considers only the positive ties.
The other measures documented here use every tie whatever its sign.
net_by_cohesion() and net_by_adhesion() are connectivity problems that
{igraph} solves directly, so they run on a network of any size.
net_by_strength() and net_by_toughness() instead take a minimum over
every subset of the tieset or the nodeset, which is \(2^n\) subsets.
Their cost therefore quadruples for every two nodes added: a ring of 16
nodes takes about 8 seconds, one of 20 over two minutes, and one of 30
more than a day. limit stops each before it becomes a hang.
net_by_robustness() removes the nodes of a network one at a time,
recording after each removal the share of the original nodes that
remain in the largest weak component.
It returns the mean of these shares over all \(N\) removals,
Schneider et al.'s \(R\).
A star attacked at its hub falls apart at once, scoring about \(1/N\),
while a complete network loses only one node with each removal,
scoring \((N-1)/2N\), which approaches the maximum of 0.5.
Comparing a random failure against an attack shows, as Albert, Jeong and
Barabási found, that a network with a few hubs tolerates failure
but is fragile under attack.
The share remaining after each number of removals is kept as the
curve attribute of the result, a table with columns
removed, the share of the nodes removed, and giant,
the share of the original nodes in the largest component,
averaged over the times runs.
Retrieve it with attr(x, "curve").
Nodes are chosen at random wherever several are tied,
so the result is averaged over times runs, by default 100.
Where an attack meets no ties, every run would be the same,
so it runs once.
Each run computes the measure once per node removed,
so an adaptive attack by an expensive measure, such as betweenness,
on a network of several hundred nodes can take some minutes.
Lower times, or attack with a node_measure object, to go faster.
For signed networks,
net_by_robustness() considers only the positive ties,
since a negative tie does not hold a component together.
For two-mode networks,
node_is_max() marks the highest-scoring node in each mode,
so an attack on a two-mode network chooses at random between the two.
White, Douglas R and Frank Harary. 2001. "The Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density." Sociological Methodology 31(1): 305-59. doi:10.1111/0081-1750.00098
Albert, Réka, Hawoong Jeong, and Albert-László Barabási. 2000. "Error and attack tolerance of complex networks." Nature 406: 378-82. doi:10.1038/35019019
Schneider, Christian M., André A. Moreira, José S. Andrade, Shlomo Havlin, and Hans J. Herrmann. 2011. "Mitigation of malicious attacks on networks." Proceedings of the National Academy of Sciences 108(10): 3838-41. doi:10.1073/pnas.1009440108
Other cohesion:
mark_triangles,
measure_breadth,
measure_cohesion,
motif_net,
motif_node
Other measures:
measure_accuracy_net,
measure_accuracy_node,
measure_assort_net,
measure_assort_node,
measure_breadth,
measure_broker_node,
measure_broker_tie,
measure_brokerage,
measure_central_between,
measure_central_close,
measure_central_degree,
measure_central_eigen,
measure_central_tie_between,
measure_central_tie_close,
measure_central_tie_degree,
measure_central_tie_eigen,
measure_closure,
measure_closure_node,
measure_cohesion,
measure_core,
measure_diffusion_infection,
measure_diffusion_net,
measure_diffusion_node,
measure_diverse_net,
measure_diverse_node,
measure_diverse_tie,
measure_features,
measure_fit,
measure_hierarchy,
measure_periods
net_by_cohesion(fict_greys)
#> # Node connectivity [0, Inf)
#> [1] 0
net_by_cohesion(to_giant(fict_greys))
#> # Node connectivity [0, Inf)
#> [1] 1
net_by_adhesion(fict_greys)
#> # Tie connectivity [0, Inf)
#> [1] 0
net_by_adhesion(to_giant(fict_greys))
#> # Tie connectivity [0, Inf)
#> [1] 1
net_by_strength(ison_adolescents)
#> # Strength [0, Inf)
#> [1] 0.5
net_by_toughness(ison_adolescents)
#> # Toughness [0, Inf)
#> [1] 0.5
sf <- generate_scalefree(50, 0.5)
net_by_robustness(sf)
#> # Robustness to random failure, normalized [0, 0.5]
#> [1] 0.247
net_by_robustness(sf, node_measure = node_by_degree)
#> # Robustness to adaptive attack, normalized [0, 0.5]
#> [1] 0.0675