Browsing by Author "Salas Cornejo, Jorge"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    A family of centrality measures based on subgraph
    (2019) Salas Cornejo, Jorge; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    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.
  • Thumbnail Image
    Item
    On the expressiveness and structural properties of centrality measures
    (2024) Salas Cornejo, Jorge; Pieris, Andreas; Riveros Jaeger, Cristian; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Centrality measures are used as analytical tools to understand graph-based data in various contexts. They are particularly useful for detecting important agents in disease spreading, influential individuals in social networks, or political decisionmakers. This is primarily due to the diversity of measures and their potential for exploitation in theoretical analyses. However, there exists a gap in the understanding of centrality from a foundational perspective. In this thesis, we provide an in-depth study of centrality measures from two different angles. Firstly, we examine how centralities behave over trees. Due to the simple structure of trees, it is easier to analyze each centrality measure in a restricted setting. We introduce the rooting tree property and propose a framework of potential functions to characterize rooting measures. In the last two Chapters, we present a novel study of the family of subgraph-based centralities (SBMs), which serve as a general framework for developing new measures. To define an SBM, we select a set of important subgraphs relevant to a specific application. The most important vertices are then determined based on the number of important subgraphs surrounding them. Initially, we investigate the absolute and ranking expressiveness of SBMs, answering the question of when an arbitrary centrality measure can be defined as an SBM. This, in turn, allows us to compare commonly used centralities within the scope of SBMs. Finally, we conduct an experimental study of important subgraph-based measures, as well as commonly used measures, using statistical scores such as Pearson correlation, ranking distances, and similarities to identify evidence of closely related measures.