Measures of node betweenness-like centrality

These functions calculate common betweenness-related centrality measures for one- and two-mode networks:

• node_by_betweenness() measures the betweenness centralities of nodes in a network.

• node_by_induced() measures the induced betweenness centralities of nodes in a network.

• node_by_flow() measures the flow betweenness centralities of nodes in a network, which uses the maximum flow that the ties can carry between other nodes in contrast to the shortest paths model used by normal betweenness centrality. Given from or to, it instead measures the maximum flow between that node and each other node.

• node_by_stress() measures the stress centrality of nodes in a network.

These four differ in what they count: node_by_betweenness() sums the proportion of shortest paths between each pair that run through a node, so every pair of nodes contributes at most one unit however many shortest paths connect it; node_by_stress() instead sums the raw count of those paths, so pairs joined by many equally short routes count for more; node_by_flow() abandons shortest paths altogether for maximum flow, crediting nodes that carry traffic along longer routes as well; and node_by_induced() asks a different question again — not how much passes through a node, but how much total betweenness the network would lose if it were removed. For ties rather than nodes, see tie_by_betweenness().

All measures attempt to use as much information as they are offered, including whether the networks are directed, weighted, or multimodal. If this would produce unintended results, first transform the salient properties using e.g. to_undirected() functions. All centrality and centralization measures return normalised or scaled measures where available, reported when the measure is printed.

node_by_betweenness(.data, normalized = TRUE, cutoff = NULL)

node_by_induced(.data, normalized = TRUE, cutoff = NULL)

node_by_flow(.data, from, to, normalized = TRUE)

node_by_stress(.data, normalized = TRUE)

Arguments

.data

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().

normalized

Logical scalar, whether scores are normalized. Different denominators may be used depending on the measure, whether the object is one-mode or two-mode, and other arguments. By default TRUE.

cutoff

The maximum path length to consider when calculating betweenness. If negative or NULL (the default), there's no limit to the path lengths considered.

from, to

Index or name of a node to measure the maximum flow from or to. If neither is given (the default), node_by_flow() returns flow betweenness centrality.

Value

A node_measure numeric vector the length of the nodes in the network, providing the scores for each node. If the network is labelled, then the scores will be labelled with the nodes' names.

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().

Cognitive social structures

A cognitive social structure records each node's report of the ties in the whole network, in a by column that names who reported each tie. Counting every report as a tie of its own would count each tie once for every perceiver who reports it. So the functions here first combine the reports into the locally aggregated structure of Krackhardt (1987), with the intersection rule: a tie exists if both of its ends report it, and a message says so. A tie that names no reporter is kept as it is.

A tie-level function still returns one value for each report, so that the result can be added back to the network it was given. Each report takes the value of the tie that it reports. A report of a tie that is not in the aggregated structure takes NA, or FALSE for a mark. tie_is_random() is the exception, and draws among the reports.

To combine the reports in a different way, do this before the function, e.g. with manynet::to_aggregated(over = "by").

Krackhardt, David. 1987. "Cognitive social structures". Social Networks 9(2): 109-134. doi:10.1016/0378-8733(87)90009-8

Signed networks

These measures read a tie as a distance, and a negative tie is hostility rather than a channel along which cohesion travels. Where the network is signed, they therefore consider only the positive ties, and say so. Use manynet::to_unsigned() first to control this yourself.

Betweenness centrality

Betweenness centrality is based on the number of shortest paths between other nodes that a node lies upon: $$C_B(i) = \sum_{j,k:j \neq k, j \neq i, k \neq i} \frac{g_{jik}}{g_{jk}}$$

Setting cutoff counts only those shortest paths no longer than \(k\), which elsewhere goes by distance-bounded betweenness (Brandes, 2008) or range-limited betweenness (Ercsey-Ravasz et al., 2012). Normalization still applies, so a bounded score remains comparable across networks.

Induced centrality

Induced centrality concerns the change in total betweenness centrality between networks with and without a given node: $$C_I(i) = C_B(G) - C_B(G\ i)$$ This "remove the node and re-measure" logic is the general delta centrality framework of Latora and Marchiori (2007); node_by_induced() is its betweenness instance, and node_by_vitality() its closeness instance.

Flow betweenness centrality

Flow betweenness centrality concerns the total maximum flow, \(f\), between other nodes \(j,k\) in a network \(G\) that a given node mediates: $$C_F(i) = \sum_{j,k:j\neq k, j\neq i, k\neq i} f(j,k,G) - f(j,k,G\ i)$$ When normalized (by default) this sum of differences is divided by the sum of flows \(f(i,j,G)\).

Maximum flow

Given from or to, node_by_flow() is not a centrality index but a flow query, as node_by_distance() is a distance query: it reports the maximum flow \(f(i,j,G)\) that the ties can carry from the named node to each other node (or to the named node from each other). By the max-flow min-cut theorem this is also the smallest total capacity of ties that would need to be removed to separate the two nodes. Flow betweenness is built from this quantity: maximum flow says how much can pass between two nodes, and flow betweenness how much of what passes between others depends on a third. The named node has no flow to itself, and so is NA. When normalized (by default) each flow is divided by the most that could leave its source or enter its target, the smaller of the source's out-strength and the target's in-strength. The smallest maximum flow between any two nodes in a network is its tie connectivity; see net_by_adhesion().

Weighted networks

