4 Search Results for "Lopez-Garcia, Pedro"

Document
DOI: 10.4230/LIPIcs.SEA.2023.6
Proxying Betweenness Centrality Rankings in Temporal Networks

Authors: Ruben Becker, Pierluigi Crescenzi, Antonio Cruciani, and Bojana Kodric

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
Identifying influential nodes in a network is arguably one of the most important tasks in graph mining and network analysis. A large variety of centrality measures, all aiming at correctly quantifying a node’s importance in the network, have been formulated in the literature. One of the most cited ones is the betweenness centrality, formally introduced by Freeman (Sociometry, 1977). On the other hand, researchers have recently been very interested in capturing the dynamic nature of real-world networks by studying temporal graphs, rather than static ones. Clearly, centrality measures, including the betweenness centrality, have also been extended to temporal graphs. Buß et al. (KDD, 2020) gave algorithms to compute various notions of temporal betweenness centrality, including the perhaps most natural one - shortest temporal betweenness. Their algorithm computes centrality values of all nodes in time O(n³ T²), where n is the size of the network and T is the total number of time steps. For real-world networks, which easily contain tens of thousands of nodes, this complexity becomes prohibitive. Thus, it is reasonable to consider proxies for shortest temporal betweenness rankings that are more efficiently computed, and, therefore, allow for measuring the relative importance of nodes in very large temporal graphs. In this paper, we compare several such proxies on a diverse set of real-world networks. These proxies can be divided into global and local proxies. The considered global proxies include the exact algorithm for static betweenness (computed on the underlying graph), prefix foremost temporal betweenness of Buß et al., which is more efficiently computable than shortest temporal betweenness, and the recently introduced approximation approach of Santoro and Sarpe (WWW, 2022). As all of these global proxies are still expensive to compute on very large networks, we also turn to more efficiently computable local proxies. Here, we consider temporal versions of the ego-betweenness in the sense of Everett and Borgatti (Social Networks, 2005), standard degree notions, and a novel temporal degree notion termed the pass-through degree, that we introduce in this paper and which we consider to be one of our main contributions. We show that the pass-through degree, which measures the number of pairs of neighbors of a node that are temporally connected through it, can be computed in nearly linear time for all nodes in the network and we experimentally observe that it is surprisingly competitive as a proxy for shortest temporal betweenness.
Cite as

Ruben Becker, Pierluigi Crescenzi, Antonio Cruciani, and Bojana Kodric. Proxying Betweenness Centrality Rankings in Temporal Networks. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SEA.2023.6,
  author =	{Becker, Ruben and Crescenzi, Pierluigi and Cruciani, Antonio and Kodric, Bojana},
  title =	{{Proxying Betweenness Centrality Rankings in Temporal Networks}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.6},
  URN =		{urn:nbn:de:0030-drops-183568},
  doi =		{10.4230/LIPIcs.SEA.2023.6},
  annote =	{Keywords: node centrality, betweenness, temporal graphs, graph mining}
}
Document
DOI: 10.4230/OASIcs.ICLP.2018.10
Towards Static Performance Guarantees for Programs with Run-Time Checks

Authors: Maximiliano Klemen, Nataliia Stulova, Pedro Lopez-Garcia, José F. Morales, and Manuel V. Hermenegildo

Published in: OASIcs, Volume 64, Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)

Abstract
This document is an extended abstract of the Technical Report CLIP-1/2018.0.
Cite as

