Does clustering work with multilayer network?

[u-xixi]

Hello, I really appreciate the work with Infomap. I have been having fun playing with it for a while. I'm thinking about building a multilayer network to somehow improve some preexisiting clustering. To test it, I made up a toy data:
this is the multilayer network, with only intra links:

*Vertices 8
# node_id name
1 "a"
2 "b"
3 "c"
4 "d"
5 "e"
6 "f"
7 "g"
8 "h"
*Intra
# layer_id node_id node_id weight
1 1 2 1
1 2 1 1
1 2 3 1
1 3 4 0.5
2 3 2 0.5
2 1 2 1
2 5 6 1
2 6 5 1
2 8 5 1
2 6 8 1
2 8 6 1

As you can see, there are 8 nodes, with node "g" not linked to any other nodes.
then I made a pre-clustering:

1 1 0.125
2 1 0.125
3 1 0.125
4 2 0.125
7 2 0.125
5 3 0.125
6 3 0.125
8 3 0.125

which is basically 3 modules, (a, b, c), (d, g), (e, f, h)
I ran infomap with this command:
infomap in_multi2.txt out2 -s 1 --cluster-data precluster2.clu --ftree --clu
the program seems to run smoothly:

=======================================================
  Infomap v1.6.0 starts at 2021-12-22 13:55:19
  -> Input network: in_multi2.txt
  -> Output path:   out2/
  -> Configuration: cluster-data = precluster2.clu
                    ftree
                    clu
                    seed = 1
=======================================================
  OpenMP 201811 detected with 4 threads...
Parsing undirected network from file 'in_multi2.txt'... 
  Parsing vertices...
  -> 8 physical nodes added
  Parsing intra-layer links...
  -> 11 intra-layer links
  -> Expanding undirected links to directed...
Generating state network from multilayer networks with simulated inter-layer links...
-> 2 networks
-> Relax rate: 0.15
Done!
-------------------------------------
  -> 10 state nodes
  -> 8 physical nodes
  -> 25 links with total weight 10
  -> Found higher order network input, using the Map Equation for higher order network flows
  -> Notice: Directed input found, changing flow model from 'undirected' to '1'
Calculating global network flow using flow model 'directed'... 
  -> Using unrecorded teleportation to links. 
  -> PageRank calculation done in 200 iterations.

  => Sum node flow: 1, sum link flow: 1
Build internal network with 10 nodes and 25 links...
Calculating one-level codelength... done!
 -> One-level codelength: 3.18578639
Calculating entropy rate... done!
  -> Entropy rate: 0.9066723944

================================================
Trial 1/1 starting at 2021-12-22 13:55:19
================================================
Read initial partition from 'precluster2.clu'... Init partition from file 'precluster2.clu'... 
 -> 2 nodes not found in cluster file are put into separate modules. done! Generated 2 levels with codelength 4.53321674
Two-level compression: 20% 
Partitioned to codelength 0 + 2.5573272 = 2.557327205 in 1 (0 non-trivial) modules.

=> Trial 1/1 finished in 0.001218s with codelength 2.5573272
Write physical flow tree to out2/in_multi2.ftree... done!
Write state flow tree to out2/in_multi2_states.ftree... done!
Write physical node modules to out2/in_multi2.clu... done!
Write state node modules to out2/in_multi2_states.clu... done!


================================================
Summary after 1 trial
================================================
Best end modular solution in 2 levels:
Per level number of modules:         [          1,           0] (sum: 1)
Per level number of leaf nodes:      [          0,          10] (sum: 10)
Per level average child degree:      [          1,          10] (average: 9.18182)
Per level codelength for modules:    [0.000000000, 0.000000000] (sum: 0.000000000)
Per level codelength for leaf nodes: [0.000000000, 2.557327205] (sum: 2.557327205)
Per level codelength total:          [0.000000000, 2.557327205] (sum: 2.557327205)

===================================================
  Infomap ends at 2021-12-22 13:55:19
  (Elapsed time: 0.00818s)
===================================================

I visualized the output ftree, which seems to miss "g" completely:

