A family of centrality measures based on subgraph
Loading...
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2019
Keywords
Datos de grafos, Medidas de centralidad, Complejidad de conteo, Tree width