manip_paths: Modifying networks paths

In manynet: Many Ways to Make, Modify, Map, Mark, and Measure Myriad Networks

Modifying networks paths

Description

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_eulerian() returns only the Eulerian path within some network data.

• 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

Usage

to_matching(.data, mark = "type", capacities = NULL)

to_mentoring(.data, elites = 0.1)

to_eulerian(.data)

to_tree(.data)

to_dominating(.data, from, direction = c("out", "in"))

Arguments

.data	An object of a manynet-consistent class: matrix (adjacency or incidence) from {base} R edgelist, a data frame from {base} R or tibble from {tibble} igraph, from the {igraph} package network, from the {network} package tbl_graph, from the {tidygraph} package
mark	A logical vector marking two types or modes. By default "type".
capacities	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.
elites	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).
from	The index or name of the node from which the path should be traced.
direction	String, either "out" or "in".

Details

Not all functions have methods available for all object classes. Below are the currently implemented S3 methods:

	data.frame	igraph	matrix	network	tbl_graph
to_eulerian	0	1	0	0	1
to_matching	1	1	1	1	1
to_mentoring	0	1	0	0	1

Value

All to_ functions return an object of the same class as that provided. So passing it an igraph object will return an igraph object and passing it a network object will return a network object, with certain modifications as outlined for each function.

to_matching()

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.

References

On matching

Gale, David, and Lloyd Stowell Shapley. 1962. "College admissions and the stability of marriage". The American Mathematical Monthly, 69(1): 9–14. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.2307/2312726")}

Goldberg, Andrew V., and Robert E. Tarjan. 1986. "A new approach to the maximum flow problem". Proceedings of the eighteenth annual ACM symposium on Theory of computing – STOC '86. 136-146. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1145/12130.12144")}

On mentoring

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. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1177/000271629956600105")}

On Eulerian trails

Euler, Leonard. 1736. "Solutio problematis ad geometriam situs pertinentis". Comment. Academiae Sci. I. Petropolitanae 8: 128–140.

Hierholzer, Carl. 1873. "Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren". Mathematische Annalen, 6(1): 30–32. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1007/BF01442866")}

On minimum spanning trees

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. \Sexpr[results=rd]{tools:::Rd_expr_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. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1002/j.1538-7305.1957.tb01515.x")}

See Also

Other modifications: manip_as, manip_correlation, manip_deformat, manip_from, manip_levels, manip_miss, manip_nodes, manip_permutation, manip_preformat, manip_project, manip_reformat, manip_scope, manip_split, manip_ties

Examples

to_matching(ison_southern_women)
#graphr(to_matching(ison_southern_women))
graphr(to_mentoring(ison_adolescents))
  to_eulerian(delete_nodes(ison_koenigsberg, "Lomse"))
  #graphr(to_eulerian(delete_nodes(ison_koenigsberg, "Lomse")))

manynet documentation built on June 23, 2025, 9:07 a.m.