# v1.6.0
# ./Infomap in_multi2.txt out2 -s 1 --cluster-data precluster2.clu --ftree --clu
# started at 2021-12-22 13:55:19
# completed in 0.00387 s
# partitioned into 2 levels with 1 top modules
# codelength 2.55733 bits
# relative codelength savings 19.727%
# path flow name node_id
1:1 0.200609 "a" 1
1:2 0.318722 "b" 2
1:3 0.145337 "c" 3
1:4 0.0353319 "d" 4
1:5 0.0893617 "e" 5
1:6 0.121277 "f" 6
1:7 0.0893617 "h" 8
*Links directed
#*Links path enterFlow exitFlow numEdges numChildren
*Links root 0 0 0 1
*Links 1 0 0 12 10
1 2 0.200518
2 1 0.200609
2 3 0.100305
3 2 0.118204
3 4 0.0353319
4 3 0.0450321
5 6 0.0606383
5 7 0.0303191
6 5 0.0590426
6 7 0.0590426
7 5 0.0303191
7 6 0.0606383

I noticed in the program message it says,

Read initial partition from 'precluster2.clu'... Init partition from file 'precluster2.clu'...
-> 2 nodes not found in cluster file are put into separate modules. done! Generated 2 levels with codelength 4.53321674

Now I have some difficulty understanding what is going on. what are the 2 nodes that were not found in the .clu ? And why the lonely node "g" is missing?

This leads me doubting whether the pre-clustering could also work with multilayer network. If not, then will it work if I represent the preclustering as a layer in a network format? e.g. a complete graph, a hamiltonian path, etc.
To give you a bit more context, I would like to do so because the network graph I am trying to build is relatively sparse, and it may not contain all the nodes. I used multilayer because I wanted to represent different types of connections between the objects. Each layer is basically relationships of a type. I'd also like to hear your take in this, whether this is a suitable scenario to use Infomap.

thanks in advance and happy holidays,
Xixi

[antoneri]

Hi and thanks for reaching out with a very thorough question!

Just a quick answer - I'm on mobile:

G is missing because it's disconnected. You can consider it belonging to a singleton module by itself. The preclustering specifies the state nodes and won't work on physical nodes, that's your missing nodes!

I'll get back with a better response if not @danieledler has answered it already. Hope this helps in the mean time!

[antoneri]

