<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Infomap
Multi-level network clustering based on the Map equation.
The Map Equation
\begin{equation}
    L(M) = q_\curvearrowright H(\mathcal{Q}) + \sum_{i = 1}^{m}{p_{\circlearrowright}^i H(\mathcal{P}^i)}
\end{equation}
$L(M)$ measures the amount of information it takes to describe a random walk on a network given a partition of the network into modules $M$. It is a sum of the amount of information needed to describe the movements between and within the modules, which balances the goodness of fit with the complexity of the model. For more information, see www.mapequation.org.
Import Infomap
Infomap includes an examples/python folder with some examples, including this notebook. Run make in that directory to build the python interface to a local folder.
The infomap package exposes two classes, Infomap and MemInfomap, that wraps an input network, an output tree, and a run method to run Infomap on the input network. The classes takes a string of options as input.
Step1:  Simple example
Step2:  Memory networks
With memory networks, the flow between two nodes depends on how you arrived at the first node. This higher-order relationships can be described by trigrams as in the example below
Step3:  Overlapping modules
Notice that node 2 in the example below exists in both module 0 and 1. This is because MemInfomap partitions the higher-order state network which can include multiple state nodes for each physical node. For trigrams, a state node is a pair of previousNode node. To keep the state network in the output tree, add the --expanded flag to configure MemInfomap
Step4:  As seen in the expanded output above, node 2 is represented by four state nodes partitioned into two modules depending on where you come from; if you go to node 2 from node 0 or 1 you are still considered to be in module 1, but if you go to node 2 from node 3 and 4 you are still considered to be in module 0.
Multi-layer networks
Step6:  Infomap + NetworkX
Generate and draw a network with NetworkX, colored
according to the community structure found by Infomap.
<ASSISTANT_TASK:>
Python Code:
from infomap import infomap
Explanation: Infomap
Multi-level network clustering based on the Map equation.
The Map Equation
\begin{equation}
    L(M) = q_\curvearrowright H(\mathcal{Q}) + \sum_{i = 1}^{m}{p_{\circlearrowright}^i H(\mathcal{P}^i)}
\end{equation}
$L(M)$ measures the amount of information it takes to describe a random walk on a network given a partition of the network into modules $M$. It is a sum of the amount of information needed to describe the movements between and within the modules, which balances the goodness of fit with the complexity of the model. For more information, see www.mapequation.org.
Import Infomap
Infomap includes an examples/python folder with some examples, including this notebook. Run make in that directory to build the python interface to a local folder.
The infomap package exposes two classes, Infomap and MemInfomap, that wraps an input network, an output tree, and a run method to run Infomap on the input network. The classes takes a string of options as input.
End of explanation
infomapWrapper = infomap.Infomap("--two-level")
# Add link weight as an optional third argument
infomapWrapper.addLink(0, 1)
infomapWrapper.addLink(0, 2)
infomapWrapper.addLink(0, 3)
infomapWrapper.addLink(1, 0)
infomapWrapper.addLink(1, 2)
infomapWrapper.addLink(2, 1)
infomapWrapper.addLink(2, 0)
infomapWrapper.addLink(3, 0)
infomapWrapper.addLink(3, 4)
infomapWrapper.addLink(3, 5)
infomapWrapper.addLink(4, 3)
infomapWrapper.addLink(4, 5)
infomapWrapper.addLink(5, 4)
infomapWrapper.addLink(5, 3)
infomapWrapper.run()
tree = infomapWrapper.tree
print("Found %d modules with codelength: %f" % (tree.numTopModules(), tree.codelength()))
print("\n#node module")
for node in tree.leafIter():
    print("%d %d" % (node.physIndex, node.moduleIndex()))
Explanation: Simple example
End of explanation
infomapWrapper = infomap.MemInfomap("--two-level")
# Trigrams represents a path from node A through B to C.
# Add link weight as an optional fourth argument
infomapWrapper.addTrigram(0, 2, 0)
infomapWrapper.addTrigram(0, 2, 1)
infomapWrapper.addTrigram(1, 2, 1)
infomapWrapper.addTrigram(1, 2, 0)
infomapWrapper.addTrigram(1, 2, 3)
infomapWrapper.addTrigram(3, 2, 3)
infomapWrapper.addTrigram(2, 3, 4)
infomapWrapper.addTrigram(3, 2, 4)
infomapWrapper.addTrigram(4, 2, 4)
infomapWrapper.addTrigram(4, 2, 3)
infomapWrapper.addTrigram(4, 3, 3)
infomapWrapper.run()
tree = infomapWrapper.tree
print("Found %d modules with codelength: %f" % (tree.numTopModules(), tree.codelength()))
print("\n#node module")
for node in tree.leafIter():
    print("%d %d" % (node.physIndex, node.moduleIndex()))
