Katz centrality (measure centrality)

Python Methods and Functions

This is similar to Google's PageRank and eigenvector centrality.

Measuring Katz centrality

Simple social network: nodes represent people or actors, and edges between nodes represent some relationship between actors

Katz centrality calculates the relative influence of a node in a network by measuring the number of nearest neighbors (nodes of the first degree), as well as all other nodes in the network that connect to the node in question through these immediate neighbors. However, connections to distant neighbors are penalized with an attenuation factor . Each path or connection between a pair of nodes is assigned a weight defined by and the distance between nodes as ,

For example, in the picture on the right, assume that John's centrality is measured and that The weight assigned to each link that connects John to his immediate neighbors Jane and Bob is Since Jose connects to John indirectly through Bob, the weight assigned to this connection (two links) will be , Likewise, the weight assigned to the connection between Agneta and John via Aziz and Jane will be and the weight assigned to Agneta and John's connection via Diego, Jose and Bob will be ,

Mathematical formulation
Let A & # 8212 ; adjacency matrix of the considered network. the elements from A are variables that take the value 1 if node i is associated with node j and 0 otherwise. Degrees A indicate the presence (or absence) of links between two nodes through intermediaries. For example, in the matrix if the element , this indicates that node 2 and node 12 are connected through several neighbors of the first and second degree of node 2. If denotes the Katz centrality of node i, then mathematically:


Note that the above definition uses the fact that the element at the adjacency matrices elevated to power (ie ) reflects the total The degree of communication between nodes and , The value of the attenuation coefficient should be chosen so that it is less than the reciprocal of the absolute value of the largest eigenvalue of the adjacency matrix A. In this case, the following expression can be used to calculate Katz centrality:


Here is is an identity matrix, is a unit vector of size n (n — number of nodes), consisting of units. indicates transposed matrix A and ( indicates matrix term inversion ().

Below is the code to calculate the centrality of the Katz graph and its various nodes.

def katz_centrality (G, alpha = 0.1 , beta = 1.0 ,

max_iter = 1000 , tol = 1.0e - 6

nstart = None , normalized = True ,

weight = ' weight' ):

& quot; & quot; & quot; Calculate Katz centrality for nodes

of graph D.

 

 

Katz Central calculates the centrality for the node

  based on the centrality of its neighbors. This

generalizes the centrality of its own vector.

Katz centrality for node 'i'

  

.. mathematics ::

  

  x_i = / alpha / sum_ {j} A_ {ij} x_j + / beta,

 

where 'A' is the adjacency matrix of graph G

  with custom values '/ lambda'.

  

  The '/ beta' parameter controls the initial centrality and

 

.. math ::

 

/ alpha & lt; / frac {1} {/ lambda_ {max}}.

 

 

Katz centrality calculates relative influence

node in the network by measuring the number

immediate neighbors (nodes of the first degree) and

  also all other nodes on the network that connect

to the node in question via these

immediate neighbors.

 

Additional weight can be given to nearest neighbors

via parameter: math:' / beta'. links

made with distant neighbors, however, are fined

attenuation factor '/ alpha', which should be

  strictly less than the inverse largest eigenvalue

  Katz adjacency matrices

centrality must be calculated correctly.

 

 

options

----------

  G: graph

  NetworkX Graph

  

alpha: float

Attenuation factor

 

  beta: scalar or dictionary, optional (default = 1.0)

The weight is attributed to the immediate neighborhood.

If not a scalar, the dictionary should have value

for each node.

 

max_iter: integer, optional (default = 1000 )

Maximum number of iterations in the power method.

 

tol: float, optional (default = 1.0e -6)

Error used to check convergence in

iteration of the power method.

 

nstart: dictionary, optional

The initial Katz iteration value for each node.

 

normalized: bool, optional (default = True)

If True, normalize the resulting values.

 

weight: none or string, optional

If None, all edge weights are considered equal.

Otherwise contains the name of the edge attribute.

used as weight.

 

Returns

-------

nodes: dictionary

Dictionary of nodes with Katz's centrality as

Meaning.

 

Promotions

------

NetworkXError

If the 'beta' parameter is not a scalar and

there is not enough value for at least one node

 

 

 

  Notes

-----

  

This algorithm uses a forceful method to find

own vector corresponding to the largest

Eigenvalue of the adjacency matrix G.

Constant alpha must be strictly less than

reciprocal of largest eigenvalue of adjacency

matrix for the convergence algorithm.

  The iteration will stop after the max_iter iterations

or the allowed deviation from numbers_f_nodes (G) * only

Was achieved.

 

When '/ alpha = 1 // lambda_ {max}' and '/ beta = 0',

Katz centrality is the same as eigenvector centrality.

 

For directed graphs, this finds "left" own vectors

which matches the edges in the graph.

For outdoor Katz, first change the centrality

graph with G.reverse ().

 

 

"" "

from math import sqrt

 

if len (G) = = 0 :

return {}

 

nnodes = G.number_of_nodes ()

 

if nstart is None :

 

# select starting vector with 0 entries

x = dict ([(n, 0 ) for n in G])

else :

x = nstart

 

try :

b = dict . fromkeys (G, float (beta))

except (TypeError, ValueError, AttributeError):

b = beta

if set (beta)! = set (G):

  raise nx.NetworkXError ( 'beta dictionary'

  ' must have a value for every node' )

 

# make up to max_iter iterations

for i in range (max_iter):

  xlast = x

x = dict . fromkeys (xlast, 0 )

 

# multiply ^ T = alpha * x ^ TA - beta

for n in x:

  for nbr in G [n]:

  x [nbr] + = xlast [n] * G [n] [nbr] .get (weight, 1 )

for n in x:

x [n] = alpha * x [n] + b [n]

 

  # check convergence

  err = sum ([ abs (x [n] - xlast [n ]) for n in x])

  if err & lt; nnodes * tol:

if normalized:

 

# normalize vector

try :

s = 1.0 / sqrt ( sum (v * * 2 for v in x.values ​​()))

 

  # should it never be zero?

  except ZeroDivisionError:

s = 1.0

  else :

s = 1

for n in x:

x [n] * = s

ret urn x

 

  raise nx.NetworkXError ( ' Power iteration failed to converge in '

  '% d iterations.' % max_iter)

The above function is called using the networkx library and after installing it you can end up using it and the following code must be written in python to implement katz node centralization.

& gt; & gt; & gt; import networkx as nx

& gt; & gt ; & gt; import math

& gt; & gt; & gt ; G = nx.path_graph ( 4 )

& gt; & gt; & gt; phi = ( 1 + math.sqrt ( 5 )) / 2.0 # largest eigenvalue of the adjacent matrix

& gt; & gt; & gt; centrality = nx.katz_centrality (G, 1 / phi - 0.01 )

& gt; & gt; & gt; for n, c in sorted (centrality.items ()):

...  print ( "% d% 0.2f" % (n, c))

Output of the above code:

0 0.37

1 0.60

2 0.60

3 0.37

The above result is a dictionary showing the value of the center of the cutter of each node. The above is a continuation of my series on centralization measures. Keep chatting !!!

Links
http://networkx.readthedocs.io/en/networkx-1.10/index.html
https://en.wikipedia .org / wiki / Katz_centrality





Tutorials