SimRank

SimRank es una medida de similitud general , basada en un modelo de teoría de grafos simple e intuitivo . SimRank es aplicable en cualquier dominio con relaciones entre objetos , y mide la similitud del contexto estructural en el que aparecen los objetos, basándose en sus relaciones con otros objetos. En efecto, SimRank es una medida que indica que dos objetos se consideran similares si son referenciados por objetos similares. Aunque SimRank es ampliamente utilizado, puede generar puntuaciones de similitud poco razonables, influenciadas por diversos factores, lo cual puede solucionarse de varias maneras, como introduciendo un factor de ponderación de la evidencia, ^{[ 1 ]} insertando términos adicionales que SimRank no considera ^{[ 2 ]} o utilizando alternativas basadas en PageRank. ^{[ 3 ]}

Muchas aplicaciones requieren medir la similitud entre objetos. Un ejemplo claro es la consulta "encontrar documentos similares" en corpus de texto tradicionales o en la World Wide Web . De forma más general, una medida de similitud puede utilizarse para agrupar objetos , como en el filtrado colaborativo de un sistema de recomendación , donde los usuarios y elementos "similares" se agrupan según las preferencias de los usuarios.

Diversos aspectos de los objetos pueden utilizarse para determinar la similitud, dependiendo generalmente del dominio y de la definición de similitud apropiada para dicho dominio. En un corpus de documentos , se puede utilizar texto coincidente, y para el filtrado colaborativo, se pueden identificar usuarios similares mediante preferencias comunes. SimRank es un enfoque general que aprovecha las relaciones entre objetos presentes en muchos dominios de interés. En la web , por ejemplo, dos páginas están relacionadas si existen hipervínculos entre ellas. Un enfoque similar puede aplicarse a artículos científicos y sus citas, o a cualquier otro corpus de documentos con información de referencias cruzadas . En el caso de los sistemas de recomendación, la preferencia de un usuario por un elemento constituye una relación entre el usuario y el elemento. Estos dominios se modelan naturalmente como grafos , donde los nodos representan objetos y las aristas representan relaciones.

La intuición detrás del algoritmo SimRank es que, en muchos dominios, los objetos similares son referenciados por objetos similares. Más precisamente, los objetos y se consideran similares si son referenciados por los objetos y , respectivamente, y y son similares entre sí. El caso base es que los objetos son máximamente similares entre sí. ^{[ 4 ]}${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle d}$${\displaystyle c}$${\displaystyle d}$

Es importante destacar que SimRank es un algoritmo general que determina únicamente la similitud del contexto estructural. SimRank se aplica a cualquier dominio donde existan suficientes relaciones relevantes entre objetos para fundamentar, al menos en cierta medida, la noción de similitud en dichas relaciones. Obviamente, la similitud de otros aspectos específicos del dominio también es importante; estos pueden —y deben— combinarse con la similitud relacional del contexto estructural para obtener una medida de similitud global. Por ejemplo, para páginas web, SimRank puede combinarse con la similitud textual tradicional; la misma idea se aplica a artículos científicos u otros corpus documentales. En los sistemas de recomendación, puede haber similitudes conocidas entre elementos (por ejemplo, ambos ordenadores, ambas prendas de vestir, etc.), así como similitudes entre usuarios (por ejemplo, mismo género, mismo nivel de gasto). Nuevamente, estas similitudes pueden combinarse con las puntuaciones de similitud calculadas en función de los patrones de preferencia para obtener una medida de similitud global.

Para un nodo en un grafo dirigido, denotamos por y el conjunto de vecinos entrantes y salientes de , respectivamente. Los vecinos entrantes individuales se denotan como , para , y los vecinos salientes individuales se denotan como , para . ${\displaystyle v}$${\displaystyle I(v)}$${\displaystyle O(v)}$${\displaystyle v}$${\displaystyle I_{i}(v)}$${\displaystyle 1\leq i\leq \left|I(v)\right|}$${\displaystyle O_{i}(v)}$${\displaystyle 1\leq i\leq \left|O(v)\right|}$

Denotemos la similitud entre objetos y por . Siguiendo la motivación anterior, se escribe una ecuación recursiva para . Si entonces se define como . De lo contrario, ${\displaystyle a}$${\displaystyle b}$${\displaystyle s(a,b)\in [0,1]}$${\displaystyle s(a,b)}$${\displaystyle a=b}$${\displaystyle s(a,b)}$${\displaystyle 1}$