node_by_flow() reads a tie's weight as its capacity: how much the tie can carry, so that a heavier tie carries more. Note that this is the reverse of the shortest-path measures documented here, which read a weight as a distance. An unweighted tie has a capacity of one. Use manynet::to_unweighted() first to treat all ties alike.

Stress centrality

Stress centrality is the number of all shortest paths or geodesics, \(g\), between other nodes that a given node mediates: $$C_S(i) = \sum_{j,k:j \neq k, j \neq i, k \neq i} g_{jik}$$ High stress nodes lie on a large number of shortest paths between other nodes, and thus associated with bridging or spanning boundaries.

References

On betweenness centrality

Freeman, Linton. 1977. "A set of measures of centrality based on betweenness". Sociometry, 40(1): 35–41. doi:10.2307/3033543

On bounding path length

Brandes, Ulrik. 2008. "On variants of shortest-path betweenness centrality and their generic computation". Social Networks 30(2): 136-145. doi:10.1016/j.socnet.2007.11.001

Ercsey-Ravasz, Maria, Ryan N. Lichtenwalter, Nitesh V. Chawla, and Zoltan Toroczkai. 2012. "Range-limited centrality measures in complex networks". Physical Review E 85(6): 066103. doi:10.1103/PhysRevE.85.066103

On induced centrality

Everett, Martin and Steve Borgatti. 2010. "Induced, endogenous and exogenous centrality" Social Networks, 32: 339-344. doi:10.1016/j.socnet.2010.06.004

On delta centrality

Latora, Vito, and Massimo Marchiori. 2007. "A measure of centrality based on network efficiency". New Journal of Physics 9(6): 188. doi:10.1088/1367-2630/9/6/188

On flow centrality

Freeman, Linton C., Stephen P. Borgatti, and Douglas R. White. 1991. "Centrality in Valued Graphs: A Measure of Betweenness Based on Network Flow". Social Networks, 13(2), 141-154. doi:10.1016/0378-8733(91)90017-N

Koschutzki, D., K.A. Lehmann, L. Peeters, S. Richter, D. Tenfelde-Podehl, and O. Zlotowski. 2005. "Centrality Indices". In U. Brandes and T. Erlebach (eds.), Network Analysis: Methodological Foundations. Berlin: Springer.

On maximum flow

Ford, Lester R., and Delbert R. Fulkerson. 1956. "Maximal flow through a network". Canadian Journal of Mathematics, 8: 399-404. doi:10.4153/CJM-1956-045-5

On stress centrality

Shimbel, A. 1953. "Structural Parameters of Communication Networks". Bulletin of Mathematical Biophysics, 15:501-507. doi:10.1007/BF02476438

See also

Other betweenness: measure_central_tie_between, measure_centralisation_between

Other centrality: 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_centralisation_between, measure_centralisation_close, measure_centralisation_degree, measure_centralisation_eigen

Other measures: measure_assort_net, measure_assort_node, measure_breadth, measure_broker_node, measure_broker_tie, measure_brokerage, 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_features, measure_fit, measure_fragmentation, measure_hierarchy, measure_periods

Other nodal: mark_core, mark_degree, mark_diff, mark_nodes, mark_select_node, measure_assort_node, measure_broker_node, measure_brokerage, measure_central_close, measure_central_degree, measure_central_eigen, measure_closure_node, measure_core, measure_diffusion_node, measure_diverse_node, member_brokerage, member_cliques, member_community, member_community_hier, member_community_modular, member_community_partition, member_community_spread, member_components, member_core, member_diffusion, member_equivalence, motif_brokerage_node, motif_clique, motif_composition, motif_exposure, motif_node, motif_path

Examples

node_by_betweenness(ison_southern_women)
#> # Betweenness centrality, normalized [0, 1]
#> ▆▂▁▁▁ 
#>   Evelyn Laura Theresa Brenda Charlotte Frances Eleanor Pearl  Ruth Verne  Myra
#> 1  0.097 0.052   0.088   0.05     0.011   0.011    0.01 0.007 0.017 0.016 0.016
#> # ... and 7 more values from this nodeset. Use `print_all(...)` to print all values.
#>      E1    E2    E3    E4    E5    E6    E7    E8    E9   E10   E11   E12   E13
#> 1 0.002 0.002 0.018 0.008 0.038 0.065  0.13 0.244 0.226 0.011  0.02 0.018 0.002
#> # ... and 1 more values from this nodeset. Use `print_all(...)` to print all values.
node_by_induced(ison_adolescents)
#> # Induced centrality (-Inf, Inf)
#> ▁▁▄▁▁ 
#>   Betty   Sue  Alice  Jane   Dale   Pam Carol  Tina
#> 1 0.095 0.362 -0.505 0.029 -0.105  1.10 0.895 0.362
node_by_flow(ison_adolescents)
#> # Flow betweenness centrality, normalized [0, 1]
#> ▃▂▁▂ 
#>   Betty   Sue Alice  Jane  Dale   Pam Carol  Tina
#> 1     0 0.357  0.25 0.067 0.143   0.4 0.176     0
node_by_flow(ison_adolescents, from = 1, normalized = FALSE)
#> # Maximum flow [0, Inf)
#> █ 
#>   Betty   Sue Alice  Jane  Dale   Pam Carol  Tina
#> 1    NA     1     1     1     1     1     1     1