tie_by_betweenness() measures the number of shortest paths going through a tie. tie_by_mainpath() measures the number of all paths going through a tie in a directed acyclic network, such as a citation network.

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 normalized measures by default, including for two-mode networks.

tie_by_betweenness(.data, normalized = TRUE)

tie_by_mainpath(.data, variant = c("spc", "splc", "spnp"), 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.

variant

Which traversal count to compute: "spc" (the default), "splc", or "spnp". See the section on main path traversal counts. The variant chosen is reported when the result is printed.

Value

A tie_measure numeric vector the length of the ties in the network, providing the scores for each tie. If the network is labelled, then the scores will be labelled with the ties' adjacent 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().

Edge betweenness centrality

The betweenness centrality of a tie, also known as edge betweenness, counts the shortest paths between other nodes that run along it. It is best known as the quantity iteratively recomputed by the Girvan-Newman community detection algorithm, where the ties with the highest betweenness are removed first; see node_in_betweenness().

For signed networks, tie_by_betweenness() reads each tie by its magnitude. A tie measure holds one value per tie, so it cannot drop the negative ties as the distance measures at the node and network level do. This is what node_by_betweenness() in effect does for a network whose ties are signed but not weighted. Use manynet::to_unsigned() first to control this yourself.

Main path traversal counts

Main path analysis traces the most important lines of development through a directed acyclic network, such as a network of citations, patents, or judgments that cite earlier ones (Hummon and Doreian 1989). Each tie gets a traversal count: the number of paths through the network that run along it. A tie that many paths must use is a critical step in the flow of knowledge from earlier to later nodes. tie_is_mainpath() then marks the main path itself.

The counts are like edge betweenness, except that they count every path, not only the shortest ones. This is possible because a network without cycles holds a finite number of paths. The number of paths through a tie from \(u\) to \(v\) is the number of paths that arrive at \(u\) multiplied by the number of paths that leave from \(v\), and both are counted in one pass through a topological order of the nodes (Batagelj 2003).

The variants differ in where a path can start and end:

  • "spc", the search path count (Batagelj 2003), counts the paths from a source, a node with no incoming ties, to a sink, a node with no outgoing ties. This is the usual choice, and does not change if all ties are reversed.

  • "splc", the search path link count (Hummon and Doreian 1989), counts the paths from any node to a sink, so every node can start a line of development.

  • "spnp", the search path node pair count (Hummon and Doreian 1989), counts the paths from any node to any other node, so ties in the middle of long chains count more than ties at either end.

Normalised counts are divided by the number of paths that the variant counts, so a tie that every such path runs along scores 1.

"splc" depends on the direction of the ties. For a citation network, the ties should point from the cited work to the citing work, as knowledge flows; use manynet::to_redirected() to reverse ties that point from the citing work to the cited one.

For networks with cycles, tie_by_mainpath() stops with an error. Use manynet::to_acyclic() first, and tie_is_feedback() to see the ties that it would remove. For undirected networks, tie_by_mainpath() also stops, since a main path needs a direction. For weighted or signed networks, tie_by_mainpath() counts paths along every tie however it is weighted or signed.

References

On edge betweenness centrality

Girvan, Michelle, and Mark E.J. Newman. 2002. "Community structure in social and biological networks". Proceedings of the National Academy of Sciences 99(12): 7821-7826. doi:10.1073/pnas.122653799

Brandes, Ulrik. 2001. "A faster algorithm for betweenness centrality". Journal of Mathematical Sociology 25(2): 163-177. doi:10.1080/0022250X.2001.9990249

On main path analysis

Hummon, Norman P., and Patrick Doreian. 1989. "Connectivity in a citation network: The development of DNA theory". Social Networks 11(1): 39-63. doi:10.1016/0378-8733(89)90017-8

Batagelj, Vladimir. 2003. "Efficient algorithms for citation network analysis". arXiv cs/0309023. doi:10.48550/arXiv.cs/0309023

Liu, John S., and Louis Y.Y. Lu. 2012. "An integrated approach for main path analysis: Development of the Hirsch index as an example". Journal of the American Society for Information Science and Technology 63(3): 528-542. doi:10.1002/asi.21692

Examples

(tb <- tie_by_betweenness(ison_adolescents))
#> # Betweenness centrality, normalized [0, 1]
#>   `Betty-Sue` `Sue-Alice` `Alice-Jane` `Sue-Dale` `Alice-Dale` `Jane-Dale`
#> 1        0.25       0.107        0.179      0.161        0.089       0.071
#> # ... and 4 more values from this nodeset. Use `print_all(...)` to print all values.
ison_adolescents |> mutate_ties(weight = tb)
#> 
#> ── # The Adolescent Society ────────────────────────────────────────────────────
#> # A labelled, weighted, undirected network of 8 adolescents and 10 friendship
#> ties
#> 
#> ── Nodes 
#> # A tibble: 8 × 1
#>   label
#>   <chr>
#> 1 Betty
#> 2 Sue  
#> 3 Alice
#> 4 Jane 
#> 5 Dale 
#> 6 Pam  
#> # ℹ 2 more rows
#> 
#> ── Ties 
#> # A tibble: 10 × 3
#>    from    to weight    
#>   <int> <int> <tie_mesr>
#> 1     1     2 0.25000000
#> 2     2     3 0.10714286
#> 3     3     4 0.17857143
#> 4     2     5 0.16071429
#> 5     3     5 0.08928571
#> 6     4     5 0.07142857
#> # ℹ 4 more rows
#> 
citations <- create_explicit(A-+C, B-+C, B-+D, C-+E, D-+E, E-+F, D-+F)
tie_by_mainpath(citations)
#> # Search path count, normalized [0, 1]
#>   `A->C` `B->C` `B->D` `C->E` `D->E` `E->F` `D->F`
#> 1   0.25   0.25    0.5    0.5   0.25   0.75   0.25
tie_by_mainpath(citations, variant = "splc", normalized = FALSE)
#> # Search path link count [0, Inf)
#>   `A->C` `B->C` `B->D` `C->E` `D->E` `E->F` `D->F`
#> 1      1      1      2      3      2      6      2