Explanation: Memory networks
With memory networks, the flow between two nodes depends on how you arrived at the first node. This higher-order relationships can be described by trigrams as in the example below:
Trigrams
End of explanation
# Store expanded state network
infomapWrapper = infomap.MemInfomap("--two-level --expanded")
infomapWrapper.addTrigram(0, 2, 0)
infomapWrapper.addTrigram(0, 2, 1)
infomapWrapper.addTrigram(1, 2, 1)
infomapWrapper.addTrigram(1, 2, 0)
infomapWrapper.addTrigram(1, 2, 3)
infomapWrapper.addTrigram(3, 2, 3)
infomapWrapper.addTrigram(2, 3, 4)
infomapWrapper.addTrigram(3, 2, 4)
infomapWrapper.addTrigram(4, 2, 4)
infomapWrapper.addTrigram(4, 2, 3)
infomapWrapper.addTrigram(4, 3, 3)
infomapWrapper.run()
tree = infomapWrapper.tree
print("Found %d modules with codelength: %f" % (tree.numTopModules(), tree.codelength()))
print("\n#previousNode node module")
for node in tree.leafIter():
    print("%d %d %d" % (node.stateIndex, node.physIndex, node.moduleIndex()))
Explanation: Overlapping modules
Notice that node 2 in the example below exists in both module 0 and 1. This is because MemInfomap partitions the higher-order state network which can include multiple state nodes for each physical node. For trigrams, a state node is a pair of previousNode node. To keep the state network in the output tree, add the --expanded flag to configure MemInfomap:
End of explanation
infomapWrapper = infomap.MemInfomap("--two-level --expanded")
# from (layer, node) to (layer, node) weight
infomapWrapper.addMultiplexLink(2, 1, 1, 2, 1.0)
infomapWrapper.addMultiplexLink(1, 2, 2, 1, 1.0)
infomapWrapper.addMultiplexLink(3, 2, 2, 3, 1.0)
infomapWrapper.run()
tree = infomapWrapper.tree
print("Found %d modules with codelength: %f" % (tree.numTopModules(), tree.codelength()))
print("\n#layer node module:")
for node in tree.leafIter():
    print("%d %d %d" % (node.stateIndex, node.physIndex, node.moduleIndex()))
Explanation: As seen in the expanded output above, node 2 is represented by four state nodes partitioned into two modules depending on where you come from; if you go to node 2 from node 0 or 1 you are still considered to be in module 1, but if you go to node 2 from node 3 and 4 you are still considered to be in module 0.
Multi-layer networks
End of explanation
import networkx as nx
import matplotlib.pyplot as plt
import matplotlib.colors as colors
%matplotlib inline
def findCommunities(G):
    
    Partition network with the Infomap algorithm.
    Annotates nodes with 'community' id and return number of communities found.
    
    infomapWrapper = infomap.Infomap("--two-level --silent")
    print("Building Infomap network from a NetworkX graph...")
    for e in G.edges_iter():
        infomapWrapper.addLink(*e)
    print("Find communities with Infomap...")
    infomapWrapper.run();
    tree = infomapWrapper.tree
    print("Found %d modules with codelength: %f" % (tree.numTopModules(), tree.codelength()))
    communities = {}
    for node in tree.leafIter():
        communities[node.originalLeafIndex] = node.moduleIndex()
    nx.set_node_attributes(G, 'community', communities)
    return tree.numTopModules()
def drawNetwork(G):
    # position map
    pos = nx.spring_layout(G)
    # community ids
    communities = [v for k,v in nx.get_node_attributes(G, 'community').items()]
    numCommunities = max(communities) + 1
    # color map from http://colorbrewer2.org/
    cmapLight = colors.ListedColormap(['#a6cee3', '#b2df8a', '#fb9a99', '#fdbf6f', '#cab2d6'], 'indexed', numCommunities)
    cmapDark = colors.ListedColormap(['#1f78b4', '#33a02c', '#e31a1c', '#ff7f00', '#6a3d9a'], 'indexed', numCommunities)
    # Draw edges
    nx.draw_networkx_edges(G, pos)
    # Draw nodes
    nodeCollection = nx.draw_networkx_nodes(G,
        pos = pos,
        node_color = communities,
        cmap = cmapLight
    )
    # Set node border color to the darker shade
    darkColors = [cmapDark(v) for v in communities]
    nodeCollection.set_edgecolor(darkColors)
    # Draw node labels
    for n in G.nodes_iter():
        plt.annotate(n,
            xy = pos[n],
            textcoords = 'offset points',
            horizontalalignment = 'center',
            verticalalignment = 'center',
            xytext = [0, 0],
            color = cmapDark(communities[n])
        )
    plt.axis('off')
    # plt.savefig("karate.png")
    plt.show()
G=nx.karate_club_graph()
findCommunities(G)
drawNetwork(G)
Explanation: Infomap + NetworkX
Generate and draw a network with NetworkX, colored
according to the community structure found by Infomap.
End of explanation
<END_TASK>