One option is to represent your data as a state network (https://www.mapequation.org/infomap/#InputStates). Then, the pre-clustering is specified using the state ids.

We are discussing ways to incorporate multilayer pre-clustering input.

[u-xixi]

Hi Anton, thanks for this tip. I transformed this toy example to a state network and ran infomap again. I am still trying to understand the output and thinking about how to apply it to my real-world question, but maybe i should also paste the output here, hopefully they'd offer some useful clues for your discussion (sorry for the verbosity below):

so this is now the input. for node i in layer l, the state node is named l-i and is assigned a unique integer:

*Vertices 8
# node_id name
1 "a"
2 "b"
3 "c"
4 "d"
5 "e"
6 "f"
7 "g"
8 "h"
*States
# state_id node_id name
1 1 1-1
5 1 2-1
2 2 1-2
6 2 2-2
3 3 1-3
7 3 2-3
4 4 1-4
8 5 2-5
9 6 2-6
10 8 2-8
*Links
1 2 1
2 1 1
2 3 1
3 4 0.5
7 6 0.5
5 6 1
8 9 1
9 8 1
10 8 1
9 10 1
10 9 1

the clu file is now:

1 1
5 1
2 1
6 1
3 1
7 1
4 2
11 2
8 3
9 3
10 3

console messages:

=======================================================
  Infomap v1.6.0 starts at 2022-01-03 17:09:00
  -> Input network: in_states.txt
  -> Output path:   out/
  -> Configuration: input-format = states
                    cluster-data = precluster.clu
                    ftree
                    clu
                    seed = 1
=======================================================
  OpenMP 201811 detected with 4 threads...
Parsing state network from file 'in_states.txt'... 
  Parsing vertices...
  -> 8 physical nodes added
  Parsing state nodes...
  -> 10 state nodes added
  Parsing links...
  -> 11 links
Done!
-------------------------------------
  -> 10 state nodes
  -> 8 physical nodes
  -> 11 links with total weight 10
  -> Found higher order network input, using the Map Equation for higher order network flows
Calculating global network flow using flow model 'undirected'... 
  -> Using undirected links.
  => Sum node flow: 1, sum link flow: 1
Build internal network with 10 nodes and 11 links...
Calculating one-level codelength... done!
 -> One-level codelength: 3.07095059
Calculating entropy rate... done!
  -> Entropy rate: 0.5

================================================
Trial 1/1 starting at 2022-01-03 17:09:00
================================================
Read initial partition from 'precluster.clu'... Init partition from file 'precluster.clu'... done! Generated 2 levels with codelength 2.28320622
Two-level compression: 46% 0% 0.921121292% 
Partitioned to codelength 0 + 1.63030514 = 1.630305145 in 3 modules.
Super-level compression: to codelength 1.630305145 in 3 top modules.

Recursive sub-structure compression: 0% . Found 2 levels with codelength 1.630305145

=> Trial 1/1 finished in 0.001824s with codelength 1.63030514
Write physical flow tree to out/in_states.ftree... done!
Write state flow tree to out/in_states_states.ftree... done!
Write physical node modules to out/in_states.clu... done!
Write state node modules to out/in_states_states.clu... done!


================================================
Summary after 1 trial
================================================
Best end modular solution in 2 levels:
Per level number of modules:         [          3,           0] (sum: 3)
Per level number of leaf nodes:      [          0,          10] (sum: 10)
Per level average child degree:      [          3,     3.33333] (average: 3.25641)
Per level codelength for modules:    [0.000000000, 0.000000000] (sum: 0.000000000)
Per level codelength for leaf nodes: [0.000000000, 1.630305145] (sum: 1.630305145)
Per level codelength total:          [0.000000000, 1.630305145] (sum: 1.630305145)

===================================================
  Infomap ends at 2022-01-03 17:09:00
  (Elapsed time: 0.00611s)
===================================================

ftree output:

# v1.6.0
# ./Infomap in_states.txt out -i states -s 1 --cluster-data precluster.clu --ftree --clu
# started at 2022-01-03 17:09:00
# completed in 0.003292 s
# partitioned into 2 levels with 3 top modules
# codelength 1.63031 bits
# relative codelength savings 46.912%
# path flow name node_id
1:1 0.15 "e" 5
1:2 0.2 "f" 6
1:3 0.15 "h" 8
2:1 0.1 "a" 1
2:2 0.15 "b" 2
2:3 0.075 "c" 3
2:4 0.025 "d" 4
3:1 0.05 "a" 1
3:2 0.075 "b" 2
3:3 0.025 "c" 3
*Links undirected
#*Links path enterFlow exitFlow numEdges numChildren
*Links root 0 0 0 3
*Links 1 0 0 5 3
1 2 0.1
2 1 0.1
2 3 0.1
3 1 0.1
3 2 0.1
*Links 2 -6.93889e-18 -6.93889e-18 4 4
1 2 0.1
2 1 0.1
2 3 0.1
3 4 0.05
*Links 3 -6.93889e-18 -6.93889e-18 2 3
1 2 0.1
3 2 0.05

i have some questions again:
(1) I was not sure how to assign the weight in the clu file anymore. Those physical nodes with 2 states, should I split the weight between the states, to make sure all physical nodes still have the same weight? e.g. state node 1 and 5 both belong to physical node a, should each state node have a weight of 0.125/2?
(2) I noticed when I use Infomap, sometimes the top modules are still visualized as connected. Did you people set a certain threshold to visualize the flow values, or it is simply because there exists a link between certain top modules?
(3) it seems if a node is disconnected in the network, it will always be treated as a loner, regardless of the preclustering?

[antoneri]

For your first question, I can tell you that the third column is not used when using .clu files as input, so no worries there! When the weights are present in the output, the weights are the PageRank, or flow, of the nodes. We always calculate the flow unless --use-node-weights-as-flow is set (see the docs, advanced parameters).

For your second question, are you talking about the network navigator? There, no threshold exists. If there is a link between the modules, then there's a link between nodes in those modules. Two caveats: The level-of-detail setting which hides weak links based on zoom level to highlight the structure, this can be disabled in the settings. Furthermore, only the 20 largest top/sub-modules and leaf nodes are visible.

Finally, yes, disconnected nodes tend to end up in singleton modules. Keep in mind that the pre-clustering is just a starting point for the optimizer. For small networks, using that often makes no difference but can be useful for large networks or to evaluate known partitions (using --no-infomap).

Hope this helps!

[antoneri]

Note that you should probably upgrade to Infomap 1.9 as we fixed a bug (#182) related to higher-order networks which could impact your results.

[u-xixi]

thanks again! i'll upgrade infomap on my machine.
yes the second question is about the navigator. for my own project I'm actually using the python API, so I didn't look into the settings there.
With your explanation now it's getting clearer to me. So my case is, I have preexisting clustering, and a graph that is not very connected. The problem here is partitioning could not be done well with just the graph. I was exploring whether it is a good idea to use infomap to modify the preclustering. Previously, I represented the preclustering also as a graph. I made each cluster into a complete graph where each node is connected to all the others. It of course ended in a dense graph. So i was trying to find a better solution. It seems that if i want to use the pre-clustering as the basis, I should still represent it as some kind of network, as leaving too many nodes unclustered is not desirable to me.