SimRank: a measure of structural-context similarity 2002 - Leitura de Artigo e outras referências

Simrank

Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '02). Association for Computing Machinery, New York, NY, USA, 538–543. DOI:https://doi.org/10.1145/775047.775126

Objetivo: medir a similaridade entre nós do mesmo tipo (melhor aplicado a grafos com vários tipos de nós). Avalia onde “random walkers” terminam quando partindo de um nó fonte.
Problema: deve ser calculado para todos os nós ( restringe o tamanho máximo do grafo que pode ser analisado)
Solução: usar um algoritmo que aproxima o simrank.

Simrank: Maneira de medir a similaridade de nós em um grafo com vários tipos de nós que consiste em iniciar um random walker em um nó e permitir que vague pelo grafo com uma probabilidade fixa de voltar ao nó inicial. A distribuição de onde o caminhante vai parar é uma boa estimativa da similaridade de dois nós. Este processo precisa ser repetido para todos os nós para gerar um “all-pairs similarity”.

The key of SimRank is

Two objects are considered to be similar if they are referenced by similar objects.

Passo 1 - Se a == b, S (a, b) = 1, senão, S (a, b) = 0

Passo 2 - Se um dos nós não tiver arestas de entrada, S (a, b) = 0

Passo 3 - S (a, b) = (constante C / grau-entrada(a) * grau-entrada(b)) * somatório (#)

Link -> https://towardsdatascience.com/simrank-similarity-analysis-1d8d5a18766a

somatório (#)

for i de 1 a |I(a)|
    for j de 1 a |I(b)|
        soma = soma + S (Ii(a), Ij(b))
I(a) são os vizinhos de a, Ii(a) é o i-ésimo vizinho de a
I(b) são os vizinhos de b, Ij(b) é o j-ésimo vizinho de b

SimRank defines similarity between 2 vertices (or nodes) i and j as the average of the similarity between their in-neighbours decayed by a constant factor C.

PageRank analyses the individual vertices of the graph with respect to the global structure, while SimRank analyses the relationship between a pair of vertices (edges).

SimRank s(a, b) can be interpreted as the measure of how soon two random surfers are expected to meet at the same node if they start at nodes a and b and walk the graph backwards.

Apresentação: https://slideplayer.com/slide/8616576/

Não trata relações n-áridas, ou seja, se n > 2

Vídeo da séria Mining Massive Datasets -> https://www.youtube.com/watch?v=Y93J27otCWM

Medindo proximidade ou similaridade: shortest path, 

SimRank para grafos k-partidos (k tipos de entidades), não escala para grandes grafos. Exemplo k=2 para grafos com Conferências e Autores, conferências similares tem conjunto de autores similares.

Outros problema são as similaridades zeradas. 

Abordagem para hipergrafo que considera a similaridade em determinada perspectiva (nós de referência) -> https://youtu.be/oDta4yVw0_8