pairwiseStability.py

'''
@author Michael J Bommarito II
@date Mar 2, 2010

This file can determine the average pairwise stability for
a dynamic graph.  Growing graphs, constant vertex count graphs, and 
even graphs with deleted vertices are supported.

It supports the following methods:
	* betweenness
	* fast_greedy
	* label_propagation
	* eigenvector
	* walktrap
	
This code is written to supplement the following paper:
	Title: On the Stability of Community Detection Algorithms on Longitudinal Citation Data
	Authors: Michael James Bommarito II, Daniel Martin Katz, Jon Zelner
	URL: http://arxiv.org/abs/0908.0449
'''

import igraph

def pairwiseStability_Average(pair):
	'''
	Calculate the average pairwise stability given the list of pair steps.
	'''
	pairAverage = []
	'''
	Now calculate the average for each pair.
	'''
	for v in pair.values():
		count = [int(v[i] == v[i+1]) for i in range(len(v)-1) if v[i] == 1]
		if len(count) > 0:
			pairAverage.append(sum(count) / float(len(count)))
	
	return sum(pairAverage) / len(pairAverage)

def pairwiseStability_Betweenness(graphList):
	'''
	This method determines the pairwise stability of a
	dynamic graph based on the edge-betweenness method.
	
	If the underlying graph is directed, we use the directed shortest
	paths in the calculation. 
	'''
	membershipList = []
	pair = {}
	
	'''
	Iterate through the graph list.
	'''
	for graph in graphList:
		'''
		Get the labels off the graph.  We need these to determine
		identity for graphs with deletions.
		'''
		try:
			labels = [v['label'] for v in graph.vs]
		except:
			raise Exception("pairwiseStability_Betweenness: v['label'] must exist for all vertices for all graphs.")

		membership = graph.community_edge_betweenness(directed = graph.is_directed()).membership
		step = dict(zip(labels, membership))
		
		'''
		Now determine the membership pairs this step.
		'''
		for i in range(len(step)):
			for j in range(i):
				vA = min(step.keys()[i],step.keys()[j])
				vB = max(step.keys()[i],step.keys()[j])
				
				if step[vA] == step[vB]:
					v = 1
				else:
					v = 0

				if pair.has_key((vA,vB)):
					pair[(vA,vB)].append(v)
				else:
					pair[(vA,vB)] = [v]

	return pairwiseStability_Average(pair)

def pairwiseStability_FastGreedy(graphList):
	'''
	This method determines the pairwise stability of a
	dynamic graph based on the fast-greedy method of modularity
	optimization.
	
	Note that this method supports edge-weighting.  Each edge
	in each graph needs to have the 'weight' attribute.
	'''
	membershipList = []
	pair = {}
	
	'''
	Iterate through the graph list.
	'''
	for graph in graphList:
		'''
		Get the labels off the graph.  We need these to determine
		identity for graphs with deletions.
		'''
		try:
			labels = [v['label'] for v in graph.vs]
		except:
			raise Exception("pairwiseStability_FastGreedy: v['label'] must exist for all vertices for all graphs.")

		'''
		Get the weights off the graph if there are any.
		'''
		try:
			weights = [e['weight'] for e in graph.es]
		except:
			weights = None

		graph.to_undirected()
		membership = graph.community_fastgreedy(weights).membership
		step = dict(zip(labels, membership))
		
		'''
		Now determine the membership pairs this step.
		'''
		for i in range(len(step)):
			for j in range(i):
				vA = min(step.keys()[i],step.keys()[j])
				vB = max(step.keys()[i],step.keys()[j])
				
				if step[vA] == step[vB]:
					v = 1
				else:
					v = 0

				if pair.has_key((vA,vB)):
					pair[(vA,vB)].append(v)
				else:
					pair[(vA,vB)] = [v]
		
	return pairwiseStability_Average(pair)

