License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2020.23
URN: urn:nbn:de:0030-drops-119474
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11947/
Go to the corresponding LIPIcs Volume Portal

Riveros, Cristian ; Salas, Jorge

A Family of Centrality Measures for Graph Data Based on Subgraphs

pdf-format:
LIPIcs-ICDT-2020-23.pdf (0.5 MB)

Abstract

We present the theoretical foundations of a new approach in centrality measures for graph data. The main principle of our approach is very simple: the more relevant subgraphs around a vertex, the more central it is in the network. We formalize the notion of "relevant subgraphs" by choosing a family of subgraphs that, give a graph G and a vertex v in G, it assigns a subset of connected subgraphs of G that contains v. Any of such families defines a measure of centrality by counting the number of subgraphs assigned to the vertex, i.e., a vertex will be more important for the network if it belongs to more subgraphs in the family. We show many examples of this approach and, in particular, we propose the all-subgraphs centrality, a centrality measure that takes every subgraph into account. We study fundamental properties over families of subgraphs that guarantee desirable properties over the corresponding centrality measure. Interestingly, all-subgraphs centrality satisfies all these properties, showing its robustness as a notion for centrality. Finally, we study the computational complexity of counting certain families of subgraphs and show a polynomial time algorithm to compute the all-subgraphs centrality for graphs with bounded tree width.

BibTeX - Entry

@InProceedings{riveros_et_al:LIPIcs:2020:11947,
  author =	{Cristian Riveros and Jorge Salas},
  title =	{{A Family of Centrality Measures for Graph Data Based on Subgraphs}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Carsten Lutz and Jean Christoph Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11947},
  URN =		{urn:nbn:de:0030-drops-119474},
  doi =		{10.4230/LIPIcs.ICDT.2020.23},
  annote =	{Keywords: Graph data, graph centrality, centrality measures}
}

Keywords: Graph data, graph centrality, centrality measures
Collection: 23rd International Conference on Database Theory (ICDT 2020)
Issue Date: 2020
Date of publication: 11.03.2020
Supplementary Material: Video of the Presentation: https://doi.org/10.5446/46822

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI