Using Graph Homomorphisms for Vertex Classification Analysis in Social Networks
| Autor: | Pedro Henrique Batista Ruas da Silveira, Gabriel Barbosa da Fonseca, Silvio Jamil Ferzoli Guimarães, M Pasteur Ottoni, Giovani Melo Marzano |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Computer science business.industry 020206 networking & telecommunications 02 engineering and technology Strength of a graph Machine learning computer.software_genre Butterfly graph law.invention law Line graph 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Graph homomorphism Regular graph Artificial intelligence Graph property business Null graph computer Complement graph MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | WebMedia |
| DOI: | 10.1145/3126858.3126895 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|