<commit_before>""" This module contains algorithms for the calculation of centrality, i.e. ranking nodes by their structural importance
to the network """


__author__ = "<NAME>"
__credits__ = ["<NAME>", "<NAME>", "<NAME>"]

# extension imports
from _NetworKit import Betweenness, PageRank, EigenvectorCentrality, DegreeCentrality, ApproxBetweenness, ApproxBetweenness2, DynBetweenness, DynApproxBetweenness


# 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 centralization(G, centralityMeasure):
	"""
	Compute the centralization of a network with respect to some centrality measure.

	The centralization of any network is a measure of how central its most central
	node is in relation to how central all the other nodes are.
	Centralization measures then (a) calculate the sum in differences
	in centrality between the most central node in a network and all other nodes;
	and (b) divide this quantity by the theoretically largest such sum of
	differences in any network of the same size.

	Parameters
	----------
	G : graph
		The graph of which to compute the centrality
	centralityMeasure : instance of Centrality (sub)class
				initialized algorithm object will be run

	Returns
	-------
	double
		centralization score

	"""
	centralityMeasure.run()
	ranking = centralityMeasure.ranking()
	(center, centerScore) = ranking[0]
	maxScore = centralityMeasure.maximum()
	diff1 = sum([(centerScore - c) for (u, c) in ranking])
	diff2 = sum([(maxScore - c) for (u, c) in ranking])
	return diff1 / diff2


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 relativeRankError(rx, ry):
	"""
	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<commit_msg>fixed indentation error in centrality.py<commit_after>""" This module contains algorithms for the calculation of centrality, i.e. ranking nodes by their structural importance
to the network """


__author__ = "<NAME>"
__credits__ = ["<NAME>", "<NAME>", "<NAME>"]

# extension imports
from _NetworKit import Betweenness, PageRank, EigenvectorCentrality, DegreeCentrality, ApproxBetweenness, ApproxBetweenness2, DynBetweenness, DynApproxBetweenness


# 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 centralization(G, centralityMeasure):
	"""
	Compute the centralization of a network with respect to some centrality measure.

	The centralization of any network is a measure of how central its most central
	node is in relation to how central all the other nodes are.
	Centralization measures then (a) calculate the sum in differences
	in centrality between the most central node in a network and all other nodes;
	and (b) divide this quantity by the theoretically largest such sum of
	differences in any network of the same size.

	Parameters
	----------
	G : graph
		The graph of which to compute the centrality
	centralityMeasure : instance of Centrality (sub)class
				initialized algorithm object will be run

	Returns
	-------
	double
		centralization score

	"""
	centralityMeasure.run()
	ranking = centralityMeasure.ranking()
	(center, centerScore) = ranking[0]
	maxScore = centralityMeasure.maximum()
	diff1 = sum([(centerScore - c) for (u, c) in ranking])
	diff2 = sum([(maxScore - c) for (u, c) in ranking])
	return diff1 / diff2


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 relativeRankError(rx, ry):
	"""
	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
{'fraction_non_alphanumeric': 0.09594739667203435, 'fraction_numerical': 0.004562533548040795, 'mean_word_length': 3.9587491683300065, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4975767', 'n_tokens_mistral': 2325, 'n_tokens_neox': 2150, 'n_words': 831}