Using Graph Homomorphisms for Vertex Classification Analysis in Social Networks

• Giovani Melo Marzano PUC-Minas
• Pedro Henrique B. Ruas da Silveira PUC-Minas
• Gabriel Barbosa da Fonseca PUC-Minas
• Pasteur Ottoni M. Jr. PUC-Minas
• Silvio Jamil F. Guimarães PUC-Minas

Resumo

A social network consists on a finite set of social entities and the relationships between them. These entities are represented as vertices in a graph which represents this network. Usually, the entities (or vertices) can be classified according to their features, like interactions (comments, posts, likes, etc.) for example. However, to work directly with these graphs and understand the relationships between the several pre-defined classes are not easy tasks due to, for instance, the graph's size. In this work, we propose metrics for evaluating how good is a graph transformation based on graph homomorphism, measuring how much the relationships of the original one are preserved after the transformation. The proposed metrics measure the edge regularity indices and indicate the proportion of the original graph's vertices that participates in the relations, moreover they measure how close to a regular homomorphism is the graph transformation. For assessing the regularity indices, some experiments taking into account synthetic and real social network data are given.