${\displaystyle s(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s(I_{i}(a),I_{j}(b))}$

donde es una constante entre y . Un pequeño detalle técnico aquí es que o pueden no tener vecinos entrantes. Dado que no hay forma de inferir ninguna similitud entre y en este caso, la similitud se establece en , por lo que la suma en la ecuación anterior se define como cuando o . ${\displaystyle C}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle s(a,b)=0}$${\displaystyle 0}$${\displaystyle I(a)=\emptyset }$${\displaystyle I(b)=\emptyset }$

Dado un valor constante arbitrario entre y , sea la matriz de similitud cuya entrada denota la puntuación de similitud , y sea la matriz de adyacencia normalizada por columnas cuya entrada es si existe una arista de a , y 0 en caso contrario. Entonces, en notación matricial, SimRank se puede formular como ${\displaystyle C}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle \mathbf {S} }$${\displaystyle [\mathbf {S} ]_{a,b}}$${\displaystyle s(a,b)}$${\displaystyle \mathbf {A} }$${\displaystyle [\mathbf {A} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}}$${\displaystyle a}$${\displaystyle b}$

${\displaystyle {\mathbf {S} }=\max\{C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} }),{\mathbf {I} }\},}$

donde es una matriz identidad . ${\displaystyle \mathbf {I} }$

Se puede llegar a una solución para las ecuaciones de SimRank de un grafo mediante iteración a un punto fijo . Sea el número de nodos en . Para cada iteración , podemos guardar entradas , donde da la puntuación entre y en la iteración . Calculamos sucesivamente basándonos en . Comenzamos con donde cada es una cota inferior de la puntuación real de SimRank : ${\displaystyle G}$${\displaystyle n}$${\displaystyle G}$${\displaystyle k}$${\displaystyle n^{2}}$${\displaystyle s_{k}(*,*)}$${\displaystyle s_{k}(a,b)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle k}$${\displaystyle s_{k+1}(*,*)}$${\displaystyle s_{k}(*,*)}$${\displaystyle s_{0}(*,*)}$${\displaystyle s_{0}(a,b)}$${\displaystyle s(a,b)}$

${\displaystyle s_{0}(a,b)={\begin{cases}1{\mbox{ }},{\mbox{ }}{\mbox{si }}a=b{\mbox{ }},\\0{\mbox{ }},{\mbox{ }}{\mbox{si }}a\neq b{\mbox{ }}.\end{cases}}}$

Para calcular a partir de , utilizamos la ecuación básica de SimRank para obtener: ${\displaystyle s_{k+1}(a,b)}$${\displaystyle s_{k}(*,*)}$

${\displaystyle s_{k+1}(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s_{k}(I_{i}(a),I_{j}(b))}$

para y para . Es decir, en cada iteración , actualizamos la similitud de utilizando las puntuaciones de similitud de los vecinos de de la iteración anterior según la ecuación básica de SimRank. Los valores no disminuyen a medida que aumenta. Se demostró en ^{[ 4 ]} que los valores convergen a límites que satisfacen la ecuación básica de SimRank, las puntuaciones de SimRank , es decir, para todo , . ${\displaystyle a\neq b}$${\displaystyle s_{k+1}(a,b)=1}$${\displaystyle a=b}$${\displaystyle k+1}$${\displaystyle (a,b)}$${\displaystyle (a,b)}$${\displaystyle k}$${\displaystyle s_{k}(*,*)}$${\displaystyle k}$${\displaystyle s(*,*)}$${\displaystyle a,b\in V}$${\displaystyle \lim _{k\to \infty }s_{k}(a,b)=s(a,b)}$

La propuesta original de SimRank sugería elegir el factor de decaimiento y un número fijo de iteraciones. Sin embargo, una investigación reciente ^{[ 5 ]} demostró que los valores dados para y generalmente implican una precisión relativamente baja en las puntuaciones de SimRank calculadas iterativamente. Para garantizar resultados de cálculo más precisos, este último artículo sugiere usar un factor de decaimiento menor (en particular, ) o realizar más iteraciones. ${\displaystyle C=0.8}$${\displaystyle K=5}$${\displaystyle C}$${\displaystyle K}$${\displaystyle C=0.6}$

CoSimRank es una variante de SimRank con la ventaja de tener también una formulación local, es decir, CoSimRank se puede calcular para un único par de nodos. ^{[ 6 ]} Sea la matriz de similitud cuya entrada denota la puntuación de similitud , y sea la matriz de adyacencia normalizada por columnas. Entonces, en notación matricial, CoSimRank se puede formular como: ${\displaystyle \mathbf {S} }$${\displaystyle [\mathbf {S} ]_{a,b}}$${\displaystyle s(a,b)}$${\displaystyle \mathbf {A} }$

${\displaystyle {\mathbf {S} }=C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} })+{\mathbf {I} },}$

