R package for graph manipulation: transitive reduction and cliques

Question

Can anyone suggest an R package for graph manipulation that can find cliques and also performs transitive reduction?

From websearching I see that I can find cliques with igraph. (Transitive reduction is on the wishlist for igraph.) I can perform transitive reduction with relations::transitive_reduction().

I would prefer to use one package that can do both operations.

FWIW: I have a data set where each variable is a predicate for some property of each case. I have found all the logical implications between the predicates. Each implication can be represented as a directed graph edge between the vertices corresponding to the antecedent and consequent predicates.

My data has ~20 vertices and ~200 edges, which makes manually examining the resultant graph rather difficult. So I am trying to simplify the graph by removing redundant vertices and edges. All the vertices in a clique are identical with respect to their relationships to predicates outside the clique, so they can be represented by a single predicate. If there are two edges, A -> B and B -> C, then the edge A -> C will necessarily be present in my data and is redundant because it can be inferred from the other two edges.

Any different suggestions for simplifying this data would also be appreciated.

Thanks

Ross

Answer 1

I don't know of any R package that can solve both tasks, but the package for Nested Effects Models at Bioconductor https://www.bioconductor.org/packages/release/bioc/html/nem.html contains a function for computing the transitive reduction of a directed acyclic graph.

Best,

Mathias

Answer 2

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

library(tidyverse)
library(arules)
library(relations)
library(igraph)
library(DiagrammeR)

# 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)), 
       rules_s01_c99@quality)

# 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")