Clustering Networks with Node Attributes using Bregman Divergences
Autores
|
7392 |
753,3215,3216
|
|
|
7393 |
753,3215,3216
|
|
|
7394 |
Maximilien Dreveton
(Co-orientador) |
753,3215,3216
|
Informações:
Publicações do PESC
O clustering de rede aborda o problema de identificação de conjuntos de nós (comunidades) que possuem padrões de conexão semelhantes. No entanto, em muitos cenários, os nós também têm atributos que geralmente estão correlacionados com a estrutura de cluster. Assim, as informações da rede (arestas) e informações do nó (atributos) podem ser aproveitados em conjunto para projetar algoritmos de clustering de alto desempenho. Sob um modelo geral para a rede e atributos do nó, este trabalho apresenta um algoritmo de clustering iterativo que maximiza a verossimilhança conjunta, assumindo que a distribuição de probabilidade das interações na rede e os atributos dos nós pertencem a famílias exponenciais. Este modelo cobre uma ampla gama de possíveis interações (por exemplo, arestas com pesos) e atributos de nó (por exemplo, distribuições não gaussianas), bem como redes esparsas, ao mesmo tempo que explora a conexão entre famílias exponenciais e divergências de Bregman permitindo uma expressão elegante para a função de log-verossimilhança. Extensos experimentos numéricos usando dados sintéticos indicam que o algoritmo proposto supera algoritmos clássicos que aproveitam apenas informações de rede ou apenas atributos bem como algoritmos de última geração que também aproveitam ambas as fontes de informação. A avaliação preliminar utilizando conjuntos de dados reais também indica a superioridade da proposta abordagem na detecção de comunidades. As contribuições deste trabalho fornecem insights sobre as técnicas práticas para inferir rótulos de comunidade em redes com atributos nos vértices.
Network clustering tackles the problem of identifying sets of nodes (communities) that have similar connection patterns. However, in many scenarios, nodes also have attributes that are often correlated with the clustering structure. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design high-performance clustering algorithms. Under a general model for the network and node attributes, this work presents an iterative clustering algorithm that maximizes the joint likelihood, assuming that the probability distribution of network interactions and node attributes belong to exponential families. This model covers a broad range of possible interactions (e.g., edges with weights) and node attributes (e.g., non-Gaussian distributions), as well as sparse networks, while also exploring the connection between exponential families and Bregman divergences allowing for an elegant expression for the log-likelihood function. Extensive numerical experiments using synthetic data indicates that the proposed algorithm outperforms classic algorithms that leverage only network or only attribute information as well as state-of-the-art algorithms that also leverage both sources of information. Preliminary evaluation using real datasets also indicate the superiority of the proposed approach in detecting communities. The contributions of this work provide insights into the practical techniques for inferring community labels on node-attributed networks.