These functions implement logical tests for various network features.
is_connected() tests whether network is connected,
by default in the strong sense where ties are directed.
Pass connectivity = "weak" to ignore tie direction.
is_perfect_matching() tests whether there is a matching
for a network that covers every node in the network.
is_eulerian() tests whether there is a Eulerian path for a network
where that path passes through every tie exactly once.
is_acyclic() tests whether network is a directed acyclic graph.
is_aperiodic() tests whether network is aperiodic.
is_connected(.data, connectivity = c("strong", "weak"))
is_perfect_matching(.data, mark = "type")
is_eulerian(.data)
is_acyclic(.data)
is_aperiodic(.data, max_path_length = 4)https://stackoverflow.com/questions/55091438/r-igraph-find-all-cycles
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
Character string, "weak" treats a directed network's components as if the network were undirected, and "strong" requires ties in both directions between members. This is ignored for undirected networks, where the two notions coincide. Note that the default differs by function: marks that assert connectedness default to "strong", while functions that scope or split a network into components default to "weak".
A logical vector marking two types or modes. By default "type".
Maximum path length considered. If negative, paths of all lengths are considered. By default 4, to avoid potentially very long computation times.
TRUE if the condition is met, or FALSE otherwise.
Not all functions have methods available for all object classes. Below are the currently implemented S3 methods for these functions:
default igraph
is_acyclic * *
is_aperiodic * *
is_connected * *
is_eulerian * *
is_perfect_matching * *If a method is not available for a particular class, but a default method is, the default method will attempt to coerce the object to a class for which a method is defined, and then coerce the output back to the original class. If no method is available for any class, an error will be thrown.
For two-mode or bipartite networks, to_matching() is used
to identify whether a perfect matching is possible.
For one-mode networks, we use the Tutte theorem.
Note that currently only subgraphs with cutpoints removed are tested,
and not all possible subgraphs.
This is to avoid computationally expensive combinatorial operations,
but may come at the cost of some edge cases where a one-mode network
cannot perfectly match as suggested.
Aperiodicity is a property of directed networks that can be interpreted as
the absence of cycles of a common length.
Aperiodicity is a necessary condition for the existence of a
unique stationary distribution in Markov chains, and thus is
an important property for the analysis of dynamic processes on networks.
The function is_aperiodic() tests for aperiodicity by finding
all simple paths from each node back to itself, and then
calculating the greatest common divisor of the lengths of these paths.
If the greatest common divisor is 1, the network is aperiodic.
Tutte, William T. 1950. "The factorization of locally finite graphs". Canadian Journal of Mathematics. 2: 44–49. doi:10.4153/cjm-1950-005-2
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. doi:10.1007/BF01442866
Other marking:
mark_is
is_connected(ison_southern_women)
#> [1] TRUE
is_connected(ison_algebra, connectivity = "weak")
#> [1] TRUE
is_perfect_matching(ison_southern_women)
#> [1] FALSE
is_eulerian(ison_brandes)
#> [1] FALSE
is_acyclic(ison_algebra)
#> [1] FALSE
is_aperiodic(ison_algebra)
#> [1] TRUE