centrality.py
""" This module contains algorithms for the calculation of centrality, i.e. ranking nodes by their structural importance
to the network """
__author__ = "Christian Staudt"
__credits__ = ["Christian Staudt", "Elisabetta Bergamini", "Henning Meyerhenke", "Marc Nemes", "Maximilian Vogel"]
# extension imports
# TODO: (+) ApproxCloseness
from _NetworKit import Betweenness, PageRank, EigenvectorCentrality, DegreeCentrality, ApproxBetweenness, ApproxBetweenness2, DynApproxBetweenness, Closeness, KPathCentrality, CoreDecomposition, KatzCentrality, LocalClusteringCoefficient, ApproxCloseness, LocalPartitionCoverage, Sfigality, SpanningEdgeCentrality, PermanenceCentrality, TopCloseness
# local imports
from networkit.algebraic import adjacencyEigenvector, PageRankMatrix, symmetricEigenvectors
# external imports
import math
def ranking(G, algorithm=Betweenness, normalized=False):
""" Return a ranking of nodes by the specified centrality type"""
# FIXME: some centrality algorithms take more parameters
centrality = algorithm(G, normalized)
centrality.run()
return centrality.ranking()
def scores(G, algorithm=Betweenness, normalized=False):
""" Return the centrality scores of nodes using the specified centrality type"""
centrality = algorithm(G, normalized)
centrality.run()
return centrality.scores()
def rankPerNode(ranking):
"""
Parameters
----------
ranking: ordered list of tuples (node, score)
Returns
_______
for each node (sorted by node ID), the ranking of the node
"""
n_nodes = len(ranking)
ranking_id = [0]*n_nodes
for index, pair in enumerate(ranking):
ranking_id[pair[0]] = index
#we assign to all nodes the ranking of the first node with the same score
for index, pair in enumerate(ranking):
if index == 0:
continue
if pair[1] == ranking[index-1][1]:
prev_node = ranking[index-1][0]
ranking_id[pair[0]] = ranking_id[prev_node]
return ranking_id
def relativeRankErrors(rx, ry):
"""
Let $r_x(u)$ be the rank of node $u$ in ranking $x$.
The relative rank error of node $u$ is defined as
$$r_x(u) / r_y(u)$$
Parameters
----------
rx : list
ranking - ordered list of tuples (node, score)
ry: list
ranking - ordered list of tuples (node, score)
Returns
_______
list of rank errors ordered by node ID
"""
diff = []
n = len(rx)
if not(n == len(ry)):
return diff
rnode_x = rankPerNode(rx)
rnode_y = rankPerNode(ry)
for i in range(n):
diff.append((rnode_x[i]+1)/(rnode_y[i]+1))
return diff
class SpectralCentrality:
"""
Abstract class to compute the spectral centrality of a graph. This class needs to be supplied with methods
to generate the correct matrices and do the correct normalization.
"""
def __init__(self, G, normalized=False):
"""
Constructor.
Parameters
----------
G : graph
The graph of which to compute the centrality
normalized : boolean
Whether to normalize the results or not
"""
super(SpectralCentrality, self).__init__()
self.graph = G
self.normalized = normalized
self.scoreList = None
self.rankList = None
self.evz = {}
def prepareSpectrum(self):
""" Method that must be implemented to set the following values:
self.eigenvectors = list of eigenvectors desired for centrality measure
self.eigenvalues = list of corresponding eigenvalues
"""
raise NotImplemented
def normFactor(self):
""" Method that must be implemented to return a correct normalization factor"""
raise NotImplemented
def run(self):
self.prepareSpectrum()
self.scoreList = None
self.rankList = None
self.evz = {}
if self.normalized:
normFactor = self.normFactor()
else:
normFactor = 1
for v in self.graph.nodes():
self.evz[v] = self.eigenvector[v] * normFactor
return self
def scores(self):
if self.scoreList is None:
self.scoreList = [v for k,v in self.evz.items()]
return self.scoreList
def ranking(self):
if self.rankList is None:
self.rankList = sorted(self.evz.items(),key=lambda x: float(x[1]), reverse=True)
return self.rankList
class SciPyEVZ(SpectralCentrality):
"""
Compute Eigenvector centrality using algebraic meh
Parameters
----------
G : graph
The graph of which to compute the centrality
normalized : boolean
Whether to normalize the results or not
"""
def __init__(self, G, normalized=False):
if G.isDirected():
raise NotImplementedError("Not implemented for directed graphs; use centrality.EigenvectorCentrality instead")
super(SciPyEVZ, self).__init__(G, normalized=normalized)
def _length(self, vector):
square = sum([val * val for val in vector])
return math.sqrt(square)
def normFactor(self):
return 1 / self._length(self.eigenvector)
def prepareSpectrum(self):
spectrum = adjacencyEigenvector(self.graph, order=0)
self.eigenvector = spectrum[1]
self.eigenvalue = spectrum[0]
class SciPyPageRank(SpectralCentrality):
# TODO: docstring
def __init__(self, G, damp=0.95, normalized=False):
super(SciPyPageRank, self).__init__(G, normalized=normalized)
self.damp = damp
def _length(self, vector):
return sum(vector)
def normFactor(self):
return 1 / self._length(self.eigenvector)
def prepareSpectrum(self):
prMatrix = PageRankMatrix(self.graph, self.damp)
spectrum = symmetricEigenvectors(prMatrix, cutoff=0, reverse=False)
self.eigenvector = spectrum[1][0]
self.eigenvalue = spectrum[0][0]