Using Graph Homomorphisms for Vertex Classification Analysis in Social Networks - Marzano, Giovani Melo; Silveira, Pedro Henrique B. Ruas da; Fonseca, Gabriel Barbosa da; M. Jr., Pasteur Ottoni; Guimarães, Silvio Jamil F. (Proceedings of the Brazilian Symposium on Multimedia and the Web (WebMedia); 2017: Proceedings of the 23rd Brazilian Symposium on Multimedia and the Web, 2017)
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.