The answer to the question seems to be that there is no readily available R package for graph analysis that currently includes clique detection and transitive reduction. (Thanks to user2957945 and Mathias Cardner for their suggestions.)
Here is what I ended up doing.
I used a mix of two packages:
- igraph (CRAN) for clique detection
- relations (CRAN) for transitive reduction
I also used DiagrammeR (CRAN), for historical reasons, for displaying the graphs.
It turned out that the cost of moving the graphs between the three packages was low compared to the cost of finding a package that did ever everything or implementing transitive reduction in a package that did clique detection.
Bear in mind that I was only simplifying a couple of relatively small graphs for display. Using multiple packages may not be so attractive if you need to manipulate many large graphs.
I also learned that the clique finding functions I looked at only supported undirected graphs whereas I was working with directed graphs. The obvious definition of clique in a directed graph requires that for every pair of vertices in the clique there are two directed edges going in opposite edges. So you need to find all the bidirectional edges between pairs of vertices, replace each bidirectional edge pair with a single undirected edge, and remove all other edges. Then you can find the same cliques in the transformed, undirected graph.
I have included the (inelegant) code I used below in case it is helpful to anyone. Sorry, I can't include my data and don't have time to generate fake data. I use the arules::apriori() to induce rules from data and use the rules as edges of the graph. So any data that you could use as input to arules::apriori() should work with this code. (Whether, there are cliques and redundant edges is another matter.)
# Use arules::apriori() to induce association rules from data frame d.
# The rules are constrained to have exactly 1 term (variable=value pair)
# on the left hand side (LHS = antecedent)
# and right hand side (RHS = consequent) of each rule.
# Each rule is interpreted as a directed edge from the LHS to the RHS.
# Each variable=value pair that appears in any rule is treated as a vertex
# in the graph that represents the logical implication relations
# between the vertices.
# The confidence parameter allows a few contradicting cases for any rule.
# The support parameter means every rule must occur in > 1% of cases.
rules_s01_c99 <- arules::apriori(d,
parameter = list(
support = 0.01, confidence = 0.99,
minlen = 2, maxlen = 2, # 1 item on LHS & RHS
target = "rules",
ext = TRUE, originalSupport = FALSE))
# Convert the rules to a data frame
# It had to be a frame rather than a tibble
# because of issues around strings as factors.
rule_df <- data.frame(
from = labels(lhs(rules_s01_c99)),
to = labels(rhs(rules_s01_c99)),
# Represent the rules as a directed graph with the relations package
from_c <- as.character(rule_df$from)
to_c <- as.character(rule_df$to)
domain <- as.list(unique(c(from_c, to_c)))
tuples <- data_frame(from_c, to_c) # note the tibble here
r <- relations::endorelation(domain = domain, graph = tuples)
# Do transitive reduction (cycles remain as cycles)
trg <- relations::transitive_reduction(r)
# Convert graph to adjacency matrix for import to igraph & DiagrammeR
adj_mat <- relations::relation_incidence(trg) # directed edges
# Identify the pairs of directed edges in cliques.
# Convert those pairs to undirected edges and remove other edges.
# Result is represented as a symmetric adjacency matrix.
sym <- (adj_mat + t(adj_mat)) %/% 2 # undirected adjacency matrix of 2-cliques
# Identify the undirected cliques with igraph
i_sym <- igraph::graph_from_adjacency_matrix(sym, mode = "undirected")
igraph::max_cliques(i_sym, min = 2)
# Import the graph with DiagrammeR
dg <- DiagrammeR::from_adj_matrix(relation_incidence(trg), mode = "directed")
# Display the graph with cliques included
DiagrammeR::render_graph(dg, output = "visNetwork")