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:
The class can be typically used as:
louvain = Louvain(graph) louvain.run()
An obvious extension would be to take edge weights into account – easy.
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