Skip to contents

Find the largest common connected subgraph (LCCS) of two graphs

Source: R/largest_common_cc.R
largest_common_cc.Rd

Find the largest common connected subgraphs of two matched graphs, which is an induced connected subgraph of both graphs that has as many vertices as possible. The largest_cc function returns the largest connected subgraph of a single graph.

Usage

largest_common_cc(A, B, min_degree = 1)

largest_cc(A)

Arguments

A

A matrix or an igraph object. See check_graph. Must be single-layer.

B

A matrix or an igraph object. See check_graph. Must be single-layer.

min_degree

A number. Defines the level of connectedness of the obtained largest common connected subgraph. The induced subgraph is a graph with a minimum vertex-degree of at least min_degree.

Value

largest_common_cc returns the common largest connected subgraphs of two aligned graphs in the igraph object form and a logical vector indicating which vertices in the original graphs remain in the induced subgraph.

Examples

cgnp_pair <- sample_correlated_gnp_pair(n = 10, corr =  0.7, p =  0.2)
g1 <- cgnp_pair$graph1
g2 <- cgnp_pair$graph2
# put no constraint on the minimum degree of the common largest conncect subgraph
lccs1 <- largest_common_cc(g1, g2, min_degree = 1)
# induced subgraph
lccs1$g1
#> IGRAPH d174f2b D--- 5 8 -- 
#> + edges from d174f2b:
#> [1] 1->4 2->3 2->4 3->2 4->1 4->2 4->5 5->4
lccs1$g2
#> IGRAPH dd94464 D--- 5 8 -- 
#> + edges from dd94464:
#> [1] 1->4 2->3 2->4 3->2 4->1 4->2 4->5 5->4
# label of vertices of the induced subgraph in the original graph
igraph::V(g1)[lccs1$keep]
#> + 5/10 vertices, from c8bb89e:
#> [1] 1 2 6 8 9

# obtain a common largest connect subgraph with each vertex having a minimum degree of 3
lccs3 <- largest_common_cc(g1, g2, min_degree = 3)

g <- igraph::sample_gnp(100, .01)
lcc <- largest_cc(g)
# induced subgraph
lcc$g
#> IGRAPH 2bd8904 D--- 7 12 -- 
#> + edges from 2bd8904:
#>  [1] 1->4 2->4 2->5 3->7 4->1 4->2 4->6 4->7 5->2 6->4 7->3 7->4
# label of vertices of the induced subgraph in the original graph
igraph::V(g)[lcc$keep]
#> + 7/100 vertices, from ded2dd0:
#> [1] 18 28 38 39 42 49 91