donde es una matriz identidad. Para calcular la puntuación de similitud de un solo par de nodos, sea , donde es un vector de la base estándar , es decir, la entrada -ésima es 1 y todas las demás entradas son 0. Entonces, CoSimRank se puede calcular en dos pasos: ${\displaystyle \mathbf {I} }$${\displaystyle p^{(0)}(i)=e_{i}}$${\displaystyle e_{i}}$${\displaystyle i}$

1. ${\displaystyle p^{(k)}=Ap^{(k-1)}}$
2. ${\displaystyle s(i,j)=\sum _{k=0}^{\infty }C^{k}\langle p^{(k)}(i),p^{(k)}(j)\rangle }$

El primer paso puede verse como una versión simplificada de PageRank personalizado . El segundo paso suma la similitud vectorial de cada iteración. Tanto la representación matricial como la local calculan la misma puntuación de similitud. CoSimRank también puede utilizarse para calcular la similitud de conjuntos de nodos, modificando . ${\displaystyle p^{(0)}(i)}$

• Fogaras y Racz ^{[ 7 ]} sugirieron acelerar el cálculo de SimRank mediante un cálculo probabilístico utilizando el método de Monte Carlo .
• Antonellis et al. ^{[ 8 ]} extendieron las ecuaciones de SimRank para tener en cuenta (i) el factor de evidencia para los nodos incidentes y (ii) los pesos de los enlaces.
• Yu et al. ^{[ 9 ]} mejoraron aún más el cálculo de SimRank mediante un método de memorización de grano fino para compartir pequeñas partes comunes entre diferentes sumas parciales.
• Chen y Giles analizaron las limitaciones y los casos de uso adecuados de SimRank. ^{[ 3 ]}

Lizorkin et al. ^{[ 5 ]} propusieron tres técnicas de optimización para acelerar el cálculo de SimRank:

1. La selección de nodos esenciales puede eliminar el cálculo de una fracción de pares de nodos con puntuaciones nulas a priori.
2. La memorización de sumas parciales puede reducir eficazmente los cálculos repetidos de la similitud entre diferentes pares de nodos al almacenar en caché parte de las sumas de similitud para su posterior reutilización.
3. Al establecer un umbral de similitud, se puede reducir aún más el número de pares de nodos que se deben calcular.

En particular, la segunda observación de la memorización de sumas parciales juega un papel primordial al acelerar enormemente el cálculo de SimRank de a , donde es el número de iteraciones, es el grado promedio de un grafo y es el número de nodos en un grafo. La idea central de la memorización de sumas parciales consta de dos pasos: ${\displaystyle {\mathcal {O}}(Kd^{2}n^{2})}$${\displaystyle {\mathcal {O}}(Kdn^{2})}$${\displaystyle K}$${\displaystyle d}$${\displaystyle n}$

Primero, las sumas parciales sobre se memorizan como ${\displaystyle I(a)}$

${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)=\sum _{i\in I(a)}s_{k}(i,j),\qquad (\forall j\in I(b))}$

y luego se calcula iterativamente a partir de como ${\displaystyle s_{k+1}(a,b)}$${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$

${\displaystyle s_{k+1}(a,b)={\frac {C}{|I(a)||I(b)|}}\sum _{j\in I(b)}{\text{Partial}}_{I(a)}^{s_{k}}(j).}$

En consecuencia, los resultados de , , se pueden reutilizar más adelante cuando calculamos las similitudes para un vértice dado como primer argumento. ${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$${\displaystyle \forall j\in I(b)}$${\displaystyle s_{k+1}(a,*)}$${\displaystyle a}$

• PageRank

• Cai, Y.; Cong, G.; Jia, X.; Liu, H.; He, J.; Lu, J.; Du, X. (1 de diciembre de 2009). «Algoritmo eficiente para calcular la similitud basada en enlaces en redes del mundo real» . Novena Conferencia Internacional IEEE sobre Minería de Datos de 2009. págs.  734–739 . doi : 10.1109/ICDM.2009.136 . ISBN 978-1-4244-5242-2. S2CID  9799597 .