rigraphsimilaritysna

How to compute the "Katz similarity" measure of regular equivalence described in Newman (2010)


I would like to know if there is an R package which is able to compute the regular equivalence measure described in Newman (2010:218) as "Katz similarity":

enter image description here

where σ is the similarity score, A is the adjacency matrix of the graph and δ is meant to increase the "self-similarity" of diagonal elements. So far I was not able to find any specific function computing this score in R. Since the textbook also explicitly states that:

"The Katz centrality of a vertex would then be simply the sum of the Katz similarities of that vertex to all others." (Newman, 2010: 219)

I was thinking that maybe there is a way to derive the similarity score from the Katz centrality measure, but I could not find a proper way to disentangle each score in the centrality.


Solution

  • I might be able to get part way there (although this is not my area of expertise). The answer may be:

    Package ‘linkprediction’
    October 19, 2018
    Title Link Prediction Methods
    Version 1.0-0
    Description Implementations of most of the existing proximity-based methods of
    link prediction in graphs. Among the 20 implemented methods are e.g.:
    Adamic L. and Adar E. (2003) <doi:10.1016/S0378-8733(03)00009-1>,
    Leicht E., Holme P., Newman M. (2006) <doi:10.1103/PhysRevE.73.026120>,
    Zhou T. and Zhang Y (2009) <doi:10.1140/epjb/e2009-00335-8>, and
    Fouss F., Pirotte A., Renders J., and Saerens M. (2007) <doi:10.1109/TKDE.2007.46>.
    

    The Leicht E., Holme P., Newman M. (2006) <doi:10.1103/PhysRevE.73.026120> citation is behind a paywall, but there is a preprint version of it that makes me think the citation you mention is a later description of the same thing: https://arxiv.org/abs/physics/0510143

    if(!require("linkprediction") ){ 
        install.packages("linkprediction", dependencies=TRUE); 
        library(linkprediction }
    if(requireNamespace("igraph")) {
      g <- igraph::make_graph(~ A -- C:D:E -- B -- F -- G:H -- I)
    }
    # LHN
    proxfun(g, method="lhn_global") $ returns matrix, possibly what your eq. described
    round( proxfun(g, method="lhn_global"), 5)
            1       2       3       4       5       6       7       8       9
    1 0.12648 0.04052 0.04052 0.04052 0.01199 0.00329 0.00101 0.00101 0.00038
    2 0.04052 0.27352 0.02352 0.02352 0.03162 0.00867 0.00266 0.00266 0.00101
    3 0.04052 0.02352 0.27352 0.02352 0.03162 0.00867 0.00266 0.00266 0.00101
    4 0.04052 0.02352 0.02352 0.27352 0.03162 0.00867 0.00266 0.00266 0.00101
    5 0.01199 0.03162 0.03162 0.03162 0.07439 0.02039 0.00625 0.00625 0.00237
    6 0.00329 0.00867 0.00867 0.00867 0.02039 0.12603 0.03862 0.03862 0.01465
    7 0.00101 0.00266 0.00266 0.00266 0.00625 0.03862 0.27152 0.02152 0.05556
    8 0.00101 0.00266 0.00266 0.00266 0.00625 0.03862 0.02152 0.27152 0.05556
    9 0.00038 0.00101 0.00101 0.00101 0.00237 0.01465 0.05556 0.05556 0.27107
    

    On the other hand you may be looking for "the Katz Index" which has a citation from 1953. Also look at https://arxiv.org/pdf/2105.01931.pdf as well as at: https://dial.uclouvain.be/memoire/ucl/en/object/thesis%3A12878/datastream/PDF_01/view (which offers Matlab code for calculations.)