Clusterização em grafos é tambem chamade de “community detection”
Para grafos nao direcionados 0/1
Proporçao de arestas dentro do cluster subtraido pela pelo número de arestas esperado se o grafo fosse aleatório com o mesmo numero de vertices e arestas (ha algumas nocões de aleatorios - configuration model)
para um par de vertices i e j:
q_{ij} = a_{ij} - \frac{k_i k_j}{2m}
a_{ij} 0/1. m numero de arestas k_i o grau (numero de arestas) do vertice i
Modularidade para o grafo todo é a soma das moduralidades para cada par de vertices
Q = \frac{1}{2m} \sum_{ij} (a_{ij} - \frac{k_i k_j}{2m}) \delta(i,j)
\delta(i,j) = 1 se i e j estão no mesmo cluster
Modularitade pode ser estendida para grafos com pesos e grafos direcionados.
encontre C_1, C_2 ... C_k ou seja o \delta(i,j) que maximize Q
problema dificil
global e há o problema de resoluçao - nao acha clusters pequenos.
Aproximações
fast greedy - similar a clusterizacao hierarquica - vai juntando os melhores
leading eingenvector - aproxima usando autoveotres da matriz de modulatridade - divisivo
multilevel - fast greedy mas colapsa as comunidades para vertices e repete
Louvain -> Leiden
passeios aleatorios pequenos devem ficar dentro do cluster
walktrap
info map
vizinhos devem estar no mesmo cluster
spin glass
label propagation
igraph p/ R ou Python https://igraph.org/
outro pacote de grafos em Python NetworkX mas ha pouca clusterização.
https://www.sciencedirect.com/science/article/pii/S0370157309002841
https://arxiv.org/abs/2101.01669 recente (bom?)
https://arxiv.org/abs/2105.12584 recente
https://dl.acm.org/doi/10.1145/3444688 recente (multiplex / multilevel / multiview)
Exemplo: Relaçao usuário/produto
dois tipos de clusterização
cada tipo de vertice (clusterizar usuários)
subconjuntos do grafo como um todo https://www.sciencedirect.com/science/article/pii/S0378437116002582 ou figura em https://www.researchgate.net/publication/2912779_Clustering_of_Bipartite_Advertiser-Keyword_Graph/figures?lo=1
mapeamento de bipartido para mono partido (projection) (numero de produtos em comum entre 2 usuários)
https://arxiv.org/abs/1308.0971
de novo, 2 tipos de clusterização: citation (tradicional) e flow
https://en.wikipedia.org/wiki/Biclustering
Para dados vetoriais, os dados sao normalmente representados por matrizes onde as colunas sao os atributos/dimensões e as linhas os dados.
clusterizaçao é agrupar as linhas em grupos tendo em visto as colunas
biclusterizaçao é agrupar ao mesmo tempo linas e colunas
Se 2 dados sao diferentes em atributos que estao no mesmo cluster de atributos, entao os dados nao sao assim tao diferentes.
Ex: documentos (linhas) e palavras (colunas)
voce tem as classes/clusters de poucos dados.
a maioria dos dados não tem rótulo.
must link dados que precisam estar num mesmo cluster
cannot link dados que precisam estar em clusters diferentes
comum em proc de images http://dataclustering.cse.msu.edu/publications.html e o algoritmo de OPF do Prof. Falcão https://books.google.com.br/books/about/Optimum_Path_Forest.html?id=xb48EAAAQBAJ&source=kp_book_description&redir_esc=y
Em vez da informação supervisionada ter que ser “obedecida” ela pode indicar “dicas” que podem ser desconsideradas “se valer a pena”
mais facil de implementar em clusterização baseada em distribuição de probabilidades (GMM).
pacotes EMcluster e Rmixmod em R fazem isso
Nao relacionado com clusterização.
Grafos direcionados
nó é importante se ele é apontado por nós importantes
p(u) = \sum_{x-> u} \frac{p(x)}{K(x)}
p(u) importancia de u, K(x) grau de saida de x
Versão com o dumping factor: (web-surfista aleatorio)
p(u) = \frac{1-d}{N}+ d \sum_{x-> u} \frac{p(x)}{K(x)}
N numero de paginas, d = 0.85 (wikipedia)
Modified adjacency matrix (A’)
Modifies adjacency matriz é um tipo de Laplaciano (da aula de spectral clustering) - uma representação do grafo que “normaliza” pelo grau de cada no.
p = (\frac{1-d}{N} I + A') p
p é um autovetor (com autovalor 1) da modified adjacency matriz mais dumping factor nas diagonais.
Eigengap - diferença do maior e segundo maior autovalor.
Alto eigengap implica que vc pode inicializar o p aleatoriamente e rapidamente ele converge (usando a equação do autoverot/ponto fixo) para o valor correto.
hub: aponta para autoridades boas
autoridade: é apontado por hubs bons
a(u) = \sum_{x -> u} h(x)
h(u) = \sum_{u -> x} a(x)
Matriz de adjacencia a_{ij}=1 se i -> j
a = A h
h = A^T a
a = A A^T a
h = A^T A h
a e h sao autovetores das matrizes A A^T e A^T A