These functions return tidygraphs containing only special sets of ties:
to_matching() returns only the matching ties in some network data.
to_mentoring() returns only ties to nodes' closest mentors.
to_tree() returns the spanning tree in some network data or,
if the data is unconnected, a forest of spanning trees.
to_dominating() returns the dominating tree of the network.
to_geodesic() returns a network of the shortest path lengths between nodes.
to_matching(.data, mark = "type", capacities = NULL)
to_mentoring(.data, elites = 0.1)
to_tree(.data)
to_dominating(.data, from, direction = c("out", "in"))
to_geodesic(.data)An object of a {manynet}-consistent class:
adjacency or incidence matrix from {base} R
edgelist data.frame from {base} R or tbl/tbl_df from {tibble}
stocnet stocnet, from the {manynet} package
igraph igraph, from the {igraph} package
network network, from the {network} package
tidygraph tbl_graph, from the {tidygraph} package
A logical vector marking two types or modes. By default "type".
An integer or vector of integers the same length as the nodes in the network that describes the maximum possible degree the node can have in the matched network.
The proportion of nodes to be selected as mentors. By default this is set at 0.1. This means that the top 10% of nodes in terms of degree, or those equal to the highest rank degree in the network, whichever is the higher, will be used to select the mentors.
Note that if nodes are equidistant from two mentors, they will choose one at random. If a node is without a path to a mentor, for example because they are an isolate, a tie to themselves (a loop) will be created instead. Note that this is a different default behaviour than that described in Valente and Davis (1999).
The index or name of the node from which the path should be traced.
Character string, “out” bases the measure on outgoing ties, “in” on incoming ties, and "all" on either/the sum of the two. By default "all".
An object of the same class as the function was given, modified as explained in the function description, details, or section. Functions that split a network return a list of such objects.
Not all functions have methods available for all object classes. Below are the currently implemented S3 methods:
This function attempts to solve the stable matching problem, also known as the stable marriage problem, upon a given two-mode network (or other network with a binary mark).
In the basic version,
to_matching() uses igraph::max_bipartite_match()
to return a network in which each node is only tied to
one of its previous ties.
The number of these ties left is its cardinality,
and the algorithm seeks to maximise this such that,
where possible, each node will be associated with just one
node in the other mode or some other mark.
The algorithm used is the push-relabel algorithm
with greedy initialization and a global relabelling
after every \(\frac{n}{2}\) steps,
where \(n\) is the number of nodes in the network.
In the more general version, each node may have a larger capacity, or even different capacities. Here an implementation of the Gale-Shapley algorithm is used, in which an iterative process of proposal and acceptance is repeated until all are matched or have exhausted their lists of preferences. This is, however, computationally slower.
This function returns a network in which each node is tied to its closest mentor. The mentors are selected as the top nodes in terms of degree, or those equal to the highest rank degree in the network, whichever is the higher. The mentees are then tied to the closest mentor in terms of geodesic distance. This can be useful for showing the hierarchical structure of a network, for example in an organisational context, or identifying the most influential nodes in a network.
This function returns a network in which each node is tied to its closest dominating node. A dominating set \(D\) in a graph \(G\) is a subset of nodes such that every node not in \(D\) is adjacent to at least one node in \(D\). The domination number, \(\gamma(G)\), is the size of the smallest such set. This concept underpins many practical network problems: facility location, sensor placement, control theory applied to networks, and backbone selection in ad hoc wireless routing.
This function returns a weighted network of the same nodes,
in which each tie is the length of the shortest path, or geodesic,
from one node to another.
A pair of nodes that no path joins has no tie,
and so a matrix of the result holds 0 for it off the diagonal.
Where the network is directed, a path follows the direction of its ties;
use to_undirected() first for paths that do not.
Where the network is signed, only its positive ties are paths. Where it is weighted, a stronger tie is a shorter step: each tie costs the mean tie weight divided by its own weight (Opsahl, Agneessens, and Skvoretz 2010), so that a tie of average weight is a step of one. The paths of a cognitive social structure are those of its locally aggregated structure, in which a tie is present where both of its nodes report it. A two-mode network returns the paths between all of its nodes, of either mode.
In a hypergraph, a path runs from node to node through the hyperedges
they share, and its length is the number of hyperedges it passes through
(Berge 1973).
The result is a network of the nodes alone, which is the same as the
network of geodesics of the hypergraph's projection, to_mode(.data, 1).
Gale, David, and Lloyd Stowell Shapley. 1962. "College admissions and the stability of marriage". The American Mathematical Monthly, 69(1): 9–14. doi:10.2307/2312726
Goldberg, Andrew V., and Robert E. Tarjan. 1986. "A new approach to the maximum flow problem". Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 136-146. doi:10.1145/12130.12144
Valente, Thomas, and Rebecca Davis. 1999. "Accelerating the Diffusion of Innovations Using Opinion Leaders", Annals of the American Academy of Political and Social Science 566: 56-67. doi:10.1177/000271629956600105
Boruvka, Otakar. 1926. "O jistem problemu minimalnim". Prace Mor. Prirodoved. Spol. V Brne III 3: 37-58.
Kruskal, Joseph B. 1956. "On the shortest spanning subtree of a graph and the travelling salesman problem". Proceedings of the American Mathematical Society 7(1): 48-50. doi:10.1090/S0002-9939-1956-0078686-7
Prim, R.C. 1957. "Shortest connection networks and some generalizations". Bell System Technical Journal 36(6):1389-1401. doi:10.1002/j.1538-7305.1957.tb01515.x
Bange, David W., Anthony E. Barkauskas, and Peter J. Slater. 1988. "Efficient dominating sets in graphs." In Applications of Discrete Mathematics, SIAM, pp. 189–99.
Haynes, Teresa W., Stephen T. Hedetniemi, and Peter J. Slater. 1998. Fundamentals of Domination in Graphs. CRC Press.
Opsahl, Tore, Filip Agneessens, and John Skvoretz. 2010. "Node centrality in weighted networks: Generalizing degree and shortest paths". Social Networks 32(3): 245-251. doi:10.1016/j.socnet.2010.03.006
Berge, Claude. 1973. Graphs and Hypergraphs. North-Holland.
to_matching(ison_southern_women)
#>
#> ── # Stable matching of Southern Women Data ────────────────────────────────────
#> # A labelled, two-mode network of 18 FALSEs and 14 TRUEs and 14 ties
#>
#> ── Nodes
#> # A tibble: 32 × 2
#> label mode
#> <chr> <chr>
#> 1 Evelyn FALSE
#> 2 Laura FALSE
#> 3 Theresa FALSE
#> 4 Brenda FALSE
#> 5 Charlotte FALSE
#> 6 Frances FALSE
#> # ℹ 26 more rows
#>
#> ── Ties
#> # A tibble: 14 × 2
#> from to
#> <int> <int>
#> 1 1 19
#> 2 2 20
#> 3 3 21
#> 4 4 22
#> 5 5 23
#> 6 6 24
#> # ℹ 8 more rows
#>
to_geodesic(ison_adolescents)
#> # A labelled, weighted, undirected network of 8 nodes and 28 ties
#>
#> ── Nodes
#> # A tibble: 8 × 1
#> name
#> <chr>
#> 1 Betty
#> 2 Sue
#> 3 Alice
#> 4 Jane
#> 5 Dale
#> 6 Pam
#> # ℹ 2 more rows
#>
#> ── Ties
#> # A tibble: 28 × 3
#> from to weight
#> <int> <int> <dbl>
#> 1 1 2 1
#> 2 1 3 2
#> 3 1 4 3
#> 4 1 5 2
#> 5 1 6 2
#> 6 1 7 3
#> # ℹ 22 more rows
#>