Created
March 3, 2010 03:23
-
-
Save mjbommar/320277 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
@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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment