Infomap quickstart

This vignette shows a small Infomap workflow with an igraph graph. It runs Infomap, compares the partition with Louvain, and inspects the resulting node assignments.

library(infomap)
library(igraph)
#> 
#> Attaching package: 'igraph'
#> The following object is masked from 'package:infomap':
#> 
#>     cluster_infomap
#> The following objects are masked from 'package:stats':
#> 
#>     decompose, spectrum
#> The following object is masked from 'package:base':
#> 
#>     union

packageVersion("infomap")
#> [1] '2.12.0'
packageVersion("igraph")
#> [1] '2.3.2'

Load a graph

Zachary’s karate club graph is a small undirected social network. The known split is used below as a reference label for summary metrics.

graph <- igraph::make_graph("Zachary")

mr_hi <- c(1, 2, 3, 4, 8, 12, 13, 14, 18, 20, 22)
truth <- ifelse(seq_len(igraph::vcount(graph)) %in% mr_hi, "Mr. Hi", "Officer")

graph
#> IGRAPH fbafd64 U--- 34 78 -- Zachary
#> + attr: name (g/c)
#> + edges from fbafd64:
#>  [1]  1-- 2  1-- 3  1-- 4  1-- 5  1-- 6  1-- 7  1-- 8  1-- 9  1--11  1--12
#> [11]  1--13  1--14  1--18  1--20  1--22  1--32  2-- 3  2-- 4  2-- 8  2--14
#> [21]  2--18  2--20  2--22  2--31  3-- 4  3-- 8  3--28  3--29  3--33  3--10
#> [31]  3-- 9  3--14  4-- 8  4--13  4--14  5-- 7  5--11  6-- 7  6--11  6--17
#> [41]  7--17  9--31  9--33  9--34 10--34 14--34 15--33 15--34 16--33 16--34
#> [51] 19--33 19--34 20--34 21--33 21--34 23--33 23--34 24--26 24--28 24--33
#> [61] 24--34 24--30 25--26 25--28 25--32 26--32 27--30 27--34 28--34 29--32
#> [71] 29--34 30--33 30--34 31--33 31--34 32--33 32--34 33--34
table(truth)
#> truth
#>  Mr. Hi Officer 
#>      11      23

Run Infomap and Louvain

Use infomap::cluster_infomap() for a compact result object with node assignments and summary fields. The function name is qualified because igraph also exports a function named cluster_infomap().

set.seed(123)

infomap_result <- infomap::cluster_infomap(
  graph,
  silent = TRUE,
  nb.trials = 20,
  two_level = TRUE
)

louvain_result <- igraph::cluster_louvain(graph)

summary(infomap_result)
#>   num_nodes num_links num_top_modules num_levels codelength
#> 1        34        78               3          2   4.311793
#>   one_level_codelength relative_codelength_savings
#> 1             4.704423                  0.08345975

Compare assignments

The numeric module ids are local labels. They identify groups within one partition and should not be interpreted as ordered values across methods.

assignments <- as.data.frame(infomap_result)
assignments <- assignments[order(assignments$node_id), c("node_id", "module_id", "flow")]
assignments$truth <- truth[assignments$node_id]
assignments$louvain_module <- unname(igraph::membership(louvain_result))[assignments$node_id]

head(assignments, 10)
#>    node_id module_id       flow   truth louvain_module
#> 1        1         1 0.10256410  Mr. Hi              1
#> 2        2         1 0.05769231  Mr. Hi              2
#> 3        3         1 0.06410256  Mr. Hi              2
#> 4        4         1 0.03846154  Mr. Hi              2
#> 13       5         2 0.01923077 Officer              1
#> 14       6         2 0.02564103 Officer              1
#> 15       7         2 0.02564103 Officer              1
#> 5        8         1 0.02564103  Mr. Hi              2
#> 18       9         3 0.03205128 Officer              3
#> 6       10         1 0.01282051 Officer              2

Normalized mutual information (NMI) compares the detected assignments with the known karate-club split.

metrics <- data.frame(
  method = c("infomap", "louvain"),
  NMI_vs_truth = c(
    igraph::compare(truth, assignments$module_id, method = "nmi"),
    igraph::compare(truth, assignments$louvain_module, method = "nmi")
  )
)

metrics
#>    method NMI_vs_truth
#> 1 infomap    0.6499535
#> 2 louvain    0.4246892

Visualize the Infomap partition

palette <- grDevices::hcl.colors(length(unique(assignments$module_id)), "Set 2")
vertex_colors <- palette[assignments$module_id]

plot(
  graph,
  layout = igraph::layout_with_fr(graph),
  vertex.color = vertex_colors,
  vertex.label = seq_len(igraph::vcount(graph)),
  vertex.size = 18,
  edge.color = "grey75",
  main = "Infomap modules"
)

Next steps

For larger workflows, use the returned infomap_result object to inspect codelength, modules, and the node table from as.data.frame(). For lower-level control, use Infomap() directly.