  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 !!!