User Tools

Site Tools


louvain

Table of Contents

Visual Analytics Course

Louvain

Here is a piece of python code that implements the Louvain community unfolding algorithm. Details of the algorithm can be found in the 2008 paper:

Blondel, V. D., J.-L. Guillaume, et al. (2008). "Fast unfolding of communities in large networks." Journal of Statistical Mechanics: Theory and Experiment: P10008.

The class can be typically used as:

louvain = Louvain(graph)
louvain.run()

An obvious extension would be to take edge weights into account – easy.

Louvain.py
from tulip import *
from GraphHandler import *
 
class Louvain():
 
    def __init__(self, graph, edgeWeight = None):
        self.graph = graph
        self.gh = GraphHandler()
        self.edgeWeight = edgeWeight
        self.weightedDegree = self.graph.getDoubleProperty('weightedDegree')
        self.communities = self.__initCommunities__()
        self.modularityValue = 0.0
        self.kIn = self.__computeInnerWeight__()
        self.kTot = self.__computeTotalWeight__()
 
    def __initCommunities__(self):
        for node in self.graph.getNodes():
            self.communities.append(set(node))
 
    def __getCommunity__(self, node):
        '''
        returns the index of the community containing node
        '''
        for i in range(len(self.communities)):
            if node in self.communities[i]:
                return i
 
    def __computeInnerCommunityWeight__(self, node, community):
        '''
        computes the weight of edges connecting a node to a community
        '''
        innerWeight = 0.0
        for neigh in self.graph.getInOutNodes(node):
            if neigh in community:
                edge = gh.findEdge(node, neigh, False)
                if edge != None:
                    innerWeight += self.edgeWeight[edge]
        return innerWeight
 
    def __computeTotalCommunityWeight__(self, community):
        '''
        computes the weight of edges connecting a node to all other nodes
        (sum of their weighted degrees)
        community is a set of nodes
        '''
        totalWeight = 0.0
        for node in self.graph.getNodes():
            totalWeight += self.weightedDegree[node]
 
    def __modularityIncrease__(self, node, targetCommunity):
        '''
        computes the weight gain when merging node with targetCommunity 
        k_i,in - sigma tot * k_i
        '''
        nodeDegree = self.edgeWeight[node]
        nodeInnerCommunityDegree = self.__computeInnerCommunityWeight__(node, targetCommunity)
        communityWeight = self.__computeTotalCommunityWeight__(targetCommunity)
        return nodeInnerCommunityDegree - communityWeight * nodeDegree
 
    def __communityMove__(self, node):
        '''
        returns the index of the community into which node
        should be placed in order to increase modularity
        '''
        nodeCommunityIndex = self.__getCommunity__(node)
        modDecrease = self.__modularityIncrease__(node, self.communities[nodeCommunityIndex])
        modIncrease = 0.0
        modIncreaseIndex = -1
        for i in range(len(self.communities)):
            if i != nodeCommunityIndex:
                increase = __modularityIncrease__(node, self.communities[i])
                if increase > modIncrease:
                    modIncrease = increase
                    modIncreaseIndex = i
        self.modularityValue += max(modIncrease, 0.0)
        return modIncreaseIndex
 
    def run(self):
        nodeMove = True
        while nodeMove:
 
            nodeMove = False
 
            for node in self.graph.getNodes():
 
                bestCommunityIndex = self.__communityMove__(node)
 
                if bestCommunityIndex != -1:
                    nodeCommunityIndex = self.__getCommunity__(node)
 
                    oldCommunity = self.communities[nodeCommunityIndex]
                    oldCommunity = oldCommunity - set([node])
                    self.communities[nodeCommunityIndex] = oldCommunity
 
                    newCommunity = self.communities[bestCommunityIndex]
                    newCommunity = newCommunity or set([node])
                    self.communities[bestCommunityIndex] = bestCommunity
 
                    nodeMove = True
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/louvain.txt · Last modified: 2012/11/22 16:01 by melancon