Visual Analytics Course

louvain

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:

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