Maximiliano Klemen, Nataliia Stulova, Pedro Lopez-Garcia, José F. Morales, and Manuel V. Hermenegildo. Towards Static Performance Guarantees for Programs with Run-Time Checks. In Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018). Open Access Series in Informatics (OASIcs), Volume 64, pp. 10:1-10:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klemen_et_al:OASIcs.ICLP.2018.10,
  author =	{Klemen, Maximiliano and Stulova, Nataliia and Lopez-Garcia, Pedro and Morales, Jos\'{e} F. and Hermenegildo, Manuel V.},
  title =	{{Towards Static Performance Guarantees for Programs with Run-Time Checks}},
  booktitle =	{Technical Communications of the 34th International Conference on Logic Programming (ICLP 2018)},
  pages =	{10:1--10:2},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-090-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{64},
  editor =	{Dal Palu', Alessandro and Tarau, Paul and Saeedloei, Neda and Fodor, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2018.10},
  URN =		{urn:nbn:de:0030-drops-98765},
  doi =		{10.4230/OASIcs.ICLP.2018.10},
  annote =	{Keywords: Run-time Checks, Assertions, Abstract Interpretation, Resource Usage Analysis}
}
Document
Short Paper
DOI: 10.4230/OASIcs.SLATE.2018.11
Non-LR(1) Precedence Cascade Grammars (Short Paper)

Authors: José-Luis Sierra

Published in: OASIcs, Volume 62, 7th Symposium on Languages, Applications and Technologies (SLATE 2018)

Abstract
Precedence cascade is a well-known pattern for writing context-free grammars (CFGs) that model the syntax of expression languages. According to this method, precedence levels are represented by non-terminals, and operators' attributes are used to write syntax rules properly. In most cases, the resulting precedence cascade grammar (PCG) has neat properties that facilitate its implementation. In particular, many PCGs are LR(1) grammars, which serve as input for conventional bottom-up parser generators. However, for some cumbersome operator tables the method does not produce such neat grammars. This paper focuses on these cumbersome operator tables by identifying several conditions leading to non-LR(1) PCGs.
Cite as

José-Luis Sierra. Non-LR(1) Precedence Cascade Grammars (Short Paper). In 7th Symposium on Languages, Applications and Technologies (SLATE 2018). Open Access Series in Informatics (OASIcs), Volume 62, pp. 11:1-11:8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sierra:OASIcs.SLATE.2018.11,
  author =	{Sierra, Jos\'{e}-Luis},
  title =	{{Non-LR(1) Precedence Cascade Grammars}},
  booktitle =	{7th Symposium on Languages, Applications and Technologies (SLATE 2018)},
  pages =	{11:1--11:8},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-072-9},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{62},
  editor =	{Henriques, Pedro Rangel and Leal, Jos\'{e} Paulo and Leit\~{a}o, Ant\'{o}nio Menezes and Guinovart, Xavier G\'{o}mez},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2018.11},
  URN =		{urn:nbn:de:0030-drops-92696},
  doi =		{10.4230/OASIcs.SLATE.2018.11},
  annote =	{Keywords: grammarware, expression grammars, grammar patterns, grammar ambiguity, LR grammars}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2010.104
A Framework for Verification and Debugging of Resource Usage Properties: Resource Usage Verification

Authors: Pedro Lopez-Garcia, Luthfi Darmawan, and Francisco Bueno

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract
We present a framework for (static) verification of general resource usage program properties. The framework extends the criteria of correctness as the conformance of a program to a specification expressing non-functional global properties, such as upper and lower bounds on execution time, memory, energy, or user defined resources, given as functions on input data sizes. A given specification can include both lower and upper bound resource usage functions, i.e., it can express intervals where the resource usage is supposed to be included in. We have defined an abstract semantics for resource usage properties and operations to compare the (approximated) intended semantics of a program (i.e., the specification) with approximated semantics inferred by static analysis. These operations include the comparison of arithmetic functions (e.g., polynomial, exponential or logarithmic functions). A novel aspect of our framework is that the static checking of assertions generates answers that include conditions under which a given specification can be proved or disproved. For example, these conditions can express intervals of input data sizes such that a given specification can be proved for some intervals but disproved for others. We have implemented our techniques within the Ciao/CiaoPP system in a natural way, so that the novel resource usage verification blends in with the CiaoPP framework that unifies static verification and static debugging (as well as run-time verification and unit testing).
Cite as

Pedro Lopez-Garcia, Luthfi Darmawan, and Francisco Bueno. A Framework for Verification and Debugging of Resource Usage Properties: Resource Usage Verification. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 104-113, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{lopezgarcia_et_al:LIPIcs.ICLP.2010.104,
  author =	{Lopez-Garcia, Pedro and Darmawan, Luthfi and Bueno, Francisco},
  title =	{{A Framework for Verification and Debugging of Resource Usage Properties: Resource Usage Verification}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{104--113},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.104},
  URN =		{urn:nbn:de:0030-drops-25889},
  doi =		{10.4230/LIPIcs.ICLP.2010.104},
  annote =	{Keywords: Program Verification and Debugging, Cost Analysis, Resource Usage Analysis, Complexity Analysis}
}
  • Refine by Author
  • 2 Lopez-Garcia, Pedro
  • 1 Becker, Ruben
  • 1 Bueno, Francisco
  • 1 Crescenzi, Pierluigi
  • 1 Cruciani, Antonio
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Networks → Network algorithms
  • 1 Software and its engineering → Syntax
  • 1 Theory of computation → Invariants
  • 1 Theory of computation → Pre- and post-conditions
  • Show More...

  • Refine by Keyword
  • 2 Resource Usage Analysis
  • 1 Abstract Interpretation
  • 1 Assertions
  • 1 Complexity Analysis
  • 1 Cost Analysis
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2018
  • 1 2010
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact