A family of centrality measures based on subgraph
| dc.contributor.advisor | Riveros Jaeger, Cristian | |
| dc.contributor.author | Salas Cornejo, Jorge | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2022-10-17T18:21:25Z | |
| dc.date.available | 2022-10-17T18:21:25Z | |
| dc.date.issued | 2019 | |
| dc.description | Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019 | |
| dc.description.abstract | Esta tesis introduce las bases teóricas de un nuevo enfoque para las medidas de centralidad sobre bases de datos de grafos. El principio fundamental de este enfoque es simple: mientras más subgrafos relevantes envuelvan a un vértice, más central será dentro de la red. La idea de ”subgrafos relevantes” se formaliza eligiendo una familia de subgrafos que, dado un grafo G y un vértice v en G, esta asigna un conjunto de subgrafos conexos de G que contienen a v. Cualquiera de estas familias define una medida de centralidad al contar la cantidad de subgrafos asignados a cada vértice, i.e, un vértice será más importante para la red si pertenece a más subgrafos dentro de la familia. Se muestran ejemplo de este enfoque, en particular, se propone all-subgraphs centrality, una medida de centralidad que toma en cuenta todos los posibles subgrafos. Se analizan las propiedades fundamentales sobre familias de subgrafos que garantizan propiedades deseables sobre la medida de centralidad. Interesantemente, all-subgraphs centrality satisface todas estas propiedades, mostrando su robustes como noción de centralidad. Finalmente, se prueba la complejidad computacional del conteo de ciertas familias de subgrafos y se muestra un algoritmo de tiempo polinomial para computar all-subgraphs centrality cuando el grafo posee tree width acotado. | |
| dc.format.extent | vii, 58 páginas | |
| dc.fuente.origen | SRIA | |
| dc.identifier.doi | 10.7764/tesisUC/ING/65048 | |
| dc.identifier.uri | https://doi.org/10.7764/tesisUC/ING/65048 | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/65048 | |
| dc.information.autoruc | Escuela de ingeniería ; Riveros Jaeger, Cristian ; S/I ; 131276 | |
| dc.information.autoruc | Escuela de ingeniería ; Salas Cornejo, Jorge ; S/I ; 223195 | |
| dc.language.iso | en | |
| dc.nota.acceso | Contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject | Datos de grafos | es_ES |
| dc.subject | Medidas de centralidad | es_ES |
| dc.subject | Complejidad de conteo | es_ES |
| dc.subject | Tree width | es_ES |
| dc.subject.ddc | 620 | |
| dc.subject.dewey | Ingeniería | es_ES |
| dc.title | A family of centrality measures based on subgraph | es_ES |
| dc.type | tesis de maestría | |
| sipa.codpersvinculados | 131276 | |
| sipa.codpersvinculados | 223195 |