Where are the communities for disconnected nodes of a graph?

[JohannHM]

Thank so much for this product. As novice user of communities a simple question comes to my mind.
What happen with disconnected nodes of a network when computing infomap communities?
The algorithm runs fine when works with a giant component, but when I work with a disconnected graph, that includes disconnected and isolated nodes, they suddenly disappear in the infomap output. It looks like infomap internally remove them out in some way before runs the infomap algorithm. I was thinking that disconnected nodes receive a proper communities...
Are they (disconnected nodes) always removed when performing infomap?

Thanks in advance for your answers!

[danieledler]

Hi @JohannHM and thanks for your question! Disconnected nodes usually end up in singleton modules (one module for each disconnected node). They should not be removed by Infomap at any stage, so can you please provide an example of what you get?

[JohannHM]

Hi @danieledler thank for your opinion.
Im working with cdlib library that uses exactly the same code here. In fact this python example was tested on your web of infomap with the same results. The idea is attacking a network by removing some hubs, thus some disconnected nodes appear, and then applying infomap. Recovering the nodes after infomap with those before applying it. Look at this:

import networkx as nx
import math

g = nx.karate_club_graph()                  # karate-club network  
k1 = dict(g.degree())                       # taking its degree k1

percentage = 10                                 # percentage of nodes to remove
n_nodes = math.floor(percentage*len(k1)/100)    # num of nodes to remove
nodes_2_remove = list(k1.keys())[:n_nodes]      # nodes to remove

G = g.copy()                                # taking a copy of graph to attack it
G.remove_nodes_from(nodes_2_remove)         # attaking the graph
k2 = dict(G.degree())                       # taking degree k2 of attaked graph

nodes_degree_zero = [n for n, k in k2.items() if k == 0] # look for nodes with degree = 0

from cdlib import algorithms                # importing the infomap
p = algorithms.infomap(G).communities       # applying infomap

recovering_nodes = []                       # recovering nodes from infomap communities
for community in p:
    recovering_nodes.extend(community)
recovering_nodes = sorted(recovering_nodes)

# comparing nodes before applying infomap with those after infomap method
missing_nodes = sorted(list(set(G.nodes()) - set(recovering_nodes)))

# infomap does not take into disconnected ndoes as singleton communities
print(missing_nodes == nodes_degree_zero)

when I testes with the web https://www.mapequation.org/infomap/
Same results.

thanks

[JohannHM]

mmm. I think something is working but I didn't understand why.
Look, my working graphs are composed by node labels labeled as strings of integer numbers, something like ['02', '368', '000', '056', etc]. When I change these line of your code:

im.add_nodes(G.nodes) by this:

nodos = list(G.nodes)
losnodos = [int(nn) for nn in nodos]

To convert them into integer labels.
Likewise, when I modify the code to convert strings nodes to integer version:

for u, v, data in G.edges(data=True):
    if 'weight' in data:        
        im.add_link(int(u), int(v), data['weight'])
    else:
        im.add_link(int(u), int(v))

The code runs without problem, but I'm unsure whether the problem is that your code only accept node labels as integer number but it does not accept node labels as strings. Is that true?

[antoneri]

Yes, you are correct that they need to be integers.

If you want to assign node labels as well, you can use the second argument:

im = Infomap()
im.add_node(1, "label 1")
im.add_node(2, "label 2")
# or:
#nodes = [(1, "label 1"), (2, "label 2")]
#im.add_nodes(nodes)
im.add_link(1, 2)

So in your case, you can map the labels to integers:

nodes = list(G.nodes)
node_map = {label: node for node, label in enumerate(nodes)}

for label, node in node_map.items():
    im.add_node(node, label)

for u, v, data in G.edges(data=True):
    node_u, node_v = node_map[u], node_map[v]
    if 'weight' in data:        
        im.add_link(node_u, node_v, data['weight'])
    else:
        im.add_link(node_u, node_v)

Hope this helps!

[JohannHM]

Hello again.
It helped a lot. Thank so much @antoneri and @danieledler for your helping hand.Very glad of discover the big usefulness of your code.
Johann

[danieledler]

Hi @JohannHM,

Glad to hear. By the way, after our last reply above on relabelling node ids to integers, we added a helper method to add a NetworkX graph to Infomap that works for both integer ids and string ids.

If the node ids are strings, they will be added as node names, but the add_networkx_graph(G) will also return a dictionary that maps the new node ids to the string labels:

G = nx.Graph([("a", "b"), ("a", "c")])
im = Infomap()
mapping = im.add_networkx_graph(G)
mapping
# {0: 'a', 1: 'b', 2: 'c'}

im.run()
for node in im.nodes:
    print(node.node_id, node.module_id, node.flow, im.get_name(node.node_id))
# Output:
# 0 1 0.5 a
# 1 1 0.25 b
# 2 1 0.25 c
# 

Should be useful in your case, so please try!

[JohannHM]

Hi again guys!
Off-course, after working with the add_networkx_graph(g) method, I got the same results. However, this method makes the life easier for those who are not python experts like me.
Thank you so much for this implementation guys. Hope to get more interesting results and honored to cite you all.
btw: for sure I'll contact you again for more foo, questions.