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