Absolute Expressiveness of Subgraph-Based Centrality Measures

Simple item page
dc.catalogadoryvc
dc.contributor.authorPieris, Andreas
dc.contributor.authorSalas Cornejo, Jorge Eduardo
dc.date.accessioned2025-02-25T15:27:28Z
dc.date.available2025-02-25T15:27:28Z
dc.date.issued2023
dc.description.abstractIn graph-based applications, a common task is to pinpoint the most important or “central” vertex in a (directed or undirected) graph, or rank the vertices of a graph according to their importance. To this end, a plethora of so-called centrality measures have been proposed in the literature. Such measures assess which vertices in a graph are the most important ones by analyzing the structure of the underlying graph. A family of centrality measures that are suited for graph databases has been recently proposed by relying on the following simple principle: the importance of a vertex in a graph is relative to the number of “relevant” connected subgraphs surrounding it; we refer to the members of this family as subgraph-based centrality measures. Although it has been shown that such measures enjoy several favourable properties, their absolute expressiveness remains largely unexplored. The goal of this work is to precisely characterize the absolute expressiveness of the family of subgraph-based centrality measures by considering both directed and undirected graphs. To this end, we characterize when an arbitrary centrality measure is a subgraph-based one, or a subgraph-based measure relative to the induced ranking. These characterizations provide us with technical tools that allow us to determine whether well-established centrality measures are subgraph-based. Such a classification, apart from being interesting in its own right, gives useful insights on the structural similarities and differences among existing centrality measures.
dc.description.funderPSRC grant EP/S003800/1 "EQUID"
dc.description.funderANID Millennium Science Initiative Program, Code ICN17_002
dc.fechaingreso.objetodigital2025-02-25
dc.format.extent18 páginas
dc.fuente.origenScopus
dc.identifier.doi10.4230/LIPIcs.ICDT.2023.9
dc.identifier.issn1868-8969
dc.identifier.scopusidScopus_ID: 85150722170
dc.identifier.urihttps://doi.org/10.4230/LIPIcs.ICDT.2023.9
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/102236
dc.information.autorucEscuela de Ingeniería; Salas Cornejo, Jorge Eduardo; S/I; 223195
dc.language.isoen
dc.nota.accesocontenido completo
dc.publisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
dc.relation.ispartofInternational Conference on Database Theory (ICDT) : 26th : 2023
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs), Volume 255
dc.revistaLeibniz International Proceedings in Informatics, LIPIcs
dc.rightsacceso abierto
dc.rights.licenseCC BY Atribución Internacional 4.0
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/deed.es
dc.subjectExpressiveness
dc.subjectGraph centrality measures
dc.subjectRanking
dc.subject.ddc620
dc.subject.deweyIngenieríaes_ES
dc.titleAbsolute Expressiveness of Subgraph-Based Centrality Measures
dc.typecomunicación de congreso
dc.volumen255
sipa.codpersvinculados223195
sipa.trazabilidadSCOPUS;2023-08-23
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
LIPIcs.ICDT.2023.9.pdf
Size:
813.01 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de conferencia