def pairwiseStability_LabelPropagation(graphList):
	'''
	This method determines the pairwise stability of a
	dynamic graph based on the label propagation method.
	
	If the underlying graph is weighted, we use those weights.
	Note that this method does not work on graphs with isolates!
	'''
	membershipList = []
	pair = {}
	
	'''
	Iterate through the graph list.
	'''
	for graph in graphList:
		'''
		Get the labels off the graph.  We need these to determine
		identity for graphs with deletions.
		'''
		try:
			labels = [v['label'] for v in graph.vs]
		except:
			raise Exception("pairwiseStability_Betweenness: v['label'] must exist for all vertices for all graphs.")

		'''
		Get the weights off the graph if there are any.
		'''
		try:
			weights = [e['weight'] for e in graph.es]
		except:
			weights = None

		membership = graph.community_label_propagation(weights).membership
		step = dict(zip(labels, membership))
		
		'''
		Now determine the membership pairs this step.
		'''
		for i in range(len(step)):
			for j in range(i):
				vA = min(step.keys()[i],step.keys()[j])
				vB = max(step.keys()[i],step.keys()[j])
				
				if step[vA] == step[vB]:
					v = 1
				else:
					v = 0

				if pair.has_key((vA,vB)):
					pair[(vA,vB)].append(v)
				else:
					pair[(vA,vB)] = [v]

	return pairwiseStability_Average(pair)


def pairwiseStability_Eigenvector(graphList):
	'''
	This method determines the pairwise stability of a
	dynamic graph based on the leading eigenvector method.
	'''
	
	membershipList = []
	pair = {}
	
	'''
	Iterate through the graph list.
	'''
	for graph in graphList:
		'''
		Get the labels off the graph.  We need these to determine
		identity for graphs with deletions.
		'''
		try:
			labels = [v['label'] for v in graph.vs]
		except:
			raise Exception("pairwiseStability_Betweenness: v['label'] must exist for all vertices for all graphs.")

		'''
		Get the weights off the graph if there are any.
		'''
		try:
			weights = [e['weight'] for e in graph.es]
		except:
			weights = None

		membership = graph.community_leading_eigenvector().membership
		step = dict(zip(labels, membership))
		
		'''
		Now determine the membership pairs this step.
		'''
		for i in range(len(step)):
			for j in range(i):
				vA = min(step.keys()[i],step.keys()[j])
				vB = max(step.keys()[i],step.keys()[j])
				
				if step[vA] == step[vB]:
					v = 1
				else:
					v = 0

				if pair.has_key((vA,vB)):
					pair[(vA,vB)].append(v)
				else:
					pair[(vA,vB)] = [v]

	return pairwiseStability_Average(pair)

def pairwiseStability_Walktrap(graphList):
	'''
	This method determines the pairwise stability of a
	dynamic graph based on the walktrap method.
	
	If the underlying graph is weighted, we use those weights.
	They need to be on the 'weight' attribute of every edge
	for every graph.
	'''
	
	membershipList = []
	pair = {}
	
	'''
	Iterate through the graph list.
	'''
	for graph in graphList:
		'''
		Get the labels off the graph.  We need these to determine
		identity for graphs with deletions.
		'''
		try:
			labels = [v['label'] for v in graph.vs]
		except:
			raise Exception("pairwiseStability_Betweenness: v['label'] must exist for all vertices for all graphs.")

		'''
		Get the weights off the graph if there are any.
		'''
		try:
			weights = [e['weight'] for e in graph.es]
		except:
			weights = None

		membership = graph.community_leading_eigenvector().membership
		step = dict(zip(labels, membership))
		
		'''
		Now determine the membership pairs this step.
		'''
		for i in range(len(step)):
			for j in range(i):
				vA = min(step.keys()[i],step.keys()[j])
				vB = max(step.keys()[i],step.keys()[j])
				
				if step[vA] == step[vB]:
					v = 1
				else:
					v = 0

				if pair.has_key((vA,vB)):
					pair[(vA,vB)].append(v)
				else:
					pair[(vA,vB)] = [v]

	return pairwiseStability_Average(pair)